Note Ingegneria Informatica · UniTN
Programmazione 1
Esercizi
Lezione
set, giorno?
in corso

Algebra di Boole

Argomento di Programmazione 1. Fatto a lezione a settembre, deck 3.1 intero: slide 2-10 (perché serve, NOT AND OR, proprietà, tavole di verità, notazioni), slide 11-21 (precedenza ed esempi di tavole), slide 22-27 (equivalenza, De Morgan, implicazione, dalla tavola alla formula, tautologia). Prima: Espressioni, operatori e costanti (precedenze del C, lazy evaluation). Dopo: Istruzioni condizionali.

Il filo del deck:

calcolare la verità      un programma deve decidere: SE LuceRossa ALLORA Stop
   |
valori                   solo due: 1 = VERO, 0 = FALSO
   |
operatori                NOT (unario), AND, OR (binari) e le loro tavole di verità
   |
precedenza               NOT, poi AND, poi OR; le parentesi cambiano l'ordine
   |
tavole di verità         una riga per ogni combinazione: 2^n righe con n variabili
   |
equivalenza              stessa tavola  ->  De Morgan, distributive, semplificazioni
   |
altri operatori          equivalenza ⇔, implicazione ⇒
dalla tavola alla        OR delle righe a 1, ognuna come AND di variabili
formula
tautologia, contraddizione   sempre vera, sempre falsa

1Definizioni

Perché serve (slide 2-3). Un programma deve “calcolare la verità” per decidere cosa fare: un sensore che esegue SE LuceRossa ALLORA Stop ALTRIMENTI Procedi ha bisogno di sapere se LuceRossa è vera. Quasi sempre la domanda è composta (“luce rossa e nessuna ambulanza”, “pioggia oppure neve”): l’algebra di Boole è il calcolo con cui si combinano queste risposte sì/no.

Algebra di Boole (slide 4-5). Opera su variabili che assumono valori binari: 0 e 1, VERO e FALSO, bianco e nero. Come tutte le algebre ha delle operazioni per manipolarli, e sono tre: NOT, AND, OR. Si applicano a operandi che possono assumere solo valori binari: VERO è il bit 1, FALSO il bit 0.

A parole, prima delle tavole:

OperatoreTipoDefinizione (slide 6)
NOTunario (un operando)NOT A è l’opposto del valore di A
ANDbinario (due operandi)A AND B è VERO se entrambi gli operandi sono VERO
ORbinarioA OR B è VERO se almeno uno degli operandi è VERO

Tavola di verità (slide 8-9). Nelle tavole di verità si compilano i valori del risultato di un’operazione in funzione dei valori degli operandi, per ogni combinazione possibile (VERO → 1, FALSO → 0). Con nn variabili le combinazioni sono 2n2^n, perché ogni variabile raddoppia i casi: 2 righe per una variabile, 4 per due, 8 per tre, 16 per quattro.

 A | NOT A        A B | A AND B        A B | A OR B
---+------       -----+--------       -----+-------
 0 |   1          0 0 |    0            0 0 |   0
 1 |   0          0 1 |    0            0 1 |   1
                  1 0 |    0            1 0 |   1
                  1 1 |    1            1 1 |   1

Per ricordarle: AND è 1 in una sola riga (tutti 1), OR è 0 in una sola riga (tutti 0).

Un modo di vederle con un disegno, che non è nelle slide ma aiuta con De Morgan: il rettangolo sono tutti i casi possibili, il cerchio A i casi in cui A è vera, il cerchio B quelli in cui B è vera. La parte colorata è dove l’espressione vale 1.

NOT A è tutto il fuori del cerchio A; A AND B è la parte comune ai due cerchi; A OR B è tutto quello che sta in almeno un cerchio.

Notazioni (slide 10). Lo stesso operatore si scrive in modi diversi a seconda del contesto:

parolaCalgebra
NOTNOT A!AAˉ\bar{A}
ANDA AND BA && BA×BA \times B (o A⋅BA \cdot B)
ORA OR BA || BA+BA + B

La notazione algebrica spiega le tavole: AND si comporta come il prodotto di 0 e 1 (1⋅1=11 \cdot 1 = 1, ogni altro prodotto è 0), OR come una somma in cui 1+11 + 1 resta 1 (non c’è un valore 2).

Proprietà (slide 7).

La seconda distributiva è quella che sorprende, quindi va controllata. Tre variabili, otto righe, una colonna per ogni pezzo:

ABCB AND CA OR (B AND C)A OR BA OR C(A OR B) AND (A OR C)
00000000
00100010
01000100
01111111
10001111
10101111
11001111
11111111

La quinta e l’ultima colonna coincidono riga per riga. L’intuizione: quando A=1A = 1 entrambi i lati valgono 1 (un OR con un 1 dentro è 1); quando A=0A = 0 entrambi si riducono a B AND C.

Altre identità che non sono sulle slide ma si verificano con una tavola da due o quattro righe, e servono per semplificare:

A AND 1 = A          A OR 0 = A            elemento neutro
A AND 0 = 0          A OR 1 = 1            elemento assorbente
A AND A = A          A OR A = A            idempotenza
A AND NOT A = 0      A OR NOT A = 1        complemento
NOT (NOT A) = A                            doppia negazione
A OR (A AND B) = A   A AND (A OR B) = A    assorbimento

L’assorbimento a parole: “A, oppure A e B insieme” è vero esattamente quando A è vero, perché il secondo caso è già dentro il primo.

Precedenza (slide 11-13). Calcolare un’espressione logica vuol dire trovarne il valore (1 o 0) a partire dai valori dei singoli operandi. Senza parentesi si valuta:

  1. prima NOT;
  2. poi AND;
  3. per ultimo OR.

Le parentesi possono modificare questa sequenza. È la stessa idea di ×\times prima di ++: AND è il “prodotto”, OR la “somma”, e A OR B AND C si legge A OR (B AND C) come a+bca + bc si legge a+(bc)a + (bc). In C vale lo stesso ordine: ! lega più di &&, che lega più di ||.

Esempio: con A=1A = 1, B=0B = 0, C=0C = 0, A OR B AND C vale 1 OR (0 AND 0) cioè 1. Controesempio: chi lo legge da sinistra a destra calcola (1 OR 0) AND 0, cioè 0, e sbaglia.

Equivalenza (slide 22). Due espressioni booleane sono equivalenti se e solo se hanno la medesima tavola di verità. Il “se e solo se” lavora in due versi:

Esempio: NOT Y AND (Y OR NOT X) e NOT X AND NOT Y sono equivalenti (si vede sotto, negli esempi del prof). Controesempio: NOT (A AND B) e NOT A AND NOT B non lo sono, basta la riga A=1A = 1, B=0B = 0: la prima vale NOT 0 cioè 1, la seconda 0 AND 1 cioè 0.

Altri operatori (slide 25).

equivalenza                    implicazione
 A B | A ⇔ B                    A B | A ⇒ B
-----+------                   -----+------
 0 0 |   1                      0 0 |   1
 0 1 |   0                      0 1 |   1
 1 0 |   0                      1 0 |   0
 1 1 |   1                      1 1 |   1

Tautologia e contraddizione (slide 27).

Nella tavola: l’ultima colonna è tutta 0 (contraddizione) o tutta 1 (tautologia). Un’espressione che ha almeno un 1 e almeno uno 0, come A AND B, non è né l’una né l’altra. In un programma una condizione che è una contraddizione rende il ramo irraggiungibile (esercizio 11), una tautologia in un while dà un ciclo infinito.

2Concetti

2.1Vero e falso in C

Il deck parla di 0 e 1; il C è più largo, come già visto in Espressioni, operatori e costanti:

Due esempi, il secondo con numeri che non sono 0 e 1:

#include <stdio.h>

int main(void)
{
    printf("%d %d %d\n", !0, !7, !-3);
    printf("%d %d %d\n", 5 && -2, 0 || 0, 4 || 0);
    printf("%d %d\n", 3 > 2, (3 > 2) + (4 > 1));
    return 0;
}

Output (verificato):

1 0 0
1 0 1
1 2
espressioneperchévalore
!00 è falso, il NOT dà vero1
!77 è vero, il NOT dà falso0
!-3-3 è vero (diverso da 0)0
5 && -2entrambi diversi da 01
0 || 0nessuno vero0
4 || 0almeno uno vero1
3 > 2il confronto è vero1
(3 > 2) + (4 > 1)i confronti sono int, 1+11 + 12

Controesempio: 3 < x < 10 non dice “x fra 3 e 10”. Si valuta da sinistra: 3 < x dà 0 o 1, e 0 o 1 è sempre minore di 10. Con x=20x = 20 vale 1:

#include <stdio.h>

int main(void)
{
    int x = 20;

    printf("%d\n", 3 < x < 10);
    printf("%d\n", 3 < x && x < 10);
    return 0;
}

Stampa 1 e poi 0 (verificato). Il blocco non è marcato c perché con -Wall gcc avvisa: comparisons like 'X<=Y<=Z' do not have their mathematical meaning. La forma giusta è la seconda, con &&.

2.2Precedenza in C, con i confronti

Nelle condizioni del C ci sono anche i confronti e l’aritmetica. Dalla tabella delle precedenze di Espressioni, operatori e costanti, dal più forte al più debole:

!  ++  --  -(unario)        unari
*  /  %
+  -
<  <=  >  >=                 confronti
==  !=
&&
||

Quindi x > 0 && x < 10 || y <mark> 0 si legge ((x > 0) && (x < 10)) || (y </mark> 0): prima i confronti, poi &&, per ultimo ||. Come in algebra di Boole.

L’insidia è il !, che lega più dei confronti. Con a che vale 0 e b che vale 5:

#include <stdio.h>

int main(void)
{
    int a = 0;
    int b = 5;

    printf("%d\n", !a > b);
    printf("%d\n", !(a > b));
    return 0;
}

Stampa 0 e poi 1 (verificato; gcc avvisa logical not is only applied to the left hand side of comparison). !a > b è (!a) > b, cioè 1 > 5, cioè 0. Per negare il confronto servono le parentesi: !(a > b), cioè !0, cioè 1. Meglio ancora scrivere a <= b.

Ricordare anche la lazy evaluation (Espressioni, operatori e costanti, slide 62 del deck 2.2): && e || si valutano da sinistra e si fermano appena il risultato è deciso. In A && B con A falso, B non si valuta; in A || B con A vero, nemmeno. Se B contiene un ++, l’incremento non avviene (esercizio 13).

2.3Leggi di De Morgan

(slide 22-24) Le leggi come le scrive il prof:

1.  A AND B  =  NOT ((NOT A) OR (NOT B))
2.  A OR B   =  NOT ((NOT A) AND (NOT B))

La forma che si usa di più, equivalente (si nega tutto da entrambe le parti e si usa la doppia negazione), è quella che nega una condizione intera:

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

L’intuizione. “Non è vero che ho chiavi e portafoglio” vuol dire “mi manca almeno una delle due”: non ho le chiavi oppure non ho il portafoglio. “Non è vero che piove o nevica” vuol dire che non piove e non nevica. Con le regioni:

In alto: il fuori della parte comune (NOT (A AND B)) è lo stesso che “fuori da A, oppure fuori da B”. In basso: il fuori di tutti e due i cerchi (NOT (A OR B)) è la parte che sta fuori da A e fuori da B.

Regola pratica: il NOT entra nella parentesi, nega ogni pezzo, e AND e OR si scambiano.

Esempi in C, dal più facile:

Controesempio: dimenticare lo scambio. NOT (A AND B) non è NOT A AND NOT B: con A=1A = 1, B=0B = 0 la prima vale 1 e la seconda 0 (esercizio 3).

Dimostrazione della legge 1 con la tavola (slide 23-24)

Si compila una colonna per ogni sotto-espressione, poi si confronta l’ultima con A AND B.

ABNOT ANOT B(NOT B) OR (NOT A)NOT ((NOT B) OR (NOT A))A AND B
0011100
0110100
1001100
1100011

Le ultime due colonne coincidono in tutte e quattro le righe, quindi le espressioni sono equivalenti. La slide scrive (NOT B) OR (NOT A) invece di (NOT A) OR (NOT B): è lo stesso per la commutativa.

Dimostrazione della legge 2 con la tavola (esercizio della slide 22)
ABNOT ANOT B(NOT A) AND (NOT B)NOT ((NOT A) AND (NOT B))A OR B
0011100
0110011
1001011
1100011

Le ultime due colonne coincidono: equivalenti.

Entrambe verificate anche in C, stampando le colonne con due cicli annidati (il while arriva in Ciclo while ed esempi: qui basta leggere l’output):

#include <stdio.h>

int main(void)
{
    int a = 0;

    printf("A B | A&&B  !(!A||!B) | A||B  !(!A&&!B)\n");
    while (a <= 1) {
        int b = 0;
        while (b <= 1) {
            printf("%d %d |  %d        %d     |  %d        %d\n",
                   a, b, a && b, !(!a || !b), a || b, !(!a && !b));
            b++;
        }
        a++;
    }
    return 0;
}

Output:

A B | A&&B  !(!A||!B) | A||B  !(!A&&!B)
0 0 |  0        0     |  0        0
0 1 |  0        0     |  1        1
1 0 |  0        0     |  1        1
1 1 |  1        1     |  1        1

2.4Negare una condizione con un intervallo

Il caso che esce di più: “x non è fra 4 e 9”. La condizione “x fra 4 e 9” è x > 3 && x < 10; la sua negazione con De Morgan è x <= 3 || x >= 10.

I punti pieni sono i valori di x per cui la condizione è vera. La negazione prende esattamente i punti vuoti della riga sopra: nessun buco, nessun punto in comune. Si vede anche perché la negazione di un “dentro” (con &&) è un “fuori” (con ||): il fuori sono due pezzi separati, e un numero non può stare in tutti e due.

Controesempio: negare x > 3 con x < 3 dimentica il 3, e negare x < 10 con x > 10 dimentica il 10. Verifica sui due bordi:

#include <stdio.h>

int main(void)
{
    int x = 3;

    printf("%d %d %d\n", !(x > 3 && x < 10), x <= 3 || x >= 10, x < 3 || x > 10);
    x = 10;
    printf("%d %d %d\n", !(x > 3 && x < 10), x <= 3 || x >= 10, x < 3 || x > 10);
    return 0;
}

Output (verificato):

1 1 0
1 1 0

La terza colonna, quella sbagliata, vale 0 proprio sui bordi.

2.5Equivalenza e implicazione in C

Non ci sono operatori ⇔ e ⇒ in C. Si scrivono con quelli che ci sono:

Attenzione all’ultimo punto: a == b e a != b confrontano i numeri, non i valori di verità. Con a che vale 2 e b che vale 5 sono entrambi veri, quindi lo XOR dovrebbe dare 0, ma a != b dà 1. Si risolve portando prima tutto a 0/1 con il !:

#include <stdio.h>

int main(void)
{
    int a = 2;
    int b = 5;

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

Output (verificato):

1 0
1 1

!a e !b valgono 0 tutti e due, quindi !a != !b è 0, il risultato giusto. La seconda riga: le due forme dell’implicazione danno lo stesso valore, come deve essere.

2.6Dalla tavola alla formula

(slide 26) Data una tavola di verità è sempre possibile calcolare l’espressione logica:

  1. prendi le righe in cui il risultato è 1;
  2. per ogni riga scrivi l’AND delle variabili, negando quelle che valgono 0 (la riga A=0, B=1 diventa NOT A AND B);
  3. metti in OR tutti questi pezzi.

Perché funziona: ogni pezzo è un AND, quindi è vero in una sola riga, quella da cui l’hai costruito (NOT A AND B è 1 solo per A=0A = 0, B=1B = 1). L’OR dei pezzi è vero dove è vero almeno un pezzo, cioè esattamente nelle righe scelte. Si chiama somma di prodotti (OR di AND). Se la tavola non ha nessun 1, l’espressione è una contraddizione e la formula è semplicemente 0.

Il risultato è corretto ma spesso lungo: dopo si semplifica con le identità (esempio della slide 26 sotto, esercizi 6 e 14).

3Metodo

Compilare una tavola di verità.

  1. Conta le variabili nn e scrivi le 2n2^n righe in ordine binario (000, 001, 010, … 111): così non ne salti nessuna. L’ultima variabile alterna 0 1 0 1, quella prima alterna a coppie, la prima a blocchi di metà.
  2. Metti le parentesi implicite con la precedenza NOT > AND > OR.
  3. Aggiungi una colonna per ogni sotto-espressione, dalle più interne verso l’esterno.
  4. Calcola colonna per colonna, usando solo le colonne già fatte.
  5. L’ultima colonna è l’espressione completa. Controllo: se l’espressione è un AND fuori, gli 1 devono essere pochi; se è un OR, gli 0.

Dimostrare un’equivalenza. Tavola delle due espressioni sulle stesse righe, confronto dell’ultima colonna riga per riga. Per dimostrare che non sono equivalenti basta una riga diversa: scrivila con i valori delle variabili e i due risultati.

Semplificare un’espressione.

  1. Cerca coppie di pezzi che differiscono per una sola variabile negata, come A AND B e A AND NOT B: raccogli (distributiva al contrario) e usa il complemento, resta A.
  2. Cerca un pezzo e la sua negazione in OR: A OR (NOT A AND X) diventa A OR X (distributiva dell’OR, complemento, neutro).
  3. Usa assorbimento, neutro e idempotenza per togliere i pezzi inutili.
  4. Controlla il risultato con la tavola: deve avere la stessa ultima colonna dell’originale.

Negare una condizione C (serve per scrivere la condizione di uscita di un while, o il ramo else).

  1. De Morgan: il ! entra, && diventa || e viceversa.
  2. Ogni confronto si inverte: < diventa >=, > diventa <=, x == y diventa x != y e viceversa.
  3. Controlla un valore dentro e i valori sui bordi.

Calcolare un’espressione C a mano.

  1. Metti le parentesi implicite: unari, aritmetica, confronti, uguaglianze (a == b, a != b), &&, ||.
  2. Valuta da sinistra && e ||, fermandoti appena il risultato è deciso: la parte non valutata non esegue i suoi ++ e --.
  3. Ogni !, confronto, && e || produce 0 o 1; nei conti successivi si usa quel numero.

4Esempi svolti a lezione

4.1Precedenza su NOT Y AND Y OR NOT X

(slide 11-12) Si mettono le parentesi un livello alla volta, applicando le regole di precedenza:

NOT Y AND Y OR NOT X
(NOT Y) AND Y OR (NOT X)              prima i NOT
((NOT Y) AND Y) OR (NOT X)            poi l'AND
(((NOT Y) AND Y) OR (NOT X))          infine l'OR

La slide si ferma qui. Vale la pena finire il conto: (NOT Y) AND Y è una contraddizione, sempre 0, e 0 OR (NOT X) è NOT X (elemento neutro dell’OR). Tutta l’espressione equivale a NOT X. Controllo con la tavola:

XYNOT XNOT Y(NOT Y) AND Y((NOT Y) AND Y) OR (NOT X)
001101
011001
100100
110000

L’ultima colonna è uguale a NOT X.

4.2Tavola di NOT Y AND (Y OR NOT X)

(slide 13-19) Stessa espressione con una parentesi in più: le parentesi modificano la sequenza di precedenza, e l’OR adesso si fa prima dell’AND. Il disegno con gli alberi mostra la differenza: l’operatore in cima è quello che si calcola per ultimo.

Il prof costruisce la tavola una colonna alla volta, con l’ordine di righe 10, 01, 00, 11:

XYNOT XNOT YY OR NOT XNOT Y AND (Y OR NOT X)
100100
011010
001111
110010

Passo per passo, come nelle slide 14-19:

  1. colonne NOT X e NOT Y: si rovesciano X e Y;
  2. colonna Y OR NOT X: 0 solo nella prima riga, dove sia YY sia NOT X valgono 0;
  3. ultima colonna: AND fra NOT Y e Y OR NOT X, 1 solo dove entrambe sono 1, cioè la terza riga.

È vera solo per X=0X = 0, Y=0Y = 0: equivale a NOT X AND NOT Y. Le parentesi hanno cambiato il risultato: senza, l’espressione era NOT X, vera anche per X=0X = 0, Y=1Y = 1.

Verifica in C, con !, && e || (anche qui il while serve solo a stampare tutte le righe):

#include <stdio.h>

int main(void)
{
    int x = 0;

    printf("X Y | NOT Y AND (Y OR NOT X)\n");
    while (x <= 1) {
        int y = 0;
        while (y <= 1) {
            printf("%d %d | %d\n", x, y, !y && (y || !x));
            y++;
        }
        x++;
    }
    return 0;
}

Output (verificato):

X Y | NOT Y AND (Y OR NOT X)
0 0 | 1
0 1 | 0
1 0 | 0
1 1 | 0

4.3Tavola di D = A AND NOT (B OR C)

(slide 20-21) Tre variabili, otto righe in ordine binario. Colonne: prima la parentesi interna B OR C, poi il suo NOT, poi l’AND con A.

ABCB OR CNOT (B OR C)D
000010
001100
010100
011100
100011
101100
110100
111100

D è vera solo quando A è vera e B e C sono entrambe false. Per De Morgan NOT (B OR C) è NOT B AND NOT C, quindi D = A AND NOT B AND NOT C, che si legge direttamente dalla riga 100. Controllo di buon senso: le prime quattro righe hanno A=0A = 0 e l’AND con 0 dà 0, quindi bastava guardare le ultime quattro.

4.4Dalla tavola alla formula, e la “forma più compatta”

(slide 26)

 A B | C
-----+---
 0 0 | 0
 0 1 | 1      NOT A AND B
 1 0 | 1      A AND NOT B
 1 1 | 1      A AND B

Somma di prodotti: C = (NOT A AND B) OR (A AND NOT B) OR (A AND B).

La slide chiede se si conosce una forma più compatta. Guardando la tavola, C è 0 solo quando A e B sono entrambe 0: è la tavola dell’OR. Quindi C = A OR B. Con l’algebra, un passo per riga:

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

5Esercizi tipo esame

In una pagina a parte, dal più facile al livello del 30: Algebra di Boole (esercizi).

6Errori tipici

7Domande