1 Boolesche Algebra und digitale Logik

1.6 Grundregeln der Booleschen Algebra

Die Booleschen Funktionen sollen jetzt einer genaueren Behandlung unterzogen werden, insbesondere soll die zweielementige Boolesche Algebra präziser definiert werden.

Zur Definition einer Booleschen Algebra können prinzipiell zwei unterschiedliche Wege beschritten werden. Es kann entweder von der Verbandstheorie oder von einem Axiomensystem ausgegangen werden.

Hier soll der axiomatische Weg verfolgt werden, wobei ein System benutzt wird, das von dem amerikanischen Mathematiker Huntington 1904 entwickelt wurde.

Bei der Behandlung des Axiomensystems kann kann eine Unterteilung in die

• Booleschen Postulate und die
• Booleschen Theoreme
  

1.6.1 Die Booleschen Postulate

Die Booleschen Postulate stellen formal die Forderungen zusammen, die eine Boolesche Algebra erfüllen muß.

Definition:
Die Boolesche Algebra ist die Menge A mit den Elementen 0 und 1, in der die zweielementigen Operationen "+" und "·" (bzw. "" und "") definiert sind, so daß gilt:

• P1: a = 0 oder a = 1 mit a A
• P2: 0 · 0 = 0
• P3: 1 + 1 = 1
• P4: 0 + 0 = 0
• P5: 1 · 1 = 1
• P6: 1 · 0 = 0 · 1 = 0
• P7: 1 + 0 = 0 + 1 = 1

1.6.2 Die Booleschen Theoreme

Unter Heranziehung der Booleschen Postulate können jetzt die Booleschen Theoreme (Lehrsätze) aufgestellt werden. Die Richtigkeit dieser Lehrsätze kann jederzeit mit Hilfe der Postulate überprüft werden (z.B unter Verwendung von Wahrheitstafeln).
Ein Theorem in der Booleschen Algebra ist eine Regel, die eine fundamentale Beziehung zwischen den Booleschen Variablen zum Ausdruck bringt. Anwendung der Theoreme wird es dann erlauben, logische Schaltungen in vielfältiger Form zu manipulieren bzw. zu vereinfachen.

Zur Definition und Diskussion der einzelnen Theoreme soll jeweils von drei Aspekten ausgegangen werden:

1. Das Theorem soll in algebraischer Form vorgestellt werden,
2. Die Bedeutung des Theorems soll mittels Venn-Diagramm veranschaulicht werden,
3. Die praktische Anwendung beim Schaltungsentwurf mit Logik-Gattern soll gezeigt werden.

T1: Kommutativgesetz (Vertauschungsgesetz)

T1.1

	a)	a + b = b + a
	b)	a · b = b · a

T1.2 Mengendarstellung:

Plausibilitätsbetrachtung:
Es ist offenbar gleich, in welcher Reihenfolge die Mengen A und B disjunktiv ("+") bzw. konjunktiv ("·") verknüpft werden.

T1.3 Gatter-Implementierung:

Abb. 1.20: Kommutativgesetz auf Gatterebene.

Plausibilitätsbetrachtung:
Es ist offenbar gleich, in welcher Reihenfolge die Eingangsvariablen an die Eingänge der ODER- bzw. UND-Gatter gelegt werden.

T2: Assoziativgesetz

T2.1

	a)	(a + b) + c = a + (b + c)
	b)	(a · b) · c = a · (b · c)

T2.2 Mengendarstellung:

Abb. 1.21: Assoziativgesetz.

Plausibilitätsbetrachtung:
Es ist offenbar gleich, in welcher Reihenfolge die Mengen A, B und C disjunktiv ("+") bzw. konjunktiv ("·") verknüpft werden.

T2.3 Gatter-Implementierung:

Jeder Klammerung, die in der algebraischen Form auftritt, entspricht bei der Gatterimplementierung eine Gatterebene (der entsprechende algebraische Ausdruck wird als "gatterisomorph" bezeichnet).

Abb. 1.22: Assoziativgesetz auf Gatterebene.

T3: Distributivgesetz (Verteilungsgesetz)

Die Funktionen "Disjunktion" und "Konjunktion" sind distributiv (verteilend), d.h. "ODER" verteilt sich über "UND, "UND" verteilt sich über "ODER".


T3.1

	a)	a + (b · c) = (a + b) · (a + c)
	b)	a · (b + c) = (a · b) + (a · c) = a · b + a · c

Aussagenlogisch bedeutet dies im Falle von Form a):
Der Ausdruck "a + (b · c)" ist genau dann wahr, wenn "a" wahr ist oder wenn "b" und "c" beide wahr sind.
"(a + b) · (a + c)" ist genau dann wahr, wenn jeder der beiden Klammerausdrücke wahr ist. Diese Ausdrücke sind wiederum wahr, wenn "a" wahr ist. Ist "a" nicht wahr, so müssen "b" und "c" beide wahr sein.

Entsprechend kann algebraische Form b) interpretiert werden.

T3.2 Mengendarstellung:

Abb. 1.23: Distributivgesetz.

Plausibilitätsbetrachtung:
Durch schrittweises Vorgehen kann die Richtigkeit des Distributivgesetzes an Hand des Mengendiagrammes veranschaulicht werden.

T3.3 Gatter-Implementierung:

Durch Anwendung dieses Theorems T3 kann die Anzahl der Gattereingänge (engl. pin count) einer Schaltung reduziert werden.

Form a):

Abb. 1.24: Distributivgesetz auf Gatterebene.

Für Form b) kann die Gatterimplementierung in ähnlicher Weise vorgenommen werden.

T4: Idempotenzgesetz (Identitätsgesetz)

T4.1

	a)	a + a = a
	b)	a · a = a

T4.2 Mengendarstellung:

Die Menge bleibt bei disjunktiver bzw. konjunktiver Verknüpfung mit sich selbst unverändert.

T4.3 Gatter-Implementierung:

Abb. 1.25: Idempotenzgesetz auf Gatterebene.

Die Gatterschaltung ist logisch redundant. Sie verzögert allerdings das Signal "a" und hat damit technische Bedeutung.

T5: Absorptionsgesetz (Verschmelzungsgesetz, Redundanzgesetz)

T5.1

	a)	a + (a · b) = a
	b)	a · (a + b) = a

Aussagenlogisch bedeutet dies

für den Ausdruck "a + (a · b)":
Ist "a" wahr, dann ist der Wert von "b" irrelevant. Ist jedoch "a" falsch, kann (a · b) nicht mehr wahr werden. Der Ausdruck ist also vollständig durch "a" bestimmt, "b" wird "absorbiert".

für den Ausdruck "a · (a + b)":
Ist "a" wahr, dann ist auch "(a + b)" wahr, d.h. der gesamte Asudruck ist wahr. Ist "a" falsch, so ist der gesamte Ausdruck falsch. Der Ausdruck ist also wiederum vollständig durch "a" bestimmt, "b" wird "absorbiert".

Dieses Gesetz folgt unmittelbar aus dem Distribtivgesetz unter Einbeziehung des Idempotenzgesetzes (T3 und T4).

T5.2 Mengendarstellung:

Auch am Venn-Diagramm kann die logische Redundanz der Schaltung überprüft werden.

T5.3 Gatter-Implementierung:

Abb. 1.26: Absorptionsgesetz auf Gatterebene.

Die Gatterschaltung ist wiederum logisch redundant. Wie später gezeigt wird, verzögert sie aber das Signal "a" um zwei Gatterlaufzeiten und hat damit eine technisch relevante Funktion.

T6: Null- und Eins-Gesetz

T6.1

	a)	0 + a = a 1 + a = 1
	b)	0 · a = 0 1 · a = a

T6.2 Mengendarstellung:

Die Verifikation dieses Theorems durch Venn-Diagramme ist natürlich trivial.

T6.3 Gatter-Implementierung:

Abb. 1.27: Null- und Eins-Gesetz auf Gatterebene.

T7: Komplement-Gesetz

Zu jedem Element "a" existiert ein komplementäres Element "\a".

"\a" wird Komplement von "a" genannt.

T7.1

	a)	a + \a = 1
	b)	a · \a = 0

T7.2 Mengendarstellung:

Abb. 1.28: Komplement-Gesetz.

T7.3 Gatter-Implementierung:

Abb. 1.29: Null- und Eins-Gesetz auf Gatterebene.

T8: De Morgansches Theorem

T8.1

	a)
	b)

Das De Morgansche Theorem hat sehr große Bedeutung für die Schaltungstechnik. Insbesondere bei der Transformation von Schaltungen kommt die in diesem Gesetz ausgedrückte Möglichkeit der Umwandlung zwischen unterschiedlichen, sogenannten dualen Booleschen Funktionen zur Anwendung:

Wie die oben wiedergegebenen algebraischen Formen verdeutlichen, ist die Umwandlung von NOR- zu UND-Schaltungen bzw. von NAND- zu ODER-Schaltungen unmittelbar möglich:

NOR UND

NAND ODER .

Dieser Sachverhalt wird besonders deutlich an der Gatterimplementierung:

T8.3 Gatter-Implementierung:

Abb. 1.30: De Morgansches Theorem auf Gatterebene.