Logica per la programmazione - unipi.itpages.di.unipi.it/levi/LogicaISU.pdfTre amici, Antonio, Bruno...
Transcript of Logica per la programmazione - unipi.itpages.di.unipi.it/levi/LogicaISU.pdfTre amici, Antonio, Bruno...
CALCOLO PROPOSIZIONALE
Tre amici, Antonio, Bruno e Corrado, sono incerti se andare al cinema. Si sa che: Se Corrado va al cinema, allora ci va anche Antonio; Condizione necessaria perché Antonio vada al cinema è che ci
vada Bruno.
Il giorno successivo possiamo affermare con certezza che:1) Se Corrado è andato al cinema, allora ci è andato anche Bruno2) Nessuno dei tre amici è andato al cinema3) Se Bruno è andato al cinema, allora ci è andato anche Corrado4) Se Corrado non è andato al cinema, allora non ci è andato
nemmeno Bruno
Come si formalizza il concetto di passaggio di deduzione valido?
UN PROBLEMA DI DEDUZIONE LOGICA(da un test d’ingresso)
IL CALCOLO PROPOSIZIONALE
E’ il nucleo di (quasi) tutte le logiche. Limitato potere espressivo, ma sufficiente per introdurre il concetto di deduzione valida
Le proposizioni atomiche sono asserzioni a cui sia assegnabile in modo univoco un valore di verità in accordo ad una interpretazione del mondo a cui si riferiscono
“dichiarativi sono non già tutti i discorsi, ma quelli in cui sussiste una enunciazione vera oppure falsa”
Aristotele
ESEMPI DI PROPOSIZIONI “ATOMICHE”
1. Roma è la capitale d’Italia
2. La Francia è uno stato del continente asiatico
3. 1+1 = 2
4. 2+2 = 3
ESEMPI DI NON PROPOSIZIONI
1. Che ora è?
2. Leggete queste note con attenzione
3. X+1 = 2
SINTASSI E SEMANTICA
● Introduciamo la sintassi e la semantica del calcolo proposizionale
● La sintassi definisce il linguaggio ovvero le asserzioni (formule): -simboli proposizionali (proposizioni atomiche)
-connettivi logici
● La semantica definisce il significato delle formule, ovvero il loro valore di verita' -dipende dal valore di verita dei simboli proposizionali
CONNETTIVI LOGICI
Connettivo Forma simbolica Operazione corrispondente
not ~ p negazione
and, e p ˰ q congiunzione
or, oppure p ˬ q disgiunzione
se p allora q p q implicazione
p se e solo se q p q equivalenza
p se q p q conseguenza
SINTASSI DELLE FORMULE PROPOSIZIONALI (GRAMMATICA)
Prop ::=
Prop Prop | Prop ˬ Prop | Prop ˰ Prop |
Prop Prop | Prop Prop |
Atom | ~AtomAtom ::= T | F | Ide | (Prop)Ide ::= p | q | …| P | Q | …
SEMANTICA (SIGNIFICATO) DELLE FORMULE PROPOSIZIONALI
Tabelle di verità dei connettivi logici:
Il valore di verita' di una formula composta si ottiene a partire dal valore di verita' delle sottoformule
Si osservi in particolare il valore di verità di un’implicazione (o di una conseguenza)
p q T F ~p p ˰ q p ˬ q p q p q p q
T T T F F T T T T T
T F T F F F T F F T
F T T F T F T T F F
F F T F T F F T T T
CALCOLO PROPOSIZIONALE PER FORMALIZZARE ENUNCIATI: ESEMPIO
Tre amici, Antonio, Bruno e Corrado, sono incerti se andare al cinema. Introduciamo tre proposizioni:
A “Antonio va al cinema” B “Bruno va al cinema” C “Corrado va al cinema”
Si sa che: Se Corrado va al cinema, allora ci va anche Antonio;
C A
Condizione necessaria perché Antonio vada al cinema è che ci vada Bruno. A B
CALCOLO PROPOSIZIONALE PER FORMALIZZARE ENUNCIATI: ESEMPIO
Il giorno successivo possiamo affermare con certezza che: Se Corrado è andato al cinema, allora ci è andato anche Bruno
C B
Nessuno dei tre amici è andato al cinema
(~A) ˰ (~B) ˰ (~ (~C)
Se Bruno è andato al cinema, allora ci è andato anche Corrado B C
Se Corrado non è andato al cinema, allora non ci è andato nemmeno Bruno (~C) (~B)
Per rispondere alla domanda del test, dobbiamo capire quale di queste quattro proposizioni è conseguenza logica delle proposizioni precedenti
∧
TAUTOLOGIE E CONTRADDIZIONI
Una tautologia è una formula del calcolo proposizionale che vale T per qualunque valore T/F assegnato alle variabili proposizionali Esempio: p ˬ p (vedi tabella di verità)
Una contraddizione è una formula che vale F per qualunque valore T/F assegnato alle variabili proposizionali
Quindi P è una tautologia se e solo se ~P è una contraddizione
IMPLICAZIONI E EQUIVALENZE
Diciamo che p implica tautologicamente q
se e solo se p q è una tautologia
p è tautologicamente equivalente a qse e solo se
p ≡ q è una tautologia
In entrambi i casi e' sufficiente costruire la corrispondente tabella di verita'
DIMOSTRAZIONE DI TAUTOLOGIE
Per dimostrare che p è una tautologia possiamo Usare le tabelle di verità
Del tutto meccanico, richiede di considerare 2n casi, dove n è il numero di variabili proposizionali in p
Mostrare che non è una tautologia individuando valori delle variabili proposizionali che rendono falsa p
ESEMPIO DI TAULTOLOGIA: TRANSITIVITA’ DELL’IMPLICAZIONE:
p q r p q q r (p q) (q r)
p r ((p q) (q r)) (p r)
T T T T T T T T
T T F T F F F T
T F T F T F T T
T F F F T F F T
F T T T T T T T
F T F T F F T T
F F T T T T T T
F F F T T T T T
EQUIVALENZE PER IMPLICAZIONI
(p q) ((~p) ˬ q) (elim- )
(p q) (p q) ˰ (q p) (elim- )
(p q) (q p) (elim-)
p q p q ~p ~p ˬ q
T T T F T
T F F F F
F T T T T
F F T T T
EQUIVALENZE PER LA NEGAZIONE
~(~ p) p (Doppia negazione)
p ˬ ~p) T (Terzo escluso)
p ˰ ~p) F (Contraddizione)
~(p ˰ q) (~p) ˬ (~q) (De Morgan)
~(p ˬ q) (~p) ˰ ~q)
~T F (T:F)
~F T (F:T)
Esercizio: dimostrare le equivalenze con tabelle di verità
ESEMPI DI IMPLICAZIONI
Dimostrare che le seguenti formule sono tautologie usando le tabelle di verita'
(p ˰ (p q)) q
(p ˰ q) p
p p ˬ q)
ESEMPI DI IMPLICAZIONI
Dimostrare che le seguenti formule non sono tautologie usando le tabelle di verita'
(p ˬ q) p
p p ˰ q)
((p ˬ ~r)) ˰ (p q)) q
PASSO DI DEDUZIONE VALIDO
Torniamo indietro al problema della deduzione Il concetto di conseguenza logica si puo' formalizzare in
modo intuitivo usando la semantica dell'implicazione E' corretto dedurre una conclusione P da un insieme di
premesse G1 ............ Gn
sse la sequente formula e' una tautologia
(G1 ˰ .... ˰ Gn) P
MODUS PONENS
Abbiamo dimostrato che la seguente formula e' una tautologia
(p ˰ (p q)) q
Se valgono le premesse p, (p q)
possiamo dedurre q
TORNIAMO ALL’ESEMPIO DAL TEST
Premesse: Se Corrado va al cinema, allora ci va anche Antonio; ( C A )
Condizione necessaria perché Antonio vada al cinema è che ci vada Bruno. ( A B )
Il giorno successivo possiamo affermare con certezza che: Se Corrado è andato al cinema, allora ci è andato anche Bruno
( C B )
Nessuno dei tre amici è andato al cinema
( (~A ) ˰ (~B) ˰ (~C) )
Se Bruno è andato al cinema, allora ci è andato anche Corrado ( B C )
Se Corrado non è andato al cinema, allora non ci è andato nemmeno Bruno ( (~C) (~B) )
Basta determinare quale delle seguenti formule è una tautologia:
1) ( (C A) ˰ A B) ) ( C B )
2) ( (C A) ˰ A B) ) ( (~A) ˰ (~B) ˰ (~C) )
3) ( (C A) ˰ A B) ) ( B C )
4) ( (C A) ˰ A B) ) ( (~ C) ~B) )
Si possono verificare con tabelle di verità
Abbiamo gia' dimostrato che (1) è una tautologia
Esercizio: mostrare che (2), (3) e (4) non sono tautologie
CONSEGUENZA LOGICA
Sia Γ un insieme di formule proposizionali (asserzioni che hanno valore T o F)
Una intepretazione assegna un valore di verita' alle proposizioni elementari
Una intepretazione che rende veri tutte le formule proposizionali in Γ è detta un modello di Γ
Se una formula Q è vera in tutti i modelli di Γ si dice che
Q è conseguenza logica di Γ (Γ Q)
CONSEGUENZA LOGICA
Dato Γ, il numero di possibili interpretazioni è finito: se n è il numero di proposizioni elementari in Γ, il numero di possibili interpretazioni è 2^n.
Si possono usare le tabelle di verita' per decidere se
Γ Q
Modo alternativo per formulare la che la conclusione Q e' deducibile dall'insieme delle premesse Γ
Esercizi: usare le tabelle di verita'
Dimostrare che q e' conseguenza logica delle premesse: p, (p q)
Dimostrare che q non e' conseguenza logica delle premesse p, ((p ˰ r ) q)
Dimostrare che (q p) (~ p ~q)
FORMALIZZAZIONE DI ENUNCIATI: ESEMPI
Piove e fa molto freddo
Fa freddo, ma non piove
Se ci sono nuvole e non c’è vento, allora piove
Piove solo se ci sono nuvole e non c’è vento
Nevica, ma non fa freddo se ci si copre
Se ci si copre, allora fa freddo o nevica
Formalizzazione di implicazioni in linguaggio naturale
Scrivere la proposizione rappresentata da ognuna delle seguenti frasi in italiano: Se P, allora Q P è una conseguenza di Q P è condizione necessaria e sufficiente per Q P è condizione necessaria per Q P è condizione sufficiente per Q P vale solo se vale Q P vale se vale Q P vale se e solo se vale Q