Algebra di Boole
1
Algebra di Boole
• Insieme di regole algebriche della logica binaria che stanno
alla base del funzionamento dei calcolatori
• È costituita da:
– un insieme di variabili booleane A,B,C,... che possono
assumere solo i valori 1 (vero) o 0 (falso).
– un insieme di funzioni (operazioni) che operano sulle
variabili di input e danno delle variabili di output
– un insieme di leggi (assiomi) che definiscono le proprietà
delle funzioni.
2
Elementi dell’algebra di Boole
• Gli elementi dell'insieme B di un'algebra di
Boole possono essere astratti o concreti; ad
esempio possono essere numeri, proposizioni,
insiemi o reti elettriche.
3
Variabili Logiche
• Una Variabile Logica è una variabile che può
assumere solo due valori:
• True (vero, identificato con 1)
• False (falso, identificato con 0)
4
Funzioni
• Usando le variabili booleane, si possono
costruire le funzioni booleane
F(x,y,z)
che possono assumere solo due stati:
– true
– false
5
Tabella di verità
• Ogni funzione booleana è caratterizzata dalla propria
tabella di verità che riporta il suo valore per ogni
possibile configurazione delle variabili in essa
contenute.
x
y
z
F
0
0
0
0
1
1
1
1
0
0
1
1
0
0
1
1
0
1
0
1
0
1
0
1
1
0
1
1
0
1
0
0
6
Tabella di verità
• La Tabella di Verità di un’espressione
logica identifica la cosiddetta funzione
booleana.
7
Costanti booleane
• Oltre alle variabili vi sono anche le costanti
• Essendo l’Algebra Booleana definita su due
soli simboli, esistono solo due costanti:
–0
–1
8
Connettivi logici
• Le operazioni booleane fondamentali, rappresentate
dai Connettivi Logici sono:
– Congiunzione (AND )
– Disgiunzione (OR )
– Negazione (NOT )
9
Funzioni Booleane
Combinando variabili logiche mediante i connettivi logici
si ottengono le espressioni logiche.
• Un’espressione logica può essere definita in maniera
esaustiva tramite la sua Tabella di Verità, che riporta il
suo valore per ogni possibile configurazione delle
variabili in essa contenute (Vedi la sezione Algoritmi).
• La Tabella di Verità di un’espressione logica identifica
la cosiddetta funzione booleana
10
L’operatore NOT
• Il risultato è il complemento (la negazione)
dell’unica variabile
x
0
1
NOT x
1
0
11
L’operatore AND
• Il risultato è vero solo se sono vere entrambe
le variabili
a
b
0
0
1
1
0
1
0
1
a AND b
0
0
0
1
12
L’operatore OR
• Il risultato è vero solo se è vera almeno una
delle variabili
a
b
a OR b
0
0
1
1
0
1
0
1
0
1
1
1
13
L’operatore XOR
• Il risultato è vero solo se è vera solo una delle
due variabili
a
b
a XOR b
0
0
1
1
0
1
0
1
0
1
1
0
14
Priorità degli operatori
15
Proprietà delle funzioni logiche
• p. commutativa
– A AND B = B AND A
A OR B = B OR A
• p. associativa
– (A AND B) AND C = A AND (B AND C) (A OR B) OR C = A OR (B OR C)
• p. distributiva
– A AND (B OR C) = (A AND B) OR (A AND C) A OR (B AND C) = (A OR B)
AND (A OR C)
• leggi di idempotenza e complementazione
– 0 OR A=A 0 AND A=0 1 OR A=1 1 AND A=A A OR A=A A AND A=A
NOT ( NOT A)=A A OR NOT A = 1 A AND NOT A = 0
16
Leggi di De Morgan
– A AND B = NOT (( NOT A) OR ( NOT B))
– A OR B = NOT (( NOT A) AND ( NOT B))
Cioè
– NOT(A AND B) = NOT A OR NOT B
– NOT(A OR B) = NOT A AND NOT B
17
Tavole di verità ed espressioni
E’ possibile :
– data la tavola di verità ricavare l’espressione
corrispondente
– data una espressione booleana trovare la
tavola di verità corrispondente.
18
Equivalenza tra espressioni
• Due espressioni sono uguali (o logicamente
equivalenti) se il loro valore di verità è identico
per ogni assegnazione delle variabili.
• L’equivalenza può essere verificata mediante
le tabelle di verità..
19
Esempio
20
Esercizi proposti
ESERCIZIO 1
Se a=5, b=7 e c=0
Determinare se le seguenti espressioni sono
vere o false (V=1, F=0):
1. (a>0) and (b>0)
2. (3<a) and (b<2)
3. (a<=2) and (b<3)
4. (a<=2) or (b<3)
5. not(a>0) and (b>1)
6. not(a>0) or (b>1)
7. (a>1) and not(b>0)
8. not ((a>0) or (b<2))
9. (a<>5) and (c>0)
10. (a<>5) or (c>0)
11. (a<>5) and (c=0)
12. (a=5) or (c=0)
13. (a<3) and (b>0) or (c>=0)
14. (a<3) and ((b>0) or (c>=0))
15. not(a<3) and (b>0) or not(c>=0)
16. (a<3) and not(b>0) or (c>=0)
ESERCIZIO 2
Costruire le tavole di verità delle seguenti
espressioni logiche:
1. NOT (A OR B)
2. A AND NOT(B)
3. A AND B OR C
4. A AND (B OR C)
5. NOT(A) AND B OR NOT(C)
6. A AND (NOT(B) OR C)
21
Esercizi proposti
Disegnare la tavola di verità della
seguente espressione logica
NOT(A) AND (B OR NOT(C))
Dimostrare la 1° legge di De Morgan
NOT(A AND B) = NOT A OR NOT B
22