Pretvaranje iz opšteg slučaja u DNF
Procedura DNF
Begin
Eliminisati veznik <=> upotrebom ekvivalencije A<=>B ≡ (A->B)*(B->A)
Eliminisati veznik -> upotrebom ekvivalencije A->B ≡ -A + B
Dok god je moguće, ponavljati primenu DeMorganovih zakona:
-(A*B) ≡ -A + -B
-(A+B) ≡ -A * -B
Dok god je moguće, ponavljati primenu zakona dvojne negacije:
--A ≡ A
Dok god je moguće, ponavljati primenu zakona distributivnosti * prema +
A*(B+C) ≡ A*B + A*C
Isto tako važi i (A+B)*(C+D) ≡ A*C + A*D + B*C + B*D
End.
Pretvaranje iz opšteg slučaja u KNF
Isto, osim poslednjeg koraka
Procedura KNF
Begin
Eliminisati veznik <=> upotrebom ekvivalencije A<=>B ≡ (A->B)*(B->A)
Eliminisati veznik -> upotrebom ekvivalencije A->B ≡ -A + B
Dok god je moguće, ponavljati primenu DeMorganovih zakona:
-(A*B) ≡ -A + -B
-(A+B) ≡ -A * -B
Dok god je moguće, ponavljati primenu zakona dvojne negacije:
--A ≡ A
Dok god je moguće, ponavljati primenu zakona distributivnosti + prema *
A+(B*C) ≡ (A+B)*(A+C)
Isto tako važi i (A*B)+(C*D) ≡ (A+C) * (A+D) * (B+C) * (B+D)
End.
Vidimo da je razlika u poslednjem koraku: kod DNF se primenjuje distributivnost * prema + a kod KNF obrnuto.
Ovako zapisan postupak nije algoritam u pravom smislu te reči jer su koraci opisani u opštem obliku, ali nije preterano teško izvesti algoritam. Jedan smer u kome možete ići sa implementacijom je da izraz predstavite kao stablo i u svakoj od ovih faza algoritma vršite prolaz kroz stablo i primenjujete odgovarajuće smene operacija. To bi izgledalo otprilike ovako nekako: ako uzmemo izraz –(A*B) i hoćemo da primenimo DeMorganov zakon, izraz bismo predstavili stablom kao na slici levo. Algoritam prepoznaje ovakvu situaciju prilikom prolaska kroz stablo (tekući čvor je operacija NOT, child čvor je operacija AND) i transformiše stablo tako da umesto NOT i AND ubaci operaciju OR i negacije oba podstabla (child čvora). Slika levo-pre, slika desno-posle.
Slično tome, dvostruka negacija se lako primećuje: ako je tekući čvor NOT i child čvor NOT onda tekući čvor može da se zameni sa child-child čvorom. Pogledajmo ovo: -(-(A*B)) = A*B
I tako dalje...
Implementacija algoritma za konvertovanje logičke formule u KNF/DNF oblik je tipičan zadatak na fakultetskom nivou obrade ove teme.
Jedna implementacija algoritma dostupna je ovde: https://www.cs.jhu.edu/~jason/tutorials/convert-to-CNF.html
DNF i KNF iz kombinacione tabele
Ako imamo kombinacionu tabelu:
- DNF dobijamo tako što uzmemo sve TRUE kombinacije
- KNF dobijamo tako što uzmemo sve FALSE kombinacije, i negiramo ih svaku zasebno
Podsetnik
DNF: disjunkcija konjuktivnih klauza, (a*b*c)+(-a * -b * c), Σ
KNF: konjukcija disjkuntivnih klauza, (a+b+c)*(a+ -b + c), П