Konjunktive Normalform bilden?

Hallo,

es ist folgender Ausdruck gegeben:

$a\wedge b\vee\neg c\ \Rightarrow\ c\wedge b\vee\neg a$ und es soll durch algebraische Transformation die KNF gebildet werden.

Ich bin soweit gekommen:

Ab hier stehe ich aber einfach auf dem Schlauch. Egal wie ich umforme, 10 Zeilen weiter bin ich immer noch nicht bei einer KNF. Könnte mir hier jemand helfen, wie man weiter vorgehen muss (bzw. ist es bis hierhin überhaupt richtig?)

Danke :)

Answer 1

[ralphdieter]

Du hast Dich schon bei der ersten Umformung vertan:

$a\wedge b\vee\neg c\ \Rightarrow\ c\wedge b\vee\neg a$

. ¬[ (a∧b) ∨ ¬c ] ∨ (c∧b) ∨ ¬a
= [ ¬(a∧b) ∧ c ] ∨ (c∧b) ∨ ¬a
= [ (¬a∨¬b) ∧ c ] ∨ (c∧b) ∨ ¬a

Du hast hier eine Disjunktion (Oder), bei der zwei Terme keine Literale sind. Such Dir einen davon aus und wende das Distributivgesetz an: (x∧y) ∨ ... ⇔ (x ∨ ...)∧(y ∨ ...). Ich nehme mal die eckige Klammer:

= [ (¬a∨¬b) ∨ (c∧b) ∨ ¬a ]∧[ c ∨ (c∧b) ∨ ¬a ]

Nun musst Du (rekursiv) beide eckige Klammern in eine KNF umformen. Davor kann man aber zusammenfassen und via „x∨(x∧y) ⇔ x“ vereinfachen:

= [ ¬a ∨¬b ∨ (c∧b) ]∧[ c ∨¬a ]

Die zweite Klammer steht schon in Literalform, aber die erste enthält noch die Konjunktion (c∧b). Das wird wieder zerlegt:

= [ ¬a ∨¬b ∨ c ]∧[ ¬a ∨¬b ∨ b ]∧[ c ∨¬a ]

Die erste Klammer wird von der dritten nach dem Schema „(x∨y)∧x ⇔ x“ absorbiert. Die mittlere Klammer kann entfallen, weil sie immer wahr ist. Also bleibt nur noch die dritte übrig:

= ( c ∨ ¬a )

Und ja, das ist eine KNF – sie hat eben nur einen Faktor.

Answer 2

[Hamburger02]

(a∧b ∨ ¬c) ∨ (c∧b ∨ ¬a)
Vereinfachen:   (a ∧ b) ∨ ¬c ∨ (c ∧ b) ∨ ¬a
KNF:            ((a ∨ ¬c) ∧ (b ∨ ¬c)) ∨ ((c ∨ ¬a) ∧ (b ∨ ¬a))