4 Algebra Di Boole

1. 1Piero Demichelis
Algebra di Boole

2. 2Piero Demichelis
La Logica Booleana
•Nel XIX secolo un matematico inglese, George Boole, si
occupò della possibilità di ricondurre il ragionamento al
rigore delle costruzioni matematiche, sviluppando l'algebra
che ancor oggi porta il suo nome.
•Gli studi di Boole rimasero semplici esercizi teorici finché,
all'inizio del ‘900, apparvero i primi dispositivi elettrici di
commutazione (relays) e si rese necessario un supporto
teorico per trattare questo tipo di circuiti.

3. 3Piero Demichelis
La Logica Booleana
•Boole poneva alla base del ragionamento le asserzioni :
queste possono essere solo vere o false, assumendo quindi
due soli stati (0 e 1).
•Anche un circuito di commutazione può assumere solo due
stati: chiuso (OFF) oppure aperto (ON).
•Da qui dunque l'analogia, e la possibilità di correlare
situazioni apparentemente così differenti.

4. 4Piero Demichelis
Variabili Booleane
•L'algebra booleana opera su variabili x1, x2, …….., xn che
possono assumere soltanto due valori: 0 e 1. Queste
variabili prendono il nome di variabili logiche o booleane.

•Con esse si possono rappresentare eventi tipicamente
binari: per esempio, un'affermazione può essere
vera (true = 1) oppure falsa (false = 0),
un interruttore può essere
aperto (ON = 1) oppure chiuso (OFF = 0),

ecc.

5. 5Piero Demichelis
Funzioni Booleane
•Sulle variabili booleane può essere definita una funzione,
detta funzione booleana, o funzione logica,
F (x1, x2, …….., xn),

la quale, in corrispondenza di ogni n-pla xi, assume
soltanto valori 0 e 1.
•Una particolare funzione booleana F è definita quando ad
essa è assegnata la tavola della verità, tabella in cui è
specificato il valore che assume F in corrispondenza di
ogni combinazione delle variabili x1, x2, …….., xn.

6. 6Piero Demichelis
Tavola della Verità: esempio
FVV
VFV
FVF
FFF
F(x1, x2)x2x1

7. 7Piero Demichelis
Funzioni Booleane
•Il numero di combinazioni di n variabili è 2
n
.
•Poiché per ogni combinazione delle n variabili una funzione
può assumere 2 valori, 0 oppure 1, si possono avere 2
2
n

funzioni diverse di n variabili.
•Ad esempio con 4 variabili si hanno 2
4
= 16 combinazioni e
2
16
= 65.536 possibili funzioni.

8. 8Piero Demichelis
Esempio di Funzione Booleana
•In una stazione un treno parte se e solo se il
semaforo è verde e il capotreno ha segnalato il via.
•Variabili logiche:
T: vale 1 (vero) se il treno parte;
S: vale 1 (vero) se il semaforo è verde;
C: vale 1 (vero) se il capotreno ha dato il via.
•Tavola di verità:
111
001
010
000
TCS

9. 9Piero Demichelis
Operatori Booleani
•Sulle variabili logiche agiscono gli operatori logici o
booleani.
•Operatori fondamentali
AND ( Ù ) prodotto logico
OR ( Ú ) somma logica
NOT (Ø) negazione logica (complementazione)
•Gli operatori di somma e prodotto logico godono della
proprietà associativa e distributiva come gli analoghi
dell'algebra numerica.

10. 10Piero Demichelis
Operatori Booleani
Operatore AND Operatore OR
FV
VF
Ø AA
VVV
VFV
VVF
FFF
A Ú BBA
VVV
FFV
FVF
FFF
A Ù BBA
Operatore NOT

11. 11Piero Demichelis
Precedenza degli Operatori
•Gerarchia degli operatori:

NOT > AND > OR

•L’ordine può essere modificato tramite l’uso delle
parentesi.
•Esempi:

f = A Ù B Ù C Ú A Ù B
f = A Ù B Ù ( C Ú A Ù B )

12. 12Piero Demichelis
Espressioni Booleane
•Un insieme di variabili booleane, a cui siano applicati
gli operatori logici AND, OR e NOT, prende il nome di
espressione booleana o espressione logica T .
•Una espressione T corrisponde e può rappresentare
quella funzione logica F che assume valore 1 in
corrispondenza di quelle combinazioni di valori delle
variabili per cui T = 1 e assume valore 0 in
corrispondenza di quelle per cui T = 0.

13. 13Piero Demichelis
Notazione
•Per motivi pratici, la notazione viene così semplificata:
–AND •
–OR +
–NOT oppure ’
•Esempio:
A Ú (Ø B )
–diventa:
A + B oppure A + B’

14. 14Piero Demichelis
Operatori Booleani non elementari
NAND (NOT AND)
FVV
VFV
VVF
VFF
A BBA
NOR (NOT OR)
FVV
FFV
FVF
VFF
A + BBA•
Falso se A e B sono veriVero se A e B sono falsi

15. 15Piero Demichelis
Operatori Booleani non elementari
EXOR (OR esclusivo)EXNOR (OR esclusivo negato)
Vero se A diverso da B Vero se A uguale a B
A
AÅB = A • B + A • B AÅB = A • B + A •
B
FVV
VFV
VVF
FFF
A Å BBA
VVV
FFV
FVF
VFF
A Å BBA

16. 16Piero Demichelis
Espressione duale

•Una espressione T
b
è detta duale di una espressione T
a

se è ottenuta da quest'ultima sostituendo l'operatore
AND con l'operatore OR, e viceversa, e la cifra 0 con la
cifra 1, e viceversa.
•Esempio:
T
a
= a • c + a • b + 0
T
b
= T
ad
= (a + c) • (a + b) • 1

17. 17Piero Demichelis
Teoremi

•I teoremi dell’algebra logica possono essere utilizzati per
dedurre espressioni che abbiano un minor numero di termini
(semplificazione delle espressioni logiche).
•Al contrario dell'algebra ordinaria, dove non è possibile
dimostrare i teoremi sostituendo alle variabili tutti i valori
che possono assumere, nell'algebra booleana i teoremi sono
dimostrabili per “induzione completa”, cioè verificandone la
validità per tutte le combinazioni di valori (0 o 1) delle
variabili.
•Per ogni teorema esiste il teorema duale, ottenuto
applicando la regola di dualità. Si può dimostrare che,
provata la validità di un teorema, risulta provata la validità
anche del teorema duale.

18. 18Piero Demichelis
Teoremi
1.Proprietà commutativa
A × B = B × A
A + B = B + A
4.Proprietà associativa
A × B × C = (A × B) × C = A × (B × C)
A + B + C = (A + B) + C = A + (B +
C)
7.Proprietà distributiva
A × ( B + C ) = A × B + A × C
A + ( B × C ) = ( A + B ) × ( A + C )

19. 19Piero Demichelis
Teoremi
l A × F = F A × V = A
l A + F = A A + V = V
l A × A = F A + A = V

l A = A A × A = A A + A = A
l A + A × B = A
l A × ( A + B ) = A
l A + A × B = A + B
l A × ( A + B ) = A × B

20. 20Piero Demichelis
Teorema di De Morgan
f ( a, b, ..., z; +, × ) = f ( a, b, ..., z; × , + )
Esempi:
A + B = ( A × B )
( A + B ) = A × B
( A × B ) = A + B

21. 21Piero Demichelis
Espressione canonica
•Un problema logico viene espresso mediante frasi che
esprimono le condizioni che devono essere soddisfatte
affinché si verifichi qualche evento.
•Avendo enucleato le variabili booleane indipendenti, è
possibile descrivere lo stesso problema per mezzo della
tavola della verità della variabile indipendente (funzione
booleana).
•Resta da fare un ultimo passo, ovvero il passaggio dalla
tavola di verità all’espressione logica che la rappresenta.

22. 22Piero Demichelis
Espressione canonica
•Per ottenere l’espressione logica dalla tavola di verità si
può applicare la seguente regola pratica:
1.l'espressione è formata da tanti termini, legati
dall'operatore OR, quanti sono gli 1 della funzione;
2.in ogni termine compaiono tutte le variabili
indipendenti, legate dall'operatore AND, nella forma
affermata o negata a seconda che per quella
combinazione nella tavola della verità assumano il
valore 1 o 0.
•L'espressione che si trova con questo metodo è detta
canonica, ed è una delle tante espressioni equivalenti che
possono rappresentare la stessa funzione.

23. 23Piero Demichelis
Espressione canonica: esempio
•Esempio: si supponga che l’analisi del problema abbia
condotto alla seguente tavola di verità:
1111
0011
1101
0001
1110
0010
1100
0000
Fzyx
a
b
c
d

24. 24Piero Demichelis
Espressione canonica: esempio
•Applicando alla precedente tavola di verità le regole per
l’estrazione dell’espressione canonica otteniamo la
seguente espressione:
F = x y z + x y z + x y z + x y z
•Questa espressione può essere ridotta con l’uso dei
teoremi dell’algebra di Boole.
a b c d

25. 25Piero Demichelis
Minimizzazione dell’espressione
F = x y z + x y z + x y z + x y z
F = x z ( y + y ) + x z ( y + y )
F = x z + x z
F = z ( x + x )
F = z
=1 =1
=1

26. 26Piero Demichelis
Applicazioni
•Il campo di applicazione dell’algebra di Boole è molto vasto,
consentendo di risolvere problemi che, in origine, sono di natura
molto diversa dalla logica.
•Ad esempio la somma di due numeri binari può essere ricondotta a
una sequenza di somme elementari di 3 bit di ugual peso:
11111
10101
10110
01100
10011
01001
01010
00000
RipScyx

27. 27Piero Demichelis
Applicazioni
•Considerando x, y e c variabili logiche possiamo scrivere:
S = c • x • y + c • x • y + c • x • y + c • x • y =
= c • ( x • y + x • y ) + c • ( x • y + x • y ) =
= c • ( x Å y ) + c • ( x Å y ) =
= c Å x Å y
•Un analoga funzione può essere scritta per il riporto risolvendo
così, con semplicità, il problema della somma binaria

28. 28Piero Demichelis
Applicazioni
x
n
•Realizzando le due funzioni (risultato e riporto) in un
unico dispositivo elettronico otteniamo un circuito di
addizione completa (full adder)
y
nr
n-1
s
ncarry
x
0
y
0
0
s
0r
0
x
1
y
1
r
0
s
1r
1