Boolesche Logik
Wahr und falsch, 1 und 0 – mit nur drei Operationen lässt sich jede Funktion von Bits beschreiben, und mit einer einzigen Sorte Gatter jede bauen. Wie aus einer Wahrheitstabelle eine Schaltung wird, und was das mit if-Bedingungen in Java zu tun hat.
Boolesche Logik, benannt nach George Boole (1854), rechnet mit nur zwei Werten: 0 und 1, falsch und wahr. Die Grundoperationen sind UND, ODER und NICHT. Jede Funktion, die aus einigen Bits ein Bit macht, lässt sich vollständig durch eine Wahrheitstabelle beschreiben – und aus jeder Wahrheitstabelle lässt sich mechanisch eine Formel aus UND, ODER und NICHT bauen.
In Hardware wird jede Operation zu einem Gatter aus wenigen Transistoren. Bemerkenswert: Eine einzige Gattersorte, NAND (nicht-und), genügt, um alle anderen nachzubauen – und damit jeden Rechner. Für Entwickler ist dieselbe Logik Alltag: Jede if-Bedingung ist eine boolesche Formel, und die Gesetze von De Morgan helfen beim Umformen.
Sechs Grundoperationen
a && b| 00 | 0 |
| 01 | 0 |
| 10 | 0 |
| 11 | 1 |
a || b| 00 | 0 |
| 01 | 1 |
| 10 | 1 |
| 11 | 1 |
!a| 0 | 1 |
| 1 | 0 |
a ^ b| 00 | 0 |
| 01 | 1 |
| 10 | 1 |
| 11 | 0 |
!(a && b)| 00 | 1 |
| 01 | 1 |
| 10 | 1 |
| 11 | 0 |
!(a || b)| 00 | 1 |
| 01 | 0 |
| 10 | 0 |
| 11 | 0 |
Mit zwei Eingängen gibt es genau 16 mögliche Funktionen (jede der vier Zeilen kann 0 oder 1 liefern, also 2⁴). Mit n Eingängen sind es 22n – bei drei Eingängen schon 256, bei vier 65 536. Trotzdem lassen sie sich alle aus denselben Bausteinen zusammensetzen.
Die wichtigsten Gesetze
| Gesetz | Formel | In Java |
|---|---|---|
| De Morgan | ¬(a ∧ b) = ¬a ∨ ¬b | !(a && b) == (!a || !b) |
| De Morgan | ¬(a ∨ b) = ¬a ∧ ¬b | !(a || b) == (!a && !b) |
| Distributiv | a ∧ (b ∨ c) = (a ∧ b) ∨ (a ∧ c) | funktioniert auch umgekehrt: a ∨ (b ∧ c) = (a ∨ b) ∧ (a ∨ c) |
| Absorption | a ∨ (a ∧ b) = a | überflüssige Teilbedingungen erkennen |
| Doppelte Negation | ¬¬a = a | !!a == a |
| Komplement | a ∧ ¬a = 0, a ∨ ¬a = 1 | Bedingungen, die nie oder immer gelten |
Von der Tabelle zur Formel
Jede Wahrheitstabelle lässt sich in eine Formel übersetzen, und zwar immer auf dieselbe Weise: Für jede Zeile mit Ergebnis 1 schreibt man ein UND der Eingänge (negiert, wo der Eingang 0 ist) – einen Minterm. Alle Minterme verbindet man mit ODER. Das Ergebnis heißt disjunktive Normalform. Klick die Ausgänge an oder wähle eine Vorlage:
Damit ist bewiesen: UND, ODER und NICHT reichen für jede boolesche Funktion. Die Normalform ist aber selten die kürzeste. Die Mehrheitsfunktion etwa lässt sich auch als (a && b) || (a && c) || (b && c) schreiben – drei UND-Gatter statt vier. Für wenige Eingänge findet man solche Vereinfachungen von Hand mit Karnaugh-Diagrammen; im Allgemeinen ist das Finden der kleinsten Schaltung ein sehr schweres Problem, das Chip-Entwurfswerkzeuge mit Heuristiken angehen.
Ein Gatter für alles
Es geht noch sparsamer. NICHT ist ein NAND, dessen beide Eingänge verbunden sind. UND ist ein NAND mit einem NICHT dahinter. ODER folgt aus De Morgan: a ∨ b = ¬(¬a ∧ ¬b) – also ein NAND aus zwei negierten Eingängen. Schalte die Eingänge um:
Das hat praktische Gründe. In der heute üblichen CMOS-Technik braucht ein NAND-Gatter vier Transistoren, ein UND dagegen sechs – es ist ein NAND mit nachgeschaltetem Inverter. Chips werden deshalb aus wenigen Standardzellen gebaut, in denen NAND, NOR und Inverter die Hauptrolle spielen. Und weil NAND allein genügt, folgt eine bemerkenswerte Tatsache: Ein ganzer Computer ist im Prinzip nichts als sehr viele, geschickt verbundene NAND-Gatter.
Für Entwickler übersetzt
Bedingungen umzuformen ist Alltag – beim Vereinfachen, beim Umdrehen eines if, beim Herausziehen einer Methode. Ob zwei Bedingungen wirklich gleichwertig sind, entscheidet die Wahrheitstabelle. Gib zwei Ausdrücke mit a, b, c ein:
Einige Java-Besonderheiten:
// && und || werten kurzgeschlossen aus – & und | immer beide Seiten
if (s != null && s.isEmpty()) … // sicher
if (s != null & s.isEmpty()) … // NullPointerException, wenn s null ist
// Auf int angewendet: 32 boolesche Operationen gleichzeitig, Bit für Bit
int rechte = LESEN | SCHREIBEN; // Bits setzen
boolean darf = (rechte & SCHREIBEN) != 0; // Bit prüfen
rechte &= ~SCHREIBEN; // Bit löschen: UND mit NICHT
x ^= y; y ^= x; x ^= y; // Tausch ohne Hilfsvariable – nett, aber unleserlich
// Viele Bits: BitSet bietet and, or, xor, andNot über beliebig lange Bitfolgen
BitSet b = new BitSet(); b.set(3); b.and(andere);Die Bitoperationen auf int sind genau das, was die Hardware tut: Eine ALU führt ein UND auf 64 Bits in einem Schritt aus, mit 64 Gattern nebeneinander. Mehr dazu in H4.
Häufige Irrtümer
!a || !b.& wertet immer beide Seiten aus. Mit Nebenwirkungen oder Null-Prüfungen macht das einen Unterschied.NULL bringt einen dritten Wert „unbekannt“. NULL = NULL ist dort nicht wahr, sondern unbekannt – deshalb braucht man IS NULL.