Normalformen

Normalformen beschreiben beliebige Funktionen in einheitlicher Form. In der Boole’schen Algebra sind zwei Normalformen gebräuchlich: die disjunktive Normalform (DNF) und konjunktive Normalform (KNF).

Beispiel 1: Zur Trinkwasserversorgung eines Hochhauses ist auf dem Dach ein Vorratsbehälter installiert. Das Wasser wird durch eine Hauptpumpe bzw. bei deren versagen durch eine Reservepumpe in den Vorratsbehälter gepumpt. Zur automatischen Steuerung der Pumpen sind an diesen und an dem Behälter Sensoren angebracht, die melden, wenn dieser nicht mehr ausreichend gefüllt ist bzw. die Pumpen defekt sind. Es ist ein Schaltnetz zur Steuerung der Pumpen zu entwickeln; es soll ein Alarmsignal ausgegeben werden, wenn beide Pumpen defekt sind.

1. Aufstellen der Wahrheitstabelle der gesuchten Schaltung
Die Eingangsvariable a steht für den Vorratsbehälter (0 = leer, 1 = gefüllt), b für die Hauptpumpe (0 = defekt, 1 = in Ordnung) und c für die Reservepumpe (0 = defekt, 1 = in Ordnung). Die Ausgangsvariable h steht für die eingeschaltete Hauptpumpe (h = 1), r für die eingeschaltete Reservepumpe (r = 1) und s für Alarm ( s = 1). Die Tabelle sieht dann wie folgt aus:

2. Die Schaltfunktionen

Für r lässt sich leicht ablesen, dass r den Wert 1 hat, wenn a=0, b=0 und c=1 ist. Bei einer UND-Verknüpfung müssen alle Variablen den Wert 1 haben, damit die Verknüpfung ebenfalls den Wert 1 hat. Es gilt also: r = ¬a ∧ ¬b ∧ c. Für h gibt es zwei Terme: h = t1 ∨ t2. t1 = ¬a ∧ b ∧ ¬c und t2 = ¬a ∧ b ∧ c. Für h ergibt sich damit der folgende Term: h = (¬a ∧ b ∧ ¬c) ∨ (¬a ∧ b ∧ c). Nach dem Distributivgesetz gilt a ∨ (b ∧ c) = (a ∨ b) ∧ (a ∨ c) bzw. (a ∨ b) ∧ (a ∨ c) = a ∨ (b ∧ c). Der Ausdruck ¬a ∧ b lässt sich ausklammern. Man erhält dann h = (¬a ∧ b) ∨ (c ∧ ¬c). Da c ∧ ¬c = 0 (Komplement) gilt h = (¬a ∧ b) ∨ 0. Nach dem Null-Theorem ergibt sich daraus h = ¬a ∧ b.
Für s lassen sich ebenfalls zwei Terme bestimmen: s = t1 ∨ t2 = (¬a ∧ ¬b ∧ ¬c) ∨ (a ∧ ¬b ∧ ¬c). Daraus ergibt sich analog der oberen Rechnung für s = ¬b ∧ ¬c.

3. Die Schaltung

Beispiel 2: Aufzugssteuerung

In einem Gebäude mit acht Stockwerken gibt es mehrere Aufzüge. Einer davon soll die Eingangshalle und die Stockwerke 4 – 7 miteinander verbinden. Die Stockwerkszahl steht als dreistellige Dualziffer zur Verfügung.

1. Schaltwerttabelle:
Die Stockwerke werden von durch drei Dualziffern a, b und c gekennzeichnet. s ist das gesuchte Stockwerk.

2. Schaltfunktionen

Wie in Beispiel 1 könnte man jetzt alle Terme, für die s = 1 ist, disjunktiv verknüpfen. Man kann aber alle Terme benutzen, für die s = 0 ist. Für s gilt dann s = t1 ∧ t2 ∧ t3. Die Terme werden konjunktiv verknüpft. Damit t1 den Wert 0 annimmt, gilt t1 = a ∨b ∨¬c; für t2 gilt t2 = a ∨¬b ∨c und für t3 gilt t3 = a ∨ ¬b ∨¬c.
Für s ergibt sich dann die folgende Funktion:
s = (a ∨ b ∨ ¬c) ∧ (a ∨ ¬b ∨ c) ∧ (a ∨ ¬b ∨ ¬c)
= a ∨ [( (b ∨ ¬c) ∧ (¬b ∨ c) ∧ (¬b ∨ ¬c)]
= a ∨ [( (b ∨¬c) ∧ ¬b]
= a ∨ [( b ∧ ¬b)∨ ¬c ∧ ¬b)]
= a ∨ (¬b ∧ ¬c).

3. Die Schaltung

Das folgende Verfahren liefert also die Schaltungssynthese:

1. Aufstellen der Wahrheitstabelle der gesuchten Schaltung
2. Ablesen einer Normalform: Treten als Werte weniger Einsen als Nullen auf, nehme man die disjunktive (DNF), andernfalls die konjunktive (KNF) Normalform.
2.1 DNF: Man bildet zu allen Zeilen der Wertetabelle, denen eine 1 zugeordnet ist, die Vollkonjunktion; dabei treten die mit 0 belegten Variablen negiert auf. Diese Vollkonjunktionen werden disjunktiv verknüpft.
2.2 KNF: Man bildet zu allen Zeilen der Wertetabelle, denen eine 0 zugeordnet ist, die Volldisjunktion; dabei treten die mit 1 belegten Variablen negiert auf. Diese Vollkonjunktionen werden konjunktiv verknüpft.
3. Vereinfachung mittels Boole’scher Algebra.

Beispiel 3:Dual-Dezimal-Umsetzer
Eine vierstellige Dualzahl soll in die entsprechende Dezimalzahl umgesetzt werden. Dazu geht auf vier Leitungen die Dualdarstellung einer Zahl in die Schaltung ein, während fünf von der Schaltung ausgehende Leitungen eine zweistellige Dezimalanzeige steuern. Für die Zehnerziffer Z genügt ein Bit, da aufgrund der vierstelligen Dualzahl Dezimalzahlen von 0 bis 15 darstellbar sind; d.h., die Zehnerziffer kann den Wert 0 oder 1 annehmen

Für Z = 1 stehen 6 Terme zur Verfügung. Es gilt also:
Z = (d3 ∧¬d2 ∧d1 ∧¬d0) ∨ (d3 ∧¬d2 ∧d1 ∧d0)∨ (d3 ∧d2 ∧¬d1 ∧¬d0) ∨ (d3 ∧d2 ∧¬d1 ∧d0) ∨ (d3 ∧d2 ∧d1 ∧¬d0)∨ (d3 ∧d2 ∧d1 ∧d0)
= d3 ∧ [(¬d2 ∧d1 ∧¬d0) ∨ (¬d2 ∧d1 ∧d0)∨ (d2 ∧¬d1 ∧¬d0) ∨ (d2 ∧¬d1 ∧d0) ∨ (d2 ∧d1 ∧¬d0)∨ (d2 ∧d1 ∧d0)]
= d3 ∧ [[(¬d2 ∧d1 ∧¬d0) ∨ (¬d2 ∧d1 ∧d0)]∨ [(d2 ∧¬d1 ∧¬d0) ∨ (d2 ∧¬d1 ∧d0)] ∨ [(d2 ∧d1 ∧¬d0)∨ (d2 ∧d1 ∧d0)]]
= d3 ∧ [[(¬d2 ∧d1) ∧ (¬d0 ∨d0)]∨ [(d2 ∧¬d1)∧ (¬d0 ∨d0)] ∨ [(d2 ∧d1) )∧ (¬d0 ∨d0)]]
= d3 ∧ [[(¬d2 ∧d1) ∧ 1]∨ [(d2 ∧¬d1)∧ 1] ∨ [(d2 ∧d1)∧ 1]]
= d3 ∧ [(¬d2 ∧d1) ∨ (d2 ∧¬d1) ∨ (d2 ∧d1)]
= d3 ∧ [(¬d2 ∧d1) ∨ [(d2 ∧d1)∨ (d2 ∧ ¬d1)]]
= d3 ∧ [(¬d2 ∧d1) ∨ [d2 ∧(d1 ∨¬d1)]]
= d3 ∧ [(¬d2 ∧d1) ∨ (d2 ∧1)]
= d3 ∧ [(¬d2 ∧d1) ∨ d2]
= d3 ∧ [(¬d2∨ d2) ∧ d1 ∨ d2)]
= d3 ∧ [1 ∧ d1 ∨ d2)]
= d3 ∧ (d1 ∨ d2)
Der Rechenaufwand, der hier betrieben wurde, ist sehr aufwändig. Wie Boole’sche Funktionen recht einfach minimiert werden können, zeigt der nächste Abschnitt. Die Funktionen für die anderen Werte können mit etwas Überlegung aus der Wahrheitswertetabelle ermittelt werden:
e0: Da die Werte für e0 und d0 identisch sind, gilt e0=d0.
e1: Solange Z=0 ist, entsprechen sich die Werte von d1 und e1. Wenn Z=1 ist, haben d3 und d2 den Wert 1 und d1 den Wert 0. e1 ist also e1=1, wenn Z=0 und d1 = 1 ist oder wenn Z=0 und d3=1, d2=1 und d1=0 sind. Die Funktion lautet dann:
e1=( ¬Z ∧d1)∨ (Z ∧d3 ∧d2 ∧ ¬d1).
e2: Für e2 gelten ähnliche Überlegungen. Die Funktion für e2 lautet:
e2 = ( ¬Z ∧ d2) ∨ (Z ∧ d3 ∧ d2 ∧ d1).
e3: Diese Funktion soll noch einmal algebraisch hergeleitet werden.
e3 = (d3 ∧ ¬d2 ∧ ¬d1 ∧ ¬d0) ∨ (d3 ∧ ¬d2 ∧ ¬d1 ∧ d0)
= (d3 ∧ ¬d2 ∧ ¬d1) ∧ (¬d0 ∨ d0)
= (d3 ∧ ¬d2 ∧ ¬d1)∧ 1
= d3 ∧ ¬d2 ∧ ¬d1.

Verfahren von Quine und McCluskey

Die algebraische Ermittlung der Funktionen kann sehr aufwändig sein. Das im Folgenden vorgestellte Verfahren erleichtert die Bestimmung von komplexen Funktionen.
1. Ermittlung aller Minterme (Wert der Zielvariablen gleich 1) der Funktionen.
2. Zusammenfassung der Minterme in Gruppen mit gleicher Anzahl negativer Eingangsvariablen (gleicher Anzahl von Nullen).
3. Wenn es möglich ist, werden Terme benachbarter Gruppen paarweise zusammengefasst. Terme, die zusammengefasst werden, werden gekennzeichnet.
4. Schritt 3 wird solange wiederholt, bis keine Vereinfachung mehr möglich ist.
5. Ermittlung der Kernimplikanten aus den gefundenen Priminplikanten. Die Kernimplikanten gehören auf jeden Fall zur gesuchten Funktion.
6. Hinzufügen von Kernimplikanten zur Funktion, bis alle Minterme berücksichtigt sind.
7. Erstellen der Primtermtabelle
8. Dominanzprüfung (Spaltendominanz- und Zeilendominanz)
Das Verfahren wird anhand des Beispiels 3 näher erläutert. Die Funktion für Z wurde oben algebraisch berechnet. Das Ergebnis war Z = d3 ∧ (d1 ∨ d2). Zu demselben Ergebnis sollte auch das Verfahren von Quine und McCluskey kommen. Die folgende Tabelle stellt einen Ausschnitt aus der Wahrheitstabelle ergänzt um die Spalten Minterm und Gruppe dar. Die Punkte 7 und 8 kommen hier nicht zur Anwendung, da das Ergebnis bereits vorher klar ist. In einem weiteren Beispiel werden sie aber berücksichtigt.

Die Minterme ergeben sich aus der konjunktiven Verknüpfung. Zur Erläuterung und zum einfacheren Bearbeiten sind die entsprechenden Dualzahlen unterhalb der Minterme aufgeführt. Da vier Eingangswerte vorliegen, wird eine vierstellige Dualzahl benutzt. In der 1. Vereinfachung werden Minterme paarweise zusammengefasst. Dazu müssen die Minterme in mindestens drei Positionen identisch sein. Die vierte Stelle fällt weg (In den Dualzahlen taucht dafür ein Strich auf.). In der zweiten Vereinfachung werden die Ergebnisse der 1. Vereinfachung auch wieder paarweise bearbeitet. Eine weitere Vereinfachung ist dem vorgegebenen Beispiel nicht möglich. Alle Terme, die nicht zur Vereinfachung benutzt wurden bzw. nicht mehr weiter vereinfacht werden können, werden konjunktiv zusammengefasst.

I2,0 und I2,2 bzw. I2,1 und I2,3 sind identisch. Deshalb werden I2,2 und I2,3 nicht berücksichtigt. Z berechnet sich aus den nicht mit x versehenen Termen.
Z =(d3 ∧ d2) ∨ (d3 ∧ d1) = d3 ∧ (d2 ∨ d1).

Es sollen nun auch die Werte für e2 und e1 mit Hilfe des Verfahrens bestimmt werden. Im Beispiel wurde das Ergebnis durch etwas Überlegung abgeleitet.

e2 = (d2 ∧ d1) ∨ (¬d3 ∧ d2) = d2 ∧ (d1 ∨ ¬d3)

Diese Lösung ist noch eleganter als die Überlegungen aus dem oberen Teil, unterscheidet sich aber von der vorherigen Lösung. Sie führt aber, wie nachher aus der Schaltung ersichtlich wird, zum selben Ergebnis.

Da I1,0 nicht weiter benutzt wurde, muss dieser Term Bestandteil der endgültigen Funktion sein. I2,0 und I2,1 sind identisch.
e1 = (d3 ∧ d2 ∧ ¬d1) ∨ (¬d3 ∧ d1)

Ein weiteres Beispiel

1. Ermitteln der Minterme

Ermitteln der Primterme

Es ergeben sich sechs Primterme. Anhand dieser Terme wird eine Primtermtabelle erstellt