Elementarkonjunktion, Elementardisjunktion
Es sei 
eine
BOOLEsche Algebra und 
eine Menge BOOLEscher
Variabler.
Jede Konjunktion bzw. Disjunktion, in der jede Variable oder ihre Negation genau einmal
vorkommt, heißt Elementarkonjunktion bzw. Elementardisjunktion (in den
Variablen 
).
Es sei 
ein BOOLEscher Ausdruck.
Eine Disjunktion 
von Elementarkonjunktionen mit 
heißt
kanonisch disjunktive Normalform (KDNF) von 
Eine Konjunktion 
von Elementardisjunktionen mit 
heißt
kanonisch konjunktive Normalform (KKNF) von
Um zu zeigen, daß sich jede BOOLEsche Funktion 
durch einen BOOLEschen
Ausdruck darstellen läßt, wird zu der in der folgenden Tabelle gegebenen Funktion
die KDNF konstruiert:
Die KDNF zur BOOLEschen Funktion
besteht aus den Elementarkonjunktionen
Diese Elementarkonjunktionen gehören zu den Belegungen 
der Variablen, die bei
den Funktionswert 1 haben.
Ist in
eine Variable 
mit 1 belegt, so wird
in die Elementardisjunktion
aufgenommen, andernfalls 
Für das obige Beispiel lautet die KDNF:
 |
(5.327) |
Die ,,duale`` Form zur KDNF ist die KKNF:
Die Elementardisjunktionen gehören zu den Belegungen
der Variablen, die bei
den Funktionswert 0 haben.
Ist in
eine Variable
mit 0 belegt, so wird
in die Elementardisjunktion
aufgenommen, andernfalls
Somit lautet die KKNF für das obige Beispiel:
 |
(5.328) |
Die KDNF und die KKNF zu
sind eindeutig bestimmt, wenn man eine Reihenfolge der
Variablen und eine Reihenfolge der Belegungen vorgibt, z.B. wenn man die Belegungen
als Dualzahlen auffaßt und der Größe nach ordnet.
