| Typ | Konzept |
|---|---|
| Quellen | Quelle - Mathematik Zusammenfassung Quelle - Neuronale Netze selbst programmieren |
| Erstellt | 2026-09-26 |
| Aktualisiert | 2026-09-26 |
| Tags | mathematik, logik, digitaltechnik, informatik |
Die Algebra der Wahrheitswerte 0 und 1 mit den Verknüpfungen und, oder, xor und nicht. Als Schaltalgebra beschreibt sie digitale Schaltungen. Mit Wahrheitstabellen, Rechengesetzen und dem Karnaugh-Diagramm lassen sich Ausdrücke prüfen und vereinfachen.
Verknüpfungen
| A | B | A ∧ B (and) | A ∨ B (or) | A xor B |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 | 1 |
| 1 | 0 | 0 | 1 | 1 |
| 1 | 1 | 1 | 1 | 0 |
not: Ā kehrt den Wert um.
Bindungsstärke: 1. not, 2. and, 3. or/xor. Also A ∨ B ∧ C = A ∨ (B ∧ C) (Quelle - Mathematik Zusammenfassung, S. 2).
Wahrheitstabelle
Bei n Eingängen gibt es 2ⁿ Zeilen, bei drei Eingängen also 8. Beispiel aus der Quelle: Y = (Ā ∧ B ∧ C) ∨ (A ∧ C) ist genau bei ABC = 011, 101 und 111 wahr. Nachgerechnet, stimmt.
Rechengesetze
- Kommutativgesetz: A ∧ B = B ∧ A, A ∨ B = B ∨ A
- Assoziativgesetz: (A ∧ B) ∧ C = A ∧ (B ∧ C), ebenso für ∨
- Distributivgesetz: A ∧ (B ∨ C) = (A ∧ B) ∨ (A ∧ C) und A ∨ (B ∧ C) = (A ∨ B) ∧ (A ∨ C). Anders als bei Zahlen gilt es in beide Richtungen.
- De Morgan: ¬(A ∧ B) = Ā ∨ B̄, ebenso ¬(A ∨ B) = Ā ∧ B̄. Der Strich wird aufgeteilt, und ∧ und ∨ tauschen die Rolle.
- Doppelte Verneinung hebt sich auf.
Das Beispiel auf S. 2 formt ¬(¬(A∧B) ∧ C) zu „A ∨ B ∨ C̄“ um. Richtig ist: Der äussere Strich wird nach De Morgan aufgeteilt, ¬¬(A∧B) ∨ C̄, und die doppelte Verneinung hebt sich auf. Das ergibt (A ∧ B) ∨ C̄. Die Quelle hat beim inneren Ausdruck ∧ zusätzlich in ∨ verwandelt. Gegenprobe mit A = 1, B = 0, C = 1: Der Ausgangsausdruck ergibt 0, „A ∨ B ∨ C̄“ ergibt 1.
Karnaugh-Diagramm
Die Wahrheitstabelle wird in ein Gitter übertragen, in dem sich benachbarte Felder nur in einer Variablen unterscheiden. Benachbarte Einsen fasst man in möglichst grossen Blöcken (1, 2, 4, 8 Felder, auch über den Rand hinweg) zusammen. Jeder Block ergibt einen einfachen Term (S. 5):
- drei Variablen: Y = Ā ∨ C̄
- vier Variablen: Z = (A ∧ C̄) ∨ (C̄ ∧ D̄)
Beide Beispiele nachgerechnet (Claude), sie stimmen mit den Tabellen überein.
Die boolesche Algebra verbindet dieses Wiki an mehreren Stellen: Schaltnetze aus and, or und not sind die Hardware-Grundlage der endlichen Automaten (Mealy/Moore). Die Wahrheitstabelle mit 2ⁿ Zeilen ist ein erstes Beispiel für exponentielles Wachstum. Ob eine Formel überhaupt erfüllbar ist (SAT), ist das erste als NP-vollständig bewiesene Problem (Komplexitätstheorie).
XOR und neuronale Netze
Trägt man die vier Eingangskombinationen als Punkte (0,0), (0,1), (1,0), (1,1) in ein Diagramm ein, lassen sich die wahren Fälle von UND und ODER mit einer einzigen Geraden von den falschen trennen. Bei XOR geht das nicht: Die wahren Punkte (0,1) und (1,0) liegen diagonal gegenüber. Ein einzelner Linearer Klassifikator kann XOR deshalb nicht lernen, zwei zusammenarbeitende schon. Das ist die Grundidee mehrschichtiger neuronaler Netze (Quelle - Neuronale Netze selbst programmieren, S. 38–43).
Verwandt
- Zahlensystem – Dualzahlen als Daten der Schaltalgebra
- Endlicher Automat – Schaltwerke aus logischen Gattern und Speicher
- Komplexitätstheorie – Erfüllbarkeit (SAT) als NP-vollständiges Problem
- Wahrscheinlichkeitsrechnung – „und“ und „oder“ bei Ereignissen, gleiche Venn-Diagramme
- HP 48G – Menü LOGIC
- Linearer Klassifikator – UND und ODER sind linear trennbar, XOR nicht: der Grund für mehrschichtige neuronale Netze
- SQL-Join – Joins werden oft mit Venn-Diagrammen erklärt (Inner Join als „Schnittmenge“), was nur bedingt stimmt