esercizi

ESERCIZI RELATIVI AL CAPITOLO PRIMO (LOGICA PROPOSIZIONALE) http://www.dif.unige.it/epi/hp/pal/ssis04/prop.pdf

1. Indicare quali dei seguenti enunciati sono proposizioni:

(a) “Milano è la capitale d’Italia”

(b)“Milano è la capitale d’Italia?”

(c) “Nelle scuole è vietato fumare”

(d)“Non fumare a scuola!”

(e) “Si può fumare a scuola?”

(f) “C’è vita fuori dal sistema solare”

(g) “L’uomo è in grado di volare”

(h)“Fosse l’uomo in grado di volare!”

(i) “Dio esiste”

(l) “Probabilmente Dio esiste”

(m) “Devi credere in Dio!”

2. Dire in quali delle seguenti proposizioni la congiunzione “e” si può formalizzare con la congiunzione logica ∧:

(a) “Carlo e Marco sono insegnanti”

(b)“Carlo e Marco sono compaesani”

(c) “Carlo e Marco stanno venendo alla festa”

(d)“Carlo e Marco stanno venendo insieme alla festa”

(e) “Carlo ha una maglia bianca e blu”

(f) “Carlo ha superato l’esame ed è andato in ferie”

(g) “Carlo è andato al bar e ha preso un caffè”

(h)“Carlo e Marco pesano ciascuno 80 Kg”

(i) “Carlo e Marco pesano insieme 160 Kg”

3. Dire se nelle seguenti proposizioni la “o” è inclusiva o esclusiva:

(a) “Nelle fermate a richiesta l’autobus si ferma se qualche persona deve scendere o salire”

(b) “Nel menu turistico è compreso il dolce o la frutta”

(c) “Paolo sposerà Marina o Monica”

(d) “Per vincere quel concorso bisogna essere molto bravi o raccomandati”

(e) “L’unanimità si raggiunge quando tutti sono favorevoli o tutti sono contrari”

(f) “Puoi farmi avere notizie tramite Claudia o tramite Elisa”

4. Dire a cosa equivalgono i termini sottolineati nelle seguenti proposizioni:

(a) “Giovanna è bella, ma Claudia è intelligente”

(b) “Marcello è in campo, benché abbia la febbre”

(c) “John è in Italia senza avere il passaporto”

(d) “Giorgio è italiano dato che è nato a Imperia”

(e) “David è spagnolo perché è nato a Barcellona”

(f) “Oggi è bello e quindi vado in barca” (g) “Carlo gioca a meno che piova”

(i) “A meno che Carlo intervenga, lo scontro è inevitabile”

(i) “Dario va al bar precisamente quando alla televisione trasmettono una partita del Milan”

(l) “Il fantasma appare nel castello esattamente ogni volta che scocca la mezzanotte”.

5. “Sono ammesse al concorso le persone che sono laureate e che hanno meno di trent’anni o hanno figli”. Aldo non è laureato, ha ventisei anni e un figlio. Paolo è laureato, ha quarant’anni e due figli. Vincenzo è laureato ha trentadue anni e non ha figli. Chi può partecipare al concorso? La “o” è inclusiva o esclusiva?

6. Si verifichi che A → B, oltre che a ¬(A ∧ ¬B), equivale a ¬A ∨ B.

7. Data una proposizione condizionale A → B, detta proposizione diretta, se si scambiano tra loro antecedente e conseguente si ottiene la proposizione inversa B → A; se si negano antecedente e conseguente si ottiene la proposizione contraria ¬A → ¬B; infine, invertendo la contraria, si ottiene la proposizione contronominale ¬B → ¬A. Verificare che:

(a) se è vera la proposizione diretta è vera la contronominale e, viceversa, se è vera la contronominale è vera la diretta.

(b) se è vera la proposizione inversa è vera la contraria e, viceversa, se è vera la contraria è vera l’inversa.

(c) se è vera la diretta non è detto che sia vera l’inversa.

8. Angelo, Bruno e Carlo sono tre studenti che hanno sostenuto un esame. Ponendo: A = “Aldo ha superato l’esame”, B = “Bruno ha superato l’esame” C = “Carlo ha superato l’esame” determinare le proposizioni composte che traducono le seguenti proposizioni:

(a) “Solo Carlo ha superato l’esame”

(b) “Solo Aldo non ha superato l’esame”

(c) “Solo uno tra Aldo, Bruno e Carlo ha superato l’esame”

(d) “Almeno uno tra Aldo, Bruno e Carlo ha superato l’esame”

(e) “Almeno due tra Aldo, Bruno e Carlo hanno superato l’esame”

(f) “Al più due tra Aldo, Bruno e Carlo hanno superato l’esame”

(g) “Esattamente due tra Aldo, Bruno e Carlo hanno superato l’esame”

9. Angelo, Bruno e Carlo sono gli unici tre membri di una commissione che vota una proposta. Ponendo: A = “Angelo vota a favore” B = “Bruno vota a favore ” C = “Carlo vota a favore” determinare le proposizioni composte che traducono le seguenti proposizioni:

(a) “La votazione è stata unanime”

(b) “La proposta è passata a maggioranza”

(c) “La proposta ha ricevuto un numero dispari di voti”

(d) “La proposta è stata respinta, ma non all’unanimità”

(e) “La proposta è stata respinta con il voto contrario di Bruno”

10. Posto: A = “Carlo è ligure” e B = “Diego è piemontese”, scrivere le fp che formalizzano le seguenti proposizioni:

(a) “Carlo non è ligure”

(b) “Carlo è ligure e Diego è piemontese”

(c) “Carlo è ligure sebbene Diego sia piemontese”

(d) “Non è vero che Carlo sia ligure e Diego piemontese”

(e) “Se Carlo non è ligure, allora Diego non è piemontese”

(f) “È falso che se Carlo è ligure, allora Diego è piemontese”

(g) “Carlo è ligure solo se Diego non è piemontese”

(h) “Carlo è ligure se e solo se Diego non è piemontese”

(i) “O Carlo è ligure o, se Carlo non è ligure, allora Diego è piemontese”

(l) “O Carlo è ligure e Diego è piemontese, o né Carlo è ligure, né Diego è piemontese”

11. Posto A = “Angelo viene alla festa” B = “Bruno viene alla festa” C = “Carlo viene alla festa” D = “Davide viene alla festa” scrivere le fp che formalizzano le seguenti proposizioni:

(a) “Angelo viene alla festa, ma Bruno no”

(b) “Se Davide viene alla festa allora vengono anche Bruno e Carlo”

(c) “Carlo viene alla festa se non vengono Angelo e Bruno”

(d) “Davide viene alla festa se e solo se viene Carlo e non viene Angelo”

(e) “O Carlo viene alla festa, o Bruno e Davide non vengono”

(f) “Se Davide viene alla festa, allora, se Carlo non viene, viene Angelo”

(g) “Carlo viene alla festa purché venga Davide, ma, se viene Davide, allora Bruno non viene”

(h) “Se vengono alla festa Angelo e Bruno, allora viene Carlo se non viene Davide”

(i) “Carlo viene alla festa se non vengono Bruno e Angelo o se viene Davide”

(l) “Se Angelo viene alla festa allora vengono Bruno o Carlo, ma se Angelo non viene alla festa, allora vengono Carlo e Davide”

(m) “Affinché Angelo venga alla festa, bisogna che se non vengono Bruno e Carlo, allora venga Davide”

(n) “Angelo, Bruno e Carlo vengono alla festa se e solo se Davide non viene, ma, se né Angelo né Bruno vengono, Davide viene se viene Carlo”

12. Calcolare la tavola di verità delle seguenti forme proposizionali e stabilire quali sono tautologie: (a) A ∨ B → A (b) A ∨ B ↔ A ∧ B (c) (A ∧ B) ∨ (¬A ∧ ¬B) (d) ((A → B) → B) → B (e) ((A → B) → B) ∨ ¬B (f) ((A → B) → B) → ¬B (g) (A ∨ B ↔ A ∧ B) ↔ (A ↔ B) 12 (h) (((A → B) → B) → ¬B) ↔ ¬B (i) ¬(A ∨ B) → (¬B ∨ ¬A)

13. Calcolare la tavola di verità delle seguenti forme proposizionali e stabilire quali sono tautologie: (a) A ∧ (B ∨ C) → A ∨ (B ∧ C) (b) A ∨ (B ∧ C) → A ∧ (B ∨ C) (c) A ∧ (B → C) → (B → A ∧ C) (d) (B → A ∧ C) → A ∧ (B → C) (e) (A → B ∨ C) ↔ (B → A ∨ C) (f) ¬(A ∧ B → C) → B ∨ ¬(A ∧ B) (g) ¬(B ∧ (C → A ∧ C)) (h) (B ∧ C) ∨ ((A ∧ B) ∨ (A ∧ C)) (i) ¬(A ∨ (B ∨ C) → A ∧ (B ∧ C))

14. Verificare che le seguenti forme proposizionali sono tautologie: (a) principio del terzo escluso: A ∨ ¬A (b) principio di non contraddizione: ¬(A ∧ ¬A) (c) idempotenza della congiunzione: A ∧ A ↔ A (d) idempotenza della disgiunzione: A ∨ A ↔ A (e) principio di identità: A → A (f) legge della doppia negazione: A ↔ ¬ ¬A

15. Verificare che le seguenti forme proposizionali sono tautologie: (a) A ∧ B ↔ B ∧ A (proprietà commutativa della congiunzione) (b) A ∨ B ↔ B ∨ A (proprietà commutativa della disgiunzione) (c) A ∧ B → A A ∧ B → B (eliminazione della congiunzione) (d) A → (B → (A ∧ B)) (introduzione della congiunzione) (e) A → A ∨ B A → B ∨ A (introduzione della disgiunzione) (f) A ∧ (A ∨ B) ↔ A (I legge di assorbimento) (g) A ∨ (A ∧ B) ↔ A (II legge di assorbimento) (h) A ∧ ¬A → B (I legge di Scoto) (i) A → (¬A → B) (II legge di Scoto)

16. Verificare che le seguenti forme proposizionali sono tautologie: (a) (¬A → ¬B) → (B → A) (I legge di contrapposizione) (b) (A → B) → (¬B → ¬A) (II legge di contrapposizione) (c) (A → ¬B) → (B → ¬A) (III legge di contrapposizione) (d) (¬A → B) → (¬B → A) (IV legge di contrapposizione) (e) ((A → B) → A) → A (legge di Peirce) (f) (A ↔ B) ↔ (B ↔ A) (proprietà commutativa del bicondizionale) (g) (A ↔ B) ↔ (¬A ↔ ¬B) (h) (¬A ↔ B) ↔ (A ↔ ¬B) (i) (A → B) ∨ (B → A) (l) A ∧ B ↔ ¬(¬A ∨ ¬B) (I legge di De Morgan) (m) A ∨ B ↔ ¬(¬A ∧ ¬B) (II legge di De Morgan) (n) (A → B) ↔ ¬A ∨ B (legge di Filone Megarico) (o) (A → B) ↔ ¬(A ∧ ¬B) (legge di Crisippo) (p) A ∧ B ↔ ¬(A → ¬B) (q) A ∨ B ↔ (¬A → B)

17. Verificare che le seguenti forme proposizionali sono tautologie: (a) A ∧ (B ∧ C) ↔ (A ∧ B) ∧ C (proprietà associativa della congiunzione) (b) A ∨ (B ∨ C) ↔ (A ∨ B) ∨ C (proprietà associativa della disgiunzione) (c) A ∧ ( B ∨ C) ↔ (A ∧ B) ∨ (A ∧ C) (proprietà distributiva della congiunzione rispetto alla disgiunzione) (d) A ∨ (B ∧ C) ↔ (A ∨ B) ∧ (A ∨ C) (proprietà distributiva della disgiunzione rispetto alla congiunzione) 13 (e) (A → B) → ((B → C) → (A → C)) (prima legge di concatenazione) (f) (A → B) ∧ (B → C) → (A → C) (seconda legge di concatenazione) (g) (A → (B → C)) ↔ ((A → B) → (A → C)) (legge di Frege) (h) (A → (B → C)) ↔ (A ∧ B → C) (i) ( A → B) → ((A → C) → (A → B ∧ C)) (l) (A → C) → ((B → C) → (A ∨ B → C)) (m) (A → (B ∧ C)) ↔ (A → B) ∧ (A → C) (n) (A → (B ∨ C)) ↔ (A → B) ∨ (A → C)

18. Verificare che i condizionali inversi di (e), (f), (i) e (l): ((B → C) → (A → C)) → (A → B) (A → C) → (A → B) ∧ (B → C) ((A → C) → (A → B ∧ C)) → (A → B) ((B → C) → (A ∨ B → C)) → (A → C) non sono tautologie.

19. Verificare se le seguenti coppie di forme proposizionali sono logicamente equivalenti: (a) A (A ∨ B) ∧ (A ∨ ¬B) (b) ¬(A ∧ B) ¬A ∨ ¬B (c) A → B ¬B → A (d) A ∨ B ¬B → A (e) A ∧ B ¬(A → ¬B) (f) ¬(A ∨ B) ¬B (g) A ∨ B (¬A ∧ B) ∨ (A ∧ ¬B) (h) ¬(A ∧ B) ¬A → ¬B (i) A → (B → (A → B)) B → (A → (B → A))

20. Verificare se le seguenti coppie di forme proposizionali sono logicamente equivalenti: (a) A ∧ (B → C) B ∧ (A → C) (b) A ∧ B → C A → C (c) A ∨ B → C (A → C) ∧ (B → C) (d) A ∧ (B ∨ C) (A ∧ B) ∨ C (e) A ∨ B → C ∧ ¬C ¬A ∧ ¬B

21. Come si è detto, la “o” del linguaggio comune è ambigua in quanto può essere usata sia in senso inclusivo che in senso esclusivo. Per evitare ambiguità si può precisare, per la disgiunzione inclusiva, “A o B o entrambi” e, per disgiunzione esclusiva, “A o B e non entrambi”. Verificare le forme proposizionali:

(A ∨ B) ∨ (A ∧ B)

(A ∨ B) ∧ ¬(A ∧ B)

22. Stabilire se la forma proposizionale a sinistra è o non è conseguenza logica della forma proposizionale a destra:

(a) ¬(A ∧ B) ¬(A ∨ B)

(b) A ∨ B A ∨ B

(c) A B → A

(d) B → A A

(e) B → (A ∧ B) A

23. Stabilire se la forma proposizionale a sinistra è o non è conseguenza logica della forma proposizionale a destra:

(a) (A ∧ B) → ¬C (A ∧ ¬B) → C

(b) ¬C → (A → ¬B) A → (B → C)

(c) (A ∨ B) → C B → C

(d) ¬A (A → B) ∧ (A → ¬B)

24. Dire quali delle seguenti forme proposizionali sono conseguenza logica delle premesse A ∨ B e A ∨ C:

(a) A

(b) B ∨ C

(c) ¬A → (B ∧ C)

(d) (B ∧ C) → ¬A

(e) (¬C → A) ∧ (¬B → A)

25. Verificare che la forma proposizionale ¬A è conseguenza logica delle forme proposizionali A → B, B → C, ¬C.

26. Verificare che la forma proposizionale A → ¬C è conseguenza logica delle forme proposizionali A → ¬B, C → B.

32. “Se Carlo ha vinto la gara, allora Mario è arrivato secondo oppure Sergio è arrivato terzo. Sergio non è arrivato terzo. Quindi, se Mario non è arrivato secondo, allora Carlo non ha vinto la gara”.

33. “Se Carlo ha vinto la gara, allora Mario è arrivato secondo oppure Sergio è arrivato terzo. Mario è arrivato secondo. Quindi, se Carlo ha vinto la gara, allora Sergio non è giunto terzo”.

34. “Se Carlo ha vinto la gara, allora Mario è arrivato secondo e Sergio è arrivato terzo. Mario non è arrivato secondo. Pertanto Carlo non ha vinto la gara”.

35. “Se Carlo ha vinto la gara, allora, se Mario è arrivato secondo, allora Sergio è arrivato terzo. Mario non è arrivato secondo. Quindi, o Carlo ha vinto o Sergio è arrivato terzo”.

36. “Se giochi e studi supererai gli esami, ma se giochi e non studi non supererai gli esami. Pertanto, se giochi, allora o studi e supererai gli esami o non studi e non supererai gli esami”.

RISPOSTE 1 . Sono proposizioni (a), (c), (f), (g), (i), (l).

2 . In (a), (c), (h).

3 . In (a), (d), (f) inclusiva; in (b), (c), (e) esclusiva.

4 . “ma” e “benché” equivalgono alla congiunzione logica ∧; “senza” equivale a “e non” (“John è in Italia” ∧ ¬ “John ha il passaporto”); “dato che” e “perché” sono indicatori di premesse: le due proposizioni sintetizzano un’applicazione del modus ponens: “Se Giorgio è nato a Imperia, allora Giorgio è italiano”, “Giorgio è nato a Imperia”, quindi “Giorgio è italiano” e “Se David è nato a Barcellona, allora David è spagnolo” e “David è nato a Barcellona”, quindi “David è spagnolo”; analogamente “e quindi” è un indicatore di conclusione: “Se oggi è bello, allora vado in barca” e “Oggi è bello”, quindi “Vado in Barca”; “A a meno che B” significa in genere “se non B, allora A” o anche, equivalentemente, “B o A”; “precisamente” ed “esattamente” in genere equivalgono a “se e solo se”.

5 . Aldo e Vincenzo no, Paolo sì.

8 . (a) ¬A ∧ ¬B ∧ C (b) ¬A ∧ B ∧ C (c) (A ∧ ¬B ∧ ¬C) ∨ (¬A ∧ B ∧ ¬C) ∨ (¬A ∧ ¬B ∧ C) (d) A ∨ B ∨ C (e) (A ∧ B ∧ C) ∨ (A ∧ B ∧ ¬C)∨(A ∧ ¬B ∧ C) ∨ (¬A ∧ B ∧ C (f) ¬(A ∧ B ∧ C) (g) (A ∧ B ∧ ¬C) ∨ (A ∧ ¬B ∧ C) ∨ (¬A ∧ B ∧ C) 9 . (a) (A ∧ B ∧ C) ∨ (¬A ∧ ¬B ∧ ¬C) (b) (A ∧ B ∧ C) ∨ (A ∧ B ∧ ¬C) ∨ (A ∧ ¬B ∧ C) ∨ (¬A ∧ B ∧ C) (c) (A ∧ B ∧ C) ∨ (A ∧ ¬B ∧ ¬C)∨(¬A ∧ B ∧ ¬C) ∨ (¬A ∧ ¬B ∧ C) (d) (A ∧ ¬B ∧ ¬C) ∨ (¬A ∧ B ∧ ¬C) ∨ (¬A ∧ ¬B ∧ C) (e) (¬A ∧ ¬B ∧ ¬C) ∨( ¬A ∧ ¬B ∧ C) ∨ (A ∧ ¬B ∧ ¬C)

10. (a) ¬A (b) A ∧ B (c) A ∧ B (d) ¬(A ∧ B) (e) ¬A → ¬B (f) ¬(A → B) (g) A → ¬B (h) A ↔ B (i) A ∨ (¬A → B) (l) (A ∧ B) ∨ (¬A ∧ ¬B)

11.

(a) A ∧ ¬B

(b) D → B ∧ C

(c) ¬A ∧ ¬B →

(d) D ↔ C ∧ ¬A

(e) C ∨ (¬B ∧ ¬D)

(f) D → (¬C → A)

(g) (D ↔ C) ∧ (D → ¬B)

(h) A ∧ B → (¬D → C)

(i) (¬B ∧ ¬A) ∨ D → C

(l) (A → B ∨ C) ∧ (¬A → C ∧ D)

(m) (¬B ∧ ¬C → D) → A

(n) (A ∧ B ∧ C ↔ ¬D) ∧ (¬A ∧ ¬B → (C → D))

12. (a)VVFV (b) VFF V (c) VF FV (d) VFVV (e) tautologia (f) FVFV (g) tautologia (h) tautologia (i) tautologia

13. (a) tautologia (b) V V V F F V V V (c) tautologia (d) VVVVVV F F (e) VVVF VFVV (f) tautologia (g) FF VVVFVV (h) VVVF VFFF (i) FVVVVVVF

19. Sono logicamente equivalenti (a), (b), (d), (e), (g), (i).

20. Sono equivalenti (c) e (e).

22. La conseguenza logica sussiste in (a), (d) e (e).

23. La conseguenza logica sussiste in (b) e (d).

24. (c) e (e).

32. Corretta.

33. Scorretta

34. Corretta.

35. Scorretta.

36. Corretta.