LOGICA MATEMATICA

Claudia Malvenuto e Roberto Maieli^{∗} Canale E-O - a.a 2002-2003 Scheda di esercizi n. 14 17 novembre 2003

Calcolo dei Predicati

Esercizio 1 Formalizzare le seguenti espressioni lingustiche, nella logica dei predicati, usando costanti e variabili individuali, connettivi e quantificatori:

1. a qualcuno piace Simona,

2. Simona non piace a nessuno,

3. nessuno ama Davide e Davide ama Maria,

4. se Davide ama qualcuno, allora ama Maria,

5. chiunque ama Davide ama anche Maria,

6. chiunque ama Davide se e solo se ama Maria,

7. se qualcuno ama Davide allora è amato da Maria,

8. chiunque ama Davide o Maria,

9. chi ama Maria non ama Davide,

10. chiunque ama Davide e Maria, ama se stesso, 11. solo se qualcuno ama Maria allora tutti sono amati da Davide,

∗Dipartimento di Informatica, Università di Roma “La Sapienza”, Via Salaria, 113.

E-mail: claudia, maieli@dsi.uniroma1.it.

12. chiunque si impegna supera l’esame,

13. se Aldo capirà la logica, allora tutti gli studenti la capiranno,

14. nessuno studente capirà la logica, a meno che Aldo la capisca,

15. tutti i professori, tranne quelli di logica, sono noiosi, e qualche professore di logica è noioso,

16. se un professore non insegna bene la logica, gli studenti non la capiranno,

17. vi è almeno uno studente che capirà la logica e uno studente che sarà apprezzato da tutti i professori,

18. ogni professore è apprezzato da qualche studente e qualche professore è apprezzato da tutti gli studenti,

19. ogni professore annoia qualche studente e gli studenti che capiscono tutto sono annoiati da ogni professore.

Esercizio 2 Data l’interpretazione I che ha dominio {2, 3, 6, 9, 18}, assegna alle costanti a := 2, b := 3, c := 18 ed interpreta il predicato P = ”essere pari” e il predicato R := ”essere multiplo”, determinare se le seguenti formule sono vere o false:

P (a),  P (b),  R(a, b),
R(a, a),  R(c, a),  ¬P (b) ∨ P (c),
R(a, c) → P (a),  R(b, b) → ¬R(b, a), ∃x(P (x) ∧ R(x, c)),
∃x∀yR(x, y) ∧ ∀y∃xR(x, y), ∃x∀yR(x, y),  ∀x(P (x) → R(x, b))
∃x(R(x, b) ∧ P (x)),  ∀xR(x, x).

Esercizio 3 Supponiamo che in una certa interpretazione I sono vere le seguenti formule:

P (a), P (b), ¬P (c), R(a, b), ¬R(a, c), R(b, c), R(c, c).

Quali tra le seguenti formule sono sicuramente false?

\begin{matrix}∀xP (x), & ¬∃xR(a, x), & ∀xR(b, x), \\ ∀x¬R(b, x), & ∀x¬R(c, x), & ∀x∃y¬R(x, y). \end{matrix}

Esercizio 4 Sia I una interpretazione con dominio D = {1, 3, 5, 15} e che interpreti i predicati P, R, S, rispettivamente come “essere pari”, “essere multiplo” ed “essere <” e che infine assegni alle costanti a, b, c, d i valori di D nel modo seguente:

a := 1, b := 3, c := 5, d := 15.

Determinare il valore di verità delle seguenti formule:

∃yP (y),  ∀x¬P (x), ∀zR(z, a),
∀xR(x, b), ∃yR(y, d), ∃zR(c, z),
∃xS(x, a),  ∀x(P (x) → R(x, a)), ∀x∃yS(x, y),
∀x∀yR(x, y),  ∀x(R(x, b) → S(x, c)), ∀x∀y(S(x, y) → ¬S(y, x)),
∀x∀y(R(x, y) → ¬R(y, x)), ∀x(R(x, c) ∨ S(x, c)), ∀x(R(x, b) ∨ S(x, b)).

Esercizio 5 Dato un dominio D = {2, 3, 4} ed un’assegnazione v che interpreti il predicato P come ′′ < 4′′ e il predicato Q com ′′ > 2′′, si assegnino alle costanti a, b valori del dominio D tali che rendano vere i seguenti insiemi di formule:

1. {P (a) ∧ Q(a), P (b) ∧ ¬Q(b)}

2. {P (a) → ∀xP (x), Q(b) → ∀xQ(x)},

3. {P (a) → ∀xP (x), Q(b) → ∀xQ(x), P (a) ∨ Q(b)}. Esercizio 6 Determinare per ciascuna delle seguenti formule un’interpretazione che la renda vera ed una che la renda falsa:

1. ∀x∃yP (y, x);

2. ∃x∀yP (x, y);

3. ∃xP (x) ∧ ∃x¬P (x);

4. ∃xP (x) ∧ ∃xQ(x) ∧ ¬∃(P (x) ∧ Q(x));

5. ∀x(P (x) → Q(x)) → ∀xP (x);

6. ∃x(P (x) ∧ Q(x)) → ¬∀x(P (x) ∨ Q(x));

7. ∃x(P (x) → Q(x)) → ∃x(P (x) ∧ Q(x)).