Logik: Wie komme ich von einer Negationsnormalformel zu einer KNF?

Question

Ich habe eine generelle Frage wie komme ich in der Logik von der Negationsnormalformel auf die KNF:

Zum Beispiel bei dieser Formel: ((p1 ∧ p2) ∨ ¬p2) ∨ p1

Gibt es hier einen Trick?

Vielen Dank im Voraus!

LG
Apple

Answer 1

Hi. Um eine NNF (Negationsnormalform) in die entsprechende KNF (Konjunktive Normalform) zu konvertieren, bedient man sich meist des Distributiv-, Kommutativ- und Assoziativgesetzes.

Beispiel: NNF $\rightarrow$ KNF

NNF = $((p_1 \land p_2)\lor \neg p_2) \lor p_1$

KNF = $(p_1 \lor \neg p_2 \lor p_1) \land (p_2 \lor \neg p_2 \lor p_1)$

Herleitung:

$$\begin{array}{rcl} ((p_1 \land p_2)\lor \neg p_2) \lor p_1 & = & ((p_1 \lor \neg p_2)\land (p_2 \lor \neg p_2)) \lor p_1 \;\;\;\;\text{(Distributivgesetz)}\\ & = & ((p_1 \lor \neg p_2)\lor p_1 ) \land ((p_2 \lor \neg p_2) \lor p_1) \;\;\;\;\text{(Distributivgesetz)}\\ & = & (p_1 \lor (\neg p_2 \lor p_1)) \land (p_2 \lor (\neg p_2 \lor p_1)) \;\;\;\;\text{(Assoziativgesetz)}\\ & = & (p_1 \lor \neg p_2 \lor p_1) \land (p_2 \lor \neg p_2 \lor p_1) \\ \end{array}$$

Ferner kann man den Ausdruck in diesem Beispiel sogar vereinfachen:

$$\begin{array}{rcl} ((p_1 \land p_2)\lor \neg p_2) \lor p_1 & = & ((p_1 \lor \neg p_2)\land (\underbrace{p_2 \lor \neg p_2}_{= 0})) \lor p_1 \\ & = & (\underbrace{(p_1 \lor \neg p_2)\land 0}_{= 0}) \lor p_1 \\ & = & 0 \lor p_1 \\ & = & p_1 \\ \end{array}$$

Ich hoffe, es hilft.

MfG

Comments

GakiRe

Danke vielmals für die schnelle und hilfreiche Antwort. Eine Frage hätte ich noch:

Beim Schritt:

Text erkannt:

$\left(\left(p_{1} \vee \neg p_{2}\right) \wedge\left(p_{2} \vee \neg p_{2}\right)\right) \vee p_{1}$

zu

Text erkannt:

$\left(\left(p_{1} \vee \neg p_{2}\right) \vee p_{1}\right) \wedge\left(\left(p_{2} \vee \neg p_{2}\right) \vee p_{1}\right)$

wird das gelb markierte p1 bei beiden Klausel hinzugefügt. Ich kann es mir logisch erklären, gibt es jedoch hier auch noch ein Gesetzt dafür?

Vielen Dank!

LG
Apple

---

Ja. Das Gesetz heißt Distributivgesetz für boolesche Algebra. Du kannst hier (https://de.m.wikipedia.org/wiki/Boolesche_Algebra) nachschauen, im Abschnitt "Definition", Regel (4) und (4').

MfG.

---

Super danke vielmals GakiRe!

---

Gern geschehen.