Lernen › Thema 3

Wahrheitstabellen und kanonische Normalformen: Σm und ΠM

8 Min. Lesezeit · bitGateLab-Team

Fast jede Entwurfsaufgabe der Digitaltechnik beginnt mit einer Beschreibung in Worten („der Alarm ertönt, wenn ...“), aus der eine Wahrheitstabelle wird. Der nächste Schritt besteht darin, aus dieser Tabelle eine Gleichung zu gewinnen, die sich mit Gattern aufbauen lässt. Hier lernst du das systematische Verfahren dafür: Minterme und Maxterme, die kanonische disjunktive und konjunktive Normalform und die kompakte Schreibweise Σm und ΠM, die in Lehrbüchern, Simulatoren und Karnaugh-Diagrammen verwendet wird.

Wie eine Wahrheitstabelle geordnet wird

Bei n Variablen gibt es 2ⁿ Zeilen. Man schreibt sie in aufsteigender binärer Reihenfolge, mit der ersten Variablen als höchstwertigem Bit. So ist jede Zeile durch eine Dezimalzahl gekennzeichnet: In einer Tabelle mit A, B und C ist die Zeile A = 1, B = 0, C = 1 die Zeile 101₂ = 5. Diese Zahl verwendest du als Index des Minterms oder Maxterms, deshalb kommt es auf die Reihenfolge der Variablen an: Änderst du die Reihenfolge, ändern sich die Nummern.

Minterme und disjunktive Normalform

Ein Minterm ist ein Produkt (AND), das alle Variablen enthält, jede genau einmal, negiert oder nicht negiert. Er wird so gebildet: Die Variable, die in dieser Zeile 1 ist, steht ohne Strich, und die Variable, die 0 ist, steht mit Strich. Der Minterm ist ausschließlich in seiner Zeile 1 und in allen anderen 0. Man bezeichnet ihn mit m_i, wobei i die Nummer der Zeile ist.

Zeile	A	B	C	Minterm	Maxterm
0	0	0	0	m₀ = ABC	M₀ = A + B + C
1	0	0	1	m₁ = ABC	M₁ = A + B + C
2	0	1	0	m₂ = ABC	M₂ = A + B + C
3	0	1	1	m₃ = ABC	M₃ = A + B + C
4	1	0	0	m₄ = ABC	M₄ = A + B + C
5	1	0	1	m₅ = ABC	M₅ = A + B + C
6	1	1	0	m₆ = ABC	M₆ = A + B + C
7	1	1	1	m₇ = ABC	M₇ = A + B + C

Wenn du die Minterme aller Zeilen, in denen die Funktion 1 ist, addierst (OR), erhältst du eine Gleichung, die genau in diesen Zeilen 1 ist. Das ist die kanonische disjunktive Normalform (KDNF; auf Englisch SOP, „sum of products“), also eine Summe von Produkten. In kompakter Schreibweise lautet sie F = Σm(Liste der Zeilen mit 1).

Maxterme und konjunktive Normalform

Ein Maxterm ist eine Summe (OR), die alle Variablen enthält. Die Regel ist umgekehrt: Die Variable, die in der Zeile 0 ist, steht ohne Strich, und die Variable, die 1 ist, steht mit Strich. Ein Maxterm ist ausschließlich in seiner Zeile 0. Man bezeichnet ihn mit M_i (mit großem M).

Wenn du die Maxterme aller Zeilen, in denen die Funktion 0 ist, multiplizierst (AND), erhältst du eine Gleichung, die genau dort 0 und überall sonst 1 ist: die kanonische konjunktive Normalform (KKNF, englisch POS), also ein Produkt von Summen. Man schreibt F = ΠM(Liste der Zeilen mit 0).

Minterm und Maxterm derselben Zeile sind Komplemente: m_i = M_i. Kennst du also die Σm-Liste einer Funktion, dann besteht die ΠM-Liste aus allen Nummern, die darin nicht vorkommen.

Beispiel 1: von der Tabelle zu beiden Formen. Eine Funktion von drei Variablen ist in den Zeilen 1, 3, 6 und 7 gleich 1.

#	A	B	C	F
0	0	0	0	0
1	0	0	1	1
2	0	1	0	0
3	0	1	1	1
4	1	0	0	0
5	1	0	1	0
6	1	1	0	1
7	1	1	1	1

Kompakte Schreibweise: F = Σm(1, 3, 6, 7) = ΠM(0, 2, 4, 5).
Kanonische disjunktive Normalform: F = ABC + ABC + ABC + ABC.
Kanonische konjunktive Normalform: F = (A + B + C)(A + B + C)(A + B + C)(A + B + C).
Vereinfache die disjunktive Form: ABC + ABC = AC und ABC + ABC = AB. Also F = AC + AB.

Probe in Zeile 5 (A = 1, B = 0, C = 1): AC = 0 und AB = 0, also F = 0, wie in der Tabelle.

Welche Form ist günstiger?

Beide Formen beschreiben dieselbe Funktion, sind aber nicht gleich groß. Nimm die Form mit weniger Termen: Hat die Funktion wenige Einsen, ist Σm kürzer; hat sie wenige Nullen, ist ΠM kürzer. Bei 8 Zeilen hat eine Funktion mit 2 Einsen eine disjunktive Form mit 2 Termen und eine konjunktive Form mit 6.

Auch die Umsetzung spielt eine Rolle. Eine Summe von Produkten baut man mit AND-Gattern auf, die ein OR speisen, und diese zweistufige Struktur lässt sich direkt in NAND-NAND überführen. Ein Produkt von Summen baut man mit OR-Gattern auf, die ein AND speisen, und daraus wird NOR-NOR.

Beispiel 2: von der Aufgabenstellung zur Gleichung. Ein Tank hat drei Füllstandssensoren: A (unten), B (Mitte) und C (oben). Jeder Sensor liefert 1, wenn das Wasser ihn erreicht. Eine Lampe „Füllstand ungültig“ soll leuchten, wenn die Kombination physikalisch unmöglich ist: ein höherer Sensor ist aktiv, während ein tieferer inaktiv ist.

Gültige Kombinationen (ABC): 000, 100, 110, 111. Das sind die Zeilen 0, 4, 6 und 7.
In den übrigen leuchtet die Lampe: F = Σm(1, 2, 3, 5).
Gleichwertig: F = ΠM(0, 4, 6, 7).
Vereinfache: m₁ + m₃ = AC, m₁ + m₅ = BC, m₂ + m₃ = AB. Verwendet man m₁ und m₃ jeweils zweimal (Idempotenz), ergibt sich F = BC + AB.

Kontrolle: Zeile 1 (001) ergibt BC = 1; Zeile 2 (010) ergibt AB = 1; Zeile 3 (011) ergibt AB = 1; Zeile 5 (101) ergibt BC = 1. Bei 000, 100, 110 und 111 sind beide Terme 0. Gelesen wird das als „C aktiv ohne B“ oder „B aktiv ohne A“.

Das Komplement einer Funktion

Ist F = Σm(1, 3, 6, 7), dann ist ihr Komplement dort 1, wo F gleich 0 ist: F = Σm(0, 2, 4, 5). Das ist nützlich, wenn du die vereinfachte konjunktive Form suchst: Du vereinfachst F als Summe von Produkten und wendest danach De Morgan an. Zum Beispiel ist F = AC + AB (prüfe es mit den Zeilen 0, 2, 4 und 5), und durch Komplementieren erhält man F = (A + C)(A + B). Ausmultipliziert: AB + AC + BC, und nach dem Konsensus-Theorem ist das AB + AC, dasselbe Ergebnis wie in Beispiel 1.

Um diese Umformungen zu vertiefen, wiederhole das Thema boolesche Algebra; grafisch vereinfachst du mit den Karnaugh-Diagrammen.

Häufige Fehler

Die Regel für die Striche zu vertauschen: Bei Mintermen trägt die 0 den Strich; bei Maxtermen ist es die 1, die den Strich trägt.
In ΠM die Zeilen einzutragen, in denen die Funktion 1 ist. ΠM listet die Nullen auf, Σm die Einsen.
Die Reihenfolge der Variablen zwischen Tabelle und Gleichung zu ändern. Mit der Reihenfolge C, B, A ist die Zeile „5“ nicht mehr dieselbe.
In einem kanonischen Term eine Variable zu vergessen. Ein Minterm von vier Variablen hat immer vier Literale; hat er weniger, ist er bereits vereinfacht und nicht mehr kanonisch.

Probiere es im Simulator aus

Im Wahrheitstabellen-Modul kannst du eine Funktion Zeile für Zeile eingeben und siehst sofort ihre kanonischen Formen und die vereinfachte Gleichung. So kannst du jeden Schritt überprüfen, den du von Hand machst.

Lege eine Tabelle mit drei Eingängen und einem Ausgang an.
Setze die Zeilen 1, 3, 6 und 7 aus Beispiel 1 auf 1 und lass die übrigen auf 0.
Sieh dir die erzeugten Ausdrücke Σm und ΠM an und vergleiche sie mit deinen eigenen.
Wandle die Tabelle in eine Schaltung um und schalte die Eingänge durch, um zu bestätigen, dass der Ausgang der Tabelle folgt.
Wiederhole das Ganze mit der Tankaufgabe und prüfe, ob die Lampe nur bei den unmöglichen Kombinationen leuchtet.

Übungen

Schreibe den Minterm m₉ und den Maxterm M₉ einer Funktion von vier Variablen A, B, C, D auf.
Lösung
9 = 1001. m₉ = ABCD und M₉ = A + B + C + D.
Gegeben ist F(A, B, C) = Σm(0, 1, 5). Schreibe F in der ΠM-Schreibweise.
Lösung
F = ΠM(2, 3, 4, 6, 7).
Bestimme die kanonische disjunktive Normalform einer Funktion von zwei Variablen, die nur dann 1 ist, wenn A und B gleich sind, und vereinfache sie, falls möglich.
Lösung
F = Σm(0, 3) = AB + AB. Das lässt sich nicht weiter vereinfachen: Es ist das XNOR.
Schreibe die kanonische konjunktive Normalform von F(A, B, C) = Σm(1, 2, 3, 4, 5, 6, 7) auf.
Lösung
Die Funktion ist nur in Zeile 0 gleich 0, also F = ΠM(0) = A + B + C. Ein einziges OR mit drei Eingängen.