Corso di Informatica
(Programmazione)
Lezione 9 (7 novembre 2008)
Logica proposizionale e
algebra di Boole
1
Introduzione
Logica proposizionale 
studio del significato delle proposizioni
connesse dai connettivi logici
Algebra di Boole 
struttura algebrica codificata da George
Boole (1815-1864) che manipola
grandezze binarie {0,1}
2
Introduzione
Logica 
studio del processo di pensiero che parte
da premesse e giunge a conclusioni
Proposizione 
dichiarazione a cui può essere associato
un valore di verità (VERO o FALSO, V o
F).
Ad esempio “Il cane di Marco è nero” è una
proposizione, mentre “Che ore sono?” non lo
è.
3
Connettivi logici
Nel seguito si:
 indicheranno le proposizioni tramite lettere
dell’alfabeto maiuscolo
 indicherà il valore di verità di una proposizione
P tramite la notazione v(P). Quindi v(P)=V se P è
vera, v(P)=F se P è falsa
Ad esempio la proposizione “Roma è la capitale
d’Italia” può essere indicata con la lettera R e
quindi:
R=“Roma è la capitale d’Italia”  v(R) vale V
4
Connettivi logici
I principali connettivi (operatori) logici
sono:
 congiunzione logica  “and”, “e”, “&”, Λ
 disgiunzione inclusiva  “or”, “o”, “|”, V
 disgiunzione esclusiva  “xor”, V
 negazione logica  “not”, “!”,
 implicazione logica  “”
 coimplicazione logica  “”
5
Congiunzione logica
Date due proposizioni A e B, l’operatore di
congiunzione logica produce la
proposizione C=A&B che è VERA se e solo
se A e B sono entrambe VERE. Negli altri
casi C è FALSA.
Ad esempio se A=“Roma è la capitale d’Italia”
(A è VERA, cioè v(A)=V) e B=“Milano si trova in
Francia” (B è FALSA, cioè v(B)=F), allora la
proposizione C=A&B=“Roma è la capitale d’Italia
e Milano si trova in Francia” è FALSA, cioè v(C)=F
6
Congiunzione logica
La tabella di verità dell’operatore di
congiunzione logica risulta quindi essere:
A
B
A & B
V
V
V
V
F
F
F
V
F
F
F
F
7
Disgiunzione inclusiva
Date due proposizioni A e B, l’operatore di
disgiunzione inclusiva produce la
proposizione C=A|B che è VERA se e solo
se almeno una proposizione tra A e B è
VERA. Negli altri casi C è FALSA.
Ad esempio se A=“Roma è la capitale d’Italia”
(A è VERA, cioè v(A)=V) e B=“Milano si trova in
Francia” (B è FALSA, cioè v(B)=F), allora la
proposizione C=A|B=“Roma è la capitale d’Italia o
Milano si trova in Francia” è VERA, cioè v(C)=V
8
Disgiunzione inclusiva
La tabella di verità dell’operatore di
disgiunzione inclusiva risulta quindi essere:
A
B
A | B
V
V
V
V
F
V
F
V
V
F
F
F
9
Disgiunzione esclusiva
Date due proposizioni A e B, l’operatore di
disgiunzione esclusiva produce la
proposizione C=A xor B che è VERA se e
solo se una proposizione tra A e B è VERA.
Negli altri casi C è FALSA.
Ad esempio se A=“Roma è la capitale d’Italia”
(A è VERA, cioè v(A)=V) e B=“Milano si trova in
Lombardia” (B è VERA, cioè v(B)=V), allora la
proposizione C=A xor B=“Roma è la capitale
d’Italia oppure Milano si trova in Lombardia” è
FALSA, cioè v(C)=F
10
Disgiunzione inclusiva
La tabella di verità dell’operatore di
disgiunzione esclusiva risulta quindi
essere:
A
B
A xor B
V
V
F
V
F
V
F
V
V
F
F
F
11
Negazione logica
Data una proposizione A, l’operatore di
negazione logica produce la proposizione
C=!A che è VERA se e solo se A è FALSA.
Ad esempio se A=“Roma è la capitale di Francia”
(A è FALSA, cioè v(A)=F), allora la proposizione
C=!A=“Roma non è la capitale di Francia” è VERA,
cioè v(C)=V
12
Disgiunzione inclusiva
La tabella di verità dell’operatore di
negazione logica risulta quindi essere:
A
!A
V
F
F
V
13
Implicazione logica
Date due proposizioni A e B, l’operatore di
implicazione logica produce la
proposizione C=AB che è FALSA se e
solo A è VERA e B è FALSA. Negli altri
casi C è VERA.
Ad esempio se A=“Fuori piove”, B=“Fuori ci sono
nuvole”, e si ha che v(A)=V e v(B)=F, allora
C=AB=“Fuori piove allora è falso che fuori ci
sono nuvole” è palesemente FALSO (quando
piove ci sono sempre le nuvole…)
14
Implicazione logica
La tabella di verità dell’operatore di
implicazione logica risulta quindi essere:
A
B
A  B
V
V
V
V
F
F
F
V
V
F
F
V
15
Coimplicazione logica
Date due proposizioni A e B, l’operatore di
coimplicazione logica produce la
proposizione C=AB che è VERA se e solo
A e B sono entrambe VERE o entrambe
FALSE. Negli altri casi C è FALSA.
Ad esempio se A=“Il triangolo ha angoli alla
base uguali”, B=“Il triangolo è isoscele”, e si ha
che v(A)=F e v(B)=F, allora C=AB=“Il triangolo
non ha angoli alla base uguali allora il triangolo
non è isoscele” è VERA
16
Coimplicazione logica
La tabella di verità dell’operatore di
coimplicazione logica risulta quindi essere:
A
B
A  B
V
V
V
V
F
F
F
V
F
F
F
V
17
Implicazione e
coimplicazione logica
Se due proposizioni A e B sono legate da
implicazione logica (A B), si dice che A è
condizione sufficiente per B e B è
condizione necessaria per A.
Se due proposizioni A e B sono legate da
coimplicazione logica (A  B), si dice che
A è condizione necessaria e sufficiente
per B.
18
La formula
Una formula f è una combinazione di
simboli di proposizioni tramite connettivi
(operatori) logici. Ad una formula è
associato un valore di verità v(f) che
dipende dai valori di verità delle
proposizioni atomiche (proposizioni che
non possono essere scomposte in ulteriori
proposizioni più piccole)
A & B è un esempio di formula
19
La sintassi di una formula
L’alfabeto delle formule è composto da:
 i simboli delle proposizioni
 i simboli dei connettivi logici
 parentesi tonde (per eliminare
ambiguità)
20
La sintassi di una formula
La grammatica delle formule definisce le
regole di buona formazione. Esse sono:
1. un simbolo di proposizione è una formula ben
formata (abbreviato FBF)
2. se f è una formula ben formata, allora la sua
negazione !f è una FBF
3. se f e f’ sono FBF, allora fopf’) (dove “op” è
uno dei connettivi logici) è una FBF
4. niente altro è una FBF
21
La sintassi di una formula
Ad esempio la formula f=(A & (!B)) | C è
una FBF in quanto, in virtù della regola
1, A, B e C sono FBF. Inoltre anche !B è
una FBF in virtù della regola 2. Infine,
per la regola 3 sono FBF anche le
formule A & !B e la formula F=(A & (!B)) |
C.
Invece la formula f’=A & (& B) non è una
FBF.
22
La semantica di una formula
Ad una formula f (che sia FBF) può essere
associato un valore di verità attraverso
la funzione di valutazione v:
v: L  {V,F}
che mappa l’insieme delle formule ben
formate L all’insieme {V,F}. La funzione
v si basa sulle tabelle di verità dei
connettivi logici visti in precedenza.
Quindi data f, v(f) è il valore di verità
associato a f
23
La semantica di una formula
Esempio:
f=(A & (!B)) | C
posto che sia v(A)=V, v(B)=V e v(C)=F
si ha:
v(!B)=F
v(A & (!B))=F
v(f)=v((A & (!B)) | C)=F
24
La semantica di una formula
Si dice che una formula f è:
 una tautologia se è sempre v(f)=V
 una contraddizione se è sempre v(f)=F
Ad esempio:
f=A & (notA)  v(f)=F sempre!
f’=A ! (notA)  v(f’)=V sempre!
25
Algebra di Boole
L’algebra di Boole si basa su:
 variabili booleane che possono
assumere uno dei valori compresi
nell’insieme {0,1}
 operatori booleani
 di negazione logica (NOT)
 di prodotto logico (AND)
 di somma logica (OR)
 etc.
26
Negazione logica (NOT)
L’operazione di negazione logica (o
complementazione) restituisce il valore
opposto rispetto alla variabile x in
ingresso.
Data la variabile booleana x, la sua
negazione logica si indica con –x, x, x’
oppure not(x). Se x vale 1, allora –x vale
0; se x vale 0, allora –x vale 1.
27
Negazione logica (NOT)
La tabella di verità dell’operatore di
negazione logica risulta quindi essere:
x
-x
0
1
1
0
28
Prodotto logico (AND)
L’operazione di prodotto logico, tra due
variabili x e y, restituisce 1 se x e y
hanno entrambe valore 1. In tutti gli altri
casi restituisce 0.
Date le variabili booleane x e y, il
prodotto logico di x e y si indica con x y,
xy oppure con (x and y).
29
Prodotto logico (AND)
La tabella di verità dell’operatore di
prodotto logico risulta quindi essere:
x
y
xy
1
1
1
1
0
0
0
1
0
0
0
0
30
Somma logica (OR)
L’operazione di somma logica, tra due
variabili x e y, restituisce 1 se almeno
una tra x e y ha valore 1. In tutti gli altri
casi restituisce 0.
Date le variabili booleane x e y, la somma
logica di x e y si indica con x+y oppure
con (x or y).
31
Somma logica (OR)
La tabella di verità dell’operatore di
somma logica risulta quindi essere:
x
y
x+y
1
1
1
1
0
1
0
1
1
0
0
0
32
Prodotti e somme notevoli
X 0=0
x+0=x
X 1=x
x+1=1
X x=x
x+x=x
x (-x)=0
x+(-x)=1
33
Proprietà dell’algebra booleana
 Proprietà di idempotenza della somma e
del prodotto  x+x=x e xx=x
 Proprietà dell’elemento nullo della somma
e del prodotto  x+1=1 e x0=0
 Proprietà commutativa della somma e del
prodotto  x+y=y+x e xy=yx
 Proprietà associativa della somma e del
prodotto  x+(y+z)=(x+y)+z=x+y+z e
x(yz)=(xy)z=xyz
34