Boolesche Funktionen

Aussagenlogik

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.

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

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

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

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.

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

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.

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.

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

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

Boolesche Algebra

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

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

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.

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)

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 ✓ (s. Wertetafel in der Aussagenlogik)
(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

Mengenalgebra

Begriffe aus der Mengenlehre

Betrachte eine Menge M. (Oder wie die Mathematiker sagen: Sei M eine Menge.)
Eine Menge enthält Elemente, z.B. a, diese sind in ihr enthalten: a∈M. Elemente kommen in einer Menge nicht mehrfach vor.

Eine Menge A heißt Teilmenge von M, geschrieben A ⊆ M, wenn alle Elemente aus A auch Elemente von M sind, d.h. a∈A ⇒ a∈M.

Die Potenzmenge ℘(M) ist 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.

Auf ℘(M) sind folgende Operationen definiert:
  • Schnittmenge von A und B: die Menge aller Elemente von M, die sowohl in A als auch in B enthalten sind.
    A ∩ B = {x ∈ M : x ∈ A ∧ x ∈ B} für alle A, B ⊆ M.
    (sprich: A geschnitten (mit) B ist die Menge aller x aus M für die gilt: x ist in A und x ist in B)
  • Vereinigungsmenge von A und B: die Menge aller Elemente von M, die in A oder in B enthalten sind.
    A ∪ B = {x ∈ M : x ∈ A ∨ x ∈ B} für alle A, B ⊆ M.
  • Mengenkomplement B ohne A: die Menge aller Elemente von B, die nicht in A enthalten sind.
    B \ A = {x ∈ B : ¬ (x ∈ A)} für alle A, B ⊆ M.
    Interessant ist insbesondere das Mengenkomplement bezüglich der Grundmenge, M \ A, auch A geschrieben.

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.

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.

Schaltalgebra

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 Bit ist ein Element aus {0, 1} oder eine Variable, die einen solchen Wert annehmen kann.

Eine Funktion in der Schaltalgebra heißt auch Schaltfunktion. 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 Schaltfunktion realisieren (beschreiben / darstellen / ausdrücken / implementieren), mit Hilfe der Booleschen Gesetze ineinander umformen.
Ist das Ergebnis der Umformung einfacher, sprechen wir auch von der Vereinfachung eines Schaltausdrucks (als Implementierung einer Schaltfunktion). Was dabei als einfacher angesehen wird, hängt allerdings von externen Kriterien ab (s.u.).

Konventionen in der Notation von Schaltausdrücken:

Beachte, dass diese Konventionen der kürzeren Schreibweise dienen, jedoch auch Verwirrung stiften können, denn im Gegensatz zur Arithmetik sind in der Booleschen Algebra die Verknüpfungen · und + hinsichtlich ihrer Eigenschaften vollkommen symmetrisch.

Gatter

ist der Name für die elektronische Realisierung einer elementaren Verknüpfung. Im folgenden Abschnitt sind u.a. die typischen Gatter für NAND, NOR, NOT („Inverter“), AND, OR, XOR dargestellt.

Die Realisierung einer Schaltfunktion, genauer eines Schaltausdrucks, als digitale Schaltung wird grafisch in einem Schaltdiagramm dargestellt, in dem die gebräuchlichen Verknüpfungen durch Schaltsymbole dargestellt 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.

Konventionen in der Notation von Schaltdiagrammen:

Äquivalente Schaltungen

Schaltungen, die nach den Regeln der Schaltalgebra (also der Booleschen Algebra) ineinander umgeformt werden können, sind funktional äquivalent.

Distributivgesetze:
…
De Morgan:
…
(Beachte aber, dass nicht-Boolesche Eigenschaften der Schaltungen ggf. signifikant verschieden sein können.)

Disjunktive Normalform

Betrachte Schaltfunktionen von n Variablen, z.B. A, B, C. Eine Konjunktion, in der alle Variablen vorkommen, entweder direkt oder negiert, heißt Minterm. Die Schaltfunktion eines Minterms hat in der Wertetafel genau eine 1.

Jede Schaltfunktion lässt sich als Disjunktion von Mintermen ausdrücken, die (kanonische) Disjunktive Normalform DNF.

Schaltverzögerung

Wenn sich Eingangswerte einer Schaltung ändern, ändern sich die Ausgangswerte gemäß der Schaltfunktion. Dies passiert nicht (mathematisch) sofort, sondern (physikalisch) nach einer Signallaufzeit (engl. „delay“), die von der Anzahl der Gatter abhängt, die maximal zwischen Eingängen und Ausgängen liegen, die Stufigkeit der Schaltung. Zur Abschätzung werden bei Einsatz der üblichen Technologien NAND/NOR/AND/OR als eine Stufe gezählt, Negationen werden ignoriert.

Mehrstellige Schaltalgebra

Betrachte die Menge aller Folgen von n Bits: Bn = {0, 1}n.
Z.B. {0, 1}3 = {000, 001, 010, 011, 100, 101, 110, 111}.

Für a, b ∈ Bn seinen Verknüpfungen der Schaltalgebra stellenweise definiert, z.B. 011 · 101 = 001 (jede Stelle wird für sich betrachtet und jeweils verknüpft).

(Bn, ·, +) ist eine Boolesche Algebra.

Beweis: durch stellenweises Nachvollziehen der Axiome.

Ein Wort ist ein Element aus Bn oder eine Variable, die einen solchen Wert annehmen kann. (Bei n=8 reden wir von einem Byte.)
Ein Register (der Länge n) ist eine digitale Schaltung, die ein Wort (aus Bn) aufnehmen / speichern kann.

Umformung von Schaltfunktionen

Übersicht:

Zwischen den Ausdrucksmöglichkeiten einer Schaltfunktion bieten sich folgende Umformungswege an:
Schaltung → Schaltausdruck
↘ ↓ ↘
Wertetafel ↔ DNF → minimaler Ausdruck
↘ ↓ ↓
KV-Diagramm → einfache Schaltung

Algebraische Vereinfachung

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
... Vorgehensweise im Beispiel:

In diesem Beispiel wird aus einer 3-stufigen Schaltung durch die Vereinfachung eine schnellere Schaltung gemacht.

Systematische Vereinfachung

Die Verfahren nach Karnaugh/Veitch bzw. nach Quine/McCluskey basieren auf der Darstellung der Schaltfunktion als Disjunktive Normalform.

Die Minterme werden in ein Schema eingetragen, das die systematische Aufspürung von Zusammenfassungen ermöglicht. Durch Zusammenfassung „benachbarter Minterme“ wird aus ihnen nach dem Distributivgesetz, Extraktion des gemeinsamen Teilterms und Eliminierung der unterschiedlichen Variablen ein jeweils einfacherer Teilausdruck.

Vereinfachung nach Karnaugh/Veitch

Die Menge der Minterme für n Variablen ist eine Mengenalgebra, die der n-stelligen Schaltalgebra entspricht. Aus dem Venn-Diagramm wird durch passende Anordnung das KV-Diagramm mit den Eigenschaften

…

Beispiel

a b c f
000 1
001 0
010 0
011 0
100 1
101 0
110 1
111 1

Optimierung von Schaltfunktionen: Kriterien

Welcher Schaltausdruck einer Schaltfunktion für einen bestimmten Zweck einfacher bzw. geeigneter ist, hängt von verschiedenen Kriterien ab, z.B.

Minimierung von Schaltfunktionen: Verfahren und ihre Eigenschaften