Digitaltechnik

Prof. Jürgen Plate

4 Schaltalgebra

4.1 Aussagelogik, Boolesche Algebra, Schaltalgebra

In der klassischen Mathematik können Variable normalerweise unendlich viele Werte annehmen (z. B. bei reellen oder komplexen Zahlen). In der Schaltalgebra sind nur zwei Werte möglich. Das ist zunächst ungewohnt, jedoch bekannt durch den Umgang mit "Aussagen", d. h. Sätzen, denen man eindeutig einen von zwei "Wahrheitswerten" ("wahr" oder "falsch") zuordnen kann.

Die Aussagenlogik stellt eine Abstraktion der logischen Struktur der Sprache dar. Sie bewegt sich dabei zwischen Mathematik und Philosophie und ist die Grundlage der logischen Verknüpfungen, die in digitalen Schaltungen eingesetzt werden. Benötigt wird hier allerdings nur ihr Formalismus, der Hintergrund natürlichsprachlicher Aussagen dient vor Allem der Motivation bzw. dem intuitiven Verständnis.

Eine Aussage ist ein Satz, von dem es sinnvoll ist, zu sagen, er sei wahr oder falsch. Mit der verbalen Verknüpfung von Aussage befaßt sich die Aussagelogik (Aussagealgebra): Aussagen (und damit deren Wahrheitswerte) werden verbal mit Bindewörtern wie "nicht", "und", "entweder-oder" etc. verknüpft, der Wahrheitswert der neuen Aussage wird bestimmt.

Beispiele:
Aussagen: "Heute ist der 21. Dezember 2012", "Heute ist Sonntag", "Der Mond besteht aus Käse", "Dieser Satz ist falsch".

keine Aussagen: "Schokoladeneis schmeckt besser als Zitroneneis", "Esst mehr Obst!".

Verknüpfung mit "Nicht": "Heute ist nicht der 21. Dezember 2012"
Verknüpfung mit "Und": "Heute ist der 21. Dezember 2012 und es ist Weltuntergang"

Diese und weitere Betrachtungen mögen philosophisch interessant sein, als Grundlage für die Digitaltechnik dient im Grunde nur eine weitere Abstraktion der Aussagenlogik, nämlich der Umgang mit den Wahrheitswerten wahr und falsch (ohne jeden sprachlichen Hintergrund). Eine mathematische Grundlage des so gewonnenen Formalismus bildet die Boolesche Algebra (auch "formale Logik" genannt, nach George Boole, Britischer Mathematiker, 1815 - 1864). Es handelt sich um eine Formalisierung der Aussagelogik: zweiwertige (binäre) Eingangsgrößen werden mit logischen Funktionen zu zweiwertigen Ausgangsgrößen verknüpft. Die logischen Verknüpfungen sind hierbei an die verbalen Verknüpfungen angelehnt, anstelle von "wahr und "falsch" verwendet man die logischen Werte "1" und "0".

Verknüpfungen zwischen Aussagen (die kurz mit A bzw. B als Aussagenvariablen dargestellt werden) bilden neue Aussagen, z. B.:

A ∧ B Konjunktion: A und B ist wahr wenn sowohl A als auch B wahr ist
A ∨ B Disjunktion: A oder B ist wahr wenn A wahr ist oder wenn B wahr ist
A → B Implikation: wenn A dann B ist wahr wenn die Behauptung, dass aus A B folgt ist, stimmt; ist die Voraussetzung (A) bereits falsch, wird nichts behauptet, und die Implikation ist in Ordnung (also wahr); ist die Voraussetzung (A) wahr, muss die Schlussfolgerung (B) ebenfalls wahr sein, sonst ist die Implikation falsch
¬ A Negation: nicht A ist wahr, wenn A falsch ist, bzw. umgekehrt
A ↔ B Äquivalenz: A genau dann wenn B ist wahr, wenn A und B den selben Wahrheitswert haben, also beide wahr oder beide falsch sind
A ⊕ B Antivalenz/Exklusiv-Oder: entweder A oder B A oder B, aber nicht beides
A ↑ B Shefferfunktion: nicht (A und B) Negation der Konjunktion
A ↓ B Peircefunktion: nicht (A oder B) weder A noch B

Die Schaltalgebra (nach Claude Elwood Shannon, Amerikanischer Mathematiker und Informatiker, 1916 - 2001) ist die ursprünglich Anwendung der Booleschen Algebra zur mathematischen Behandlung und Darstellung von Relaisschaltungen, ausgehend von den drei Grundverknüpfungen NICHT, UND, ODER. In der Digitaltechnik:

Beschreibung des logischen Verhaltens von binären Digitalschaltungen

Die wesentlichen Unterschiede zwischen Schaltalgebra und bisher bekannten algebraischen Strukturen sind:

Variable und Konstante können nur die Werte "0" oder "1" annehmen. (Die Werte 0 und 1 sind nicht identisch mit den Zahlen 0 und 1)
Es gibt andere Verknüpfungen mit entsprechenden Verknüpfungszeichen
Mit endlich vielen Variablen sind nur endlich viele Funktionen möglich.
Funktionen können mit Tabellen vollständig beschrieben werden.

Im Unterschied zu analogen oder linearen Schaltungen sind reale logische Schaltungen zur Übertragung zweier bestimmter Signalzustände vorgesehen: "High" (H) oder logisch 1 und "LOW" (L) oder logisch 0. Die den beiden Zuständen zugeordneten Signalpegel sind vom Typ der verwendeten Schaltung abhängig. Sie hängen von der Art der verwendeten Logik-Schaltkreise verschiedener Familien oder anderen technischen Gegebenheiten ab. Die Zuordnung der logischen Zustände ist im Prinzip willkürlich, in der Regel ist die "positivere" Spannung oder "HIGH" dem Logikzustand "EINS" und die "negativere" Spannung oder "LOW" dem Logikzustand "NULL" zugewiesen, d. h. wir verwenden sogenannte positive Logik.

Da die Eingangsvariablen einer Funktion nur die beiden Werte 0 oder 1 annehmen können, lassen sich alle schaltalgebraischen Funktionen in Tabellenform mit einer sogenannten Wahrheitstabelle beschreiben. Bei n unabhängigen Eingangsvariablen gibt es 2ⁿ mögliche Eingangskombinationen, die auf der linken Seite einer Tabelle untereinander geschrieben werden. Auf der rechten Seite der Tabelle wird dann der jeweilige Funktionswert y angegeben.

Beispiel 1: Wahrheitstabelle einer Funktion y von einer Eingangsvariablen x:

x y

0 1

1 0

Beispiel 2: Wahrheitstabelle einer Funktion z von zwei Eingangsvariablen x1, x0:

x1 x0 y

0 0 0

0 1 1

1 0 1

1 1 0

Beispiel 3: Wahrheitstabelle einer Funktion u von drei Eingangsvariablen x2, x1, x0:

x2 x1 x0 y

0 0 0 0

0 0 1 1

0 1 0 1

0 1 1 0

1 0 0 1

1 0 1 0

1 1 0 1

1 1 1 0

Die Wahrheitstabellen von Funktionen mit mehr als drei Eingangsvariablen sind analog aufgebaut.

Darstellungsformen von Logikfunktionen

Wahrheitstabelle (Wertetabelle, Funktionstabelle)
Allen möglichen Wertekombinationen der Eingangsgrößen werden die Werte der jeweiligen Ausgangsgrößen zugeordnet - siehe oben.
Algebraische Gleichung (Funktionsgleichung):
y = F(x1,x2,x3,...,xn) Die Grundverknüpfungen und einige logischen Verknüpfungen erhalten Operatorsymbole, z. B.: y(x1,x2) = x1 ∧ x2
Blockschaltung (Logik-Diagramm):
Elementare Logikbausteine realisieren die Grundverknüpfungen. Diesen Bausteinen wird ein Schaltzeichen zugeordnet, sie werden auch als "Gatter" bezeichnet (Norm durch DIN 40700, Teil 14, Juli 1976).
Impulsdiagramm:
Das Verhalten von Ein- und Ausgängen wird durch Graphen des Signalverlaufs angezeigt.

Funktionen einer Variablen

Die Eingangsvariable x kann zwei Werte annehmen, wobei die Ausgangsvariable jeweils auch zwei Werte annehmen kann, d. h. es gibt vier verschiedene Funktionen y0, y1, y2, y3:

x y0 y1 y2 y3 y0 = 0: "Nie", Kontradiktion

0 0 0 1 1 y1 = x: Identität

1 0 1 0 1 y2 = NOT x: "Nicht", Negation, Inversion

y3 = 1: "Immer", Tautologie

x	y0	y1	y2	y3	y0 = 0: "Nie", Kontradiktion
0	0	0	1	1	y1 = x: Identität
1	0	1	0	1	y2 = NOT x: "Nicht", Negation, Inversion
	y3 = 1: "Immer", Tautologie

Von der Aussagelogik her ist die Negation y2 am anschaulichsten: Durch die Negation wird aus einer wahren Aussage eine falsche Aussage, aus einer falschen Aussage hingegen eine wahre Aussage. Übertragen auf die Schaltalgebra bedeutet dies: Durch Negation wird aus einer 0 eine 1, aus einer 1 hingegen eine 0.

Funktionen von zwei und mehr Variablen

Mit zwei Eingangsvariablen x1 und x2 ergeben sich 2^2² = 16 mögliche Funktionen y0 ... y15:

    x1   x2     y0   y1   y2   y3   y4   y5   y6   y7   y8   y9  y10  y11  y12  y13  y14  y15 

    0    0      0    0    0    0    0    0    0    0    1    1    1    1    1    1    1    1
    0    1      0    0    0    0    1    1    1    1    0    0    0    0    1    1    1    1
    1    0      0    0    1    1    0    0    1    1    0    0    1    1    0    0    1    1
    1    1      0    1    0    1    0    1    0    1    0    1    0    1    0    1    0    1

Einige Funktionen entsprechen Verknüpfungen, die von der Aussagelogik her bekannt sind.

UND-Verknüpfung, Konjunktion: y1 = x1 ∧ x2
ODER-Verknüpfung, Disjunktion: y7 = x1 ∨ x2
Gleichheit, Äquivalenz: y9 = x1 ≡ x2
Ausschließendes ODER, Antivalenz: y6 = x1 ⊕ x2
Negierte UND-Verknüpfung, NAND: y14 = ¬(x1 ∧ x2) (Shefferfunktion)
Negierte ODER-Verknüpfung, NOR: y8 = ¬(x1 ∨ x2) (Peircefunktion)

4.2 Logische Grundfunktionen

Die Grundverknüpfungen NICHT (NOT), UND (AND), ODER (OR) sind die logischen Grundoperationen (Grundfunktionen). Sie sind als Axiome definiert und werden postuliert (nicht beweisbar). Von Shannon wurden die UND und die ODER-Verknüpfung sowie die Negation als Grundfunktionen gewählt, weil:

alle logische Verknüpfungen (= alle Schaltfunktionen) auf die Grundfunktionen zurückzuführen sind.
Die Wahl dieser Grundfunktionen ist willkürlich. Auch ein anderes System von Funktionen wäre möglich.

Die logische Grundfunktionen sind hier zusammengestellt. Zuerst die drei Grundverknüpfungen:

Negation (Nicht-Verknüpfung)

UND-Verknüpfung

Die Konjunktion (UND) kann auf beliebig viele Eingänge erweitert werden. Die Ausgangsvariable hat nur dann den Wert 1, wenn alle Eingangsvariablen den Wert 1 haben.

ODER-Verknüpfung

Die Disjunktion (ODER) kann auf beliebig viele Eingänge erweitert werden. Die Ausgangsvariable hat dann den Wert 1, wenn mindestens eine Eingangsvariable den Wert 1 hat.

Einige weitere Funktionen werden relativ häufig benötigt und haben daher eigene Schaltsymbole:

EXOR-Verknüpfung (Exklusiv-Oder, Antivalenz)

Äquivalenz-Verknüpfung

NICHT-UND-Verknüpfung (NAND)

NICHT-ODER-Verknüpfung (NOR)

Auch für die bisher nicht betrachteten Funktionen gibt es z. T. spezielle Bezeichnungen/Symbole:

		         
   y0 = 0    __            __          formal falscher Ausdruck, Kontradikton
   y2 = x1 ∨ x2, y4 = x2 ∨ x1          Inhibitionen
  y11 = x2 → x1, y13 = x1 → x2         Implikationen
  y15 = 1                              formal wahrer Ausdruck, Tautologie

Die restlichen Funktionen werden mit den Eingangsvariablen bzw. negierten Eingangsvariablen beschrieben:

                               __           __
  y3 = x1,   y5 = x2,    y10 = x2,    y12 = x1

Für diese Funktionen gibt es keine speziellen Logiksymbole, ähnlich wie die NAND- und NOR-Verknüpfung kann man diese Funktionen mit UND-Gattern, ODER-Gattern und Negationen darstellen, z. B.:

Bei mehr als zwei Eingangsvariablen wird die Anzahl der möglichen Funktionen sehr groß. Man kann jedoch auch bei mehr als zwei Eingangsvariablen alle möglichen Funktionen auf die von Shannon gewählten Grundverknüpfungen NICHT, UND und ODER zurückführen; die UND- und die ODER-Verknüpfung werden hierzu auf beliebig viele Eingangsvariable erweitert (die Logiksymbole weisen dann entsprechend mehr Eingänge auf):

Die UND-Verknüpfung von n Eingangsvariablen x1, x2, ... xn ergibt nur dann den Wert 1, wenn alle Eingangsvariable den Wert 1 haben:

x1 ∧ x2 ∧ ... ∧ xn = 1 ⇔ x1 = x2 = ... = xn = 1

Die ODER-Verknüpfung von n Eingangsvariablen x1, x2, ... xn ergibt nur dann den Wert 0, wenn alle Eingangsvariable den Wert 0 haben:

x1 ∨ x2 ∨ ... ∨ xn = 0 ⇔ x1 = x2 = ... = xn = 0

Für diese Verknüpfungen gibt es Rechenregeln (Theoreme), mit denen man schaltalgebraische Ausdrücke von beliebigen Funktionen (in der Regel zur Vereinfachung) umformen kann. Diese Theoreme werden im folgenden Abschnitt behandelt.

Auch die NAND und NOR-Verknüpfungen sowie die Äquivalenz kann man auf beliebig viele Eingangsvariable erweitern:

Die NAND-Verknüpfung von n Eingangsvariablen x1, x2, ... xn ergibt nur dann den Wert 0, wenn alle Eingangsvariable den Wert 1 haben:
________________
x1 ∧ x2 ∧ ... ∧ xn = 0 ⇔ x1 = x2 = ... = xn = 1
Die NOR-Verknüpfung von n Eingangsvariablen x1, x2, ... xn ergibt nur dann den Wert 1, wenn alle Eingangsvariable den Wert 0 haben.
________________
x1 ∨ x2 ∨ ... ∨ xn = 1 ⇔ x1 = x2 = ... = xn = 0
Die Äquivalenz-Verknüpfung von n Eingangsvariablen x1, x2, ... xn ergibt nur dann den Wert 1, wenn alle Eingangsvariable den gleichen Wert haben.
x1 ≡ x2 ≡ ... ≡ xn = 1 ⇔ x1 = x2 = ... = xn
Die Antivalenz-Verknüpfung (Exklusiv-Oder) von n Eingangsvariablen x1, x2, ... xn ergibt nur dann den Wert 1, wenn nur ein Eingang 1 ist.

Oft werden wegen der zur Verfügung stehenden Typographie die Ersatzdarstellungen für die logischen Grundfunktionen verwendet. Insbesondere die Übersteichung der Negation ist oft schwierig darzustellen, weshalb im Skript in der Regel das Zeichen "¬" verwendet wird. Die Alternativdarstellungen sind:

Grundfunktion	Zeichen	Beispiel
Negation (NICHT)	¬ ! /	y = ¬ x1
Konjunktion (UND)	* &	y = x1 * x2
Disjunktion (ODER)	+	y = x1 + x2
Äquivalenz	≡ = ↔	y = x1 ↔ x2
Antivalenz (Exklusiv ODER)	⊕	y = x1 ⊕ x2

Schreib-Vereinfachung: Ähnlich wie bei der Multiplikation kann man bei der UND-Verknüpfung das Verknüpfungszeichen weglassen:

a ∧ b ∧ c = abc

4.3 Theoreme der Schaltalgebra

Sei B eine Menge und seien ∧ und ∨ Verknüpfungen (zweistellige Funktionen) auf B, d. h. Abbildungen ∧: B x B → B und ∨: B X B → B . Die Struktur (B, ∧, ∨) heißt eine Boolesche Algebra, wenn die folgenden vier Axiome gelten:

(B1) Kommutativgesetze: für alle x1, x2 ∈ B gilt:: x1 ∧ x2 = x2 ∧ x1; x1 ∨ x2 = x2 ∨ x1
(B2) Distributivgesetze: für alle x1, x2, x3 ∈ B gilt:: x1 ∧ (x2 ∨ x3) = (x1 ∧ x2) ∨ (x1 ∧ x3); x1 ∨ (x2 ∧ x3) = (x1 ∨ x2) ∧ (x1 ∨ x3)
(B3) Existenz neutraler Elemente: es gibt 0 ∈ B und 1 ∈ B, so dass für alle x1 ∈ B gilt:: x1 ∨ 0 = x1; x1 ∧ 1 = x1
(B4) Existenz komplementärer Elemente: zu jedem x1 ∈ B gibt es ein ¬ x1 ∈ B, so dass gilt:: x1 ∨ ¬ x1 = 1; x1 ∧ ¬ x1 = 0

Die Postulate für Konjunktion und Disjunktion zeigen Ähnlichkeit. Vertauscht man in den Postulaten von ∧ die Werte 0 und 1, erhält man die Postulate von ∨, und umgekehrt. Die Disjunktion bezogen auf den Wert 1 kann als Konjunktion auf den Wert 0 aufgefaßt werden und umgekehrt. Es gibt also eine Dualität von Konjunktion und Disjunktion. Die Operationen ∧ und ∨ sind also in ihren Eigenschaften völlig symmetrisch. Dieser Sachverhalt kann auch so ausgedrückt werden:

Ist (B, ∧, ∨) eine Boolesche Algebra, so ist auch (B, ∨, ∧) eine Boolesche Algebra.

Daraus ergibt sich, dass die Übergänge 0 nach 1 und 1 nach 0 durch die Negation darstellbar sind und somit die Funktion ∨ durch ∧ und die Negation nachgebildet werden kann (umgekehrt kann ∧ durch ∨ und Negation nachgebildet werden). Erstaunlicherweise sind also nur zwei Grundfunktionen für die Darstellung aller digitaler Schaltungen ausreichend (natürlich wird es einfacher, wenn man weitere "Grundfunktionen" hinzunimmt).

In jeder Booleschen Algebra gelten weitere Gesetze, deren Gültigkeit sich aus den vier Axiomen ableiten lässt.

(B5) Eindeutigkeit von 0 und 1: die neutralen Elemente sind als Elemente von B eindeutig bestimmt.
(B6) Eindeutigkeit der Komplemente: zu jedem x ∈ B gibt es nur ein komplementäres Element ¬ x ∈ B.
(B7) Doppeltes Komplement: für alle x ∈ B gilt: ¬ ¬ x = x
(B8) Idempotenz: für alle x ∈ B gilt: x ∧ x = x; x ∨ x = x
(B9) Gesetze von Null und Eins (Extremalgesetze): für alle x ∈ B gilt: x ∨ 1 = 1; x ∧ 0 = 0
(B10) Absorbtionsgesetze: für alle x1, x2 ∈ B gilt: x1 ∨ (x1 ∧ x2) = x1; x1 ∧ (x1 ∨ x2) = x1
(B11) Assoziativgesetze: für alle x1, x2, x3 ∈ B gilt: (x1 ∨ x2) ∨ x3 = x1 ∨ (x2 ∨ x3); (x1 ∧ x2) ∧ x3 = x1 ∧ (x2 ∧ x3)
(B12) Gesetze von De Morgan: für alle x1, x2 ∈ B gilt: ¬ (x1 ∨ x2) = ¬ x1 ∧ ¬ x2; ¬ (x1 ∧ x2) = ¬ x1 ∨ ¬ x2
(B13) Shannonsches Inversionstheorem: für alle x1, x2, ... xn ∈ B gilt: ¬ F(x1, x2, ... xn, ∧, ∨) = F(¬ x1, ¬ x2, ... ¬ xn, ∨, ∧)

Zweck der Theoreme ist die Umformen von Ausdrücken der Schaltalgebra zur optimalen technischen Realisierung der Logikschaltungen. Sie lassen sich aus den obigen Postulaten für die Grundschaltungen herleiten. Ein Beweis kann jederzeit durch vollständiges Einsetzen der Werte 0 und 1, durch Nachprüfen mit Wahrheitstabellen oder Ableiten aus bewiesenen Theoremen geführt werden. Bis auf zwei (doppelte Negation und Satz von Shannon) gibt es zu jedem Theorem eine duale Variante. Die Theoreme sind umkehrbar eindeutig, was eine Anwendung in beiden Richtungen gestattet. Die Theoreme gelten auch ohne Einschränkung, d. h. für jede Variable kann eine Schaltfunktion (in Klammern) stehen. Die folgende Tabelle fasst alle Postulate und Theoreme nochmals zusammen:

x ∨ 0 = x x ∧ 1 = x

x ∨ 1 = 1 x ∧ 0 = 0

Idempotenz-Gesetz x ∨ x = x x ∧ x = x

x ∨ ¬ x = 1 x ∧ ¬ x = 0

doppelte Negation ¬ ¬ x = x

Kommutativ-Gesetz x1 ∨ x2 = x2 ∨ x1 x1 ∧ x2 = x2 ∧ x1

Assioziativ-Gesetz x1 ∨ (x2 ∨ x3) = (x1 ∨ x2) ∨ x3 x1 ∧ (x2 ∧ x3) = (x1 ∧ x2) ∧ x3

Distributiv-Gesetz x1 ∧ (x2 ∨ x3) = (x1 ∧ x2) ∨ (x1 ∧ x3) x1 ∨ (x2 ∧ x3) = (x1 ∨ x2) ∧ (x1 ∨ x3)

Absorptionsgesetz x1 ∨ (x1 ∧ x2) = x1 x1 ∧ (x1 ∨ x2) = x1

x1 ∨ (¬x1 ∧ x2) = x1 ∨ x2 x1 ∧ (¬x1 ∨ x2) = x1 ∧ x2

Expansiosgesetz x1 = (x1 ∧ x2) ∨ (x1 ∧ ¬x2) x1 = (x1 ∨ x2) ∧ (x1 ∨ ¬x2)

Theoreme von de Morgan ¬ (x1 ∨ x2 ∨ x3 ∨ ... ∨ xn) = ¬ x1 ∧ ¬ x2 ∧ ¬ x3 ∧ ... ∧ ¬ xn ¬ (x1 ∧ x2 ∧ x3 ∧ ... ∧ xn) = ¬ x1 ∨ ¬ x2 ∨ ¬ x3 ∨ ... ∨ ¬ xn

Shannonsches Inversionstheorem ¬ F(x1,x2,x3,...,xn, ∨, ∧) = F(¬ x1,¬ x2,¬ x3,...,¬ xn, ∧, ∨)

Die Distributivgesetze werden vor allem in der umgekehrten Reihenfolge zum Ausklammern von Variablen oder Ausdrücken verwendet, um Schaltfunktionen zu vereinfachen.

Die de Morgan-Theoreme sind in der Praxis sehr bedeutsam, denn sie drücken die Dualität zwischen Konjunktion und Disjunktion aus. Die Disjunktion kann dementsprechend mitttels Konjunktion und Negation realisiert werden und umgekehrt. Damit reichen, wie oben schon erwähnt, zwei Grundoperationen aus, um alle Schaltfunktionen darzustellen. Andere Schreibweise (für 2 Variable):

x1 ∨ x2 = ¬(¬x1 ∧ ¬x2) x1 ∧ x2 = ¬(¬x1 ∨ ¬x2)

Das Shannonsches Inversionstheorem erlaubt das Invertieren einer Schaltfunktion. Dazu ein Beispiel. Gesucht wird die Inversion der Schaltfunktion

y = (x1 ∧ (¬x2 ∨ (x3 ∧ x4))) ∨ (x2 ∧ ¬x4)

Es ergibt sich auf konventiounellem Weg der Umformung:

¬y = ¬(x1 ∧ (¬x2 ∨ (x3 ∧ x4))) ∧ ¬(x2 ∧ ¬x4) =
   = (¬x1 ∨ ¬(¬x2 ∨ (x3 ∧ x4))) ∧ (¬x2 ∨ x4) =
   = (¬x1 ∨ (x2 ∧ ¬(x3 ∧ x4))) ∧ (¬x2 ∨ x4) =
   = (¬x1 ∨ (x2 ∧ (¬x3 ∨ ¬x4))) ∧ (¬x2 ∨ x4)

Vergleicht man die Ausdrücke für y und ¬ y, zeigt sich, dass alle Variablen invertiert sind und alle Disjunktionen durch Konjunktionen ersetzt wurden und umgekehrt. Dies ist eine allgemeingültige Regel für das Invertieren einer Schaltfunktion, eben das Shannonsches Inversionstheorem.
Achtung: Die ursprüngliche Rangfolge der Operationen muss beibehalten werden. Daher sind immer alle Ausdrücke in Klammern zu setzen, auch dort, wo diese zunächst nicht erforderlich wären. Zum Beispiel:

 y =  x1  + (x2 * ¬x3) + (¬x2 +  x3)
¬ y = ¬x1 * (¬x2 +  x3) * ( x2 * ¬x3)

Da in Gleichungen i. a. mehrere Grundfunktionen vorkommen, gibt es auch in der Booleschen Algebra Vorrangregeln für die Reihenfolge der Durchführung der einzelnen Operationen. Die Negation besitzt die höchste Präferenz, danach folgt die Konjunktion und schließlich die Disjunktion. Wegen den Ahnlichkeiten zwischen den arithmetischen und logischen Operatoren wird der AND-Operator (∧) auch als logische Multiplikation und der OR-Operator (∨) als logische Addition bezeichnet. Durch Klammerung kann die Präferenzreihenfolge verändert werden; Klammerausdrücke werden zuerst ausgewertet. Um Fehlinterpretationen zu vermeiden, empfiehlt es sich, häufig Klammern zu setzen.

Beispiel: Ausdrücke berechnen:

y1 = 1 ∨ 1 ∧ 0 = 1 ∨ 0 = 1
y2 = (1 ∨ 1) ∧ 0 = 1 ∧ 0 = 0 
y3 = (1 ∨ 1) ∧ ¬0 = 1 ∧ ¬0 = 1 ∧ 1 = 1

y4 = a ∨ ¬b ∧ c   mit a=1, b=0, c=0
y4 = 1 ∨ ¬0 ∧ 0 
   = 1 ∨ 1 ∧ 0
   = 1 ∨ 0
   = 1

y5 = (a ∨ ¬b) ∧ c   mit a=1, b=0, c=0
y5 = (1 ∨ ¬0) ∧ 0 
       = (1 ∨ 1) ∧ 0
       = 1 ∧ 0
       = 0

Beispiel: Negation eines Ausdrucks:

¬(a ∨ b ∧¬c ∨ ¬b ∧ c)
= ¬a ∧ ¬(b ∧ ¬c) ∧ ¬(¬b ∧ c)
= ¬a ∧ (¬b ∨ c) ∧ (b ∨ ¬c)

Beispiel: Vereinfachung eines Ausdrucks:

b ∧ c ∧ ¬(a ∧ ¬c ∧ c) ∨ ¬a ∧ (¬b ∨ c) 
= b ∧ c ∧ ¬(a ∧ 1) ∨ ¬a ∧ b ∧ ¬c 
= (b ∧ c ∧ ¬a) ∨ (¬a ∧ b ∧ ¬c) 
= (b ∧ ¬a) ∨ (¬a ∧ b)
= b ∧ ¬a

Betrachtet man die Theoreme oben genauer, lassen sich folgende Kürzungsregeln ableiten:

X1 ∨ (X1 ∧ X2) = X1
X1 ∧ (X1 ∨ X2) = X1
X1 ∨ (¬X1 ∧ X2) = X1 ∨ X2
X1 ∧ (¬X1 ∨ X2) = X1 ∧ X2
(X1 ∧ X2) ∨ (X1 ∧ ¬X2) = X1
(X1 ∨ X2) ∧ (X1 ∨ ¬X2) = X1

Für X1 und X2 können natürlich wieder beliebige boolesche Ausdrücke stehen.

Realisierung von UND, ODER, NICHT durch NAND und NOR

Wie schon erwähnt, lasse sich die Grundfunktionen NICHT, UND, ODER durch die Funktionen NAND und NOR darstellen. Die Realisierung mit NAND und NOR ist häufig anzutreffen, weil eben nur noch ein Gattertyp zum Einsatz kommt. NAND und NOR werden auch von den Herstellern digitaler Schaltungen in zahlreichen Varianten angeboten. Im Folgenden wird die Realisierung der drei Grundfunktionen durch NAND und NOR gezeigt.

Funktion	Realisierung mit NAND	Realisierung mit NOR
NICHT	y = ¬ x = ¬ (x ∧ x) = ¬ (x ∧ 1)	y = ¬ x = ¬ (x ∧ x) = ¬ (x ∨ 0)
UND	y = x1 ∧ x2 = ¬ ¬ (x1 ∧ x2)	y = x1 ∧ x2 = ¬ (¬ x1 ∨ ¬ x2)
ODER	y = x1 ∨ x2 = ¬ (¬ x1 ∧ ¬ x2)	y = x1 ∨ x2 = ¬ ¬ (x1 ∨ x2)

Beispiel: UND/ODER durch NAND ersetzen:

a ∧ b ∨ a ∧ c ∧ d ∨ a ∧ b ∧ d
= ¬(¬(a ∧ b) ∧ ¬(a ∧ c ∧ d) ∧ ¬(a ∧ b ∧ d))

Schaltfunktionen

Boolesche Verknüpfungen lassen sich elektrotechnisch realisieren. Dazu werden Schaltungen eingesetzt, deren Eingänge und Ausgänge jeweils einen von zwei Werten annehmen können, 0 oder 1. Eine solche Digitalschaltung ist eine bestimmte Form, eine Schaltfunktion durch Verknüpfungen auf den Variablen zu realisieren. Schaltausdrücke, welche dieselbe Schaltfunktionen implementieren, lassen sich mit Hilfe der oben aufgeführten Theoreme ineinander überführen (umformen). Ist das Ergebnis der Umformung einfacher, sprechen wir auch von der Vereinfachung der Schaltfunktion. Was dabei als "einfacher" angesehen wird, hängt allerdings von externen Kriterien ab.

Die Realisierung einer Schaltfunktion als digitale Schaltung wird grafisch in einem Blockschaltbild dargestellt, in dem die oben aufgeführten Schaltsymbole für die gebräuchlichen Verknüpfungen (und weitere Schaltelemente) sowie Leitungsverbindungen, Ein- und Ausgänge etc. dargestellt werden. Womit wir schon mitten in der Digitaltechnik gelandet wären.

Beispiel: Es soll für die Gleichung Y = (¬A ∨ B ∨ C) ∧ ¬(A ∨ D) eine Wahrheitstabelle und ein Blockschaltbild erstellt werden. Zuerst die Wahrheitstabelle:

 D   C   B   A   Y 
 0   0   0   0   1
 0   0   0   1   0 
 0   0   1   0   1
 0   0   1   1   0
 0   1   0   0   1 
 0   1   0   1   0
 0   1   1   0   1
 0   1   1   1   0
 1   0   0   0   0
 1   0   0   1   0
 1   0   1   0   0
 1   0   1   1   0
 1   1   0   0   0
 1   1   0   1   0
 1   1   1   0   0
 1   1   1   1   0

Und nun das Blockschaltbild:

Allerdings bietet die Gleichung ein hohes Potential für eine Vereinfachung, was man schon auf einen Blick an der Wahrheitstabelle erkennt. Für D = 1 ist beispielsweise Y immer 0 und für D = 0 ist Y = ¬A woraus sich die Vereinfachung Y = ¬D ∧ ¬A ergibt (B und C spielen keine Rolle). Deshalb werden Werkzeuge benötigt, die einen systematischen Aufbau von Gleichung und Schaltung erlauben - die Normalformen von Schaltfunktionen.

4.4 Normalformen von Schaltfunktionen

Bisher kennen wir vier Möglichkeiten für die Beschreibung eines Schaltnetzes:

Wahrheitstabelle (Wertetabelle):
Vorteil: Für jede Eingangskombination läßt sich sofort der Funktionswert ablesen. Nachteil: Struktur der Schaltung nicht ersichtlich.
Funktionsgleichung:
Vorteil: Schaltungsstruktur sofort ersichtlich Nachteil: Funktionswert für irgendeine Eingangskombination nicht ersichtlich
Blockschaltung:
Umsetzung der Funktionsgleichung mit Elementarbausteinen, also technische Realisierung.
Impulsdiagramm:
Zeitliches Verhalten von Ein- und Ausgängen (erst später wichtig).

Aus der Algebra ist bekannt, dass Funktionen in unterschiedlichen Gleichungen dargestellt werden können. Gleichungen können erweitert, durch Klammerausdrücke verschachtelt werden usw. Ähnlich kann man auch mit den Booleschen Gleichungen verfahren. Bei der Entwicklung logischer Schaltungen geht man meistens von Wahrheitstabellen aus. Eine Schaltung wird zunächst als 'Black Box' betrachtet. Im nächsten Schritt wird dann, ausgehend von der Wahrheitstabelle, eine Funktionsgleichung ermittelt, von der aus man zur Blockschaltung gelangt. Es wird nun ein einheitlicher Weg gesucht, wie man von der Wahrheitstabelle zur Funktionsgleichung gelangt. Dieser Schritt kann anhand der Normalformen durchgeführt werden. Man unterscheidet zwischen der disjunktiven und der konjunktiven Normalform. Beide Formen ergeben gleichwertige, jedoch unterschiedliche Funktionsgleichungen. Hat man eine disjunktive Verknüpfung (oder) zwischen konjunktiven Termen (und), so spricht man von einer disjunktiven Normalform. Bei konjunktiver (und) Verknüpfung zwischen disjunktiven Termen (oder) erhält man eine konjunktive Normalform, abgekürzt:

Disjunktive Normalform (DNF)
Konjunktive Normalform (KNF)

Disjunktive Normalform

Um zur disjunktiven Normalform zu gelangen, werden alle Zeilenkombinationen der Wahrheitstabelle herausgegriffen, bei der die Ausgangsvariable den Wert 1 annimmt. Alle Eingangsvariablen jeder Zeile werden in Eigenform (falls der Wert 1 ist) oder negierter Form (falls der Wert 0 ist) konjunktiv verknüpft. Die sich so ergebenden Vollkonjunktionen oder Minterme werden disjunktiv verknüpft. Zum Beispiel:

x1  x2  x3   y     Minterme
 0   0   0   0
 0   0   1   1 → (¬x1 ∧ ¬x2 ∧  x3)
 0   1   0   1 → (¬x1 ∧  x2 ∧ ¬x3)
 0   1   1   0
 1   0   0   1 → (x1 ∧ ¬x2 ∧ ¬x3)
 1   0   1   1 → (x1 ∧ ¬x2 ∧  x3)
 1   1   0   1 → (x1 ∧  x2 ∧ ¬x3) 
 1   1   1   0

y = (¬x1 ∧ ¬x2 ∧ x3) ∨ (¬x1 ∧ x2 ∧ ¬x3) ∨ (x1 ∧ ¬x2 ∧ ¬x3) ∨
    ∨ (x1 ∧ ¬x2 ∧ x3) ∨ (x1 ∧ x2 ∧ ¬x3)

Disjunktive Normalform (DNF, Standard Sum)

Die Disjunktive Normalform (DNF) einer Funktion Y ist die disjunktive Verknüpfung aller Vollkonjunktionen (=Minterme), für welche die Funktion y den Wert 1 annimmt. Die DNF entspricht einer auf den Wert "1" verkürzten Wahrheitstabelle. Minterm (auch: "Vollkonjunktion"): Konjunktive Verknüpfung (UND) aller Eingangsvariablen.

Die Notation kann auch weiter standardisiert werden, indem man die Zeilen der Wahrheitstabelle durchnummeriert, wobei die Zeilen nach den Engangsvariablen aufsteigend sortiert sind. Die Nummerierung entspricht somit dem dezimalen Wert, der sich ergibt, wenn man die Eingangsvariablen als Stellen einer Dualzahl auffasst. Zum Beispiel für zwei Eingangsvariable:

   b  a	    alle Minterme   Kurzform    
   0  0        ¬b ∧ ¬a          k0
   0  1	       ¬b ∧  a          k1
   1  0	        b ∧ ¬a          k2
   1  1	        b ∧  a          k3

Die Wahrheitstabelle kann dann durch die verkürzte Notation Σ(0, 1, ... n) beschrieben werden, wobei in der Klammer nur die Zeilennummern aufgenommen werden, bei denen y(b,a) gleich 1 ist. Zum Beispiel:

 Wahrheitstabelle      verkürzte Tabelle         Kurzschreibweise

  b  a  y(b,a)          b  a   y(b,a)    
  0  0    0    k0       0  1     1    k1         y(b,a) = (b ∧ ¬a) ∨ (b ∧ a)
  0  1    1    k1       1  1     1    k3                = k1 ∨ k3 
  1  0    0    k2                                       = Σ(1,3)
  1  1    1    k3

Für drei Eingangsvariable gilt:

   c    b    a      alle Minterme         
   0    0    0      ¬c ∧ ¬b ∧ ¬a       k0
   0    0    1      ¬c ∧ ¬b ∧  a       k1
   0    1    0      ¬c ∧  b ∧ ¬a       k2
   0    1    1      ¬c ∧  b ∧  a       k3
   1    0    0       c ∧ ¬b ∧ ¬a       k4
   1    0    1       c ∧ ¬b ∧  a       k5
   1    1    0       c ∧  b ∧ ¬a       k6
   1    1    1       c ∧  b ∧  a       k7

Beispiel 1:

   c    b    a    z(c,b,a)       
   0    0    0       0    k0    
   0    0    1       0    k1
   0    1    0       1    k2
   0    1    1       0    k3
   1    0    0       1    k4
   1    0    1       1    k5
   1    1    0       0    k6
   1    1    1       1    k7

z(c,b,a) = (¬c ∧ b ∧ ¬a) ∨ (c ∧ ¬b ∧ ¬a) ∨ (c ∧ b ∧ ¬a) ∨ (c ∧ b ∧ a)
         = k2 ∨ k4 ∨ k5 ∨ k7  
         = Σ(2,4,5,7)

Beispiel 2:

   c    b    a    y(c,b,a)       
   0    0    0       0    k0  
   0    0    1       0    k1
   0    1    0       1    k2
   0    1    1       1    k3
   1    0    0       0    k4
   1    0    1       1    k5
   1    1    0       1    k6
   1    1    1       0    k7

z(c,b,a) = (¬c ∧ b ∧ ¬a) ∨ (¬c ∧ b ∧ a) ∨ (c ∧ ¬b ∧ a) ∨ (c ∧ b ∧ ¬a)
         = k2 ∨ k3 ∨ k5 ∨ k6  
         = Σ(2,3,5,6)

Anmerkung: Eine ODER-Verknüpfung von beliebigen UND-Verknüpfungen nennt man eine disjunktive Form.

Konjunktive Normalform

Um zur konjunktiven Normalform zu gelangen werden alle Zeilenkombinationen der Wahrheitstabelle herausgegriffen, bei der die Ausgangsvariable den Wert 0 annimmt (Maxterme bzw. Volldisjunktionen). Beispiel:

x1  x2  x3   y     Maxterme
 0   0   0   0 → (x1 ∨ x2 ∨ x3)
 0   0   1   1
 0   1   0   1
 0   1   1   0 → (x1 ∨ ¬x2 ∨ ¬x3)
 1   0   0   1
 1   0   1   1
 1   1   0   1
 1   1   1   0 → (¬x1 ∨ ¬x2 ∨ ¬x3)

y = (x1 ∨ x2 ∨ x3) ∧ (x1 ∨ ¬x2 ∨ ¬x3) ∧ (¬x1 ∨ ¬x2 ∨ ¬x3)

Alternativ stellt man zuerst die disjunktive Normalform für ¬y auf. Beispiel:

x1  x2  x3   y     Minterme
 0   0   0   0 → (¬x1 ∧ ¬x2 ∧ ¬x3)
 0   0   1   1
 0   1   0   1
 0   1   1   0 → (¬x1 ∧ x2 ∧ x3)
 1   0   0   1
 1   0   1   1
 1   1   0   1
 1   1   1   0 → (x1 ∧ x2 ∧ x3)

¬y = (¬x1 ∧ ¬x2 ∧ ¬x3) ∨ (¬x1 ∧ x2 ∧ x3) ∨ (x1 ∧ x2 ∧ x3)

Nach Negation beider Seiten erhält man mit dem Theorem von de Morgan:

y = (x1 ∨ x2 ∨ x3) ∧ (x1 ∨ ¬x2 ∨ ¬x3) ∧ (¬x1 ∨ ¬x2 ∨ ¬x3)

Konjunktive Normalform (KNF, Standard Product):

Die Konjunktive Normalform (KNF) einer Funktion Y ist die konjunktive Verknüpfung aller Volldisjunktionen (=Maxterme), für welche die Funktion y den Wert 0 annimmt. Die KNF entspricht einer auf den Wert "0" verkürzten Wahrheitstabelle. Maxterm (auch: "Volldisjunktion"): Disjunktive Verknüpfung (ODER) aller Eingangsvariablen

Die Notation kann auch hier standardisiert werden, indem man die Zeilen der Wahrheitstabelle wie bei der DNF durchnummeriert. Zum Beispiel für zwei Eingangsvariable:

   b  a	    alle Maxterme   Kurzform    
   0  0         b ∨  a          d0
   0  1	        b ∨ ¬a          d1
   1  0	       ¬b ∨  a          d2
   1  1	       ¬b ∨ ¬a          d3

Die Wahrheitstabelle kann dann durch die verkürzte Notation Π(0, 1, ... n) beschrieben werden, wobei in der Klammer nur die Zeilennummern aufgenommen werden, bei denen y(b,a) gleich 0 ist. Zum Beispiel:

 Wahrheitstabelle      verkürzte Tabelle         Kurzschreibweise

  b  a  y(b,a)          b  a   y(b,a)    
  0  0    0    d0       0  0     0    d1         y(b,a) = (b ∨ a) ∧ (¬b ∨ a)
  0  1    1    d1       1  0     0    d3                = d1 ∧ d2 
  1  0    0    d2                                       = Π(0,2)
  1  1    1    d3

Für drei Eingangsvariable gilt:

   c    b    a      alle Maxterme          
   0    0    0       c ∨  b ∨  a      d0
   0    0    1       c ∨  b ∨ ¬a      d1
   0    1    0       c ∨ ¬b ∨  a      d2
   0    1    1       c ∨ ¬b ∨ ¬a      d3
   1    0    0      ¬c ∨  b ∨  a      d4
   1    0    1      ¬c ∨  b ∨ ¬a      d5
   1    1    0      ¬c ∨ ¬b ∨  a      d6
   1    1    1      ¬c ∨ ¬b ∨ ¬a      d7

Beispiel 1:

   c    b    a    z(c,b,a)       
   0    0    0       0    d0    
   0    0    1       0    d1
   0    1    0       1    d2
   0    1    1       0    d3
   1    0    0       1    d4
   1    0    1       1    d5
   1    1    0       0    d6
   1    1    1       1    d7

z(c,b,a) = (c ∨ b ∨ a) ∧ (c ∨ b ∨ ¬a) ∧ (c ∨ ¬b ∨ ¬a) ∧ (¬c ∨ ¬b ∨ a)
         = d0 ∧ d1 ∧ d3 ∧ d6  
         = Π(0,1,3,6)

Beispiel 2:

   c    b    a    y(c,b,a)       
   0    0    0       0    d0  
   0    0    1       0    d1
   0    1    0       0    d2
   0    1    1       1    d3
   1    0    0       0    d4
   1    0    1       1    d5
   1    1    0       1    d6
   1    1    1       1    d7

z(c,b,a) = (c ∨ b ∨ a) ∧ (c ∨ b ∨ ¬a) ∧ (c ∨ ¬b ∨ a) ∧ (¬c ∨ b ∨ a)
         = d0 ∧ d1 ∧ d2 ∧ d4  
         = Π(0,1,2,4)

Anmerkung: Eine UND-Verknüpfung von beliebigen ODER-Verknüpfungen nennt man eine konjunktive Form.

Disjunktive und konjunktive Normalform sind vollständig gleichwertig. Die DNF ist aus der Wahrheitstabelle leichter ablesbar und i. A. Basis für die anschließende Vereinfachung. Man kann aber auch den Ansatz wählen, dass man abhängig vom Wert der Ausgangsvariablen DNF oder KNF wählt:

y wird häufiger 1 als 0 → KNF
y wird häufiger 0 als 1 → DNF

Die Normalformen belegen auch die folgende, in der Praxis sehr wichtige Aussage:

Jede Schaltfunktion läßt sich immer durch eine zweistufige Schaltung realisieren.

DNF: 1. Stufe: Konjunktionen, 2. Stufe: Disjunktion der "Zwischenergebnisse"
KNF: 1. Stufe: Disjunktionen, 2. Stufe: Konjunktion der "Zwischenergebnisse"

Umwandlung DNF ↔ KNF

Gegeben sei die DNF oder KNF einer Funktion, gesucht ist die zugehörige KNF bzw. DNF.

Erste Möglichkeit:

Umformung mit den Logiktheoremen: Schwierig und langwierig.

Beispiel:

y(b,a) = ¬b ∧ ¬a ∨ b ∧ a 
¬ ¬y   = ¬ ¬(¬b ∧ ¬a ∨ b ∧ a)
       = ¬(¬(¬b ∧ ¬a) ∧ ¬(b ∧ a))
       = ¬((b ∨ a) ∧ (¬b ∨ ¬a))

Zweite Möglichkeit:

Eintragen der DNF(oder KNF) in eine Wahrheitstabelle, hieraus dann die zugehörige KNF (oder DNF) entnehmen: Einfach aber umständlich. Beispiel:

y(c,b,a) = (¬c ∨ ¬b ∨ a) ∧ (c ∨ ¬b ∨ ¬a) ∧ (c ∨ b ∨ a) (KNF)
→ eintragen ergibt:

  c  b  a  y(c,b,a)    
  0  0	0     0 	 
  0  0	1     1
  0  1  0     1
  0  1	1     0
  1  0  0     1
  1  0  1     1
  1  1  0     0
  1  1  1     1

Nun die DNF anschreiben:

y(c,b,a) = (c ∧ ¬b ∧ a) ∨ (¬c ∧ b ∧ ¬a) ∨ (c ∧ ¬b ∧ ¬a) ∨ (c ∧ ¬b ∧ a) ∨ (c ∧ b ∧ a)

Dritte Möglichkeit:

Verwendung der Kurzschreibweise: Einfach und schnell.

Beispiel:
DNF = Σ(1,2,4,5,7) → KNF = Π(0,3,6)

DNF oder KNF in NAND oder NOR realisieren

Anmerkung: Hierbei geht es nicht um Vereinfachung, sondern um die Realisierung mit nur einer Sorte von Logik-Gattern.

DFN in NAND

Liegt eine Funktionsgleichung in der disjunktiven Normalform (DNF, ODER-Normalform) vor, so erhält man die Funktionsgleichung in NAND-Technik, indem man

die Gleichung zweifach negiert und
die "innere" Negation (den unteren Negationsstrich) nach der Regel von De Morgan auflöst.

  Y = (¬A ∧ ¬B) ∨ (A ∧ ¬B) ∨ (A ∧ B)
    = ¬ ¬((¬A ∧ ¬B) ∨ (A ∧ ¬B) ∨ (A ∧ B))
    = ¬(¬(¬A ∧ ¬B) ∧ ¬(A ∧ ¬B) ∧ ¬(A ∧ B))

Achtung: NAND ist nicht assoziativ!

DNF in NOR

Liegt eine Funktionsgleichung in der disjunktiven Normalform (DNF) vor, so erhält man die Funktionsgleichung in NOR Technik, indem man

jeden Minterm doppelt invertiert,
die "innere" Negation (den unteren Negationsstrich) nach der Regel von De Morgan auflöst und
die gesamte Gleichung dann doppelt invertiert.

  Y = (¬A ∧ ¬B) ∨ (A ∧ ¬B) ∨ (A ∧ B)
    = ¬ ¬(¬A ∧ ¬B) ∨ ¬ ¬(A ∧ ¬B) ∨ ¬ ¬(A ∧ B)
    = ¬(¬A ∨ ¬B) ∨ ¬(A ∨ ¬B) ∨ ¬(A ∧ B)
    = ¬ ¬(¬(¬A ∨ ¬B) ∨ ¬(A ∨ ¬B) ∨ ¬(A ∧ B))

KNF in NAND

Liegt eine Funktionsgleichung in der konjunktiven Normalform (KNF, UND-Normalform) vor, so erhält man die Funktionsgleichung in NAND Technik, indem man

jeden Maxterm doppelt invertiert,
die "innere" Negation (den unteren Negationsstrich) nach der Regel von De Morgan auflöst und
die gesamte Gleichung dann doppelt invertiert.

  Y = (A ∨ ¬B) ∧ (A ∨ B)
    = ¬ ¬(A ∨ ¬B) ∧ ¬ ¬(A ∨ B)
    = ¬(¬A ∧ B) ∧ ¬(¬A ∧ ¬B)
    = ¬ ¬(¬(¬A ∧ B) ∧ ¬(¬A ∧ ¬B))

KNF in NOR

Liegt eine Funktionsgleichung in der konjunktiven Normalform (KNF) vor, so erhält man die Funktionsgleichung in NOR Technik, indem man

die Gleichung zweifach negiert,
die "innere" Negation (den unteren Negationsstrich) nach der Regel von De Morgan auflöst.

  Y = (A ∨ ¬B) ∧ (A ∨ B)
    = ¬ ¬((A ∨ ¬B) ∧ (A ∨ B))
    = ¬(¬(A ∨ ¬B) ∨ ¬(A ∨ B))

Beispiel: Würfel-Decodierung

Als etwas komplexeres Beispiel soll eine Binärzahl im 8-2-4-1-Code in die Anzeige für Würfelaugen umgesetzt werden. Die Würfelaugen werden nach folgendem Schema belegt:

Die Wahrheitstabelle ergibt sich dann zu:

W x3 x2 x1 a b c d e f g

1 0 0 0 0 0 0 1 0 0 0

2 0 0 1 0 1 0 0 0 1 0

3 0 1 0 0 1 0 1 0 1 0

4 0 1 1 1 1 0 0 0 1 1

5 1 0 0 1 1 0 1 0 1 1

6 1 0 1 1 1 1 0 1 1 1

W	x3	x2	x1	a	b	c	d	e	f	g
1	0	0	0	0	0	0	1	0	0	0
2	0	0	1	0	1	0	0	0	1	0
3	0	1	0	0	1	0	1	0	1	0
4	0	1	1	1	1	0	0	0	1	1
5	1	0	0	1	1	0	1	0	1	1
6	1	0	1	1	1	1	0	1	1	1

Wie man sofort sieht, müssen nur vier der sieben Gleichungen berücksichtigt werden, denn es gilt:

e = c
f = b
g = a

Die DNF für die vier verbleibenden Variablen lautet dann:

  a = (¬x3 ∧ x2 ∧ x1) ∨ (x3 ∧ ¬x2 ∧ ¬x1) ∨ (x3 ∧ ¬x2 ∧ x1)
  b = (¬x3 ∧ ¬x2 ∧ x1) ∨ (¬x3 ∧ x2 ∧ ¬x1) ∨ (¬x3 ∧ x2 ∧ x1) ∨ (x3 ∧ ¬x2 ∧ ¬x1) ∨ (x3 ∧ ¬x2 ∧ x1)
  c = (x3 ∧ ¬x2 ∧ x1)
  d = (¬x3 ∧ ¬x2 ∧ ¬x1) ∨ (¬x3 ∧ x2 ∧ ¬x1) ∨ (x3 ∧ ¬x2 ∧ ¬x1)

Die DNF lässt sich noch vereinfachen:

Ein Blick auf die Wahrheitstabelle zeigt, dass offensichtlich d = ¬x1 ist.
Für b wählt man besser die KNF; dann bleibt nur ein Term übrig: b = (x3 + x2 + x1)
Der Ausdruck für a lässt sich mit den Theoremen vereinfachen.

Nach Vereinfachung ergibt sich insgesamt:

a = (x1 * x2) + x3
b = (x3 + x2 + x1)
c = (x3 * ¬x2 * x1)
d = ¬x1
e = c
f = b
g = a

Was dann zur folgenden Schaltung führt:

Anmerkung: Da die Eingangs-Kombinationen 110 und 111 nicht vorkommen können, könnte man die Ausgangswerte für diese Kombinationen beliebig 0 oder 1 setzen - je nachdem, wie es für die Vereinfachung günstiger ist.

4.5 Schaltnetze und Schaltwerke

Grundsätzlich lassen sich Digitalschaltungen in zwei Gruppen unterscheiden, Schaltnetze und Schaltwerke.

Bisher wurden nur Schaltfunktionen mit einer Ausgangsvariablen behandelt. Man kann die bisher behandelten Prinzipien auf Binärschaltungen mit mehreren Ausgangsvariablen erweitern, wobei jede Ausgangsvariable getrennt von den anderen betrachtet werden kann. Das führt dann zu sogenannten Schaltnetzen.

Dies sind Digitalschaltungen, bei denen der Zustand der Ausgänge zu jedem Zeitpunkt nur vom Zustand der Eingänge zu diesem Zeitpunkt abhängt. Die Vorgeschichte spielt keine Rolle. Es sind keine Rückkopplungen oder Speicher vorhanden.

Jeder Ausgang Y_n kann als Funktion f_n der Eingangssignale X₀ ... X_m betrachtet werden:

Y_n = f_n(₀, ..., X_m)

Typische Beispiele von Schaltnetzen:

Schaltungen zur Addition oder Subtraktion von Zahlen
Schaltungen zur Umwandlung von Dualzahlen in Dezimalzahlen (BCD)

Kein Schaltnetz ist dagegen z. B. eine Fernbedienung mit Ein/Aus-Taste. Anhand von Zeitdiagrammen kann man oft erkennen, dass es sich nicht um ein Schaltnetz handeln kann:

Obiges Impulsdiagramm liefert für gleiche Eingangswerte (z. B. A = 1 und B = 0) unterschiedliche Ausgangswerte.

Soll die Vorgeschichte, d. h. der Zustand der Ausgänge zu einem früheren Zeitpunkt eine Rolle spielen, ist eine Erweiterung um Speicherelemente notwendig. Schaltwerke sind Digitalschaltungen, bei denen der Zustand der Ausgänge zu jedem Zeitpunkt vom Zustand der Eingänge zu diesem Zeitpunkt und endlich vielen vorausgegangenen Zuständen abhängt. Der Zustand von endlich vielen vorhergegangenen Zeitpunkten führt zu inneren Zuständen, welche die Schaltung einnimmt → Kombinatorik mit externer (asynchroner oder synchroner) Rückkopplung.

Als Speicherelemente werden in der Regel Flipflops verwendet (siehe späteres Kapitel). Die Kombinatorik arbeitet, bis sich ein stabiler Wert der Rückkopplungssignale einstellt. Dabei kann es vorkommen, dass bei instabilen Rückkopplungen das System schwingen (oszillieren) kann (aufgrund der Signallaufzeiten im Schaltnetz). Als Sonderfall lassen sich auch die Ausgangssignale als Rückkopplungssignale verwenden. Nachdem die Rückkopplungssignale einen stabilen Wert angenommen haben und sich die Eingänge nicht ändern, werden auch die Ausgänge einen stabilen Wert annehmen:

Die Schaltung befindet sich in einem stabilen Zustand.
Die Rückkopplungssignale kennzeichnen den Zustand → Zustandsvektor.
Änderungen der Eingangssignale können zu einer Änderung der Ausgangssignale oder der Rückkopplungssignale führen → Schaltung nimmt einen neuen Zustand ein.
Der Zustand ist das "Gedächtnis" der Schaltung, das von früheren Eingangswerten abhängt.
Man spricht auch von sequenziellen Schaltungen, da sie eine Folge (Sequenz) von Zuständen einnehmen.

Ergänzungen

Positive und negative Logik

Die Schaltalgebra arbeitet immer mit den logischen Werten "0" und "1". In der realen Schaltungstechnik besitzen die Schaltkreise Eingänge oder Ausgänge, an denen Spannungswerte angelegt oder gemessen werden können; bei digitalen Schaltungen gibt es zwei Spannungswerte, bzw. Spannungsbereiche:

einen niedrigeren Wert (z. B., 0 V) oder Bereich (z. B. 0 .. 0,3 V), "L"
einen höheren Wert (z. B. 5 V) oder Bereich (z. B. 4,0 .. 5,0 V), "H"

Positive bzw. negative Logik resultiert aus der Zuordnung der Spannungswerte zu den logischen Werten:

Positive Logik: "1" ↔ "L"-Pegel
Negative Logik: "0" ↔ "H"-Pegel

Beispiel:

An den Eingängen einer Schaltung werden verschiedene Spannungswerte angelegt und man misst die Werte am Ausgang:

Arbeitstabelle     Pos. Logik      Neg. Logik

   b  a   y        b  a   y        b  a   y  
   L  L   L        0  0   0        1  1   1 
   L  H   L        0  1   0        1  0   1
   H  L   L        1  0   0        0  1   1
   H  H   H        1  1   1        0  0   0

Demzufolge erhält man je nach Logik eine UND- bzw. eine ODER-Funktion.

Gebräuchliche Gatterbausteine

Integrierte Schaltkreise gibt es in zahlreichen Ausführungen und Technologien. Schaltkreise mit festgelegten Gatterfunktionen werden jedoch in zunehmendem Maß von universellen Bausteinen verdrängt, deren Funktion durch eine Form der "Programmierung" festgelegt wird. Die Anzahl und Auswahl der zur Verfügung stehenden Gatterbausteine wird daher stetig abnehmen.

Folgende Bausteine sind z.Zt. gebräuchlich:

NAND-Gatter mit 2/3/4/8 Eingängen
NOR-Gatter mit 2/3/4/8 Eingängen
Inverter
UND-Gatter
ODER-Gatter
EXOR-Gatter

Einen aktuellen Überblick erhält man am besten durch die Produktübersicht von verschiedenen Halbleiterherstellern im Internet. Nachfolgend einige Adressen:

www.fairchildsemi.com (Fairchild)
www.semiconductor.hitachi.com (Hitachi)
www.philips.com (Philips)
www.st.com (SGS-Thomson)
www.ti.com (Texas Instruments)
www.infineon.com (Siemens/Infineon)

(Die obige Auswahl an Firmen stellt keinerlei Wertung dar.)

Realisierung beliebiger Funktionen

Oft steht man vor der Aufgabe, mit vorgegebenen Gattern eine beliebige Funktion realisieren zu müssen. Hierbei ergeben sich möglicherweise folgende Probleme, die anhand von Beispielen illustriert werden:

Die Gatter haben zu viele Eingänge

Die Gatter haben zu wenige Eingänge

Die benötigten Gatter sind nicht vorhanden

Tri-State und Wired-AND-Ausgang

Tri-State

Etliche Digitalbausteine können am Ausgang nicht nur die beiden Werte entsprechend "0" und "1" annehmen, sondern lassen sich noch in einen Zustand schalten, bei dem der Ausgang hochohmig ist (Alle Ausgangstransistoren gesperrt). Dieser Modus erlaubt das Anschalten mehrerer Gatter an eine gemeinsame Leitung, die "Bus" genannt wird. Durch entsprechende Koordination wird immer nur ein Ausgang auf dem Bus aktiv. Diese Form findet vor allem in Computersysteme Verwendung, wo CPU, Speicher und Ein-/Ausgabebausteine sich den Bus teilen.

Wired AND

Hier haben die Logik-Gatter einen Open-Collector- bzw. Open-Drain-Ausgang (OC), weshalb ein zusätzlich erforderlicher Pull-Up-Widerstand (R) angeschlossen werden muss. Es gilt bei positiver Logik:

log. Ausgangssignal "0": Transistor leitet → "0" am Ausgang,
log. Ausgangssignal "1": Transistor sperrt → "1" am Ausgang.

An den Arbeitswiderstand lassen sich mehrere OC-Ausgänge anschließen → Verbindung der Gatterausgänge erzeugt bei positiver Logik ein logisches UND (→ Wired AND).

Beispiel für 2 Ausgänge:

Gate 1 Gate 2 Ausgang

0 0 0

0 1 0

1 0 0

1 1 1

"0" → Ausgangstransistor leitet, "1" → Ausgangstransistor sperrt.

Gate 1	Gate 2	Ausgang
0	0	0
0	1	0
1	0	0
1	1	1

4.7 Übungen

Aufgaben

Aufgabe 1:

Wie viele Zeilen hat die Wahrheitstabelle einer Funktion von sechs Eingangsvariablen?
Wie viele verschiedene Funktionen mit vier Eingangsvariablen gibt es?
Für eine Addierschaltung, welche 32-Bit-Zahlen verarbeiteten soll, ist eine Wahrheitstabelle zu erstellen. Welches Problem tritt hierbei auf?

Aufgabe 2: Bestimmen Sie den Wert der folgenden Funktionen für die jeweils angegebenen Werte der Eingangsvariablen.

f1(a,b,c) = ( 0 ∨ b ) ∧ ¬( a ∨ c ) für a = 0, b = 1, c = 0;
f2(a,b,c) = a ∧ b ∧ ( c ∨ 0 ) für a = 1, b = 1, c = 0;
f3(a,b,c,d) = ( a ∧ b ) ∧ ( c ∨ ¬d ) für a = 0, b = 1, c = 0, d = a;
f4(a,b,c,d) = ( a ∨ ( b ∧ c ) ) ∧ ( 1 ∧ ¬d ) ∧ ¬c für a = 0, b = 1, c = 1, d = 0;
f5(a,b,c,d) = ( a ∧ d ) ∧ ( b ∨ c ) für a = 1, b = 1, c = 0, d = 1;

Aufgabe 3: Negieren Sie die folgenden Funktionen.

g1(a,b) = ( a ∧ b ) ∨ ¬ ( a ∨ b );
g2(a,b,c) = a ∧ b ∨ 0 ∧ c ∨ a ∧ ¬ ( c ∧ b );
g3(a,b,c,d) = a ∧ b ∨ c ∨ { [ a ∨ b ∧ ( a ∨ b ) ] ∨ ¬a ∧ ¬b ∨ c };

Aufgabe 4:

Stellen Sie die Funktionen NICHT, UND und ODER durch die NOR-Funktion dar und skizzieren Sie jeweils das zugehörige Logikdiagramm.
Stellen Sie die Äquivalenz-Funktion durch die NAND-Funktion dar und skizzieren Sie das zugehörige Logikdiagramm.

Aufgabe 5: Gegeben ist die Funktion y(c,b,a) = c ∧ (b ∨ a) ∨ ¬ (c ∨ b).

Erstellen Sie die Wahrheitstabelle zu der Funktion y.
Ermitteln Sie die DNF und die KNF von y und geben Sie diese in drei verschiedenen Schreibweisen an.
Skizzieren Sie die Logikdiagramme der gegebenen Funktion sowie der DNF und KNF von y.

Aufgabe 6: Von der Funktion z(d,c,b,a) = d ∧ (c ∨ b ∧ a) ∨ ¬(c ∧ a) ist die Wahrheitstabelle sowie die DNF und die KNF zu bestimmen.

Aufgabe 7:

Gegeben ist die Funktion u(c,b,a) = Σ(1,4,5). Bestimmen Sie die zugehörige KNF.
Gegeben ist die Funktion v(d,c,b,a) = Π(1,4,5,8,11,14). Bestimmen Sie die zugehörige DNF.

Aufgabe 8: Eine Funktion w(a,b,c,d) soll immer dann den Wert 1 aufweisen, wenn zwei oder drei Eingangsvariablen den Wert 0 annehmen.

Erstellen Sie die zugehörige Wahrheitstabelle.
Geben Sie die DNF und die KNF der Funktion an.

Lösungen

1a) 64; b) 65536; c) zu viele Zeilen;

2a) f1 = 1; b) f2 = 0; c) f3 = 0; d) f4 = 0; e) f5 = 1;

3a) ¬g1 = (¬a ∨ ¬b ) ∧ ( a ∨ b );

3b) ¬g2 = (¬a ∨ ¬b) ∧ (1 ∨ ¬c) ∧ (¬a ∨ ( c ∧ b ));

3c) ¬g3 = (¬a ∨ ¬b) ∧ ¬c ∧ { [¬a ∧ (¬b ∨ (¬a ∧ ¬b )) ] ∧ (a ∨ b) ∧ ¬c  };

4a)	¬x    = ¬(x ∨ 0) = ¬(x ∨ x);
    a ∧ b = ¬ (¬ (a ∨ 0) ∨ ¬ (b ∨ 0));
    a ∨ b = ¬  ¬ (a ∨ b);

4b)	a ∧ b ∨  a ∧ b = (a ∧ b) ∧ (a ∧ b);

5) y = Σ(0,1,5,6,7) = Π(2,3,4);

6) z = Σ(1,3,9,11,12,13,14,15) = Π(0,2,4,5,6,7,8,10);

7a) u = Π(0,2,3,6,7);

8) w = Σ(1,2,3,4,5,6,8,9,10,12) = Π(0,7,11,13,14,15);

Zum vorhergehenden Abschnitt

Zum Inhaltsverzeichnis

Zum nächsten Abschnitt

A ∧ B	Konjunktion: A und B	ist wahr wenn sowohl A als auch B wahr ist
A ∨ B	Disjunktion: A oder B	ist wahr wenn A wahr ist oder wenn B wahr ist
A → B	Implikation: wenn A dann B	ist wahr wenn die Behauptung, dass aus A B folgt ist, stimmt; ist die Voraussetzung (A) bereits falsch, wird nichts behauptet, und die Implikation ist in Ordnung (also wahr); ist die Voraussetzung (A) wahr, muss die Schlussfolgerung (B) ebenfalls wahr sein, sonst ist die Implikation falsch
¬ A	Negation: nicht A	ist wahr, wenn A falsch ist, bzw. umgekehrt
A ↔ B	Äquivalenz: A genau dann wenn B	ist wahr, wenn A und B den selben Wahrheitswert haben, also beide wahr oder beide falsch sind
A ⊕ B	Antivalenz/Exklusiv-Oder: entweder A oder B	A oder B, aber nicht beides
A ↑ B	Shefferfunktion: nicht (A und B)	Negation der Konjunktion
A ↓ B	Peircefunktion: nicht (A oder B)	weder A noch B

	x ∨ 0 = x	x ∧ 1 = x
	x ∨ 1 = 1	x ∧ 0 = 0
Idempotenz-Gesetz	x ∨ x = x	x ∧ x = x
	x ∨ ¬ x = 1	x ∧ ¬ x = 0
doppelte Negation	¬ ¬ x = x
Kommutativ-Gesetz	x1 ∨ x2 = x2 ∨ x1	x1 ∧ x2 = x2 ∧ x1
Assioziativ-Gesetz	x1 ∨ (x2 ∨ x3) = (x1 ∨ x2) ∨ x3	x1 ∧ (x2 ∧ x3) = (x1 ∧ x2) ∧ x3
Distributiv-Gesetz	x1 ∧ (x2 ∨ x3) = (x1 ∧ x2) ∨ (x1 ∧ x3)	x1 ∨ (x2 ∧ x3) = (x1 ∨ x2) ∧ (x1 ∨ x3)
Absorptionsgesetz	x1 ∨ (x1 ∧ x2) = x1	x1 ∧ (x1 ∨ x2) = x1
	x1 ∨ (¬x1 ∧ x2) = x1 ∨ x2	x1 ∧ (¬x1 ∨ x2) = x1 ∧ x2
Expansiosgesetz	x1 = (x1 ∧ x2) ∨ (x1 ∧ ¬x2)	x1 = (x1 ∨ x2) ∧ (x1 ∨ ¬x2)
Theoreme von de Morgan	¬ (x1 ∨ x2 ∨ x3 ∨ ... ∨ xn) = ¬ x1 ∧ ¬ x2 ∧ ¬ x3 ∧ ... ∧ ¬ xn	¬ (x1 ∧ x2 ∧ x3 ∧ ... ∧ xn) = ¬ x1 ∨ ¬ x2 ∨ ¬ x3 ∨ ... ∨ ¬ xn
Shannonsches Inversionstheorem	¬ F(x1,x2,x3,...,xn, ∨, ∧) = F(¬ x1,¬ x2,¬ x3,...,¬ xn, ∧, ∨)

W	x3	x2	x1	a	b	c	d	e	f	g
1	0	0	0	0	0	0	1	0	0	0
2	0	0	1	0	1	0	0	0	1	0
3	0	1	0	0	1	0	1	0	1	0
4	0	1	1	1	1	0	0	0	1	1
5	1	0	0	1	1	0	1	0	1	1
6	1	0	1	1	1	1	0	1	1	1

W	x3	x2	x1	a	b	c	d	e	f	g
1	0	0	0	0	0	0	1	0	0	0
2	0	0	1	0	1	0	0	0	1	0
3	0	1	0	0	1	0	1	0	1	0
4	0	1	1	1	1	0	0	0	1	1
5	1	0	0	1	1	0	1	0	1	1
6	1	0	1	1	1	1	0	1	1	1