Boolesche Funktionen und ihre Normalformen

Man betrachtet die Boolesche Algebra mit der Trägermenge B={0,1}. Die Funktionen f mit
f : {0, 1}ⁿ → {0, 1}, n ≥ 1 werden als Boolesche Funktionen bezeichnet. Die Anzahl n der Argumente (Variablen) einer Booleschen Funktion heißt ihre Stelligkeit. Für n = 1 spricht man von unären (unary), für n = 2 von binären (binary) und für n = 3 von ternären (ternary) Funktionen.
Eine Boolesche Funktion ist damit eine Abbildung, die jeweils n bits auf ein einziges bit abbildet.  Alle sechzehn binären Booleschen Funktionen sind hier in gleicher Nummerierung wie auf Seite 12 (in modifizierter Tabellenform) nochmals aufgeführt:

Jede n-stellige Boolesche Funktion kann durch ihre Wahrheitstafel dargestellt werden. Rechts ist z.B. die Wahrheitstafel einer tenären Booleschen Funktion f mit f: y = f(a, b, c) zu sehen. Jede solche Wahrheitstafel enthält je eine Spalte für die Funktionsargumente (atomare Variablen), jeweils eine Zeile für jede Kombination der Wahrheitswerte und eine zusätzliche letzte Spalte, in der der zugehörige Funktionswert angegeben wird.

 Die abgebildete Wahrheitstafel hat 

Zeilen, die Wahrheitstafel einer n-stelligen Booleschen Funktion hat 2ⁿ Zeilen.
Es gibt dreistellige (tenäre) und n-stellige Boolesche Funktionen.

Die Darstellung mithilfe einer Wahrheitstafel kommt folglich mit wachsender Variablenzahl schnell an ihre Grenzen. Für die Herstellung elektronischer Schaltungen ist es in der Praxis daher sehr bedeutsam, dass zu jeder Wahrheitstafel ein äquivalenter logischer Term generiert werden kann. Statt die Wahrheitstafel mit viel Rechenaufwand aufzustellen, kann dann der äquivalente Term nach den Rechengesetzen der Booleschen Algebra umgeformt und auf der Grundlage des vereinfachten Terms eine Schaltung konstruiert werden.

Beim Aufstellen von äquivalenten Termen zu vorgegebenen Wahrheitstafeln spielen die  Normalformen von Booleschen Funktionen eine entscheidende Rolle. Normalformen von Booleschen Funktionen werden im Informatikunterricht der Kursstufe behandelt und sollen daher hier nicht im Mittelpunkt stehen.²⁶ Vielmehr soll im nächsten Kapitel ein anschaulicher Zugang erläutert werden, der im Rahmen einer optionalen Vertiefung in einer neunten Klasse denkbar wäre und sich dabei hauptsächlich auf binäre Booleschen Funktionen beschränkt.  

Kanonische Disjunktive und Konjunktive Normalform (KDNF, KKNF)

Den aussagelogischen Funktionsterm zu einer durch ihre Wahrheitstafel vorliegenden Booleschen Funktion kann man auf zwei fundamentale Arten generieren. In der konjunktiven Normalform (KNF) als Konjunktion von Disjunktionen der beteiligten Variablen bzw. ihrer Negationen und in der disjunktiven Normalform (DNF) als Disjunktion von entsprechenden Konjunktionen.²⁷ Wir beschäftigen uns hier nur mit kanonischen Normalformen. Anmerkungen zur Unterscheidung von Normalformen  (DNF und KNF) und den kanonischen Normalformen (KDNF und KKNF) folgen am Ende dieses Abschnittes.

Was sich hinter den Normalformen verbirgt, soll hier zunächst am Beispiel einer binären Booleschen Funktion erläutert werden. Disjunktive und konjunktive Normalformen lassen sich mit Venn-Diagrammen auch anschaulich motivieren. Jeder Vollkonjunktion²⁸ der atomaren Aussagen (bzw. ihrer Negationen) in den einzelnen Zeilen der Wahrheitstabelle entspricht dabei eine der Teilflächen im Venn-Diagramm, was hier für den Fall n=2 am Beispiel der Bijunktion a↔b erläutert wird.

a) Wir beginnen mit der KDNF, die vier möglichen Vollkonjunktionen sind hier dargestellt.

Man bildet die Disjunktion aus den Vollkonjunktionen, bei denen in der Spalte von f eine "1" eingetragen ist. Im Beispiel wählt man also (1) und (4) aus und kann sofort die kanonische disjunktive Normalform (KDNF) von f notieren:  (a∧b)∨(¬a∧¬b).
Dieser Term liefert nur bei den Kombinationen (1) und (4) eine "1", anderfalls eine "0".
Im anschaulichen Modell der Mengenalgebra geht man dabei von den Schnittmengen in den ersten vier Spalten aus und setzt durch Vereinigung der passenden Schnittmengen das gesuchte Venn-Diagramm zusammen.
Die Disjunktion (in der Aussagenalgebra) entspricht der Vereinigung (in der Mengenalgebra) bzw. einer Addition (in der Booleschen Algebra). Die Konjunktion (in der Aussagenalgebra) entspricht dem Durchschnitt (in der Mengenalgebra) bzw. dem Produkt (in der Booleschen Algebra). Abstrahiert man dies in der kontextfreien Struktur der Booleschen Algebra, so werden beim Aufstellen der KDNF also Summen von Produkten gebildet, weshalb das Verfahren im engl. Sprachraum auch als sum of products (SOP) bezeichnet wird.  

b) Das Vorgehen zum Aufstellen der KKNF ist dual zu dem bei der KDNF. Die vier möglichen Volldisjunktionen erhält man durch Negation der Vollkonjunktionen von oben:

Nun geht man nach dem Dualitätsprinzip vor. Während oben die "Summe von Produkten" gebildet wurde, bildet man nun das "Produkt von Summen" (engl. product of sums (POS)).
Man bildet also die Konjunktion aus den Volldisjunktionen, bei denen in der Spalte von f eine "0" eingetragen ist. Im Beispiel wählt man (2) und (3) aus und kann damit die kanonische konjunktive Normalform (KKNF) von f notieren: ((¬a∨b)∧(a∨¬b).
Dieser Term liefert nur bei den Kombinationen (2) und (3) eine "0", andernfalls eine "1".
Im anschaulichen Modell der Mengenalgebra geht man dabei von Vereinigungsmengen der  ersten vier Spalten aus und bildet deren Schnittmenge, um das gesuchte Venn-Diagramm zu erhalten, eben gerade "anders herum", dual im Sinne der Booleschen Algebra.

Didaktischer Hinweis: Würde man die Venn-Diagramme auf Folie drucken und übereinander legen, so könnte man die Schnittmenge daran erkennen, dass sie am dunkelsten gefärbt wäre. Dazu müsste man die Farbintensität der gefärbten Ausgangsmengen relativ niedrig wählen, was in der mitgelieferten GeoGebradatei M9aug02_VENN-2Var.ggb mithilfe des Schiebereglers DK ("Deckkraft") realisiert werden könnte. Geschickter ist allerdings das Invertieren der Farben, dann bleibt die der Schnittmenge entsprechende Teilfläche weiß.
 

Zur Dualität von KDNF und KKNF in der Wahrheitstafel

Betrachtet man die Wahrheitstafeln der vier Vollkonjunktionen, so enthalten diese jeweils genau eine "1" und 4-1=3 Nullen. Durch die Disjunktion der Vollkonjunktionen werden alle Einsen in die Spalte von f "übertragen". Es wird gewissermaßen die Summe gebildet.
Bei der dualen Vorgehensweise der KNF nimmt jede der vier Volldisjunktionen nur genau einmal den Wert "0" an, sonst immer "1". Durch die Konjunktion der Volldisjunktionen werden alle Nullen in die Spalte von f "übertragen", es wird das Produkt gebildet.

Betrachtet man dies in der Wahrheitstafel, so lassen sich die beiden dualen Vorgehensweisen auch auf numerischer Ebene der Tabellen gut nachvollziehen:

Kanonische Kanonische
Disjunktive Normalform Konjunktive Normalform
"Summe von Produkten" "Produkt von Summen"
   
Diese duale Sicht soll nun abschließend noch am Beispiel einer ternären Booleschen Funktion
erläutert werden, wobei auf eine ausführliche Darstellung verzichtet wird.

Beispiel:  y = f(a, b, c) (Es liegt nur die Wahrheitstafel vor, ein Term ist nicht bekannt)

Analog zum vorangegangenen Beispiel der binären Funktion sind auch hier die Wahrheitstafeln der Vollkonjunktionen (C2, C3, C5 und C7) und der
Volldisjunktionen  (¬C1, ¬C4, ¬C6 und ¬C8) zu sehen:

Unterschied zwischen Normalformen und kanonischen Normalformen

Wie bereits angemerkt, spricht man bei einer Konjunktion, in der alle auftretenden Variablen (oder ihre Negationen) einmal eingebunden sind, von einer Vollkonjunktion (Minterm). Bei einer Volldisjunktion (Maxterm) verhält es sich analog. Wenn in einer DNF nur Vollkonjunktionen auftreten, so wie das hier der Fall war, so handelt es sich um eine kanonische disjunktive Normalform (KDNF). Entsprechend spricht man von einer kanonischen konjunktiven Normalform (KKNF), wenn nur Volldisjunktionen auftreten. Bei der KDNF (KKNF) sind also alle Variablen (bzw. ihre Negationen) in allen Klammern genau einmal enthalten.
Die DNF ist dagegen "nur" als disjunktive Verknüpfung konjunktiver Terme definiert, deswegen können bei einer DNF auch Variablen (bzw. ihre Negationen) fehlen, z.B. wäre
f(a, b, c) = (a∧b∧c) v (a∧¬b) v ¬c eine DNF. Analog verhält es sich bei der KNF.

In Klasse 9 ist diese Unterscheidung nicht erforderlich. Man kann vereinfachend von der DNF bzw. KNF sprechen, da jede KDNF (KKNF) gleichzeitig eine DNF (KNF) ist, nur umgekehrt ist dies nicht der Fall.²⁹

²⁶ Zum Einlesen eignet sich z.B. [BEU], S. 245 ff. Dort ist u.a. ein von Karnaugh und Veitch entwickeltes grafisches Verfahren zur Veinfachung boolescher Ausdrücke beschrieben, bei dem sog. KV-Diagramme eingesetzt werden.  [AIG], S. 217ff und [LES], S. 116 ff bieten ebenfalls kompakte überlicke.  

²⁷Vgl. Aufgabe 2.26 , [AHR], S. 48

²⁸ Von einer Vollkonjunktion spricht man, wenn alle auftretenden Variablen (oder ihre Negationen) eingebunden sind.

²⁹ Eine Möglichkeit zur Vertiefung bietet die im Unterrichtsgang näher beschriebene Lernplattform LogicTraffic von Ruedi Arnold, bei der auch zwischen DNF und KDNF unterschieden werden könnte.

 

Hintergrund: Herunterladen [odt][601 KB]

Hintergrund: Herunterladen [pdf][698 KB]

 

Weiter zu Historische Anmerkungen