6. Calcolo dei sequenti LC
pdella Logica classica proposizionale ax-id
Γ, A, Γ
0` ∆, A, ∆
0ax-⊥
Γ, ⊥, Γ
0` ∇
ax-tt Γ ` ∇, tt, ∇
0Σ, Γ, Θ, Γ
0, ∆ ` Σ
0Σ, Γ
0, Θ, Γ, ∆ ` Σ
0sc
sxΓ ` Σ, ∆, Θ, ∆
0, ∇ Γ ` Σ, ∆
0, Θ, ∆, ∇ sc
dxΓ ` A, ∆ Γ ` B, ∆
Γ ` A&B, ∆ &−D Γ, A, B ` ∆
Γ, A&B ` ∆ &−S Γ ` A, B, ∆
Γ ` A ∨ B, ∆ ∨−D Γ, A ` ∆ Γ, B ` ∆
Γ, A ∨ B ` ∆ ∨−S Γ, A ` ∆
Γ ` ¬A, ∆ ¬−D Γ ` A, ∆
Γ, ¬A ` ∆ ¬−S Γ, A ` B, ∆
Γ ` A → B, ∆ → −D Γ ` A, ∆ Γ, B ` ∆
Γ, A → B ` ∆ → −S
1. il sequente
C, A&(B → C), M ` H&C, A&(B → C)
`
e un assioma identit`a?
2. la seguente `e una derivazione in logica classica proposizionale LCp P &Q`Q P &Q`P
P &Q`Q&P
???
3. la seguente `e una derivazione in logica classica proposizionale LCp
P &Q`C P &Q`Q ∨ P P &Q`(C&Q)∨P
???
4. Derivare in LCp
A&B ` B&A 5. Derivare in LCp
(A&B)&C`A&(B&C) 6. Derivare in LCp
A&(P → C) ` (P → C)&A
?
E possibile ottenere una derivazione di questo sequente a partire da quella di A&B ` B&A?` Come?
1
7. Provare a vedere quali sequenti del tipo ` pr ottenuti sostituendo pr con le sequenti proposizioni hanno un albero di derivazione:
(a) ¬( (A → B) ∨ A ) (b) (A → B)&¬A
(c) P &Q → P ∨ R (d) P → P
(e) P ∨ ¬P (f) P &¬P (g) P ∨ Q → Q (h) Q → (P &Q) ∨ C
Provando e riprovando a trovare derivazioni per i sequenti sopra riesci a vedere un legame tra il fatto che il sequente ` pr ha una derivazione e il fatto che pr `e una tautologia o un’opinione o un paradosso??
6. bis Esercizi di formalizzazione e validit` a sequenti
Formalizzare in seguenti le seguenti asserzioni (secondo i suggerimenti indicati) e mostrare se la propo- sizione ottenuta `e valida tramite derivazione nel calcolo dei sequenti classico.
Nel seguito si ricordi che quando si scrive
frase1
frase2
....
frasen
frase s’intende
‘’frase1 ,frase2, ..., frasen ` vale frase”
e stabilire la loro validit`a derivando il sequente ottenuto in LCp
1. Solo se mi sento stanco rimango a casa.
Non rimango a casa se non mi sento stanco.
si consiglia di usare:
R =rimango a casa S = mi sento stanco
2. Non si d`a il caso che l’affare sia non sicuro o non sia conveniente.
L’affare `e conveniente e sicuro.
A =l’affare `e conveniente S = l’affare `e sicuro
3. Non si d`a il caso che l’affare non sia conveniente o sicuro.
L’affare non `e conveniente n`e sicuro.
A =l’affare `e conveniente S =l’affare `e sicuro
4. Se Mario `e scontento non programma bene.
Mario `e contento solo se programma bene.
C=Mario `e contento P =Mario programma bene
5. C’`e un assemblea studentesca o `e giorno festivo solo se le lezioni tacciono.
Non `e giorno festivo e non c’`e un assemblea studentesca, perci´o le lezioni non tacciono.
L=le lezioni tacciono
A=c’`e un assemblea studentesca F =`e giorno festivo
6.
Non si d`a il caso che il fattoriale termini mentre non si esce dal ciclo.
Si esce dal ciclo.
Non si d`a il caso che si esca dal ciclo solo se il fattoriale non termina.
3
F = il fattoriale termina C=si esce dal ciclo
7.
Non prendo l’ombrello se non piove.
Non piove.
Non prendo l’ombrello.
P =piove
O=prendo l’ombrello
8. Se il tuo vicino di banco non `e Napoleone ne segue che lui non canta alla Scala di Milano.
Se il tuo vicino di banco canta alla Scala di Milano allora lui `e Napoleone.
ponendo
V = “il tuo vicino di banco `e Napoleone”
S= “il tuo vicino di banco canta alla Scala di Milano”
9. Solo se non dormo la notte la mattina mi alzo stanco.
La mattina non mi alzo stanco se non si d`a il caso che non dorma la notte.
ponendo:
D =”dormo la notte”
S =”la mattina mi alzo stanco”
Curiosit` a su implicazione classica
MEMO
pr VALIDA in logica classica (ovvero `e tautologia classica) se vera (ovvero ha valore 1) in TUTTE le righe della sua tabella
pr SODDISFACIBILE in logica classica
se vera (ovvero ha valore 1) per QUALCHE riga della sua tabella
pr NON VALIDA in logica classica
se falsa (ovvero ha valore 0) in QUALCHE riga della sua tabella
pr INSODDISFACIBILE in logica classica
se falsa (ovvero ha valore 0) in TUTTE le righe della sua tabella
Test di comprensione: attenzione all’implicazione classica!
1. `E vero secondo la logica classica che
“Se passerete l’esame di logica al I appello, allora a giugno farete una vacanza alle Hawai, e se a giugno farete una vacanza alle Hawai allora passerete l’esame di logica al I appello”
??
Formalizzare ponendo
L= “Passerete l’esame di logica al I appello”
R= “A giugno farete una vacanza alle Hawai”
e mostrare se la proposizione ottenuta `e tautologia classica.
In caso di non validit`a specificare per quali valori delle variabili proposizionali la proposizione `e falsa (ovvero su quale riga della tabella di verit`a la proposizione `e falsa) e poi se la proposizione ottenuta `e soddisfacibile e su che valori lo `e, oppure alternativamente se `e insoddisfacibile.
2. `E vero secondo la logica classica che
“Se passerete l’esame di logica al I appello, allora a giugno farete una vacanza alle Hawai, oppure se a giugno farete una vacanza alle Hawai allora passerete l’esame di logica al I appello”
??
Formalizzare ponendo
L= “Passerete l’esame di logica al I appello”
R= “A giugno farete una vacanza alle Hawai”
e mostrare se la proposizione ottenuta `e tautologia classica.
In caso di non validit`a specificare per quali valori delle variabili proposizionali la proposizione `e falsa (ovvero su quale riga della tabella di verit`a la proposizione `e falsa) e poi se la proposizione
5
ottenuta `e soddisfacibile e su che valori lo `e, oppure alternativamente se `e insoddisfacibile.
3. `E vero secondo la logica classica che
“Se non si d`a il caso che se tu sei a Londra allora sei a Padova, allora sei a Londra e non sei a Padova”
??
Formalizzare ponendo L= “Tu sei a Londra”
P= “Sei Padova”
e mostrare se la proposizione ottenuta `e tautologia classica.
In caso di non validit`a specificare per quali valori delle variabili proposizionali la proposizione `e falsa (ovvero su quale riga della tabella di verit`a la proposizione `e falsa) e poi se la proposizione ottenuta `e soddisfacibile e su che valori lo `e, oppure alternativamente se `e insoddisfacibile.
4. `E vero secondo la logica classica che
“Se il tuo vicino di banco non `e a Londra allora ne segue che se il tuo vicino di banco `e a Londra allora il tuo vicino di banco `e un acrobata ”
??
Formalizzare ponendo
V= “il tuo vicino di banco `e a Londra”
A= “il tuo vicino di banco `e un acrobata”
e mostrare se la proposizione ottenuta `e tautologia classica.
In caso di non validit`a specificare per quali valori delle variabili proposizionali la proposizione `e falsa (ovvero su quale riga della tabella di verit`a la proposizione `e falsa) e poi se la proposizione ottenuta `e soddisfacibile e su che valori lo `e, oppure alternativamente se `e insoddisfacibile.
