Terme und Termbäume
Was ist ein Term?
Terme wie (g ∧ ¬h) ∨ (s ∧ h) beschreiben Schaltungen. Damit Mensch und Computer sie eindeutig lesen können, legt man genau fest, was ein Term ist – Schritt für Schritt aus kleineren Termen:
Aussagenlogischer Term (induktive Definition)
- Jede Variable (a, b, …) und die Konstanten 0 und 1 sind Terme.
- Ist T ein Term, dann ist auch ¬T ein Term (Negation).
- Sind T₁ und T₂ Terme, dann sind auch (T₁ ∧ T₂) (Konjunktion) und (T₁ ∨ T₂) (Disjunktion) Terme.
- Nur was so entsteht, ist ein Term.
Äußere Klammern lässt man weg. ¬ bezieht sich nur auf das, was direkt dahinter steht: ¬a ∧ b bedeutet (¬a) ∧ b.
Termbäume
Wie ein Term aus kleineren Termen entsteht, zeigt sein Termbaum: Ganz oben steht die Verknüpfung, die zuletzt ausgewertet wird; darunter ihre Teilterme; unten die Variablen.
Termbaum und Schaltung
Der Termbaum ist die Schaltung, „gekippt“: Die Wurzel ist das letzte Gatter vor dem Ausgang, die Blätter sind die Eingänge.
Aufgabe 2: Baue den Termbaum zu (a ∨ b) ∧ ¬c.
Hier ist ein Termbaum:
Aufgabe 3: Gib den Term zu diesem Termbaum an.
Aufgabe 4: Baue die Schaltung zu x = (a ∨ ¬b) ∧ c.