Zuerst Beispiele für ein Literal, Minterm und Maxterm
Literal = eine negierte oder nicht negierte Aussagenvariable.
Minterm = eine Konjunktion von (nicht unbedingt verschiedenen) Literalen.
Maxterm = eine Disjumnktion von Literalen.
Disjunktive Normalform (DNF)
Eine DNF ist eine Disjunktion von Mintermen, wie z. B. (p∧¬q∧w)∨(r∧s∧¬t)∨(s∧s∧f)
Konjunktive Normalform (KNF)
Eine KNF ist eine Konjunktion von Maxtermen, wie z. B. (p∨¬q∨p∨f)∧(r∨s)∧t
Eine Basiskonjunktion ist ein Minterm, der alle gegebenen Aussagevariablen genau einmal als Literal (aber weder „w“ noch „f“) enthält.
Eine Basisdisjunktion ist ein Maxterm, der alle gegebenen Aussagevariablen genau einmal als Literal (ohne „w“ und „f“) enthält.
Für die Variablen p, q, r wäre also p∧¬q∧r eine Basiskonjunktion und p∨q∨¬r eine Basisdisjunktion.
Eine kanonisch (ausgezeichnete) DNF (KDNF) ist eine disjunktive Verknüpfung von Basiskonjunktionen, bei der jede Basiskonjunktion höchstens einmal auftritt.
Eine kanonisch (ausgezeichnete) KNF (KKNF) ist eine konjunktive Verknüpfung von Basisdisjunktionen, bei der jede Basisdisjunktion höchstens einmal auftritt.
Die Konstante f alleine ist auch eine DNF bzw. w eine KNF.
Zu jeder aussagelogischen Formel gibt es eine KDNF (KKNF), die zu dieser äquivalent ist.
Beispiel:
Gesucht ist eine KDNF, die äquivalent ist zu: ¬(¬p→q)∨r
1) Wahrheitstafel erstellen
rot ist die Negation von p; türkis die Implikation, welche nur bei w →f falsch ist, sonst immer wahr; amber ist die Negation des Klammerinhalts, die mit r verknüpft wird.
| p | q | r | ¬(¬p→q) | ∨r | |
| w | w | w | f (w) f | w | 1 |
| w | w | f | f (w) f | f | |
| w | f | w | f (w) f | w | 2 |
| w | f | f | f (w) f | f | |
| f | w | w | w (w) f | w | 3 |
| f | w | f | w (w) f | f | |
| f | f | w | w (f) w | w | 4 |
| f | f | f | w (f) w | w | 5 |
Es gibt 5 Ergebnisse mit „w“ aus diesen Zeilen können die Literale übernommen werden, wenn die Voraussetzung „w“ war, sonst wird die Negation übernommen, weil eine Basiskonjunktion nur dann wahr ist, wenn alle Literale wahr sind. Mit einer Konjugation ergeben sich die Basiskonjunktionen und wenn disjunktiv verknüpft werden, erhält man eine KDNF. Eine Disjunktion von Basiskonjunktionen ist genau dann wahr, wenn mindestens eine Basiskonjunktion wahr ist.
| Zeile | p | q | r | Literale | Basiskonjunktion | ||
| 1 | w | w | w | p | q | r | p∧q∧r |
| 2 | w | f | w | p | ¬q | r | p∧¬q∧r |
| 3 | f | w | w | ¬p | q | r | ¬p∧q∧r |
| 4 | f | f | w | ¬p | ¬q | r | ¬p∧¬q∧r |
| 5 | f | f | f | ¬p | ¬q | ¬r | ¬ p∧¬q∧¬r |
KDNF: (p∧q∧r)∨(p∧¬q∧r)∨(¬p∧q∧r)∨( ¬p∧¬q∧r)∨(¬ p∧¬q∧¬r)
Die KDNF hat genau die gleichen Wahrheitswerte wie die gegebene Formel und ist damit äquivalent zu ihr. Wenn in der Resultatsspalte nur „f“ vorkommen, dann ist „f“ die KDNF.
Bei den Verfahren zur Bildung der KKNF bzw. KDNF werden „und“ mit „oder“ und „f“ mit „w“ bzw. umgekehrt vertauchst, wie bei den Gesetzten von De Morgan, den Distributiv- und Verschmelzungsgesetzen, weil wegen des Dualitätsprinzips gilt:
Sind zwei Ausdrücke a und b, in denen nur die Junktoren ¬, ∧, und ∨ vorkommen äquivalent, dann sind auch die Formeln, die aus a und b dadurch entstehen, dass alle ∧ durch ∨, ∨ durch ∧, w durch f und f durch w erstetzt werden.
Z. B.: a ∧w↔a es gilt daher auch a∨ f↔a