ELEMENTI DI LOGICA

• La logica insegna a ragionare in modo corretto ed è
alla base di qualsiasi costruzione matematica
• In logica, si dice proposizione un’ affermazione
che può essere riconosciuta come “vera” o “falsa”
11/08/2016
Prof. Giovanni Ianne
1
ESEMPI DI PROPOSIZIONI
 Tre moltiplicato quattro fa dodici” è una proposizione “vera”
 “I triangoli hanno quattro lati” è una proposizione “falsa”
 “Qual è il triplo di 5?” non è una proposizione: si tratta di una frase
interrogativa, della quale non ha senso decidere la verità o la
falsità
11/08/2016
Prof. Giovanni Ianne
2
DEFINIZIONE
Detto V(p) il valore associato alla proposizione p, si ha:
1
se p è vera
0
se p è falsa
V(p) =
11/08/2016
Prof. Giovanni Ianne
3
ESEMPI
 La proposizione: p = “Tutti i numeri divisibili per 4 sono divisibili
per 2” è vera, quindi V(p) = 1
 La proposizione: q = “Un triangolo ha quattro lati” è falsa, quindi
V(p) = 0
11/08/2016
Prof. Giovanni Ianne
4
LE OPERAZIONI DI LOGICA
 La negazione NOT
 La congiunzione AND
 La disgiunzione inclusiva OR
 La disgiunzione esclusiva XOR
11/08/2016
Prof. Giovanni Ianne
5
LA NEGAZIONE NOT
 A ogni proposizione possiamo far corrispondere la proposizione
opposta
 L’ opposta di una proposizione p si indica con
11/08/2016
Prof. Giovanni Ianne
p
oppure con NOT p
6
ESEMPIO
 p = “Mario possiede una automobile”
 p = “Mario non possiede l’ automobile”
11/08/2016
Prof. Giovanni Ianne
7
TABELLA DI VERITA’
 Esprime il fatto evidente che se la proposizione p è
“vera” la sua opposta è “falsa” e viceversa
 In generale, la tabella di verità è composta da tante
colonne quante sono le proposizioni e da una colonna
finale
 In generale, la tabella di verità avrà due righe se è
coinvolta una sola proposizione, quattro se ne sono
coinvolte due proposizioni, otto se ne sono coinvolte
tre e così via, raddoppiando
 Per la negazione NOT sono due righe e due colonne
11/08/2016
Prof. Giovanni Ianne
8
TABELLE DI VERITA’ PER LA NEGAZIONE NOT
11/08/2016
p
p
V(p)
vera
falsa
1
0
falsa
vera
0
1
Prof. Giovanni Ianne
V( p)
9
LA CONGIUNZIONE AND
 La proposizione congiunzione di p e q si indica
pq
oppure
p AND q
•
•
pq
pq
11/08/2016
è “vera” se p e q sono entrambe vere
è “falsa” se almeno una delle due è falsa
Prof. Giovanni Ianne
10
TABELLE DI VERITA’ DELLA CONGIUNZIONE AND
p
q
pq
vera
vera
vera
V(p)
V(q)
V (p  q )
vera
1
1
1
falsa
falsa
1
0
0
falsa
vera
falsa
0
1
0
falsa
falsa
falsa
0
0
0
11/08/2016
Prof. Giovanni Ianne
11
LA DISGIUNZIONE INCLUSIVA OR
 La proposizione disgiunzione inclusiva di p e q si indica
oppure p OR q
p  q è “vera” se almeno una delle due è vera
•
•
p  q è “falsa” se sono entrambe false
11/08/2016
Prof. Giovanni Ianne
pq
12
TABELLE DI VERITA’ DELLA DISGIUNZIONE INCLUSIVA OR
p
q
pq
V(p)
V(q)
V (p  q)
vera
vera
vera
1
1
1
vera
falsa
vera
1
0
1
falsa
vera
vera
0
1
1
falsa
falsa
falsa
0
0
0
11/08/2016
Prof. Giovanni Ianne
13
LA DISGIUNZIONE ESCLUSIVA XOR
 La proposizione disgiunzione esclusiva di p e q si indica
p  q
oppure p XOR q
•
p  q è “vera” se p è falsa e q è vera oppure se p è vera e q è
falsa
p  q è “falsa” se p e q sono entrambe vere o entrambe false
•
11/08/2016
Prof. Giovanni Ianne
14
TABELLE DI VERITA’ DELLA DISGIUNZIONE ESCLUSIVA XOR
p
q
p  q
V(p)
V(q)
V(p
 q)
vera
vera
falsa
1
1
0
vera
falsa
vera
1
0
1
falsa
vera
vera
0
1
1
falsa
falsa
falsa
0
0
0
11/08/2016
Prof. Giovanni Ianne
15
TABELLE DI VERITA’ CON I CONNETTIVI LOGICI
11/08/2016
p  q  r 
p
q
r
qr
vera
vera
vera
vera
vera
vera
vera
falsa
vera
vera
vera
falsa
vera
vera
vera
vera
falsa
falsa
falsa
falsa
falsa
vera
vera
vera
falsa
falsa
vera
falsa
vera
falsa
falsa
falsa
vera
vera
falsa
falsa
falsa
falsa
falsa
falsa
Prof. Giovanni Ianne
16
TABELLE DI VERITA’ CON I CONNETTIVI LOGICI
11/08/2016
p   p  p
p
p
p p
vera
falsa
falsa
vera
falsa
vera
falsa
falsa
Prof. Giovanni Ianne
17
TABELLE DI VERITA’ CON I CONNETTIVI LOGICI
p
p
11/08/2016
 p  p  p
vera
falsa
falsa
falsa
vera
falsa
Prof. Giovanni Ianne
18
PROPRIETA’ DEI CONNETTIVI AND E OR
Proprietà commutativa
pq  q p
pq  q p
Proprietà distributiva
p  q  r    p  q    p  r 
p  q  r    p  q    p  r 
Proprietà di assorbimento
p   p  q  p
p   p  q  p
11/08/2016
Prof. Giovanni Ianne
Proprietà associativa
p  q  r    p  q   r
p  q  r    p  q   r
Proprietà di idempotenza
p p  p
p p  p
Leggi di De Morgan
pq  pq
pq  pq
19
TAUTOLOGIA
La proposizione p  p che, qualunque sia il valore di verità di p , risulta
sempre vera, viene detta tautologia.
p
11/08/2016
p
p p
V
F
V
F
V
V
Prof. Giovanni Ianne
20
CORRISPONDENZA TRA CONNETTIVO LOGICO E UN’ OPERAZIONE
INSIEMISTICA
NOT  C (COMPLEMENTARE)
AND
 
(INTERSEZIONE)
OR
 
(UNIONE)
XOR
 
(DIFFERENZA SIMMETRICA)
11/08/2016
Prof. Giovanni Ianne
21
PROPRIETA’ DELL’ ALGEBRA DEI SOTTOINSIEMI
Proprietà commutativa
pq  q p
pq  q p
A B  B  A
A B  B  A
Proprietà distributiva
p  q  r    p  q    p  r 
A  B  C    A  B    A  C 
p  q  r    p  q    p  r 
A  B  C    A  B    A  C 
Elementi neutri
p
p
p
p
11/08/2016
 0  p
1  p
 p 1
 p  0
Prof. Giovanni Ianne
A   A
A X  A
A  CA  X
A  CA 

22
11/08/2016
Prof. Giovanni Ianne
23