Wie lautet die ausgezeichnete/kanonische konjunktive Normalform KNF?

Question

Hallo zusammen,

 

könnt ihr mir bitte bei folgender Aufgabe helfen? Man soll die kanonische KNF bilden.

 

nicht(b->) * nicht b + (b-> nicht (a-> nicht c))

 

Mein Ergebnis hierzu lautet:

nicht  b+a+c * nicht b+a+nicht c * nicht b+ c + nicht a

 

Vielen, vielen lieben Dank

Nadine

Comments

nicht(b->fehlt hier noch etwas? eine schliessende Klammer einfach so verstehe ich gar nicht) * nicht b + (b-> nicht (a-> nicht c))

---

Entschuldigung. Ja, da fehlt ein a.

nicht(b->a) * nicht b + (b-> nicht (a-> nicht c))

Answer 1

Ich versuch's auch mal zu rechnen. (ohne Gewähr!)

nicht(b->a) * nicht b + (b-> nicht (a-> nicht c)) =

nicht (nicht b + a) * nicht b + (nicht b + nicht (nicht a + nicht c)) =

b * nicht a * nicht b + (nicht b + (a * nicht c)) =

0 + (nicht b + a) * (nicht b + nicht c) =

(nicht b + a) * (nicht b + nicht c)

Meiner Meinung nach ist das eine KNF.
Ob die auch ausgezeichnet/kanonisch ist, weiss ich nicht.
Hast du da eine spezielle Vorschrift?

Comments

Mein Resultat stimmt mit der CNF von WolframAlpha überein.

http://www.wolframalpha.com/input/?i=NOT+%28NOT%28+b%29+OR+a%29+AND+NOT%28+b%29+OR+%28NOT+%28b%29+OR+NOT+%28NOT+%28a%29+OR+NOT%28c%29%29%29+%3D

---

Vielen Dank Lu. Da bin ich aber froh, dass du aufs selbe Ergebnis kommst.

Bei einer kanonischen/ausgezeichneten KNF müssen bei der einzelnen Disjunktionen alle Literale vorkommen. Da bei (nicht b + a) das c nicht vorkommt, muss man es in die Disjunktion mitaufnehmen und gleich wieder negieren.

So meine Rechenschritte ab der KNF aus:

= nicht b + a + c * nicht b + a + nicht c * a + nicht b + c * nicht a + nicht b + c
= nicht b+a+c * nicht b+a+nicht c * nicht b+ c + nicht a

 

Danke für deine Hilfe.

---

Aha. Gern geschehen.

Ich ergänze bei deiner Rechnung Klammern, damit mir das auch einleuchtet und sortiere am Schluss noch.

= (nicht b + a + c) *( nicht b + a + nicht c) *( a + nicht b + c) *( nicht a + nicht b + c)
= (nicht b+a+c) * (nicht b+a+nicht c) * (nicht b+ c + nicht a)

=(a + nicht b + c)* (a + nicht b + nicht c)*(nicht a + nicht b + c)