Prevesti funkciju u KNF: -(( p + -q) -> r) -> ( p * q )
Nemamo <=>
Imamo dve -> pa ćemo ih eliminisati redom, jednu pa drugu. Delove iskaza ćemo predstaviti kao A,B,C i označiti bojama, da bismo lakše ispratili šta se smenjuje i kako se eliminiše.
Smena A->B = -A + B pa dobijamo:
-(-( p + -q) + r) -> ( p * q )
Sada radimo veliku ->, dobijamo:
- (-(-( p + -q) + r)) + ( p * q )
Eliminišemo dvojnu negaciju nad levim delom
(-( p + -q) + r) + ( p * q )
Primenjujemo DeMorganove zakone -(A*B) ≡ -A + -B -(A+B) ≡ -A * -B
(-( p + -q) + r) + ( p * q ) -(A+B) pa dobijamo:
(-p * -(-q) + r) + ( p * q )
Eliminišemo dvojnu negaciju nad --q
(-p * q + r) + ( p * q )
Imamo nepotrebnih zagrada sad, i izraz je zapravo u DNF, ali ćemo ga prebaciti u KNF.
-p*q + r + p*q
Primenjujemo distributivnost + prema * A+(B*C) ≡ (A+B)*(A+C)
Tretiraćemo prvi deo kao A: -p*q + r + p*q, -p*q + r = A, pa imamo A + (p*q) = (A+p)*(A+q), tj.
(-p*q + r + p)*( -p*q + r + q)
Isto dalje primenjujemo unutar zagrada. U levoj zagradi tretiramo r+p kao A, u desnoj r+q. Sredićemo redosled operanada da bi bilo očiglednije:
(p+r + -p*q)*(q+r + -p*q)
Smene su A=p+r, B=q+r pa imamo: (A + -p*q) * (B + -p*q) = ( (A + -p)*(A + q) )*( (B + -p)*(B + q) ) tj.
( (p+r + -p)*( p+r + q) )*( (q+r + -p)*( q+r + q) )
Uklanjamo suvišne zagrade, po asocijativnosti operacije * imamo da je (a*b)*c = a*b*c pa imamo:
(p+r + -p)*( p+r + q)*(q+r + -p)*( q+r + q)
Sređujemo redosled literala unutar klauza i primećujemo da postoje neka jednostavna svođenja:
(p+ -p + r)*(p + q + r)*(-p + q + r)*(q + q + r)
Pogledajmo prvu klauzu: p + -p + r i primenimo komplementarnost i zakon nule:
p + -p + r = 1 + r = 1, pa ovu klauzu možemo da izbacimo.
Pogledajmo poslednju klauzu: q + q + r i primenimo idempotenciju:
q + q + r = q + r
Dobijamo:
1*(p+q+r)*(-p+q+r)*(q+r)
odnosno
(p+q+r)*(-p+q+r)*(q+r)
i ovo jeste KNF.
Provera:
F = -(( p + -q) -> r) -> ( p * q ) Skraćeni zapisi(smene):
A = p + -q
B = ( p + -q) -> r = A -> r ceo iskaz: F = -B -> p*q
KNF(F) = (p+q+r)*(-p+q+r)*(q+r) = X*Y*Z
|
p |
q |
r |
-q |
A |
B |
-B |
p*q |
F=-B -> p*q |
X |
Y |
Z |
KNF(F) |
F <=>DNF(F) |
|
1 |
1 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
1 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
1 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
|
1 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
|
0 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
|
0 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
|
0 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
|
0 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
Vidimo da su originalni iskaz i dobijeni KNF ekvivalentni po svim kombinacijama vrednosti p,q,r.