Esercitazione 14 aprile 2010
• Formalizzare le frasi seguenti usando
P= “Il programma fattoriale termina sull’ input 5.”
F= ”Ad un certo punto la condizione del while diventa falsa”.
1. Il programma fattoriale termina sull’input 5 perch`e ad un certo punto la condizione del while diventa falsa.
2. Ad un certo punto la condizione del while diventa falsa e quindi il programma fattoriale termina sull’input 5.
3. Se ad un certo punto la condizione del while diventa falsa allora il programma fattoriale termina sull’input 5.
4. Solo se ad un certo punto la condizione del while diventa falsa allora il programma fattoriale termina sull’input 5.
5. Se e solo se ad un certo punto la condizione del while diventa falsa allora il programma fattoriale termina sull’input 5.
6. Non si d`a il caso che il programma fattoriali termini sull’input 5 e che ad un certo punto la condizione del while non diventi falsa.
7. Se non si d`a il caso che il programma fattoriale non termini sull’input 5, allora il programma fattoriale termina sull’input 5 oppure non si d`a il che il caso che ad un certo punto la condizione del while diventa falsa.
8. Posto che se il programma termina sull’input 5 allora ad un certo punto la condizione del while diventa falsa, se non si d`a il caso che la condizione del while diventi falsa allora il programma non termina sull’input 5.
Qualcuna delle proposizioni formali ottenute `e tautologia???
• Negare le precedenti proposizioni e scrivere la loro formulazione corrispondente nel linguaggio natu- rale (si pu`o adottare una formulazione equivalente a patto di mostrare che segue dalla proposizione formale negata tramite equivalenze logiche note)
esempio:
“Il programma termina sull’input 5 e ad un certo punto la condizione del while diventa falsa.”
diventa
P&F La sua negazione `e ¬(P &F )
e sappiamo che |= ¬(P &F ) ↔ ¬P ∨ ¬F
quindi otteniamo traducendo l’equivalente ¬P ∨ ¬F che la negazione della proposizione iniziale in linguaggio naturale diventa
“Il programma NON termina sull’input 5 oppure non si d`a il caso che ad un certo punto la condizione del while diventi falsa.”
• Trovare la proposizione in forma normale disgiuntiva delle seguenti tabelle di verit`a 1.
V1 V2 con( V1, V2)
0 1 1
0 0 0
1 1 0
1 0 1
1
che connettivo `e?
2.
V1 V2 V3 con( V1, V2, V3 )
0 0 0 1
0 0 1 0
0 1 0 0
1 0 0 1
1 0 1 0
1 1 0 0
0 1 1 0
1 1 1 1
• Quali delle seguenti sono tautologie?
1. |= P &Q → P ? 2. |= P &Q → Q ? 3. |= P → (Q → P &Q)?
4. |= ( ( P → C )&( Q → C ) ) → (P ∨ Q → C ) ? 5. |= P → P ?
6. |= P ∨ ¬P ? 7. |= P &¬P ? 8. |= P → (P → P ) ? 9. |= (P → P ) → P ? 10. |= P → (Q → P ) ? 11. |= P &Q → P ∨ Q ? 12. |= P ∨ Q → P ? 13. |= P → P ∨ Q ?
14. |= (P → Q) → ¬P ∨ Q ? 15. |= ¬P ∨ Q → (P → Q) ? 16. |= P ∨ Q → (¬P → Q) ? 17. |= (P → Q) ∨ (Q → P ) ? 18. |= (P → Q) → (Q → P ) ?
19. |= P &(Q ∨ R) → (P &Q) ∨ (P &R)?
• Scrivere la forma normale disgiuntiva delle precedenti proposizioni.
• i. Dire se le seguenti argomentazioni sono corrette o meno informalmente;
ii. formalizzatele traducendo la sbarra di conclusione come un’implicazione;
iii. provate se sono meno tautologie le implicazioni ottenute:
Se Giorgio ha l’acquario allora ama le donne.
Giorgio non ha l’acquario
Quindi Giorgio non ama le donne.
si consiglia di usare:
G= “Giorgio ha l’acquario”
A=”Giorgio ama le donne.
2
O vinci o perdi
Se non vinci allora perdi.
si consiglia di usare:
V=”Vinci”
P=”Perdi”
Se non vinci allora perdi.
Se non perdi allora vinci.
si consiglia di usare:
V=”Vinci”
P=”Perdi”
Spunti per approfondimento personale sul ragionamento-fuori programma:
• Mario dialoga con Alberto come segue:
Mario dice “Alberto, tu possiedi ci`o che non hai ancora perduto. Giusto?”
Alberto risponde “ Certamente!”
Mario chiede “Hai forse perduto una Ferrari?”
Alberto risponde “ Certo che no!”
Mario conclude “ Dunque, tu possiedi una Ferrari.”
La conclusione di Mario `e corretta?
Motivare la risposta
• Bambina: Come sono contenta che gli asparagi non mi piacciano.
Amico: Perch`e carina?
Bambina: Perch`e se mi piacessero, dovrei mangiarli...e invece non li sopporto!
(Lewis Carroll)
La ragione della bambina `e valida?
Motivare la risposta.
• L’espressione
“ Se questa frase `e vera allora 2+2=5.”
(Loeb)
`e una proposizione nel senso classico di espressione che si pu`o verificare essere vera o essere falsa??
3
