Mi a különbség a diszjunktív- és konjuktív normálforma között?

A diszjunktív normálformánál a literálok (bötűk) ÉS-eléséből áll egy-egy kifejezés, és ezek vannak összeVAGY-olva. Tehát akkor IGAZ, ha a sok, egy-egy esetben igaz kifejezés bármelyike IGAZ.

A konjunktív normálformánál a literálok VAGY-olásából áll egy-egy kifejezés, és ezek vannak össze ÉS-elve. Tehát akkor HAMIS, ha az egy-egy esetben hamis kifejezések bármelyike HAMIS.

(p -> q) <-> r

Igazságtáblázat... 3 változó, 2^3=8 sor.

Pontosan akkor igaz a kifejezés, ha (p,q,r) = III, IHH, HII, vagy HHI.

Pontosan akkor hamis, ha nem ezek az esetek fordulnak elő, vagyis (p,q,r) = IIH, IHI, HIH, HHH.

Tehát az első alapján egy lehetséges diszjunktív normálforma: (P és Q és R) vagy (P és nem Q és nem R) vagy (nem P és Q és R) vagy (nem P és nem Q és R).

Az utóbbi alapján egy lehetséges konjunktív normálforma:

(nem P vagy nem Q vagy R) és (nem P vagy Q vagy nem R) és (P vagy nem Q vagy R) és (P vagy Q vagy R).

Megjegyzés: tagokat néha össze lehet vonni, de nem kötelező. Például az előbbinél a "(nem P és Q és R) vagy (nem P és nem Q és R)" helyett lehetett volna simán annyit írni, hogy "(nem P és R)", hiszen a két formula ekvivalens.Példa a másikból: "(P vagy nem Q vagy R) és (P vagy Q vagy R)" helyett "(P vagy R)".

De igen. Meg kell tanulnod magát a kifejezést bontani.

Pl. a->b az "nem a vagy b", a<->b az "a és b vagy nem a és nem b", stb... Zárójelet felbontani pedig a de-morgan szabállyal tudsz.

Zárójelet úgy is felbonthatsz, hogy mindent mindennel, mint az (a+b)*(c+d)=ac+ad+bc+bd műveletnél. Csak logikában mégszebb a dolog, mert a VAGY-nál és az ÉS-nél is működik ez (algebrában (a*b)+(c*d) az nagyon nem (a+c)*(a+d)*(b+c)*(b+d)).

Pl.: (A VAGY B) ÉS (C VAGY D) = (A ÉS C) VAGY (A ÉS D) VAGY (B ÉS C) VAGY (B ÉS D), és tádám, kész a diszjunktív normálforma.

Ha viszont a külső művelet nem az ÉS, hanem a VAGY:

Pl.: (A ÉS B) VAGY (C ÉS D)... akkor már eleve megvan a diszjunktív normálforma, tehát még egyszerűbb a dolgod.

A De-Morgan szabály még ezt a lépést megelőzően ahhoz kell, hogy a negálásokat le tudd vinni a változók szintjére (tehát hogy ne egy bonyolult kifejezés legyen negálva, hanem egy-egy változó, pl. NEM (A ÉS B) helyett (NEM A) VAGY (NEM B)).