Erstelle eine Wertetabelle.
Für diskunktive Normalform, nimm die Zeilen mit Wert 1. Forme aus der Belegung der Variablen der Zeile eine Konjunktion. Forme eine Disjunktion aus den Zeilen.
Für konjunktive Normalform, negiere die Formel, bestimme die disjunktive Normalform, Negiere das Ergebnis und verwende die beiden Identitäten
¬(x ∨ y) ≡ ¬x ∧ ¬y
und
¬(x ∧ y) ≡ ¬x ∨ ¬y.
Beispiel: (x∨y)→((x∨y) ∧ z)
\( \begin{matrix} \text{Zeile}&x&y&z&(x\vee y)\to ((x\vee y)\wedge z)\\ 1.&0&0&0&1\\ 2.&0&0&1&1\\ 3.&0&1&0&0\\ 4.&0&1&1&1\\ 5.&1&0&0&0\\ 6.&1&0&1&1\\ 7.&1&1&0&0\\ 8.&1&1&1&1 \end{matrix} \)
Disjunktive Normalform:
- Zeile 1 liefert ¬x ∧ ¬y ∧ ¬z
- Zeile 2 liefert ¬x ∧ ¬y ∧ z
- Zeile 4 liefert ¬x ∧ y ∧ z
- Zeile 6 liefert x ∧ ¬y ∧ z
- Zeile 8 liefert x ∧ y ∧ z
Disjunktive Normalform ist also
(¬x ∧ ¬y ∧ ¬z) ∨ (¬x ∧ ¬y ∧ z) ∨ (¬x ∧ y ∧ z) ∨ (x ∧ ¬y ∧ z) ∨ (x ∧ y ∧ z)
Konjunktive Norrmalform:
- Zeile 3 der negierten Formel liefert ¬x ∧ y ∧ ¬z
- Zeile 5 der negierten Formel liefert x ∧ ¬y ∧ ¬z
- Zeile 7 der negierten Formel liefert x ∧ y ∧ ¬z
Negation der disjunktiven Normalform der negierten Formel ist
¬((¬x ∧ y ∧ ¬z) ∨ (x ∧ ¬y ∧ ¬z) ∨ (x ∧ y ∧ ¬z)).
Erste obige Identität liefert dann
¬(¬x ∧ y ∧ ¬z) ∧ ¬(x ∧ ¬y ∧ ¬z) ∧ ¬(x ∧ y ∧ ¬z).
Zweite obige Identität liefert dann
(x ∨ ¬y ∨ z) ∧ (¬x ∨ y ∨ z) ∧ (¬x ∨ ¬y ∨ z).
