Boolesche Algebra

Schreibe bei jeder Aufgabe deinen Lösungsweg auf.

1.
Welches Gesetz besagt $A \land \neg A = 0$ ?
1. a)Komplementgesetz
2. b)Idempotenzgesetz
3. c)Absorptionsgesetz
4. d)Neutralitätsgesetz
Lösung: Komplementgesetz
Das Komplementgesetz: Eine Variable UND ihre eigene Negation ist immer 0, denn $A$ und $\neg A$ sind nie beide wahr. Die ODER-Form lautet $A \lor \neg A = 1$ .
2.
Was ist $A \lor 1$ , egal welchen Wert $A$ hat? Gib 1 für wahr oder 0 für falsch ein.
Lösung: 1
Extremalgesetz: $A \lor 1 = 1$ . Ist $A = 0$ , dann $0 \lor 1 = 1$ ; ist $A = 1$ , dann $1 \lor 1 = 1$ .
3.
Vereinfache $(A \lor 0) \land (B \lor 1)$ und prüfe zwei Zeilen.
Lösung: 0
1. Nach dem Extremalgesetz ist $B \lor 1$ eine Konstante. Welche? Gib 0 oder 1 ein. 1
2. Der Ausdruck ist also $A \land 1 = A$ . Kontrolle: Was ergibt der Ausgangsausdruck für $A = 1$ , $B = 0$ ? 1
3. Und für $A = 0$ , $B = 0$ ? 0
4.
$A \lor A$ lässt sich vereinfachen zu:
1. a) $2A$
2. b) $A$
3. c) $\neg A$
4. d) $A^2$
Lösung: $A$
Idempotenzgesetz: $A \lor A = A$ , denn $0 \lor 0 = 0$ und $1 \lor 1 = 1$ . $2A$ und $A^2$ stammen aus der gewöhnlichen Algebra und gelten hier nicht.
5.
Vereinfache $\neg\neg A \land 0$ . Das Ergebnis ist eine Konstante: Gib 0 oder 1 ein.
Lösung: 0
Die doppelte Negation ergibt $\neg\neg A = A$ , und das Extremalgesetz ergibt $A \land 0 = 0$ . Der Wert von $A$ spielt keine Rolle.
6.
Prüfe das De Morgansche Gesetz $\neg(A \land B) = \neg A \lor \neg B$ für $A = 1$ und $B = 0$ .
Lösung: 1
1. Was ist $A \land B$ ? 0
2. Was ist also $\neg(A \land B)$ ? 1
3. Was ist $\neg A$ ? 0
4. Was ist $\neg A \lor \neg B$ ? 1
7.
Welcher Ausdruck ist äquivalent zu $\neg(A \lor B)$ ?
1. a) $\neg A \land \neg B$
2. b) $A \land B$
3. c) $\neg A \lor \neg B$
4. d) $\neg A \lor B$
Lösung: $\neg A \land \neg B$
De Morgansches Gesetz: $\neg(A \lor B) = \neg A \land \neg B$ . NICHT (A ODER B) ist nur wahr, wenn keins von beiden wahr ist. $\neg A \lor \neg B$ ist dagegen die Negation von $A \land B$ .
8.
Welcher Ausdruck ist gleich $A \lor (B \land C)$ ?
1. a) $A \land (B \lor C)$
2. b) $(A \lor B) \land C$
3. c) $(A \lor B) \land (A \lor C)$
4. d) $(A \land B) \lor (A \land C)$
Lösung: $(A \lor B) \land (A \lor C)$
Distributivgesetz (ODER über UND): $A \lor (B \land C) = (A \lor B) \land (A \lor C)$ . Prüfe $A = 1$ : Beide Seiten sind 1. Prüfe $A = 0$ : Beide Seiten sind $B \land C$ .
9.
Welchen Wert hat $\neg(A \land \neg B)$ für $A = 1$ und $B = 0$ ? Gib 0 oder 1 ein.
Lösung: 0
$\neg B = 1$ , also $A \land \neg B = 1 \land 1 = 1$ und $\neg 1 = 0$ . Mit De Morgan: $\neg A \lor B = 0 \lor 0 = 0$ , derselbe Wert.
10.
$(A \land B) \lor (A \land \neg B)$ lässt sich zu $A$ vereinfachen. Wie viele Gatter spart die Vereinfachung, wenn du für jedes $\land$ , $\lor$ und $\neg$ ein Gatter zählst?
Lösung: 4
Ausgangsausdruck: zweimal UND, einmal NICHT und einmal ODER, also 4 Gatter. $A$ braucht 0 Gatter. Gespart: $4 - 0 = 4$ .
11.
Prüfe das Absorptionsgesetz $A \land (A \lor B) = A$ Zeile für Zeile.
Lösung: 2
1. Was ist $A \land (A \lor B)$ für $A = 0$ , egal welchen Wert $B$ hat? 0
2. Was ist $A \land (A \lor B)$ für $A = 1$ und $B = 0$ ? 1
3. Und für $A = 1$ und $B = 1$ ? 1
4. In wie vielen der 4 Zeilen ist $A \land (A \lor B)$ wahr? 2
12.
Vereinfache $(A \lor B) \land (A \lor \neg B)$ und prüfe das Ergebnis.
Lösung: 2
1. Das Distributivgesetz ergibt $A \lor (B \land \neg B)$ . Welche Konstante ist $B \land \neg B$ ? Gib 0 oder 1 ein. 0
2. Der Ausdruck ist also $A \lor 0 = A$ . Prüfe die Zeile $A = 0$ , $B = 1$ : Was ergibt der Ausgangsausdruck? 0
3. Prüfe die Zeile $A = 1$ , $B = 0$ : 1
4. In wie vielen der 4 Zeilen ist der Ausgangsausdruck wahr? 2
13.
Vereinfache $\neg(A \lor \neg B)$ mit dem De Morganschen Gesetz.
Lösung: 1
1. Das De Morgansche Gesetz ergibt $\neg A \land \neg\neg B$ . Wie viele $\neg$ -Zeichen hat diese Form? 3
2. Nach der doppelten Negation lautet der Ausdruck $\neg A \land B$ . Wie viele $\neg$ -Zeichen bleiben übrig? 1
3. $\neg A \land B$ ist nur in einer Zeile wahr. Welchen Wert hat $A$ in dieser Zeile? Gib 0 oder 1 ein. 0
4. Und welchen Wert hat $B$ in dieser Zeile? 1
14.
Welcher Ausdruck ist NICHT äquivalent zu $A$ ?
1. a) $(A \lor B) \land (A \lor \neg B)$
2. b) $A \lor (A \land B)$
3. c) $A \land (A \lor B)$
4. d) $A \lor (\neg A \land B)$
Lösung: $A \lor (\neg A \land B)$
Die ersten beiden sind die Absorptionsgesetze, und $(A \lor B) \land (A \lor \neg B) = A \lor (B \land \neg B) = A$ . Aber $A \lor (\neg A \land B) = (A \lor \neg A) \land (A \lor B) = A \lor B$ , und das ist 1 für $A = 0$ , $B = 1$ .
15.
In wie vielen der 4 Zeilen ist $(A \lor B) \land (A \lor \neg B) \land (\neg A \lor B)$ wahr?
Lösung: 1
$(A \lor B) \land (A \lor \neg B) = A$ . Dann gilt $A \land (\neg A \lor B) = (A \land \neg A) \lor (A \land B) = 0 \lor (A \land B) = A \land B$ , und das ist nur in der Zeile $A = 1$ , $B = 1$ wahr.
16.
Vereinfache $\neg(A \land B) \land (A \lor \neg B)$ und zähle die eingesparten Gatter.
Lösung: 4
1. De Morgan ergibt $(\neg A \lor \neg B) \land (A \lor \neg B)$ , und das Distributivgesetz ergibt $\neg B \lor (\neg A \land A)$ . Welche Konstante ist $\neg A \land A$ ? 0
2. Der Ausdruck ist also $\neg B \lor 0 = \neg B$ . Prüfe $A = 1$ , $B = 1$ : Was ergibt der Ausgangsausdruck? 0
3. Prüfe $A = 0$ , $B = 0$ : 1
4. Wie viele Gatter braucht der Ausgangsausdruck, wenn du für jedes $\land$ , $\lor$ und $\neg$ ein Gatter zählst? 5
5. Wie viele Gatter spart man, wenn man stattdessen $\neg B$ verwendet? 4
17.
Vereinfache $A \lor (\neg A \land B)$ .
Lösung: 3
1. Das Distributivgesetz ergibt $(A \lor \neg A) \land (A \lor B)$ . Welche Konstante ist $A \lor \neg A$ ? 1
2. Der Ausdruck ist also $1 \land (A \lor B) = A \lor B$ . Prüfe $A = 0$ , $B = 1$ : Was ergibt der Ausgangsausdruck? 1
3. In wie vielen der 4 Zeilen ist $A \lor B$ wahr? 3
18.
Vereinfache $(A \land B) \lor (A \land \neg B \land C)$ und zähle die Zeilen, in denen der Ausdruck wahr ist.
Lösung: 3
1. Ausklammern von $A$ ergibt $A \land (B \lor (\neg B \land C))$ , und das Distributivgesetz macht aus der Klammer $(B \lor \neg B) \land (B \lor C)$ . Welche Konstante ist $B \lor \neg B$ ? 1
2. Der Ausdruck ist also $A \land (B \lor C)$ . Wie viele Gatter braucht er, wenn du für jedes $\land$ , $\lor$ und $\neg$ ein Gatter zählst? 2
3. Eine Tabelle für $A$ , $B$ und $C$ hat 8 Zeilen. In wie vielen davon ist $A = 1$ ? 4
4. In diesen Zeilen ist $B \lor C$ nur für $B = 0$ und $C = 0$ falsch. In wie vielen Zeilen ist der Ausdruck wahr? 3