Algebra Booleana
A. Lorenzi – V. Moriggia
INFORMATICA. C++. TEORIA E AMBIENTE
DI PROGRAMMAZIONE
Atlas
Copyright © Istituto Italiano Edizioni Atlas
Calcolo delle proposizioni
Proposizioni
 Valori di verità
Vero = 1
Falso = 0
+
Connettivi
AND ,  ,  , 
OR , , + , 
XOR ,  , 
NOT , 
Proposizioni composte
A AND B
A OR B
A XOR B
NOT A
Operatore AND (congiunzione)
Tavola di verità
A
1
0
1
0
B
1
1
0
0
A and B
1
0
0
0
Operatore OR (disgiunzione)
Tavola di verità
A
1
0
1
0
B
1
1
0
0
A or B
1
1
1
0
Operatore NOT (negazione)
Tavola di verità
A
not A
1
0
0
1
Esercizi “on the fly”
Se: A = Vero, B = Falso, C = Vero, qual è il valore
di verità delle seguenti espressioni:
•
•
•
•
A
A
B
A
or (not B and C)
and Falso
or Vero
and B and C
Esercizi
Costruire la tavola di verità di:
•
•
•
•
•
A or Vero
A and Vero
not not A
not (A and B)
(not A) or (not B)
(A or Falso)
(A and Falso)
Proprietà
Gli operatori introdotti godono di numerose
proprietà:
• Commutativa ed associativa
• 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)
• not not A = A
• A and A = A
A or A = A
• A or (notA) = Vero
A and (notA) = Falso
• ….
- NOT
Leggi di De Morgan
· AND
NOT (A AND B) = (NOT A) OR (NOT B)
+ OR
A
1
0
1
0
B
1
1
0
0
-A
0
1
0
1
-B
0
0
1
1
A B
1
0
0
0
- (A  B)
0
1
1
1
(-A)+(-B)
0
1
1
1
NOT (A OR B) = (NOT A) AND (NOT B)
A
B
-A
-B
A+B
- (A+B)
(-A) (-B)
1
1
0
0
1
0
0
0
1
1
0
1
0
0
1
0
0
1
1
0
0
0
0
1
1
0
1
1
Osservazioni
• Le leggi di De Morgan sono utili per negare
espressioni complesse:
not ( X>5 or N<1000 ) = not (X>5) and (not(N<1000))
• Le leggi di De Morgan mostrano che i tre operatori
AND OR NOT non sono indipendenti
• E’ possibile esprimere AND tramite OR e NOT:
A and B = not not ( A and B ) = not ((not A) or (not B))
• E’ possibile esprimere OR tramite AND e NOT:
A or B = not not (A or B) = not ((not A) and (not B))
Esempi di applicazione
delle leggi di De Morgan
• (prezzo = 80 ) OR (peso > 50)
prodotti che costano sicuramente 80 euro o pesano
tanto
Negazione:
(prezzo <> 80) e (peso <=50)
Non costano 80 euro e pesano poco
• (distanza < 50 ) or (popolazione > 20000)
città vicine oppure città popolose
Negazione:
città lontane e disabitate
(distanza >=50) e (popolazione <= 20000)
Operatore XOR
(disgiunzione esclusiva)
Tavola di verità
A
1
0
1
0
B
1
1
0
0
A xor B
0
1
1
0
Esercizi
Se A = Vero, B = Vero, C = Falso
qual è il valore di verità di:
• A xor (B or C)
• A xor B xor C
• (A and B) xor C
Costruire la tavola di verità di:
• A xor B xor C
• not (A xor B)
Esercizi
Costruire la tabella di verità delle espressioni
logiche:
1) A  (- B) + C
2) A + B  (C  (- C))
3) A  B + (C  (- C))
4) (A + (- A))  B
Applicare le leggi di De Morgan a:
5) -(A + (- B) + C)
6) -(-(A + (- B)  (- C)))
7) -(-A  (- B)  (- C))
Dalla tabella alla funzione booleana
A
B
F(A,B)
F(A,B) = A(-B) + (-A)(-B)
= (- B)  ( A + (- A))
1
1
0
1
0
1
0
1
0
0
0
1
= (- B)  Vero
=-B
A  (- B)
(-A)  (- B)
Calcolatrice di Windows
(Accessori)
Accedere a
Visualizza per
selezionare la
modalità:
Scientifica
Operatori booleani
Dove si usano
•
Nelle formule di Excel
•
Nella riga dei criteri nelle query di Access
•
Nei motori di ricerca in Internet
•
Nei linguaggi di programmazione
•
Nella progettazione dei circuiti logici
•
Nella crittografia
Motori di ricerca
• Google: non è
necessario usare
l'operatore booleano
AND (per
impostazione
predefinita, Google
ricerca tutte le parole
chiave inserite
dall'utente).
• Uso di OR (maiuscolo)
• Ricerca avanzata
milano
università
milano OR
università
7.550.000
pagine
91.100.000
pagine
Crittografia (chiave simmetrica)
•
(A xor K) xor K = A
Decodifica:
A = C xor K
Messaggio A
C = A xor K
Messaggio codificato
Chiave K
Chiave K
Bob
Alice
A
K
C
C xor K
110011010
101110001
011101011
110011010