Alle Tabs der Lerneinheit (Erklärung · Interaktiv verstehen · Praxis-Übung · Klausur-Quiz) als durchgehender Text. Ideal zum Wiederholen vor der Klausur, und für Suchmaschinen wie Google, Bing und KI-Suche (ChatGPT, Perplexity).
Erklärung
Boolesche Algebra und Logikgatter
Wie rechnet ein Computer, der nur 0 und 1 kennt? Mit boolescher Algebra: einem Rechensystem, das George Boole 1854 erfand, lange bevor es Computer gab. Jede CPU, jeder Speicher, jede Schaltung basiert darauf. Klausurpflicht in 7/8 Rechnerarchitektur-Modulen, oft der rechenintensivste Aufgabenteil.
Die Idee in einem Satz
Boolesche Algebra arbeitet mit nur zwei Werten (0 und 1) und drei Grundoperationen (AND, OR, NOT). Logikgatter sind die Hardware-Bausteine, die diese Operationen physisch ausführen.
Die Werte
Nur zwei: 0 (falsch, low, aus) und 1 (wahr, high, an). Das ist alles. Eine boolesche Variable kann nur einen dieser zwei Zustände annehmen.
Die drei Grundoperationen
| Operation | Zeichen | Bedeutung | Ergebnis 1, wenn... |
|---|---|---|---|
| AND (UND) | A · B, A ∧ B | Konjunktion | BEIDE Eingänge 1 sind |
| OR (ODER) | A + B, A ∨ B | Disjunktion | MINDESTENS EIN Eingang 1 ist |
| NOT (NICHT) | ¬A, Ā | Negation | der Eingang 0 ist (kehrt um) |
Wahrheitstafeln der Grundgatter
AND OR NOT
A B | Y A B | Y A | Y
0 0 | 0 0 0 | 0 0 | 1
0 1 | 0 0 1 | 1 1 | 0
1 0 | 0 1 0 | 1
1 1 | 1 1 1 | 1
Merke: AND = "Reihenschaltung" (alle müssen leiten), OR = "Parallelschaltung" (einer reicht).
Die abgeleiteten Gatter
| Gatter | Definition | Ergebnis 1, wenn... |
|---|---|---|
| NAND | ¬(A · B) | NICHT beide 1 |
| NOR | ¬(A + B) | KEINER 1 ist |
| XOR (Antivalenz) | A ⊕ B | die Eingänge VERSCHIEDEN sind |
| XNOR (Äquivalenz) | ¬(A ⊕ B) | die Eingänge GLEICH sind |
XOR ist der Schlüssel zum Addieren: 1 + 1 = 0 mit Übertrag, genau das liefert XOR (Summe) plus AND (Übertrag) im Halbaddierer.
Die Gesetze der booleschen Algebra
Diese Gesetze braucht man, um Ausdrücke zu vereinfachen (= Schaltungen mit weniger Gattern zu bauen):
| Gesetz | AND-Form | OR-Form |
|---|---|---|
| Kommutativ | A · B = B · A | A + B = B + A |
| Assoziativ | (A · B) · C = A · (B · C) | (A + B) + C = A + (B + C) |
| Distributiv | A · (B + C) = A·B + A·C | A + (B·C) = (A+B)·(A+C) |
| Neutrales Element | A · 1 = A | A + 0 = A |
| Extremalgesetz | A · 0 = 0 | A + 1 = 1 |
| Idempotenz | A · A = A | A + A = A |
| Komplement | A · ¬A = 0 | A + ¬A = 1 |
| Absorption | A · (A + B) = A | A + (A · B) = A |
| Doppelnegation | ¬(¬A) = A |
Die DeMorgan-Regeln (Klausur-Liebling)
Die wichtigsten Vereinfachungs-Regeln:
¬(A · B) = ¬A + ¬B (NICHT-UND wird zu ODER der Negationen) ¬(A + B) = ¬A · ¬B (NICHT-ODER wird zu UND der Negationen)
Eselsfrei gemerkt: Negation reinziehen, Operator umdrehen (AND ↔ OR). DeMorgan erlaubt es, jede Schaltung nur mit NAND oder nur mit NOR zu bauen.
Funktionale Vollständigkeit
Mit {AND, OR, NOT} lässt sich JEDE boolesche Funktion darstellen. Noch stärker: NAND allein und NOR allein sind je für sich funktional vollständig. Deshalb baut man integrierte Schaltungen oft komplett aus NAND-Gattern (billiger in der Fertigung).
Von der Funktion zur Schaltung
- Wahrheitstafel aufstellen (alle 2ⁿ Eingangs-Kombinationen).
- Disjunktive Normalform (DNF): für jede Zeile mit Y=1 einen UND-Term, alle mit ODER verknüpfen.
- Vereinfachen mit den Gesetzen oder dem KV-Diagramm (Karnaugh-Veitch).
- Schaltung aus Gattern zeichnen.
Klausur-Faustregeln
1. AND = alle 1, OR = mind. ein 1, NOT = umkehren. Auswendig.
2. NAND = ¬AND, NOR = ¬OR. Das kleine "N" steht für die Negation am Ausgang.
3. XOR = Ungleichheit, XNOR = Gleichheit.
4. DeMorgan: Negation reinziehen, Operator umdrehen.
5. A + 1 = 1 und A · 0 = 0 (Extremalgesetze, sparen viel Rechnerei).
6. Wahrheitstafel hat 2ⁿ Zeilen bei n Eingängen.
Häufige Stolpersteine
1. AND mit OR verwechseln. A · B (Punkt) = AND. A + B (Plus) = OR. Der Punkt steht für UND, das Plus für ODER, nicht für Multiplikation/Addition im üblichen Sinn.
2. DeMorgan falsch anwenden. Beim Reinziehen der Negation MUSS der Operator umklappen. ¬(A · B) ist NICHT ¬A · ¬B, sondern ¬A + ¬B.
3. XOR mit OR verwechseln. Bei A=1, B=1 ist OR = 1, aber XOR = 0 (gleich → 0).
4. Distributivgesetz nur in eine Richtung kennen. In der booleschen Algebra gilt das Distributivgesetz BEIDSEITIG, auch A + (B·C) = (A+B)·(A+C), anders als in der normalen Arithmetik.
5. Anzahl der Zeilen falsch. Bei 3 Eingängen sind es 2³ = 8 Zeilen, nicht 6.
6. A · A = A vergessen (Idempotenz). In der booleschen Algebra ist A · A = A, nicht A².
Interaktiv verstehen
Logikgatter, interaktiv
Schalte die Eingänge A und B um und wähle ein Gatter (AND, OR, NOT, NAND, NOR, XOR, XNOR). Der Simulator zeigt live den Ausgang und die vollständige Wahrheitstafel mit hervorgehobener aktueller Zeile. Im zweiten Modus siehst du, wie sich XOR aus den Grundgattern AND, OR und NOT zusammensetzt.
Interaktive Visualisierung
Interaktive Komponente: probiere sie im Topic-Player oben aus.
Klausur-Tipp: Trainiere, jede Wahrheitstafel auswendig hinzuschreiben. Erkenne ein Gatter sofort am Muster der Ausgangsspalte: AND hat nur eine 1 (ganz unten), OR nur eine 0 (ganz oben), XOR die typischen "0 1 1 0".
Praxis-Übung
Boolesche Algebra, Praxis-Übung
6 Aufgaben zu Gattern, Wahrheitstafeln und Gesetzen.
Klausurfragen mit Lösungen (6)
- F1.Wann liefert ein AND-Gatter mit den Eingängen A und B eine 1 am Ausgang?
Antwort: Wenn beide Eingänge 1 sind
Erklärung: Das AND-Gatter (UND, A · B) liefert NUR dann 1, wenn BEIDE Eingänge 1 sind (1·1=1). In allen anderen Fällen ist der Ausgang 0. Merkhilfe: AND = Reihenschaltung, alle Schalter müssen geschlossen sein. OR dagegen reicht ein Eingang. Klausur-Grundlage.
- F2.Welche Operation realisiert die Negation (kehrt 0 zu 1 und 1 zu 0 um)?
Antwort: NOT
Erklärung: NOT (NICHT, ¬A oder Ā) ist die Negation: aus 0 wird 1, aus 1 wird 0. Es ist das einzige einstellige Grundgatter (nur ein Eingang). AND und OR sind zweistellig, XOR vergleicht zwei Eingänge auf Ungleichheit. Klausur-Grundbegriff.
- F3.Ordne das Gatter seiner Wahrheitstafel-Eigenschaft zu.
Zuordnungen:
- AND → 1 nur wenn beide Eingänge 1
- OR → 0 nur wenn beide Eingänge 0
- XOR → 1 wenn Eingänge verschieden
- NAND → 0 nur wenn beide Eingänge 1
Erklärung: AND: 1 bei (1,1). OR: 0 nur bei (0,0). XOR: 1 bei Ungleichheit (0,1) und (1,0). NAND = ¬AND: also genau invers zu AND, 0 nur bei (1,1), sonst 1. Diese Muster muss man in der Klausur sofort erkennen. Stolperstein: XOR ist 0 bei (1,1), nicht 1.
Typ: Zuordnung
- F4.Wie lautet die DeMorgan-Regel für ¬(A · B)?
Antwort: ¬A + ¬B
Erklärung: DeMorgan: ¬(A · B) = ¬A + ¬B. Regel: Negation reinziehen UND Operator umdrehen (AND wird zu OR). Die zweite DeMorgan-Regel lautet ¬(A + B) = ¬A · ¬B. Häufigster Fehler: den Operator nicht umzudrehen (¬A · ¬B wäre falsch). Klausur-Pflichtregel.
- F5.Bei den Eingängen A=1 und B=1 liefert ein XOR-Gatter den Ausgang 1.
Antwort: Falsch
Erklärung: FALSCH. XOR (Antivalenz) liefert 1 nur, wenn die Eingänge VERSCHIEDEN sind. Bei A=1, B=1 sind sie GLEICH, also ist der Ausgang 0. XOR liefert 1 bei (0,1) und (1,0), aber 0 bei (0,0) und (1,1). Klassischer Stolperstein, weil OR hier 1 liefern würde.
Typ: Wahr/Falsch
- F6.Vereinfache den Ausdruck A + (A · B) mit den booleschen Gesetzen.
Antwort: A
Erklärung: A + (A · B) = A (Absorptionsgesetz). Begründung: Wenn A=1, ist der Ausdruck 1 (egal was B ist). Wenn A=0, ist A·B=0 und A=0, also 0. Der Ausdruck hängt also nur von A ab. Das Absorptionsgesetz (A + A·B = A bzw. A·(A+B) = A) spart in Schaltungen Gatter. Klausur-Vereinfachung.
Klausur-Quiz
Boolesche Algebra, Klausur-Quiz
6 Klausur-Fragen zu Gattern, DeMorgan und funktionaler Vollständigkeit.
Klausurfragen mit Lösungen (6)
- F1.Wie viele Zeilen hat die Wahrheitstafel einer Funktion mit 3 Eingängen?
Antwort: 8
Erklärung: Eine Wahrheitstafel mit n Eingängen hat 2ⁿ Zeilen, weil jede Eingangsvariable 2 Werte (0/1) annehmen kann. Bei 3 Eingängen: 2³ = 8 Zeilen. Bei 4 Eingängen wären es 2⁴ = 16. Häufiger Fehler: 2·3 = 6 zu rechnen. Klausur-Grundlage.
- F2.Welches Gatter ist allein funktional vollständig (kann jede boolesche Funktion bilden)?
Antwort: NAND
Erklärung: NAND (und ebenso NOR) ist allein funktional vollständig: man kann AND, OR und NOT nur aus NAND-Gattern aufbauen (z.B. NOT = NAND mit beiden Eingängen gleich). Deshalb baut man Chips oft komplett aus NAND. AND, OR oder XOR allein reichen nicht (man braucht zusätzlich die Negation). Klausur-Transferfrage.
- F3.Ordne das boolesche Gesetz seiner Aussage zu.
Zuordnungen:
- Extremalgesetz → A + 1 = 1
- Komplement → A + ¬A = 1
- Idempotenz → A · A = A
- Neutrales Element → A · 1 = A
Erklärung: Extremalgesetz: A + 1 = 1 (und A · 0 = 0). Komplement: A + ¬A = 1 (und A · ¬A = 0). Idempotenz: A · A = A (und A + A = A). Neutrales Element: A · 1 = A (und A + 0 = A). Diese Gesetze sind die Werkzeuge zum Vereinfachen. Klausur-Pflicht-Zuordnung.
Typ: Zuordnung
- F4.Welche Funktion realisiert ein XOR-Gatter (Summe ohne Übertrag im Halbaddierer)?
Antwort: Ausgang 1, wenn die Eingänge verschieden sind
Erklärung: XOR (exklusiv-oder, Antivalenz) liefert 1 bei VERSCHIEDENEN Eingängen: (0,1)→1, (1,0)→1, (0,0)→0, (1,1)→0. Im Halbaddierer liefert XOR die Summe (0+1=1, 1+1=0) und AND den Übertrag. XNOR ist das Gegenteil (1 bei Gleichheit). Klausur-Kernfrage zur Addition.
- F5.Nach DeMorgan gilt: ¬(A + B) = ¬A · ¬B.
Antwort: Wahr
Erklärung: RICHTIG. Die zweite DeMorgan-Regel: ¬(A + B) = ¬A · ¬B. Negation reinziehen, Operator umdrehen (OR wird zu AND). Beispiel: 'nicht (A oder B)' bedeutet 'weder A noch B', also 'nicht A UND nicht B'. Zusammen mit ¬(A·B) = ¬A + ¬B die wichtigste Vereinfachungsregel. Klausur-Pflicht.
Typ: Wahr/Falsch
- F6.Eine Schaltung liefert 1 genau bei den Eingängen (A=0,B=1) und (A=1,B=0). Welches Gatter ist das?
Antwort: XOR
Erklärung: Ausgang 1 nur bei verschiedenen Eingängen (0,1) und (1,0), 0 bei (0,0) und (1,1) ist exakt die XOR-Funktion (Antivalenz). Vorgehen in der Klausur: Wahrheitstafel aus der Beschreibung aufstellen, Muster mit den bekannten Gattern abgleichen. Das Muster '0 1 1 0' in der Ausgangsspalte = XOR. Klausur-Erkennungsaufgabe.
