Neutralitäts- und Extremalgesetz

Vereinfache $(A \land 1) \lor (B \land 0)$.

Wende das Neutralitätsgesetz auf die erste Klammer an: $A \land 1 = A$, denn UND mit wahr ändert nichts = $A \lor (B \land 0)$

Wende das Extremalgesetz auf die zweite Klammer an: $B \land 0 = 0$, denn UND mit falsch ist immer falsch = $A \lor 0$

Wende noch einmal das Neutralitätsgesetz an: $A \lor 0 = A$, denn ODER mit falsch ändert nichts = $A$

Answer: $(A \land 1) \lor (B \land 0) = A$. Der Wert von $B$ spielt überhaupt keine Rolle.

Das Absorptionsgesetz beweisen

Zeige mit anderen Gesetzen, dass $A \lor (A \land B) = A$ gilt.

Schreibe $A$ als $A \land 1$ (Neutralitätsgesetz): $A \lor (A \land B) = (A \land 1) \lor (A \land B)$ = Beide Klammern beginnen mit $A$

Klammere $A$ aus (Distributivgesetz, von rechts nach links gelesen): $(A \land 1) \lor (A \land B) = A \land (1 \lor B)$ = $A \land (1 \lor B)$

Wende Kommutativ- und Extremalgesetz an: $1 \lor B = B \lor 1 = 1$ = $A \land 1$

Wende das Neutralitätsgesetz an: $A \land 1 = A$ = $A$

Answer: $A \lor (A \land B) = A$. In Worten: Ist $A$ wahr, ist das ganze ODER wahr, und ist $A$ falsch, ist auch $A \land B$ falsch. In beiden Fällen ist das Ergebnis gleich $A$.

De Morgan und doppelte Negation

Vereinfache $\neg(\neg A \land B)$ und prüfe das Ergebnis mit einer Wahrheitstabelle.

Wende das De Morgansche Gesetz an: Das NICHT eines UND wird zum ODER der Negationen: $\neg(\neg A \land B) = \neg\neg A \lor \neg B$ = $\neg\neg A \lor \neg B$

Wende die doppelte Negation an: $\neg\neg A = A$ = $A \lor \neg B$

Stelle die Spalte des Ausgangsausdrucks auf: Zeilen $(A, B)$ = 00, 01, 10, 11: $\neg A \land B$ ist 0, 1, 0, 0, also ist $\neg(\neg A \land B)$ gleich 1, 0, 1, 1 = 1, 0, 1, 1

Stelle die Spalte des Ergebnisses auf: $\neg B$ ist 1, 0, 1, 0, also ist $A \lor \neg B$ gleich 1, 0, 1, 1 = Gleiche Spalte in jeder Zeile

Answer: $\neg(\neg A \land B) = A \lor \neg B$. Die beiden Spalten stimmen in allen 4 Zeilen überein, also ist die Vereinfachung richtig.

Ausklammern und Komplementgesetz

Vereinfache $(A \land B) \lor (A \land \neg B)$ und prüfe es mit einer Wahrheitstabelle.

Klammere $A$ aus (Distributivgesetz): $(A \land B) \lor (A \land \neg B) = A \land (B \lor \neg B)$ = $A \land (B \lor \neg B)$

Wende das Komplementgesetz an: $B \lor \neg B = 1$, denn $B$ ist entweder wahr oder falsch = $A \land 1$

Wende das Neutralitätsgesetz an: $A \land 1 = A$ = $A$

Prüfe mit einer Wahrheitstabelle: Zeilen $(A, B)$ = 00, 01, 10, 11: $A \land B$ ist 0, 0, 0, 1 und $A \land \neg B$ ist 0, 0, 1, 0, also ist das ODER 0, 0, 1, 1 = Wie die Spalte $A$: 0, 0, 1, 1

Answer: $(A \land B) \lor (A \land \neg B) = A$. Aus einer Schaltung mit 4 Gattern (zwei UND, ein NICHT, ein ODER) wird eine einfache Leitung.

Weniger Gatter in einer Schaltung

Eine Schaltung berechnet $\neg(A \lor B) \lor (\neg A \land B)$. Vereinfache sie und zähle die eingesparten Gatter (ein Gatter für jedes $\land$, $\lor$ und $\neg$).

Zähle die Gatter des Ausgangsausdrucks: Operatoren: $\neg$ und $\lor$ im ersten Teil, $\neg$ und $\land$ im zweiten Teil und das $\lor$ in der Mitte = 5 Gatter

Wende das De Morgansche Gesetz auf den ersten Teil an: $\neg(A \lor B) = \neg A \land \neg B$ = $(\neg A \land \neg B) \lor (\neg A \land B)$

Klammere $\neg A$ aus (Distributivgesetz): $(\neg A \land \neg B) \lor (\neg A \land B) = \neg A \land (\neg B \lor B)$ = $\neg A \land (\neg B \lor B)$

Wende Komplement- und Neutralitätsgesetz an: $\neg B \lor B = 1$ und $\neg A \land 1 = \neg A$ = $\neg A$

Zähle die Gatter noch einmal: $\neg A$ braucht ein einziges NICHT-Gatter: $5 - 1 = 4$ = 4 Gatter gespart

Answer: Die Schaltung ist äquivalent zu $\neg A$: ein NICHT-Gatter statt 5 Gattern. Kontrolle: Der Ausgangsausdruck ist genau in den Zeilen 00 und 01 wahr, also in den Zeilen mit $A = 0$.

Mistake: $\neg(A \land B) = \neg A \land \neg B$ schreiben

Why: Das De Morgansche Gesetz dreht nicht nur die Variablen um, sondern auch den Operator. Teste $A = 1$, $B = 0$: Die linke Seite ist $\neg 0 = 1$, die rechte Seite $0 \land 1 = 0$.

Correct: Strich brechen, Zeichen tauschen: $\neg(A \land B) = \neg A \lor \neg B$ und $\neg(A \lor B) = \neg A \land \neg B$.

Mistake: Regeln der gewöhnlichen Algebra verwenden, etwa $A \lor A = 2A$ oder $A \land A = A^2$

Why: Boolesche Variablen sind nur 0 oder 1, und $1 \lor 1$ ist 1, nicht 2. Eine Variable zu wiederholen bringt nichts Neues.

Correct: Verwende das Idempotenzgesetz: $A \lor A = A$ und $A \land A = A$.

Mistake: $A \lor B \land C$ als $(A \lor B) \land C$ lesen

Why: UND wird vor ODER ausgewertet, genau wie Multiplikation vor Addition. Mit $A = 1$, $B = 0$, $C = 0$ ist der richtige Wert $1 \lor 0 = 1$, die falsche Lesart ergibt aber $1 \land 0 = 0$.

Correct: Setze die Klammern, bevor du ein Gesetz anwendest: $A \lor B \land C = A \lor (B \land C)$.

Mistake: Das Komplementgesetz auf zwei verschiedene Variablen anwenden, etwa $A \land \neg B = 0$

Why: Das Komplementgesetz gilt nur für eine Variable und ihre eigene Negation. Mit $A = 1$, $B = 0$: $A \land \neg B = 1 \land 1 = 1$, nicht 0.

Correct: Achte auf denselben Buchstaben: $A \land \neg A = 0$ und $B \lor \neg B = 1$, aber $A \land \neg B$ lässt sich nicht vereinfachen.

Billigere Chips entwerfen

Chipdesigner vereinfachen jede Schaltung mit boolescher Algebra, bevor sie gebaut wird, denn jedes Gatter kostet Platz, Strom und Geld.

Eine Schaltung für $(A \land B) \lor (A \land C)$ braucht 3 Gatter. Ausgeklammert als $A \land (B \lor C)$ braucht sie nur 2.

Lesbare Bedingungen im Programm

Programmierer nutzen die De Morganschen Gesetze, um verwirrende doppelte Verneinungen aus Bedingungen in ihrem Code zu entfernen.

NICHT (Wochenende ODER Feiertag) ist dasselbe wie (NICHT Wochenende) UND (NICHT Feiertag): Der Laden hat an Tagen geöffnet, die keins von beiden sind.

Suchfilter

Suchmaschinen und Datenbanken vereinfachen Filter mit dem Absorptionsgesetz, bevor sie sie ausführen.

Der Filter Mathe ODER (Mathe UND Logik) liefert genau dieselben Bücher wie der Filter Mathe.

Q: Warum ist ODER über UND distributiv, obwohl $a + b \times c$ bei Zahlen nicht $(a + b) \times (a + c)$ ist?

A: Weil boolesche Variablen nur 0 oder 1 sind. Prüfe beide Fälle: Ist $A = 1$, sind beide Seiten von $A \lor (B \land C) = (A \lor B) \land (A \lor C)$ gleich 1; ist $A = 0$, werden beide Seiten zu $B \land C$. Mit gewöhnlichen Zahlen ist $1 + 2 \times 3 = 7$, aber $(1 + 2) \times (1 + 3) = 12$, also gilt dieses Gesetz nur in der booleschen Algebra.

Q: Woher weiß ich, welches Gesetz als Nächstes dran ist?

A: Achte auf Muster: Ein NICHT vor einer Klammer verlangt De Morgan, eine Variable, die in zwei Klammern vorkommt, verlangt Ausklammern (Distributivgesetz), und eine Variable neben ihrer eigenen Negation verlangt das Komplementgesetz. Die Konstanten 0 und 1 verschwinden mit dem Neutralitäts- und dem Extremalgesetz.

Q: Brauche ich noch Wahrheitstabellen, wenn ich die Gesetze kenne?

A: Die Gesetze finden die Vereinfachung, die Wahrheitstabelle bestätigt sie. Eine Tabelle mit 2 Variablen hat nur 4 Zeilen, also ist sie eine schnelle und sichere Kontrolle, vor allem wenn du dir bei einem Schritt nicht sicher bist.

Q: Kann ich ein Gesetz mit gewöhnlicher Arithmetik prüfen?

A: Ja, mit 0 und 1: $A \land B = A \times B$, $\neg A = 1 - A$ und $A \lor B = A + B - A \times B$. Zum Beispiel mit $A = 1$ und $B = 1$: $1 + 1 - 1 \times 1 = 1$, also $1 \lor 1 = 1$. Der Rechner in dieser Lektion arbeitet mit diesen Zahlen.