Von der Tabelle zum Term: die DNF
Vom Wunsch zur Schaltung
Eine Verkehrsampel hat drei Lampen: rot (R), gelb (Y) und grün (G). Sie wird von zwei Bits x und y gesteuert. Festgelegt ist nur, was leuchten soll:
| x | y | R | Y | G |
|---|---|---|---|---|
| 0 | 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 | 0 |
| 1 | 0 | 0 | 0 | 1 |
| 1 | 1 | 0 | 1 | 0 |
(00 rot, 01 rot-gelb, 10 grün, 11 gelb). Wie findet man zu einer solchen Tabelle die Schaltung?
Disjunktive Normalform (DNF)
- Suche alle Zeilen, in denen das Ergebnis 1 ist.
- Schreibe für jede solche Zeile eine Konjunktion aller Variablen; eine Variable, die in der Zeile 0 ist, bekommt ein ¬. Diese Konjunktion ist genau bei dieser Belegung wahr.
- Verbinde alle Konjunktionen mit ∨.
Beispiel: Ergebnis 1 nur in den Zeilen 01 und 10 → (¬x ∧ y) ∨ (x ∧ ¬y).
Aufgabe 1: Gib die DNF für die grüne Lampe G an.
Aufgabe 2: Gib die DNF für die gelbe Lampe Y an.
Aufgabe 3: Baue die Ampelsteuerung mit allen drei Lampen. Teste sie mit den Knöpfen x und y an der Ampel.
Abstimmen
Drei Jurymitglieder a, b und c drücken je einen Knopf (1 = Ja). Die Lampe x soll leuchten, wenn die Mehrheit Ja sagt, also mindestens zwei Knöpfe gedrückt sind.
Aufgabe 4: Fülle zuerst die Tabelle für die Mehrheit aus.
Aufgabe 5: Gib die DNF für x an.