Note Ingegneria Informatica · UniTN
Programmazione 1
esercizi
Teoria
in corso

Algebra di Boole (esercizi)

Esercizi tipo esame di Algebra di Boole, dove stanno teoria, metodo ed esempi svolti a lezione. Testo in chiaro, soluzione chiusa: prima provaci da solo.

Esercizio 1. Completa la tavola di verità di (A OR B) AND C e di’ quando è vera.

Soluzione

Tre variabili, quindi 8 righe in ordine binario. Per precedenza la parentesi si fa prima: colonna A OR B, poi l’AND con C.

ABCA OR B(A OR B) AND C
00000
00100
01010
01111
10010
10111
11010
11111

È vera quando C è vera e almeno una fra A e B è vera: righe 011, 101, 111. Controllo: l’AND esterno con C azzera tutte le righe con C=0C = 0, e infatti la prima, la terza, la quinta e la settima riga valgono 0.

Esercizio 2. Dimostra con la tavola che NOT (A AND B) è equivalente a NOT A OR NOT B.

Soluzione
ABA AND BNOT (A AND B)NOT ANOT BNOT A OR NOT B
0001111
0101101
1001011
1110000

La quarta e l’ultima colonna coincidono in tutte le righe: sono equivalenti (è De Morgan).

Esercizio 3. NOT (A AND B) è equivalente a NOT A AND NOT B?

Soluzione

Si riconosce il tranello: è De Morgan senza lo scambio di AND in OR. Per dire di no basta una riga.

ABNOT (A AND B)NOT A AND NOT B
0011
0110
1010
1100

No. Nella riga A=1A = 1, B=0B = 0: NOT (1 AND 0) è NOT 0, cioè 1, mentre NOT 1 AND NOT 0 è 0 AND 1, cioè 0. Differiscono anche in 01. A parole: “non entrambi” è diverso da “nessuno dei due”.

Esercizio 4. Dimostra che A ⇒ B è equivalente a NOT A OR B.

Soluzione
ABA ⇒ BNOT ANOT A OR B
00111
01111
10000
11101

Stessa colonna finale. A parole: l’implicazione è vera se A è falsa (prima metà) oppure se B è vera.

Esercizio 5. Scrivi la formula della tavola seguente e semplificala se puoi.

 A B | R
-----+---
 0 0 | 0
 0 1 | 1
 1 0 | 1
 1 1 | 0
Soluzione

Righe a 1: 01 e 10. La riga 01 dà NOT A AND B, la riga 10 dà A AND NOT B. R = (NOT A AND B) OR (A AND NOT B).

È vera quando A e B sono diversi: è l’OR esclusivo (XOR), il contrario di A ⇔ B. In C, fra valori 0/1, a != b; fra interi qualunque !a != !b. Non si semplifica ulteriormente con AND, OR e NOT: i due pezzi differiscono per due variabili, non una, quindi non si raccoglie niente.

Esercizio 6. Semplifica (A AND B) OR (A AND NOT B) OR (NOT A AND NOT B).

Soluzione

I primi due pezzi differiscono solo per B, quindi si raccoglie A.

(A AND B) OR (A AND NOT B)  =  A AND (B OR NOT B)        distributiva al contrario
                            =  A AND 1                    complemento
                            =  A                          elemento neutro
A OR (NOT A AND NOT B)      =  (A OR NOT A) AND (A OR NOT B)   distributiva dell'OR
                            =  1 AND (A OR NOT B)              complemento
                            =  A OR NOT B                      elemento neutro

Controllo con la tavola:

ABA AND BA AND NOT BNOT A AND NOT BoriginaleA OR NOT B
0000111
0100000
1001011
1110011

Le ultime due colonne coincidono: l’originale è 0 solo per A=0A = 0, B=1B = 1, come A OR NOT B.

Esercizio 7. (A AND B) ⇒ A è una tautologia, una contraddizione o nessuna delle due?

Soluzione

L’implicazione è falsa solo se la premessa è vera e la conclusione falsa. A AND B vero vuol dire A vero, quindi la conclusione A è vera: il caso falso non si verifica mai.

ABA AND B(A AND B) ⇒ A
0001
0101
1001
1111

Ultima colonna tutta 1: tautologia.

Esercizio 8. Per quali interi x la condizione C !(x > 3 && x < 10) è vera? Riscrivila senza !.

Soluzione

Si riconosce un “non dentro l’intervallo”, quindi De Morgan.

!(x > 3 && x < 10)
!(x > 3) || !(x < 10)          De Morgan: il ! entra, && diventa ||
x <= 3 || x >= 10              negazione dei confronti

Vera per x≤3x \leq 3 oppure x≥10x \geq 10, falsa per xx da 4 a 9. Controllo sui bordi: con x=3x = 3, x > 3 è falso, quindi l’AND è falso e il ! dà 1; nella forma riscritta 3 <= 3 è vero. Con x=4x = 4 l’originale vale !(1 && 1), cioè 0, e la riscritta 4 <= 3 || 4 >= 10 vale 0. Vedi la figura della negazione di un intervallo.

Esercizio 9. Scrivi l’output esatto.

#include <stdio.h>

int main(void)
{
    int a = 3;
    int b = 0;
    int c = -2;

    printf("%d %d %d %d %d\n", a && b, a || b, !c, !a || (b && c), !!a);
    return 0;
}
Soluzione

In C ogni valore diverso da 0 è vero, e gli operatori logici restituiscono 0 o 1.

espressionecalcolovalore
a && b3 vero, 0 falso0
a || b3 vero, si ferma1
!c-2 è vero, il NOT dà falso0
!a || (b && c)!3 vale 0; b && c vale 0 (si ferma su b); 0 OR 00
!!a!3 vale 0, !0 vale 11

Output: 0 1 0 0 1 (verificato). Il doppio NOT !! è il modo di trasformare un intero qualunque in 0/1.

Esercizio 10. Scrivi l’output esatto. (Attenzione alle precedenze.)

#include <stdio.h>

int main(void)
{
    int x = 7;
    int y = 0;
    int z = -1;

    printf("%d %d %d %d %d\n", !x == y, x > y > z, !(x > 5) || y && z, !!z + !y, x && y || !z && x);
    return 0;
}
Soluzione

Si riconosce un esercizio di precedenze: per ogni espressione prima le parentesi implicite, poi il calcolo.

espressionecon le parentesicalcolovalore
!x <mark> y(!x) </mark> y!7 vale 0; 0 == 01
x > y > z(x > y) > z7 > 0 vale 1; 1 > -11
!(x > 5) || y && z(!(x > 5)) || (y && z)!(1) vale 0; y && z vale 0 senza guardare z; 0 || 00
!!z + !y(!(!z)) + (!y)!-1 vale 0, !0 vale 1; !0 vale 1; 1+11 + 12
x && y || !z && x(x && y) || ((!z) && x)7 && 0 vale 0; !-1 vale 0, 0 && 7 vale 0; 0 || 00

Output: 1 1 0 2 0 (verificato). Il programma compila, ma con -Wall gcc dà quattro avvisi, uno per trappola: ! applicato solo a sinistra del confronto, X<=Y<=Z che non ha il significato matematico, due volte “metti le parentesi attorno a && dentro ||”. Per questo il blocco non è marcato c.

Esercizio 11. Il programmatore vuole sapere se x è fuori dall’intervallo da 1 a 10 e scrive questo. Trova l’errore e correggilo.

#include <stdio.h>

int main(void)
{
    int x = 0;
    int fuori = x < 1 && x > 10;

    printf("x=%d fuori=%d\n", x, fuori);
    x = 11;
    fuori = x < 1 && x > 10;
    printf("x=%d fuori=%d\n", x, fuori);
    return 0;
}
Soluzione

Output (verificato):

x=0 fuori=0
x=11 fuori=0

x < 1 && x > 10 chiede un numero che sia insieme minore di 1 e maggiore di 10: non esiste, è una contraddizione, vale 0 per ogni x. Il compilatore non avvisa, quindi l’errore si trova solo ragionando. “Fuori” vuol dire “da una parte oppure dall’altra”:

int fuori = x < 1 || x > 10;

Si ricava anche con De Morgan dalla condizione “dentro”: !(x >= 1 && x <= 10) diventa x < 1 || x > 10. Con la correzione le due righe stampano fuori=1. Controllo con un valore dentro: con x=5x = 5, 5 < 1 || 5 > 10 vale 0.

Esercizio 12. Scrivi un’espressione C che vale 1 se l’int anno è bisestile: divisibile per 4 ma non per 100, oppure divisibile per 400. Poi scrivi, con De Morgan e senza !, quella che vale 1 se non è bisestile. Prova con 1900, 2000, 2024, 2026.

Soluzione

“Divisibile per 4” è anno % 4 == 0. La frase si traduce pezzo per pezzo:

(anno % 4 == 0 && anno % 100 != 0) || anno % 400 == 0

Le parentesi attorno all’&& non servono per la precedenza, ma rendono chiaro come si raggruppa (e tolgono l’avviso di gcc).

Negazione, un passo per riga:

!( (anno % 4 == 0 && anno % 100 != 0) || anno % 400 == 0 )
!(anno % 4 == 0 && anno % 100 != 0) && !(anno % 400 == 0)      De Morgan sull'||
(!(anno % 4 == 0) || !(anno % 100 != 0)) && anno % 400 != 0    De Morgan sull'&&
(anno % 4 != 0 || anno % 100 == 0) && anno % 400 != 0          negazione dei confronti
#include <stdio.h>

int main(void)
{
    int anno = 1900;
    int bis = (anno % 4 == 0 && anno % 100 != 0) || anno % 400 == 0;
    int non_bis = (anno % 4 != 0 || anno % 100 == 0) && anno % 400 != 0;

    printf("%d: bis=%d non_bis=%d\n", anno, bis, non_bis);
    anno = 2000;
    bis = (anno % 4 == 0 && anno % 100 != 0) || anno % 400 == 0;
    non_bis = (anno % 4 != 0 || anno % 100 == 0) && anno % 400 != 0;
    printf("%d: bis=%d non_bis=%d\n", anno, bis, non_bis);
    anno = 2024;
    bis = (anno % 4 == 0 && anno % 100 != 0) || anno % 400 == 0;
    non_bis = (anno % 4 != 0 || anno % 100 == 0) && anno % 400 != 0;
    printf("%d: bis=%d non_bis=%d\n", anno, bis, non_bis);
    anno = 2026;
    bis = (anno % 4 == 0 && anno % 100 != 0) || anno % 400 == 0;
    non_bis = (anno % 4 != 0 || anno % 100 == 0) && anno % 400 != 0;
    printf("%d: bis=%d non_bis=%d\n", anno, bis, non_bis);
    return 0;
}

Output (verificato):

1900: bis=0 non_bis=1
2000: bis=1 non_bis=0
2024: bis=1 non_bis=0
2026: bis=0 non_bis=1

1900 è divisibile per 100 e non per 400, quindi non è bisestile; 2000 sì per il 400. Controllo: bis e non_bis sono sempre opposti (verificato su tutti gli anni da 1 a 4000).

Esercizio 13. Scrivi l’output esatto. (Lazy evaluation.)

#include <stdio.h>

int main(void)
{
    int a = 0;
    int b = 2;
    int c = 5;
    int r1;
    int r2;
    int r3;

    r1 = a && b++;
    r2 = a || b++;
    r3 = !a && c-- > 4 || b++;
    printf("%d %d %d a=%d b=%d c=%d\n", r1, r2, r3, a, b, c);
    return 0;
}
Soluzione

Si riconosce dai ++ dentro && e ||: bisogna sapere quali parti vengono valutate davvero.

istruzionecosa si valutaabcrisultato
iniziale025
r1 = a && b++a è 0: l’AND è già falso, b++ non si esegue025r1 vale 0
r2 = a || b++a è 0, serve la destra: b++ vale 2 (vero), poi b diventa 3035r2 vale 1
r3 = ...parentesi implicite: ((!a) && ((c--) > 4)) || (b++)035
!a vale 1, serve la destra dell’AND035
c-- vale 5, 5 > 4 vale 1, poi c diventa 4; l’AND vale 1034
l’OR è già vero: b++ non si esegue034r3 vale 1

Output: 0 1 1 a=0 b=3 c=4 (verificato). gcc avvisa di mettere le parentesi attorno all’&& dentro l’||, per questo il blocco non è marcato c.

Esercizio 14. (Livello 30) La funzione maggioranza di tre variabili vale 1 quando almeno due su tre valgono 1. Scrivi la tavola, ricava la formula come somma di prodotti e semplificala.

Soluzione

Tavola, 8 righe in ordine binario:

ABCM
0000
0010
0100
0111
1000
1011
1101
1111

Righe a 1: 011, 101, 110, 111. Somma di prodotti:

M = (NOT A AND B AND C) OR (A AND NOT B AND C) OR (A AND B AND NOT C) OR (A AND B AND C)

Semplificazione. Il pezzo A AND B AND C differisce da ognuno degli altri tre per una sola variabile. Per idempotenza (X OR X = X) lo si può scrivere tre volte e accoppiarlo con ciascuno:

(NOT A AND B AND C) OR (A AND B AND C)  =  (NOT A OR A) AND B AND C    distributiva al contrario
                                        =  B AND C                      complemento, neutro
(A AND NOT B AND C) OR (A AND B AND C)  =  A AND C                      stessi passi su B
(A AND B AND NOT C) OR (A AND B AND C)  =  A AND B                      stessi passi su C
M = (A AND B) OR (A AND C) OR (B AND C)

Controllo a parole: “almeno due su tre” vuol dire che almeno una delle tre coppie è tutta vera, ed è esattamente la formula. Verificata anche su tutte le 8 righe. In C: (a && b) || (a && c) || (b && c).

Esercizio 15. (Livello 30) Mostra che (A ⇒ B) AND (B ⇒ A) è equivalente ad A ⇔ B. Poi di’ se A ⇒ B è equivalente a B ⇒ A, e se è equivalente a NOT B ⇒ NOT A.

Soluzione
ABA ⇒ BB ⇒ A(A ⇒ B) AND (B ⇒ A)A ⇔ B
001111
011000
100100
111111

Le ultime due colonne coincidono: “A e B si implicano a vicenda” vuol dire “hanno lo stesso valore”. È il “se e solo se” della definizione di equivalenza.

A ⇒ B e B ⇒ A: la terza e la quarta colonna differiscono nella riga 01 (1 contro 0) e nella riga 10, quindi non sono equivalenti.

NOT B ⇒ NOT A: con l’esercizio 4 si riscrive senza tavola.

NOT B ⇒ NOT A  =  NOT (NOT B) OR NOT A     esercizio 4: X ⇒ Y = NOT X OR Y
               =  B OR NOT A                doppia negazione
               =  NOT A OR B                commutativa
               =  A ⇒ B                     esercizio 4 al contrario

Sono equivalenti. “Se piove prendo l’ombrello” dice lo stesso di “se non ho l’ombrello allora non piove”.