La logica
• Dare un significato preciso alle
affermazioni matematiche
• Introdurre al ragionamento logico
• Applicazioni in Informatica:
–
–
–
–
Disegno di circuiti
Specifica di sistemi
Progettazione di software
Verifica di correttezza di programmi
La logica
• La logica proposizionale
• La logica dei predicati
– Quantificatori universali ed esistenziali
• Introduzione alle dimostrazioni
Proposizioni
• Proposizione: una sentenza dichiarativa cui
è possibile assegnare, in modo non
ambiguo, un valore di verità.
– Può essere vera o falsa ma non entrambe
• Variabili Proposizionali: p, q, r, s
• Valori di verità: vero (T) o falso (F)
Proposizioni
• Esempi di proposizioni:
– 1+1=2
– Parigi è la capitale della Francia
– Parigi è la capitale della Germania
• Non sono Proposizioni:
– Che ora è?
–x>1
– Carlo è alto
Proposizioni composte
• Nuove proposizioni formate da
proposizioni esistenti usando operatori
logici
• Chiamate anche: formule proposizionali o
espressioni della logica delle proposizioni
• Operatori logici:
 (negazione),  (congiunzione),  (disgiunzione),
 (implicazione),  (equivalenza)
Negazione
•Se p è una proposizione, la negazione di p,
denotata da p, è
“non è vero che p”
– “not p”
TABLE 1 (1.1)
歐亞書局
P. 3
Congiunzione e Disgiunzione
• Se p e q sono proposizioni, la
congiunzione di p e q, denotata p  q, è la
proposizione
“p and q” (“p e q” )
• Se p e q sono proposizioni, la disgiunzione
di p e q, denotata p  q, è la proposizione
“p or q” (“p o q” )
TABLE 2 (1.1)
歐亞書局
P. 4
TABLE 3 (1.1)
歐亞書局
P. 4
Disgiunzione esclusiva
• Se p e q sono proposizioni, la disgiunzione
esclusiva di p e q, denotata p  q, è la
proposizione che è vera esattamente
quando una tra p e q è vera (ma non
entrambe)
TABLE 4 (1.1)
歐亞書局
P. 6
Implicazione
(conditional statement)
• Se p e q sono proposizioni, la implicazione
p  q è la proposizione
“ se p allora q”
– p: ipotesi (o antecedente o premessa)
– q: conclusione (o conseguenza)
Se p allora q
• Molti modi per esprimere l’implicazione:
q se p, q quando p, q ogni qualvolta che p,
p è (condizione) sufficiente per q,
q è (condizione) necessaria per p,
p solo se q, q a meno che “not p”
…..
TABLE 5 (1.1)
歐亞書局
P. 6
Implicazione Inversa, Contraria,
Contronominale
•pq
• Inversa: q  p (Converse)
• Contronominale: q  p (Contrapositive)
• Contraria: p   q (Inverse)
Inversa, Contraria, Contronominale
• Due proposizioni composte sono
equivalenti se hanno sempre lo stesso
valore di verità
• Ogni implicazione p  q è equivalente
al proprio contronominale  q   p
– L’inversa q  p è equivalente alla contraria
p   q (ma non sono equivalenti a p  q )
Doppia Implicazione
(biconditional statement)
• Se p e q sono proposizioni, la doppia
implicazione p  q è la proposizione
“p se e solo se q.”
– “p è condizione necessaria e sufficiente per q”
– “p iff q”
TABLE 6 (1.1)
歐亞書局
P. 9
Uso implicito di doppia
implicazione
• La doppia implicazione non è sempre
esplicita nel linguaggio naturale
• “Se mangi tutta la minestra, allora puoi avere il
dolce.” Con il significato:
• “Puoi avere il dolce se e solo se mangi tutta la
minestra.”
• Doppia implicazone implicita nelle
definizioni:
• “n è pari se è divisibile per 2”
• ma è implicita l’implicazione inversa
Tavoledi verità per le
proposizioni composte
TABLE 7 (1.1)
歐亞書局
P. 10
Precedenza degli operatori logici
• La negazione è applicata prima degli altri
operatori
• La congiunzione ha precedenza sulla
disgiunzione
• Implicazione e doppia implicazione hanno
precedenza più bassa
• Le parentesi sono usate quando sono
necessarie
TABLE 8 (1.1)
歐亞書局
P. 11
Tradurre frasi del linguaggio
naturale
Specifiche di sistema
• Controllo di non ambiguità
• Verifica della consistenza
– Quando il software del sistema è in
aggiornamento, gli utenti non possono accedere
al file system.
– Gli utenti possono salvare nuovi file se possono
accedere al file system.
– Se gli utenti non possono salvare nuovi file,
allora il software del sistema non è in
aggiornamento.
Tautologie e contraddizioni
• Tautologia: una proposizione composta che
è sempre VERA
• Equivalente a T
• p  p
• Contraddizione: una proposizione
composta che è sempre FALSA
•Equivalente a F
•p  p
TABLE 1 (1.2)
歐亞書局
P. 22
Equivalenza logica
• Proposizioni composte che hanno lo stesso
valore di verità in ogni possibile caso
• p e q sono logicamente equivalenti if p  q è
una tautologia
– denoted by p  q or p  q
Equivalenza logica - Esempi
• Leggi di De Morgan:
 (p  q)   p   q
(p  q)   p   q
• Distributività:
p  (p  r)  (p  q)  (p  r)
• Proprietà dell’implicazione:
pqp q
TABLE 3 (1.2)
歐亞書局
P. 22
TABLE 4 (1.2)
pq
歐亞書局
P. 23
TABLE 5 (1.2)
歐亞書局
P. 23
TABLE 6 (1.2)
歐亞書局
P. 24
TABLE 7 (1.2)
歐亞書局
P. 25
TABLE 8 (1.2)
歐亞書局
P. 25
Construire Nuove Equivalenze
Logiche
• Come mostrare equivalenze logiche:
– Usare una tavola di verità
– Usare equivalenze logiche già note
Dimostrazioni
• Una dimostrazione è una valida
argomentazione che stabilisce la verità di
una affermazione matematica
– Argumentazione: una sequenza di
affermazioni che portano ad una conclusione
– Valida: la conclusione deve seguire dalle
affermazioni precedenti (premesse)
• Regole di Inferenza
Argomentazioni valide nella Logica
Proposizionale
– “Se hai una password corrente, allora puoi
entrare nella rete”
– “Tu hai una password corrente”
– Quindi, “Puoi entrare nella rete”
• Regola di Inferenza (Modus ponens)
p q
p
______
:q
TABLE 1 (1.5)
歐亞書局
P. 66
Un esempio
– “Oggi non c’è il sole”
– “Andiamo al mare solo se c’è il sole”
– “ Quando non andiamo al mare, facciamo una
passeggiata”
– “Se facciamo una passeggiata, torniamo a casa
prima del tramonto”
• Conclusione: “Oggi torniamo a casa prima
del tramonto”
Attenzione!
• ((p  q) q)  p non è una tautologia
• “Se fai tutti gli esercizi imparerai bene la materia.
• Tu hai imparato bene la materia
• Quindi, tu hai svolto tutti gli esercizi.”
CONCLUSIONE ERRATA
• ((p  q) p)  q non è una tautologia
Logica dei Predicati
• Predicato: una proprietà che il soggetto
della frase può soddisfare
– Ex: x>3
• x: variabile
• >3: predicato
• P(x): x>3
– FUNZIONE PROPOIZIONALE
– P(x1,x2, …, xn): predicato con n argomenti
Quantificatori
• Quantificazione universale: un predicato è
vero per ogni elemento
• Quantificazione esistenziale: c’è uno o
più elementi per cui un predicato è vero
Quantificatore universale
• Dominio (o Universo): elementi cui si fa
rierimento nelle affermazioni
• La quantificazione universale di P(x) è: “P(x)
vale per tutti i valori di x nel dominio
– denotato da x P(x)
• Contresempio: un elemento per cui P(x) è falso
– Quandi gli elementi del dominio possono
essere listati è equivalente a:
P(x1) P(x2) … P(xn)
Quantificatore esistenziale
• La quantificazione esistenziale di P(x) è:
“esiste un valore di x nel dominio tale che
P(x) vale” per tutti i valori di x nelThe
existential
– Denotato da x P(x)
– Quandi gli elementi del dominio possono
essere listati è equivalente a:
P(x1) P(x2) … P(xn)
TABLE 1 (1.3)
歐亞書局
P. 34
Altri quantificatori
• !x P(x) or 1x P(x)
– Esiste un unico valore di x tale che P(x) è vero
• Quantificatori con domini ristretti:
– x<0 (x2>0)
• Condizionale: x(x<0  x2>0)
– z>0 (z2=2)
• Congiunzione: z(z>0  z2=2)
Precedenza di quantificatori
•  e  hanno precedenza maggiore di tutti
gli operatori logici
– Ex: x P(x) Q(x)
• (x P(x)) Q(x)
Equivalenze logiche che coinvolgono
quantificatori
• Espressioni logiche che coinvolgono
predicati e quantificatori sono logicamente
equivalenti se e solo se essi hanno lo stesso
valore di verità
• E.g. x (P(x)  Q(x)) and x P(x)  x Q(x)
Negare le espressioni quantificate
• x P(x)  x P(x)
– Negazione di “Tutti gli studenti della classe
frequentano il corso di Programmazione”:
– “C’è uno studente della classe che non frequenta il
corso di Programmazione”
x Q(x)  x Q(x)
TABLE 2 (1.3)
歐亞書局
P. 41
Tradurre il linguaggio naturale in
espressioni logiche
• “Ogni studente della classe ha studiato
Matematica Discreta” x (x ha studiato M.D.)
• “Alcuni studenti hanno visitato il
Messico”: x (x ha visitato il Messico)
• “Tutti gli studenti hanno visitato il Messico o il
Canada” : x ((x ha visitato il Messico)  (x
ha visitato il Canada))
Quantificatori annidati
• Due quantificatori sono annidati se uno è
nello scope dell’altro
– x y (x+y=0)
– x  y ((x>0)  (y<0)  (xy<0))
• L’ordine dei quantificatori è importante a
meno che non siano tutti universali o tutti
esistenziali
TABLE 1 (1.4)
歐亞書局
P. 53
Regole di Inferenza per espressioni
quantificate
• Instanziazione universale
– x P(x), P(c)
• Generalizzazione universale
– P(c) per un generico c, x P(x)
• Instanziazione esistenziale
– x P(x), P(c) per un c
• Generalizzazione esistenziale
– P(c) per un c,  x P(x)
TABLE 2 (1.5)
歐亞書局
P. 70
Generalizzazioni delle regole di
inferenza
• Combinare regole di infrenza per
proposizioni ed espressioni quantificate
– Universal modus ponens
• x (P(x)  Q(x))
P(a), dove a è un particolare elemento nel dominio
Q(a)
– Universal modus tollens
• x (P(x)  Q(x))
Q(a) , dove a è un particolare elemento nel dominio
P(a)