Äquivalenz: gleiche Wirkung, weniger Gatter
Gleiche Wirkung, andere Schaltung
Zwei Schaltungen können verschieden aussehen und doch bei jeder Schalterstellung dasselbe tun. Für die Herstellung ist das wichtig: Weniger Gatter heißt billiger, kleiner und schneller.
Äquivalenz
Zwei Terme heißen äquivalent, wenn sie bei jeder Belegung der Variablen denselben Wert haben – ihre Belegungstabellen stimmen in der Ergebnisspalte überein. Äquivalente Terme beschreiben Schaltungen mit gleicher Wirkung.
Aufgabe 1: Vergleiche ¬(a ∧ b) und ¬a ∨ ¬b mit einer Tabelle.
Aufgabe 2: Sind ¬(a ∧ b) und ¬a ∨ ¬b äquivalent?
Regeln von De Morgan
¬(a ∧ b) ist äquivalent zu ¬a ∨ ¬b.
¬(a ∨ b) ist äquivalent zu ¬a ∧ ¬b.
Merkregel: Beim Hineinziehen der Negation wird aus ∧ ein ∨ und umgekehrt.
Diese Schaltung braucht drei Gatter:
Aufgabe 4: Baue eine Schaltung mit derselben Wirkung, die mit zwei Gattern auskommt.
Aufgabe 5: Gib einen zu ¬(¬a ∨ ¬b) äquivalenten Term mit nur einer Verknüpfung an.