Lezione 06 · Algebra booleana¶

Un calcolatore deve saper fare i conti, ma anche ragionare: decidere se una condizione è vera o falsa e dedurne nuove verità. L'algebra di Boole è lo strumento matematico che rende possibile questo ragionamento automatico. È la base dei circuiti del processore e delle condizioni che scrivi negli if di Python.

Il ragionamento logico¶

La logica studia le regole del ragionamento. Un esempio classico è il sillogismo di Aristotele: da due premesse si deduce una conclusione.

Tutti gli uomini sono mortali, tutti i Greci sono uomini, quindi tutti i Greci sono mortali.

Lo schema è: se A implica B, e B implica C, allora A implica C. Anche il ragionamento matematico funziona così: se X > Y e Y > Z, allora X > Z.

Ragionare significa due cose:

• elaborare dei fatti (verità) sul mondo;
• dedurre nuove verità applicando regole logiche, cioè degli algoritmi.

L'aritmetica è facile da automatizzare (esistevano già calcolatrici meccaniche come la Pascalina). Il ragionamento logico è più difficile. Nel 1847 George Boole notò che anche il ragionamento sui fatti si può scrivere come un'algebra, con operazioni e regole simili a quelle dei numeri.

Dai fatti agli insiemi¶

I fatti si esprimono con predicati, cioè frasi vere o false:

• "Marco è un mammifero" → vero (Marco appartiene all'insieme dei mammiferi);
• "Marco è un cavallo" → falso.

Indichiamo con:

• Ø l'insieme vuoto: i fatti che non esistono, cioè le cose false;
• 1 l'insieme totale (l'"universo"): i fatti veri;
• + l'unione di insiemi (⋃);
• * l'intersezione di insiemi (⋂).

Se leggi Ø come 0, queste operazioni sembrano la somma e il prodotto dei numeri. C'è una sola eccezione: 1 + 1 = 1 (non 2). La conclusione è importante: la logica si può trattare come un'algebra, e quindi si può automatizzare.

Variabili booleane¶

Un'algebra booleana lavora su variabili booleane (o logiche), che possono assumere solo due valori:

È adatta a descrivere eventi binari: una lampadina è accesa (1) o spenta (0). In Python conosci già il tipo bool, con i valori True e False.

Definizione di algebra di Boole¶

Prendiamo un insieme V che contiene almeno gli elementi 0 e 1. È un'algebra di Boole se su V sono definite tre operazioni:

• somma logica + (operazione binaria: prende due elementi e ne restituisce uno);
• prodotto logico • (operazione binaria);
• complemento o inversione ¬ (operazione unaria: prende un solo elemento).

e se valgono questi assiomi:

Altre proprietà¶

Dagli assiomi si ricavano altre proprietà utili per semplificare le espressioni.

Ad esempio l'assorbimento della somma si dimostra così: x + x • y = x • 1 + x • y = x • (1 + y) = x • 1 = x.

Le leggi di De Morgan¶

Le leggi di De Morgan dicono come si nega una somma o un prodotto: si negano i singoli termini e si scambia + con •. Verifichiamo la prima con la tabella di verità:

Le due colonne in grassetto sono uguali riga per riga: le due espressioni sono equivalenti.

Diverse algebre di Boole¶

La stessa struttura si può interpretare in modi diversi: algebra binaria, algebra degli insiemi, algebra delle proposizioni, algebra delle reti (circuiti).

Le proposizioni sono frasi che possono essere vere o false. Esempio:

• (a) "In questo momento sta piovendo";
• (b) "In questo momento non sta piovendo": b = NOT a;
• © "Sta piovendo oppure non sta piovendo": c = a OR (NOT a) = vero sempre. È una tautologia;
• (d) "Sta piovendo e non sta piovendo": d = a AND (NOT a) = falso sempre. È una contraddizione.

Gli operatori logici¶

Gli operatori (o connettivi) logici combinano variabili booleane e restituiscono ancora un valore booleano.

AND, OR, NOT¶

AND (congiunzione, simboli • o ∧, spesso sottinteso: ab = a • b): è vero se e solo se entrambi gli operandi sono veri. OR (disgiunzione o inclusione, simboli + o ∨): è vero se almeno uno degli operandi è vero. NOT (negazione, simbolo ¬): restituisce il valore opposto.

NAND, NOR, XOR, XNOR¶

• NAND e NOR sono AND e OR seguiti da NOT.
• XOR (OR esclusivo) è vero quando gli operandi sono diversi: "o l'uno o l'altro, ma non entrambi".
• XNOR è vero quando gli operandi sono uguali.

Operatori bit a bit¶

Gli stessi operatori si possono applicare a due stringhe di bit, posizione per posizione (in inglese bitwise). Ogni operatore corrisponde a una porta logica, il componente base dei circuiti digitali.

    00001101          00001101
AND 11101100       OR 11101100      NOT 00001101
  = 00001100        = 11101101        = 11110010

Controlla colonna per colonna: nell'AND esce 1 solo dove entrambi i bit sono 1; nell'OR esce 0 solo dove entrambi sono 0; il NOT inverte ogni bit.

Funzioni booleane e tabella di verità¶

Una funzione booleana F(x₁, …, xₙ) prende n variabili booleane e restituisce 0 o 1. Il modo più completo per descriverla è la tabella di verità: elenca tutte le combinazioni dei valori in ingresso e il valore della funzione per ciascuna.

Esempio: superare l'esame¶

Uno studente supera l'esame se vale almeno una di queste condizioni:

• supera l'esonero e la prova orale;
• è sufficiente allo scritto di un appello regolare e supera la prova orale.

Assegniamo una variabile a ogni evento: a = esonero superato, b = scritto regolare superato, c = orale superato. Con 3 variabili ci sono 2³ = 8 combinazioni. La funzione "superamento esame" è S(a, b, c) = (a + b) • c:

S = 1 solo se lo studente supera l'orale e almeno una tra esonero e scritto.

Espressioni logiche¶

Una funzione booleana si può scrivere anche come espressione logica, combinando con gli operatori:

• variabili booleane;
• le costanti 0 (falso) e 1 (vero);
• altre espressioni.

Esempi: (a + b) • c, oppure ab + c(d + ae).

Insiemi funzionalmente completi¶

AND, OR e NOT formano un insieme funzionalmente completo: con questi tre operatori si può scrivere qualunque funzione logica. Grazie alle leggi di De Morgan bastano anche solo {AND, NOT} oppure {OR, NOT}. Ad esempio a + b = ¬(¬a • ¬b).

Precedenza degli operatori¶

Come in aritmetica la moltiplicazione viene prima della somma, anche in logica c'è un ordine:

1. le parentesi;
2. NOT (¬);
3. AND (∧, •);
4. OR (∨, +).

Python usa lo stesso ordine: not prima di and, and prima di or.

Dall'espressione alla tabella di verità¶

Prendiamo F(a, b, c) = a ∧ b ∨ ¬c. Si procede così:

1. si contano le variabili diverse (qui 3: a, b, c);
2. si scrivono tutte le 2³ = 8 combinazioni;
3. si aggiunge una colonna per ogni operazione, nell'ordine di precedenza: prima ¬c, poi a ∧ b, infine l'OR tra le due.

Puoi far costruire la stessa tabella a Python. Tre cicli for annidati generano le 8 combinazioni; int() trasforma True/False in 1/0.

print('a b c | a∧b ¬c | F')
for a in range(2):
    for b in range(2):
        for c in range(2):
            a_e_b = int(a and b)
            non_c = int(not c)
            F = int(a_e_b or non_c)
            print(a, b, c, '|', a_e_b, '  ', non_c, ' |', F)

Prova a cambiare la riga di F con un'altra espressione, ad esempio int((a or b) and c): ottieni la tabella dell'esame.

Equivalenti, complementari, duali¶

Espressioni equivalenti. F1 e F2 sono equivalenti se hanno lo stesso valore per ogni combinazione degli ingressi: ad ingressi uguali, uscite uguali. Esempio: x + ¬x • y e x + y.

Espressioni complementari. F1 e F2 sono complementari se hanno valori opposti per ogni combinazione: dove una vale 1 l'altra vale 0, e viceversa. Esempio: F1 = ab e F2 = a NAND b.

Espressioni duali. La duale di un'espressione si ottiene scambiando + con • e 0 con 1 (le variabili e le negazioni restano come sono). Esempio: la duale di x + 0 = x è x • 1 = x. Per questo nelle tabelle delle proprietà ogni regola per la somma ha una "gemella" per il prodotto.

Errori frequenti negli esercizi¶

Esercizi¶

Esercizio 1 · Operazioni bit a bit. Date le stringhe A = 10110010 e B = 01100111, calcola A AND B, A OR B e NOT A.

# Puoi verificare la tua risposta qui

    10110010          10110010
AND 01100111       OR 01100111      NOT 10110010
  = 00100010        = 11110111        = 01001101

A = '10110010'
B = '01100111'
e = ''
o = ''
n = ''
for i in range(len(A)):
    e = e + str(int(A[i] == '1' and B[i] == '1'))
    o = o + str(int(A[i] == '1' or B[i] == '1'))
    n = n + str(int(A[i] == '0'))
print('AND:', e)
print('OR: ', o)
print('NOT:', n)

Esercizio 2 · Tabella di verità. Costruisci la tabella di verità di F(a, b, c) = (a ∨ ¬b) ∧ (b ∨ c), con le colonne intermedie. Per quante combinazioni F vale 1?

# Puoi verificare la tua risposta qui

for a in range(2):
    for b in range(2):
        for c in range(2):
            F = int((a or not b) and (b or c))
            print(a, b, c, F)

Esercizio 3 · Dal testo alla funzione. Il cancello di un garage si apre (A = 1) se il proprietario preme il telecomando (t) e il codice del telecomando è valido (k), oppure se viene premuto il pulsante di emergenza (e). Scrivi l'espressione logica di A, costruisci la tabella di verità e verifica con la seconda distributiva che A = (t + e) • (k + e).

# Puoi verificare la tua risposta qui

for t in range(2):
    for k in range(2):
        for e in range(2):
            A1 = int((t and k) or e)
            A2 = int((t or e) and (k or e))
            print(t, k, e, A1, A2, A1 == A2)

Verifica¶