Prevesti funkciju u DNF: -(( 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.
-(( p + -q) -> r) -> ( p * q )
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), A=p, B=-q 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 doveden u DNF, ali može da se još malo optimizuje:
-p*q + r + p*q
ako grupišemo po q, imamo:
q*(-p + p) + r = q*(T) + r = q + r
Dobili smo da je DNF = q + r. Ovo je prilično jednostavan oblik, pošto ima disjunkciju klauza u kojima je samo po jedan literal.
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
DNF(F) = q*r
|
p |
q |
r |
-q |
A |
B |
-B |
p*q |
F=-B -> p*q |
DNF(F) = q+r |
F <=>DNF(F) |
|
1 |
1 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
|
1 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
|
1 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
|
1 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
|
0 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
|
0 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
|
0 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
|
0 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
Vidimo da su originalni iskaz i dobijeni DNF ekvivalentni po svim kombinacijama vrednosti p,q,r.