Boolesche Logik und Schaltkreise

Einführung

1854 veröffentlichte der britische Mathematiker George Boole ein Werk mit dem sperrigen Titel „An Investigation of the Laws of Thought”. Darin zeigte er: Logik — das Schlussfolgern nach Regeln — lässt sich wie Algebra behandeln. Statt Zahlen gibt es nur zwei Werte: wahr und falsch.

Fast hundert Jahre später erkannte der Ingenieur Claude Shannon, dass sich Booles Algebra direkt in elektrische Schaltkreise übersetzen lässt. Strom an = wahr, Strom aus = falsch. Damit war der Weg frei für moderne Computer. Jede Berechnung, die dein Prozessor je durchgeführt hat, basiert letztlich auf boolescher Logik.

Grundidee

Stell dir drei Schalter vor: Du kommst durch eine Tür, wenn Schalter A und Schalter B beide gedrückt sind. Oder du kommst durch, wenn Schalter A oder Schalter B gedrückt ist. Oder die Tür öffnet, wenn Schalter A nicht gedrückt ist.

Das sind die drei Grundoperationen: AND, OR, NOT. Aus diesen drei Bausteinen lässt sich jede beliebige logische Funktion und letztlich jede Berechnung aufbauen.

Erklärung

Die drei Grundoperationen

AND (Und-Verknüpfung): Das Ergebnis ist nur dann wahr, wenn beide Eingaben wahr sind.

A	B	A AND B
0	0	0
0	1	0
1	0	0
1	1	1

OR (Oder-Verknüpfung): Das Ergebnis ist wahr, wenn mindestens eine Eingabe wahr ist.

A	B	A OR B
0	0	0
0	1	1
1	0	1
1	1	1

NOT (Nicht-Verknüpfung): Das Ergebnis ist das Gegenteil der Eingabe.

A	NOT A
0	1
1	0

Erweiterte Gatter

XOR (Exklusives Oder): Wahr, wenn genau eine der Eingaben wahr ist — nicht beide.

A	B	A XOR B
0	0	0
0	1	1
1	0	1
1	1	0

XOR ist besonders nützlich für Additionsschaltungen, weil 1+1 im Binärsystem 10 (also 0 mit Übertrag 1) ergibt — genau wie XOR: 1 XOR 1 = 0.

NAND (Not-And): Das Gegenteil von AND. Wahr, außer wenn beide Eingaben wahr sind.

NOR (Not-Or): Das Gegenteil von OR. Nur wahr, wenn beide Eingaben falsch sind.

NAND und NOR sind in der Praxis besonders wichtig, weil sie funktional vollständig sind: Man kann aus NAND allein (oder aus NOR allein) jeden anderen Gattertyp nachbauen. Viele Chips arbeiten deshalb ausschließlich mit NAND-Gattern.

Von Transistoren zu Gattern

Ein Logikgatter ist eine physische Schaltung aus Transistoren. Ein AND-Gatter benötigt zwei Transistoren in Serie — beide müssen leiten, damit Strom fließt. Ein OR-Gatter verbindet zwei Transistoren parallel — einer reicht.

Moderne Prozessoren enthalten Milliarden von Transistoren auf einer Fläche kleiner als ein Fingernagel. Jede dieser Milliarden von Schaltstellen führt boolesche Logik aus.

Einfache Schaltung: Halbaddierer

Ein Halbaddierer addiert zwei einzelne Bits. Er besteht aus einem XOR-Gatter (für die Summe) und einem AND-Gatter (für den Übertrag):

• Summe = A XOR B
• Übertrag = A AND B

Beispiel: 1 + 1 = Summe 0, Übertrag 1 — also binär 10, was dezimal 2 entspricht. Korrekt.

Durch Kombination mehrerer Halbaddierer (und Volladdierer, die auch den Übertrag aus der vorherigen Stelle berücksichtigen) kann man beliebig große Zahlen addieren.

De Morgan’sche Gesetze

Zwei wichtige Umformungsregeln, benannt nach dem Mathematiker Augustus De Morgan:

1. NOT (A AND B) = (NOT A) OR (NOT B)
2. NOT (A OR B) = (NOT A) AND (NOT B)

Auf Deutsch: Das Negieren einer Und-Verknüpfung ist dasselbe wie das Oder-Verknüpfen der negierten Werte — und umgekehrt. Diese Regeln sind in der Schaltkreisoptimierung und beim Programmieren sehr hilfreich, um Bedingungen umzuformulieren.

Beispiel aus dem Alltag

if-Bedingungen im Code:

Jede if-Bedingung in einem Programm ist boolesche Logik:

if alter >= 18 AND hatFuehrerschein:
    print("Darf Auto fahren")

if istKrank OR hatUrlaub:
    print("Kommt nicht zur Arbeit")

if NOT istGesperrt:
    print("Zugang erlaubt")

Suchmaschinen:

Wenn du in einer Suchmaschine Klimawandel AND Lösung eingibst, werden nur Seiten gefunden, die beide Begriffe enthalten. Mit Klimawandel OR Erderwärmung findest du Seiten mit einem der beiden Begriffe. Mit Klimawandel NOT Verschwörung schließt du Seiten aus, die das zweite Wort enthalten.

Zugangskontrollen:

Eine Tür öffnet, wenn (Karte gültig AND PIN korrekt) oder wenn Notschlüssel gesteckt. Das ist boolesche Logik in Hardware.

Anwendung

Erstelle die vollständige Wahrheitstabelle für den folgenden Ausdruck:

(A AND B) OR (NOT A AND C)

Fülle alle 8 möglichen Kombinationen (A, B, C je 0 oder 1) aus und berechne das Ergebnis.

Überlege anschließend: Was bedeutet dieser Ausdruck in Worten? In welcher Alltagssituation könnte er vorkommen?

Zusatzaufgabe: Vereinfache den Ausdruck NOT (NOT A OR NOT B) mithilfe der De Morgan’schen Gesetze.

Typische Fehler

OR mit XOR verwechseln: OR ist auch wahr, wenn beide Eingaben wahr sind. XOR ist nur dann wahr, wenn genau eine Eingabe wahr ist. Im Alltag sagen wir oft „entweder/oder” und meinen XOR — in der Logik ist OR der häufigere Operator.

NOT falsch binden: NOT A AND B wird als (NOT A) AND B ausgewertet, nicht als NOT (A AND B). Die De Morgan’schen Gesetze zeigen, dass diese beiden Ausdrücke verschieden sind.

Wahrheitstabellen unvollständig aufstellen: Bei n Eingaben gibt es 2^n Kombinationen. Bei 2 Variablen sind es 4 Zeilen, bei 3 Variablen 8, bei 4 bereits 16. Alle müssen ausgefüllt werden.

Logik und Sprache verwechseln: Im Deutschen bedeutet „oder” oft „entweder/oder” (XOR). In der Logik ist OR inklusiv — beide können wahr sein. Das ist ein häufiges Missverständnis.

Zusammenfassung

• Boolesche Logik arbeitet nur mit zwei Werten: wahr (1) und falsch (0)
• Die drei Grundoperationen sind AND (beide wahr → wahr), OR (mindestens eine wahr → wahr) und NOT (Umkehrung)
• XOR ist nur wahr, wenn genau eine Eingabe wahr ist; NAND und NOR sind funktional vollständig
• Logikgatter setzen diese Operationen physisch aus Transistoren um; moderne Prozessoren enthalten Milliarden davon
• Halbaddierer aus XOR und AND zeigen, wie aus einfacher Logik echte Rechenoperationen entstehen
• De Morgan’sche Gesetze erlauben es, AND und OR ineinander umzuformen

Quiz

Frage 1: Was ist der Unterschied zwischen OR und XOR?

Frage 2: Warum sind NAND-Gatter besonders wichtig?

Frage 3: Wie lautet das De Morgan’sche Gesetz für NOT (A OR B)?

Frage 4: Ein Halbaddierer berechnet 1 + 1. Was sind Summe und Übertrag?