Algebra di Boole

Scrivi il procedimento per ogni esercizio.

1.
Quale legge dice che $A \land \neg A = 0$ ?
1. a)Legge del complemento
2. b)Legge di idempotenza
3. c)Legge di assorbimento
4. d)Legge di identità
Risposta: Legge del complemento
La legge del complemento: una variabile AND la sua stessa negazione vale sempre 0, perché $A$ e $\neg A$ non sono mai vere insieme. La sua forma OR è $A \lor \neg A = 1$ .
2.
Quanto vale $A \lor 1$ , qualunque sia il valore di $A$ ? Scrivi 1 per vero o 0 per falso.
Risposta: 1
Legge di annullamento: $A \lor 1 = 1$ . Se $A = 0$ , allora $0 \lor 1 = 1$ ; se $A = 1$ , allora $1 \lor 1 = 1$ .
3.
Semplifica $(A \lor 0) \land (B \lor 1)$ e controlla due righe.
Risposta: 0
1. Per la legge di annullamento, $B \lor 1$ è una costante. Quale? Scrivi 0 o 1. 1
2. Quindi l'espressione è $A \land 1 = A$ . Controllo: quanto vale l'espressione iniziale per $A = 1$ , $B = 0$ ? 1
3. E per $A = 0$ , $B = 0$ ? 0
4.
$A \lor A$ si semplifica in:
1. a) $2A$
2. b) $A$
3. c) $\neg A$
4. d) $A^2$
Risposta: $A$
Idempotenza: $A \lor A = A$ , perché $0 \lor 0 = 0$ e $1 \lor 1 = 1$ . $2A$ e $A^2$ vengono dall'algebra ordinaria e qui non valgono.
5.
Semplifica $\neg\neg A \land 0$ . Il risultato è una costante: scrivi 0 o 1.
Risposta: 0
La doppia negazione dà $\neg\neg A = A$ , e la legge di annullamento dà $A \land 0 = 0$ . Il valore di $A$ non conta.
6.
Controlla la legge di De Morgan $\neg(A \land B) = \neg A \lor \neg B$ per $A = 1$ e $B = 0$ .
Risposta: 1
1. Quanto vale $A \land B$ ? 0
2. Quindi quanto vale $\neg(A \land B)$ ? 1
3. Quanto vale $\neg A$ ? 0
4. Quanto vale $\neg A \lor \neg B$ ? 1
7.
Quale espressione è equivalente a $\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$
Risposta: $\neg A \land \neg B$
Legge di De Morgan: $\neg(A \lor B) = \neg A \land \neg B$ . NOT (A OR B) è vero solo se nessuna delle due è vera. $\neg A \lor \neg B$ è invece la negazione di $A \land B$ .
8.
Quale espressione è uguale a $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)$
Risposta: $(A \lor B) \land (A \lor C)$
Proprietà distributiva (OR rispetto ad AND): $A \lor (B \land C) = (A \lor B) \land (A \lor C)$ . Controlla $A = 1$ : entrambi i lati valgono 1. Controlla $A = 0$ : entrambi i lati valgono $B \land C$ .
9.
Qual è il valore di $\neg(A \land \neg B)$ per $A = 1$ e $B = 0$ ? Scrivi 0 o 1.
Risposta: 0
$\neg B = 1$ , quindi $A \land \neg B = 1 \land 1 = 1$ e $\neg 1 = 0$ . Con De Morgan: $\neg A \lor B = 0 \lor 0 = 0$ , lo stesso valore.
10.
$(A \land B) \lor (A \land \neg B)$ si semplifica in $A$ . Contando una porta per ogni $\land$ , $\lor$ e $\neg$ , quante porte fa risparmiare la semplificazione?
Risposta: 4
Iniziale: due AND, un NOT e un OR, quindi 4 porte. $A$ richiede 0 porte. Risparmio: $4 - 0 = 4$ .
11.
Controlla la legge di assorbimento $A \land (A \lor B) = A$ riga per riga.
Risposta: 2
1. Per $A = 0$ , quanto vale $A \land (A \lor B)$ , qualunque sia $B$ ? 0
2. Per $A = 1$ e $B = 0$ , quanto vale $A \land (A \lor B)$ ? 1
3. E per $A = 1$ e $B = 1$ ? 1
4. In quante delle 4 righe $A \land (A \lor B)$ è vera? 2
12.
Semplifica $(A \lor B) \land (A \lor \neg B)$ e controlla il risultato.
Risposta: 2
1. La proprietà distributiva dà $A \lor (B \land \neg B)$ . Quale costante è $B \land \neg B$ ? Scrivi 0 o 1. 0
2. Quindi l'espressione è $A \lor 0 = A$ . Controlla la riga $A = 0$ , $B = 1$ : quanto vale l'espressione iniziale? 0
3. Controlla la riga $A = 1$ , $B = 0$ : 1
4. In quante delle 4 righe l'espressione iniziale è vera? 2
13.
Semplifica $\neg(A \lor \neg B)$ con la legge di De Morgan.
Risposta: 1
1. La legge di De Morgan dà $\neg A \land \neg\neg B$ . Quanti segni $\neg$ ha questa forma? 3
2. Dopo la doppia negazione l'espressione è $\neg A \land B$ . Quanti segni $\neg$ restano? 1
3. $\neg A \land B$ è vera in una sola riga. Quanto vale $A$ in quella riga? Scrivi 0 o 1. 0
4. E quanto vale $B$ in quella riga? 1
14.
Quale espressione NON è equivalente ad $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)$
Risposta: $A \lor (\neg A \land B)$
Le prime due sono le leggi di assorbimento, e $(A \lor B) \land (A \lor \neg B) = A \lor (B \land \neg B) = A$ . Ma $A \lor (\neg A \land B) = (A \lor \neg A) \land (A \lor B) = A \lor B$ , che vale 1 per $A = 0$ , $B = 1$ .
15.
In quante delle 4 righe $(A \lor B) \land (A \lor \neg B) \land (\neg A \lor B)$ è vera?
Risposta: 1
$(A \lor B) \land (A \lor \neg B) = A$ . Poi $A \land (\neg A \lor B) = (A \land \neg A) \lor (A \land B) = 0 \lor (A \land B) = A \land B$ , che è vera solo nella riga $A = 1$ , $B = 1$ .
16.
Semplifica $\neg(A \land B) \land (A \lor \neg B)$ e conta le porte risparmiate.
Risposta: 4
1. De Morgan dà $(\neg A \lor \neg B) \land (A \lor \neg B)$ , e la proprietà distributiva dà $\neg B \lor (\neg A \land A)$ . Quale costante è $\neg A \land A$ ? 0
2. Quindi l'espressione è $\neg B \lor 0 = \neg B$ . Controlla $A = 1$ , $B = 1$ : quanto vale l'espressione iniziale? 0
3. Controlla $A = 0$ , $B = 0$ : 1
4. Contando una porta per ogni $\land$ , $\lor$ e $\neg$ , quante porte usa l'espressione iniziale? 5
5. Quante porte si risparmiano usando invece $\neg B$ ? 4
17.
Semplifica $A \lor (\neg A \land B)$ .
Risposta: 3
1. La proprietà distributiva dà $(A \lor \neg A) \land (A \lor B)$ . Quale costante è $A \lor \neg A$ ? 1
2. Quindi l'espressione è $1 \land (A \lor B) = A \lor B$ . Controlla $A = 0$ , $B = 1$ : quanto vale l'espressione iniziale? 1
3. In quante delle 4 righe $A \lor B$ è vera? 3
18.
Semplifica $(A \land B) \lor (A \land \neg B \land C)$ e conta le righe in cui è vera.
Risposta: 3
1. Raccogliendo $A$ si ottiene $A \land (B \lor (\neg B \land C))$ , e la proprietà distributiva trasforma la parentesi in $(B \lor \neg B) \land (B \lor C)$ . Quale costante è $B \lor \neg B$ ? 1
2. Quindi l'espressione è $A \land (B \lor C)$ . Contando una porta per ogni $\land$ , $\lor$ e $\neg$ , quante porte usa? 2
3. Una tavola per $A$ , $B$ e $C$ ha 8 righe. In quante di queste $A = 1$ ? 4
4. In queste righe $B \lor C$ è falsa solo per $B = 0$ e $C = 0$ . In quante righe l'espressione è vera? 3