2. Boolesche Funktionen

2.0. Aussagenlogik

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

2.0.1. Eine Aussage ist ein Satz, von dem es sinnvoll ist, zu sagen, er sei wahr oder falsch.

Beispiele:
Satz Aussage? Bemerkung
Dreiecke sind rund. ja eindeutig falsch
Der Mond besteht aus Schweizer Käse. ja Wir wissen es seit 1969.
Es regnet. ja Der Wahrheitswert variiert zwar mit dem Kontext (Ort und Zeit der Aussage), dieser jedoch ist nicht Bestandteil des Logiksystems der elementaren Aussagenlogik; wir beschäftigen uns hier mit einer Abstraktion einiger Aspekte der natürlichen Sprache, „Zeit spielt keine Rolle“.
Dieser Satz ist falsch. nein Aus der Annahme, der Satz wäre wahr bzw. falsch, folgt jeweils ein Widerspruch. Daher ist keine der beiden Annahmen sinnvoll. (Paradox)
Es gibt andere bewohnte Planeten. ja Diese Aussage ist entweder wahr oder falsch, auch wenn wir dieses möglicherweise nie entscheiden können.
Esst mehr Obst! nein Hat keinen Wahrheitswert im Sinne einer Bestätigung, auch wenn der Satz eine gewisse Wahrheit enthält...
Wir sind zu Ihnen gekommen, um Ihnen mitzuteilen, dass heute Ihre Ausreise ja Dieser historische Satz ist zwar grammatisch unvollständig, seine Aussagekraft war aber dennoch eindeutig.

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 (s.u.).

2.0.2. 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

2.0.3. Verknüpfungen zwischen Aussagen lassen sich auch durch Wahrheitstabellen beschreiben. Je Zeile werden für eine Kombination der Wahrheitswerte der Variablen (hier a, b) die Wahrheitswerte (f = falsch, w = wahr) der beschriebenen Aussagenverknüpfungen dargestellt.
a b a ∨ b a ∧ b a → b
f f f f w
f w w f w
w f w f f
w w w w w

2.0.4. Die Anzahl der zweistelligen Aussagenfunktionen (also Verknüpfungen auf zwei Aussagen) beträgt 16.
Begründung: Jede Funktion lässt sich durch eine Spalte in der Wahrheitstabelle beschreiben. Bei zwei Variablen hat sie 4 Zeilen, die sich auf 24 = 16 verschiedene Arten füllen lassen.

2.0.5. Die Anzahl der einstelligen Aussagenfunktionen (also Funktionen von einer Aussage) beträgt 4.
Übungsaufgabe: Belege diese Aussage (sic) mit einer vollständigen Wahrheitstafel.

2.0.6. Die Beschreibung der Verknüpfung von Aussagen unter Verwendung von Aussagenvariablen heißt Aussagenausdruck oder Aussagenform,
z.B. A ∧ B bei nicht näher spezifizierten A und B, die als Platzhalter für irgendwelche Aussagen stehen.

2.0.7. Aussagenverknüpfungen lassen sich durch andere Aussagenverknüpfungen ausdrücken, z.B. ist
A → B = ¬A ∨ B

Eine Teilmenge der Aussagenverknüpfungen, mit denen sich alle Aussagenverknüpfungen ausdrücken lassen, wird auch „Junktorbasis“ genannt.
∧ , ∨ , ¬ ist die gebräuchlichste Junktorbasis (in dem Sinne, dass in der Schaltalgebra fast nur diese drei Verknüpfungen eingesetzt werden).
↑ alleine ist ebenfalls eine Junktorbasis.

2.0.9. Über Verknüpfungen von Aussagen lassen sich Gesetzmäßigkeiten aufstellen, mit deren Hilfe sich Aussageausdrücke in andere Aussagenausdrücke (andere „Formen“) der gleichen Aussage umformen lassen. Insbesondere lassen sich Aussagenausdrücke auf diesem Wege vereinfachen bzw. in eine gewünschte Form bringen.

2.0.10. Eine Konjunktion, in der alle betrachteten Variablen einfach oder negiert vorkommen, beschreibt genau eine Kombinationsmöglichkeit dieser Variablen, den Wahrheitswert wahr zu ergeben. Die durch diese Verknüpfung entstandene Aussage hat in genau einer Zeile der Wertetafel den Wert w.
Ein solcher Aussagenausdruck wird Minterm genannt.
Bei 2 Variablen gibt es 4 verschiedene Minterme:
a b ¬a ∧ ¬b ¬a ∧ b a ∧ ¬b a ∧ b
f f w f f f
f w f w f f
w f f f w f
w w f f f w

2.1. Boolesche Algebra

2.1.0. Wir werden gleich den Begriff Boolesche Algebra anhand gewisser Kriterien definieren. Die Vorgehensweise ist in der Mathematik üblich, um Strukturen zu benennen und mit ihren Gesetzmäßigkeiten umgehen zu können. Aus der Schule sind in ähnlicher Weise Strukturen wie Gruppe, Ring, Körper oder Vektorraum bekannt (oder auch nicht). Eine Analogie aus der Gesetzgebung erläutert auch die Bedeutung des nächsten Abschnitts: Es gibt eine gesetzliche Definition des Begriffs „GmbH“ – sie muss einen eingetragenen Geschäftsführer haben, über ein bestimmtes Mindestkapital verfügen etc. Manche Wirtschaftsunternehmen sind GmbHs, weil sie den Kriterien (unten „Axiome“ genannt) entsprechen, andere nicht. Wenn eine Gesellschaft eine GmbH ist, folgen daraus gewisse weitere Regeln, z.B. die Pflicht zur regelmäßigen Buchführung (und natürlich zum Steuerzahlen).

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

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

2.1.2. Im Axiomensystem der Booleschen Algebra besteht das Dualitätsprinzip: Durch Vertauschen der beiden Operationen ∧ und ∨ sowie der beiden neutralen Elemente 1 und 0 gegeneinander erhält man wieder das selbe Axiomensystem (die selbe Menge von Grundregeln). 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.

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

(B5) Eindeutigkeit von 0 und 1: die neutralen Elemente sind als Elemente von B eindeutig bestimmt.
Beweis: Nehmen wir an, es gebe ein weiteres Element 0~ ∈ B, das ebenfalls neutrales Element bezüglich der Operation ∨ sei. Dann gilt also für alle x ∈ B: x ∨ 0~ = x. Also gilt das auch für x = 0, nämlich 0 ∨ 0~ = 0.
Somit ist 0= 0 ∨ 0~
(Kommutativgesetz)= 0~ ∨ 0
(0 ist neutrales Element)= 0~
Das heißt: wenn wir annehmen, es gebe eine weitere Null in B, so können wir nachweisen, es ist die selbe, die wir schon haben.
Es gibt nur eine Null. (Es kann nur eine geben.)
Übungsaufgabe: Es gibt nur eine Eins.
(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 x, y ∈ B gilt
x ∨ (x ∧ y) = x
x ∧ (x ∨ y) = x
(B11) Gesetze von De Morgan: für alle x, y ∈ B gilt
(x ∨ y)' = x' ∧ y'
(x ∧ y)' = x' ∨ y'
(B12) Assoziativgesetze: für alle x, y, z ∈ B gilt
(x ∨ y) ∨ z = x ∨ (y ∨ z)
(x ∧ y) ∧ z = x ∧ (y ∧ z)

2.2. Aussagenalgebra

 Sei A die Menge aller Aussagen.

(A, ∧, ∨) ist eine Boolesche Algebra.
Beweis: Die vier Axiome der Booleschen Algebra gelten in der Aussagenlogik; im Einzelnen:
(B1) Kommutativgesetze: gelten ✓
(B2) Distributivgesetze: gelten ✓
(B3) Existenz neutraler Elemente: gilt mit den Entsprechungen
0 = F (die Kontradiktion ist neutral bzgl. der Disjunktion),
1 = T (die Tautologie ist neutral bzgl. der Konjunktion)
(B4) Existenz komplementärer Elemente: gilt mit der Entsprechung x' = ¬ x

2.3. Mengenalgebra

2.3.0. Begriffe

Sei M eine Menge.
Dann ist die Potenzmenge ℘(M) die Menge aller Teilmengen von M,
also A ∈ ℘(M) genau dann wenn A ⊆ M.

Beispiel: Mit M = {1, 2, 3} ist
℘(M) = {{}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}.
Wenn M n Elemente hat, hat ℘(M) 2n Elemente.

2.3.1.

Sei M eine Menge.

(℘(M), ∩, ∪) ist eine Boolesche Algebra.
Beweis: Die vier Axiome der Booleschen Algebra gelten für die Mengenoperationen; im Einzelnen:
(B1) Kommutativgesetze: A ∩ B = {x ∈ M : x ∈ A ∧ x ∈ B}
= {x ∈ M : x ∈ B ∧ x ∈ A} nach dem Kommutativgesetz der Aussagenalgebra
= B ∩ A
Entsprechend gilt A ∪ B = B ∪ A
(B2) Distributivgesetze: gelten entsprechend
(B3) Existenz neutraler Elemente: gilt mit den Entsprechungen
0 = {} (die leere Menge ist neutral bzgl. der Mengenvereinigung),
1 = M (die gesamte Grundmenge M ist neutral bzgl. des Mengendurchschnitts von Teilmengen von M)
(B4) Existenz komplementärer Elemente: gilt mit der Entsprechung A' = A
Damit gelten auch alle abgeleiteten Gesetze (B5 etc) der Booleschen Algebra in der Mengenalgebra.

2.3.2. Mengendiagramme

Mit Mengendiagrammen lassen sich die Verhältnisse bestimmter Teilmengen einer Grundmenge (also von speziellen Elementen einer Mengenalgebra) grafisch darstellen.

Mit sogenannten Venn-Diagrammen lassen sich die Verhältnisse beliebiger Teilmengen einer Grundmenge allgemeingültig grafisch darstellen. Dazu muss das Diagramm alle Überschneidungsmöglichkeiten der betrachteten Teilmengen enthalten; bei n Teilmengen sind also 2n Bereiche dargestellt, entsprechend den 2n Zeilen einer Wertetafel für n Variablen der Aussagenlogik.

Effektiv lassen sich somit mit Venn-Diagramm Gesetze der Booleschen Algebra veranschaulichen.

2.4. Schaltalgebra

2.4.0. Digitale Schaltungen

Aussagenlogische bzw. Boolesche Verknüpfungen lassen sich elektrotechnisch realisieren. Dazu werden Schaltungen eingesetzt, deren Eingänge und Ausgänge jeweils einen von 2 Werten annehmen können, meist 0 bzw. 1 genannt. Auf diesen beiden Werten sind folgende Verknüpfungen definiert:
A B A · B A + B A
00 001
01 011
10 010
11 110
Da es sich offensichtlich um die bekannten logischen Verknüpfungen UND, ODER, NICHT handelt – nur in anderer Notation – ist
({0, 1}, ·, +) per Konstruktion eine Boolesche Algebra.

Ein Schaltausdruck ist eine bestimmte Form, eine Schaltfunktion durch Verknüpfungen auf den Variablen zu realisieren. Wie in jeder Booleschen Algebra lassen sich Schaltausdrücke, die dieselbe Schaltfunktionen realisieren (implementieren, beschreiben, darstellen, ausdrücken), mit Hilfe der Booleschen Gesetze ineinander umformen.
Ist das Ergebnis der Umformung einfacher, sprechen wir auch von der Vereinfachung eines Schaltausdrucks (bzw. der Schaltfunktion). Was dabei als einfacher angesehen wird, hängt allerdings von externen Kriterien ab (s.u.).

Die Realisierung einer Schaltfunktion, genauer eines Schaltausdrucks, als digitale Schaltung wird grafisch in einem Schaltdiagramm dargestellt, in dem Schaltsymbole für die gebräuchlichen Verknüpfungen (und weitere Schaltelemente) sowie Leitungsverbindungen, Ein- und Ausgänge etc. symbolisiert werden.

Für die wichtigsten Booleschen Verknüpfungen gibt es jeweils grafische Symbole, und zwar in drei verschiedenen Notationen:

Die Tabelle der 16 zweistelligen Booleschen Funktionen stellt diese in den verschiedenen Notationen dar.

2.5. Vereinfachung von Schaltfunktionen

Die Umformung von Schaltausdrücken mit dem Ziel, möglichst einfache Schaltungen zu erreichen (welches im Folgenden noch definiert werden muss), führen wir am Beispiel einer Schaltung ein, die folgenden Schaltausdruck hat:

¬ (¬ (ac ∧ bc) ∧ ac)
...
ac + ac ∧ bc
= ac + b + c
...

Es gibt auch systematische Verfahren zur Vereinfachung von Schaltfunktionen. Dabei hilft die Tatsache, dass sich jede Schaltfunktion als Disjunktion von Mintermen darstellen lässt, die sogenannte Disjunktive Normalform.