XOR, NAND, NOR

Mit UND, ODER und NICHT aus Lektion 7 kannst du theoretisch jede logische Funktion bauen. In der Praxis arbeiten Hardware-Entwickler und Programmierer*innen aber mit drei weiteren wichtigen Operatoren, die häufig auftauchen: XOR, NAND und NOR. Sie sind nicht „neue" Operationen – sie sind Kombinationen der drei Grundoperatoren. Aber sie sind so nützlich und kompakt, dass sie eigene Symbole bekommen.

Außerdem behandeln wir in dieser Lektion die wichtigste Umformungs-Regel der Booleschen Algebra: die DeMorganschen Gesetze. Sie verbinden UND und ODER über die Negation und sind das, was du in einer Klausur am ehesten zur Umformung logischer Ausdrücke brauchst.

1) XOR – das exklusive Oder

Im Alltagsdeutsch ist „oder" zweideutig: „Möchten Sie Kaffee oder Tee?" meint meist genau einen der beiden (exklusiv), nicht beides. Das Boolesche ODER aus Lektion 7 ist aber das inklusive ODER – beide ist auch okay. Für das exklusive Oder braucht es einen eigenen Operator: XOR (eXclusive OR).

XOR liefert 1, wenn die beiden Eingänge unterschiedlich sind – einer 1 und der andere 0. Bei gleichen Eingängen (beide 0 oder beide 1) ist das Ergebnis 0. Anders gesagt: XOR ist ein „Unterschieds-Detektor". Sehr nützlich, weil dieses Verhalten in Kryptografie, Fehlererkennung und vielen Algorithmen vorkommt.

2) NAND und NOR – die Negationen von UND und ODER

NAND ist die Kurzform von „NOT AND" – also UND, gefolgt von NICHT. Es liefert das Gegenteil von UND: 0 wenn beide Eingänge 1 sind, sonst 1. Genauso ist NOR die Kurzform von „NOT OR": Gegenteil von ODER, liefert nur dann 1, wenn beide Eingänge 0 sind.

Klingt nach trivialer Doppel-Operation? Ist es konzeptionell auch. Aber: in echter Hardware ist NAND oft das einfachste Gatter zu bauen. Und – wie wir gleich sehen – NAND alleine ist vollständig: man kann aus reinen NAND-Gattern jede beliebige logische Schaltung zusammenbauen. Das macht NAND zum Star der Chip-Fertigung.

3) Notation und Symbole

Die mathematischen Symbole und Code-Operatoren für die erweiterten Operationen variieren je nach Kontext. Hier die wichtigsten Schreibweisen:

• XOR: mathematisch ⊕ oder A ⊻ B. In Java/C: ^ als bitweise XOR-Operator. In SQL kennt das selten – meist nimmt man (A OR B) AND NOT (A AND B) oder A != B.
• NAND: selten in Code zu finden – meist explizit als NOT(A AND B) oder !(A && B) oder ~(A & B) geschrieben.
• NOR: ebenso meist explizit: NOT(A OR B), !(A || B), ~(A | B).
• XNOR: auch „Äquivalenz" oder „Gleichheit" genannt. A ↔ B mathematisch, oder einfach A == B im Code.

In der digitalen Schaltungstechnik sieht man oft eine Mischung: ein NAND-Gatter wird als A · B mit Querstrich darüber geschrieben, ein NOR als A + B mit Querstrich. Der Querstrich ist die Negation – wie in Lektion 7 beschrieben.

4) Die DeMorganschen Gesetze

Jetzt zum vielleicht wichtigsten Umformungs-Werkzeug der gesamten Booleschen Algebra. Die zwei DeMorganschen Gesetze beschreiben, wie sich ein NICHT durch eine UND/ODER-Verknüpfung „durcharbeitet". Sie sind regelmäßiger Klausurstoff:

5) DeMorgan in der Praxis

Wofür braucht man die DeMorgan-Gesetze konkret? Drei typische Anwendungen:

Vereinfachung in Code: die Bedingung !(a > 0 && b > 0) ist nicht intuitiv. Mit DeMorgan wird daraus a <= 0 || b <= 0 – viel besser lesbar. Beim Negieren einer Bedingung mit Vergleichen muss man dran denken: ≥ wird zu <, == wird zu !=, && wird zu ||.

Hardware-Optimierung: wie schon erwähnt – NAND-Gatter sind in der Chip-Fertigung besonders effizient. Eine Schaltung, die ursprünglich als UND-ODER-Logik entworfen wurde, lässt sich mit DeMorgan in eine reine NAND-Schaltung umwandeln. Das spart Chip-Fläche und damit Geld.

Boolesche Vereinfachung: in der Logik-Optimierung (Karnaugh-Diagramme, Quine-McCluskey-Verfahren) sind DeMorgan-Umformungen ein Standard-Werkzeug, um Ausdrücke in eine kompaktere Form zu bringen.

6) NAND ist universell

Eine bemerkenswerte Eigenschaft von NAND: aus reinen NAND-Gattern kann man jede beliebige Boolesche Funktion bauen. Man nennt NAND deshalb funktional vollständig. Dasselbe gilt für NOR – auch damit lässt sich alles bauen. Diese Eigenschaft ist der Grund, warum CPUs auf der untersten Ebene oft hauptsächlich aus NAND- oder NOR-Schaltungen bestehen.

Wie geht das? Schauen wir uns die drei Grundoperatoren UND/ODER/NICHT an und konstruieren sie aus reinen NANDs:

7) Anwendungen von XOR

XOR ist nicht nur Wahrheitstabellen-Theorie – es ist in der echten Informatik überall. Ein paar besonders prägnante Beispiele:

8) Häufige Stolperfallen

Drei Patterns, die in IHK-Klausuren regelmäßig Punkte kosten – und die du sicher beherrschen solltest:

• DeMorgan halbherzig anwenden: beim Negieren von (A AND B) wird zu (NOT A OR NOT B) – beide Operanden negieren und den Operator wechseln. Häufiger Fehler: nur den Operator wechseln, oder nur einen Operanden negieren.
• XOR mit OR verwechseln: Im Alltagsdeutsch sagt man „A oder B" oft exklusiv, aber das Boolesche OR ist inklusiv (auch beide ist okay). XOR ist die korrekte Wahl, wenn „entweder ... oder" gemeint ist.
• NAND/NOR mit AND/OR verwechseln: die Wahrheitstabellen sind genau invertiert. Bei zwei 1en liefert AND eine 1, NAND aber eine 0. Wer in der Schaltung den kleinen Negations-Kreis übersieht, hat das falsche Verhalten.

Zusammenfassung

Aus den drei Grundoperationen UND, ODER, NICHT lassen sich drei häufig genutzte Kombinationen ableiten: XOR (exklusives Oder) – liefert 1 bei unterschiedlichen Eingängen, 0 bei gleichen. Wird als „Unterschieds-Detektor" oder „Toggle" verwendet, Code-Operator ^. NAND (Not AND) – Negation von AND, liefert 0 nur wenn beide 1 sind. NOR (Not OR) – Negation von OR, liefert 1 nur wenn beide 0 sind. Bonus: XNOR – Negation von XOR, „Gleichheits-Detektor". Wichtigste Umformungsregel: DeMorgansche Gesetze: ¬(A ∧ B) = ¬A ∨ ¬B und ¬(A ∨ B) = ¬A ∧ ¬B. NICHT geht durch die Klammer, dabei wechselt UND ↔ ODER. Hilft beim Vereinfachen von Bedingungen im Code und in der Hardware-Optimierung. Wichtige Eigenschaft: NAND und NOR sind funktional vollständig – jede beliebige Boolesche Funktion lässt sich aus nur NAND-Gattern (oder nur NOR-Gattern) bauen. Das macht beide zu den Stars der Chip-Fertigung. XOR-Killer-Anwendungen: Paritäts-Bit, einfache Verschlüsselung, Bit-Toggle, RAID-5-Parität – alle nutzen die selbstinverse Eigenschaft (A XOR B XOR B = A). In der nächsten Lektion sehen wir alle diese Operatoren in der Praxis: Bitmasken in der IT.