Elementi di informatica
Algebra di Boole
Algebra di
Algebra di Boole Boole
L
L’ ’algebra di algebra di Boole Boole (dal suo inventore G. (dal suo inventore G. Boole Boole ) ) serve a descrivere le operazioni logiche.
serve a descrivere le operazioni logiche.
Componenti dell
Componenti dell’ ’algebra di Boole: algebra di Boole:
??Operatori Operatori booleanibooleani((notnot, and, or), and, or)
??Regole di trasformazione ed equivalenza tra operatori Regole di trasformazione ed equivalenza tra operatori booleani
booleani
Gli
Gli operandi operandi booleani booleani assumono solo due valori: assumono solo due valori:
Vero/Falso
Vero/Falso TrueTrue/False/False 1/01/0 SSìì/No/No
…
…
Operatore Operatore not not Tavola di verit Tavola di verit à à
0 1
1 0
not x x
Esempi di Esempi di not not
x :
x : "piove" "piove" VERO VERO not
not x : x : "non piove" "non piove" FALSO FALSO
Posso scrivere:
Posso scrivere:
not
not x x oppure oppure
¬
¬x x oppure oppure x
x
Tavola di verità: and
1 1
1
0 0
1
0 0
0
0 0
0
x and y y
x
Posso scrivere:
Posso scrivere:
x and y x and y oppure
oppure x x? ?y y oppure oppure x * y x * y
Esempi di and
x : "Benevento è capoluogo di provincia" VERO y : "il NA gioca in serie A" FALSO
x and y :
"Benevento è capoluogo di provincia e il NA gioca in serie A"
FALSO
x : “la terra è un pianeta" VERO
y : “la luna è un satellite della terra" VERO x and y :
“la terra è un pianeta e la luna è un satellite della terra"
VERO
Tavola di verità:or
1 1
1
1 0
1
1 0
0
0 0
0
x or y y
x
Esempi di or
x : "Benevento è capoluogo di provincia" VERO y : "il NA gioca in serie A" FALSO z : "Benevento è capitale d'Italia" FALSO x or y :
"Benevento è capoluogo di provincia oppure il NA gioca in serie A"
VERO y or z :
"Il NA gioca in serie A oppure Benevento è capitale d'Italia"
FALSO
Precedenza degli operatori logici
Operatori Associatività
Operatore unario : not da destra a sinistra
Operatore binario: and da sinistra a destra
Operatore binario: or da sinistra a destra
+ alta
+ bassa
Esempio
Se a è vero b è falso c è falso
a or b and c ?
a or (b and c)
vero
Tabella di verità di: a or (b and c)
Teoremi fondamentali
Identità 1?x=x 0+x=x
Nullo 0?x=0 1+x=1
Idempotenza x?x=x x+x=x
Inverso x?x=0 x+x=1
Commutativa x?y=y?x x+y=y+x
Asspciativa (x?y) ?z=x?(y?z) (x+y)+z=x+(y+z )
Distributiva x?(y+z)=x ?y+x?z x+(y?z)=(x+y) ?(x+z )
Principio di dualità:
Derivabili l ’una dall’altra Scambiando
+ con ? 0 con 1
Valgono le proprietà distributive
x and (y or z)=( x and y) or (x and z) x and (y or z)=( x and y) or (x and z)
"mi piace" e ( "ho i soldi" oppure "la carta di
"mi piace" e ( "ho i soldi" oppure "la carta di credito")
credito")
=
=
(" mi piace" e "ho i soldi") oppure (" mi piace" e "ho (" mi piace" e "ho i soldi") oppure (" mi piace" e "ho
la la
carta di credito") carta di credito")
Regole di De Morgan
Fondamenti di
Informatica 1 Algebra di Boole 15
Circuiti logici
Un circuito logico è biunivocamente associato ad una funzione logica
La struttura del circuito è biunivocamente associato alla forma della funzione
Funzioni elementari: porte logiche
AND
OR NOT
Esempio
y = (( a or b) and (not c)) or (c and d)
circuito
y = (( a or b) and (not c)) or (c and d)
Semplificazione
Il vantaggio dell’algebra di boole sta nel fatto di permettere la semplificazione dei circuiti
Dalla tabella all’espressione
Conosciamo la tabella, ma non sappiamo qual è l’espressione
Ci basta trovare una delle espressioni equivalenti che hanno questa tabella della verità
1 1
1 1
1 0
1 1
1 1
0 1
0 0
0 1
1 1
1 0
0 0
1 0
0 1
0 0
0 0
0 0
espressione c
b a
Dalla tabella all’espressione
1. identificazione di tutte le righe che hanno valore 1;
2. per ogni riga identificata si costruisce una sottoespressione prodotto (and) di tutte le lettere che sono prese nella loro forma naturale o complementata seguendo i seguenti principi:
? le lettere che nella riga in esame hanno valore 1 sono prese nella forma naturale;
? le lettere che nella riga in esame hanno valore 0 sono prese nella forma complementata;
3. le sottoespressioni prodotto così ottenute vengono sommate (or) tra loro per realizzare l’espressione desiderata.
Dalla tabella all’espressione (1)
? 1
1 1 1 riga 7
? 1
0 1 1 riga 6
? 1
1 0 1 riga 5
0 0
0 1 riga 4
? 1
1 1 0 riga 3
0 0
1 0 riga 2
0 1
0 0 riga 1
0 0
0 0 riga 0
espressione c
b a
Dalla tabella all’espressione (2)
a × b × c
? 1
1 1 1 riga 7
a × b × (c)
? 1
0 1 1 riga 6
a × (b) × c
? 1
1 0 1 riga 5
0 0
0 1 riga 4
(a) × b × c
? 1
1 1 0 riga 3
0 0
1 0 riga 2
0 1
0 0 riga 1
0 0
0 0 riga 0
espressione c
b a
Dalla tabella all’espressione (3)
expr
expr = m = m
11+ m + m
22+ m + m
33+ m + m
44expr
expr = ((a) = ((a) × × b b × × c) + (a c) + (a × × (b) (b) × × c) + (a c) + (a × × b b × × (c)) + (a (c)) + (a × × b b × × c)
c)
a × b × c
? 1
1 1 1 riga 7
a × b × (c)
? 1
0 1 1 riga 6
a × (b) × c
? 1
1 0 1 riga 5
0 0
0 1 riga 4
(a) × b × c
? 1
1 1 0 riga 3
0 0
1 0 riga 2
0 1
0 0 riga 1
0 0
0 0 riga 0
espressione c
b a
Verifica
1 1
0 0
0 1
1 1
1 0
1 0
0 0
1 1
1 0
0 1
0 1
0 1
0 0
0 0
0 0
0 1
1 0
0 0
1 1
1 0
0 0
0 0
0 0
1 0
0 0
0 0
0 1
0 0
0 0
0 0
0 0
0 0
m1 + m2+ m3+ m4 m4 =
a × b × c m3=
a × b × (c) m2 =
a × (b) × c m1=
(a) × b × c
c b a
Un’altra espressione equivalente
1 1
1 1 1 1 1
1 0
0 1 0 1 1
1 0
1 0 1 0 1
0 0
0 0 0 0 1
1 1
0 0 1 1 0
0 0
0 0 0 1 0
0 0
0 0 1 0 0
0 0
0 0 0 0 0
(a × b) + (a × c) + (b × c) b × c
a × c a × b
c b a
