LOGICA MATEMATICA

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

Logica dei predicati

Svolgere i seguenti esercizi usando il metodo dei tableaux semantici o il calcolo dei sequenti di Gentzen. Esercizio 1 Verificare che le seguenti formule sono valide:

1. ∀xP (x) ∨ ∃x¬P (x);

2. ∀xP (x) → ∀zP (z);

3. ¬AxP (x) → ∃z¬P (x);

4. P (a) ∨ (∀xP (x) → Q(a);

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

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

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

8. ∀x(P (x) ∨ Q(x)) → (∃x¬P (x) → ∃xQ(x));

9. ∀y(∀xP (x) → P (y)); 10. ∀y(P (y) → ∃xP (x));

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

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

11. ∃y(P (y) → ∀xP (x));

12. ∃y(∃xP (x) → P (y);

13. ∀x∀y(P (x) → Q(y)) → ∀x(P (x) → ∀yQ(y));

14. (∃xP (x) → ∀xP (x)) → ∀xP (x) → ∀zP (z));

15. ∃x∀yR(x, y) → ∃xR(x, x);

16. ∃xR(x, x) → ∃x∃yR(x, y);

17. ∃x∃y(R(x, y) ∨ R(y, x)) → ∃x∃yR(x, y);

18. ∀x∀y(R(x, y) ∨ R(y, x)) → ∀xR(x, x). Esercizio 2 Verificare che le seguenti formule non sono valide:

1. ∃xP (x) ∧ ∃xQ(x) → ∃x(P (x) ∧ Q(x);

2. ∀x(p(x) ∨ Q(x) → ∀xP (x) ∨ Q(x);

3. (∀xP (x) → Q(a)) → ∀x(P (x) → Q(a));

4. (∀xP (x) → ∀xQ(x)) → ∀x(P (x) → Q(x));

5. (∃xP (x) → Q(a) → ∃x(P (x) → Q(a));

6. ∃x(P (x) → Q(x)) → (∃xP (x) → ∃xQ(x));

7. ∀xP (x) ∨ ∀x¬P (x);

8. ∀x¬P (x) ∨ ¬∃xP (x);

9. ∀x(P (x) ∧ Q(x) → M(x)) → ∀x(P (x) → Q(x) ∧ M(x));

10. ∃xP (x) ∧ ∃xQ(x) → ∀x(P (x) ∨ Q(x));

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

12. ∃x(P (x) → Q(x)) → ∀x(P (x) → Q(x));

13. ∀x(P (x) → Q(x)) ∧ ∃xP (x) → ∀xQ(x); 14. ∀x(P (x) → Q(x)) → ∀x(P (x) → ∀yQ(y));

15. ∀x(P (x) → ∀yR(x, y)) → ∃x(P (x) → ¬∀yR(x, y));

16. ∀y(∃xR(x, y) → ∃xR(x, x);

17. ∀x(R(a, x) ↔ S(a, x)) ∧ ¬R(a, b) → ¬S(b, a);

18. ∀x¬∀yR(x, y) → ¬∀yR(y, y);

19. ∀x∃yR(x, y) → ∃y∀xR(x, y) (attenzione, l’albero procede all’infinito!);

20. ¬∀x(P (x) → ∃yR(y, x)) ∨ ∀x¬P (x)) (attenzione, l’albero procede all’infinito!).

Esercizio 3 Verificare le conseguenze logiche:

1. ∀x(P (x) → Q(x)), ∀xP (x) ⊧ Q(a);

2. ∀x(P (x) → Q(x)), ¬∃xQ(x) ⊧ ¬Q(a);

3. ¬∀x(P (x) → Q(x)), ¬∃xP (x) ⊧ ∃xQ(x);

4. ∃x(P (x)∨Q(x)), ∀x(P (x) → ¬Q(x)), ∀x(Q(x) → ¬P (x)) ⊧ ∃x¬(P (x)∧ Q(x));

5. ∀x(R(b, x) → R(x, b)), ∀x(P (x) → ¬R(x, b)) ⊧ ¬∃x(P (x) ∧ R(b, x));

6. ∀x(R(b, x) → R(x, b)), ∃x(P (x) ∧ ¬R(x, b)) ⊧ ∃x(P (x) ∧ ¬R(b, x));

7. ∀x(P (x) → R(b, x)), ∀x(Q(x) → ¬R(b, x)), Q(c) ⊧ ∃x¬P (x);

8. ∀x(P (x) → ∃yR(y, x)), ∀x∀y¬R(x, y) ⊧ ∀x¬P (x);

9. ∀x¬P (x), ∃yR(a, y) → ∃xP (x) ⊧ ∀y¬R(a, y);

10. ∀x(P (x) ∧ Q(x) → T (x)), ∀yQ(y) ∧ ¬∀zS(z, a) ⊧ ∀z(P (z) → T (z)). Esercizio 4 Verificare che non sono conseguenze logiche:

1. ∀x(P (x) → Q(x)), ∀xQ(x) ⊧ P (a);

2. P (a) → Q(b), ∀x¬P (x) ⊧ ¬Q(b); 3. ¬∃x(P (x) ∧ Q(x)) ⊧ ¬P (a);

4. ∀x(P (x) → Q(x)) → ∃xM(x), ∀x(M(x) → Q(x)) ⊧ ∀x(¬P (x) ∨ Q(x));

5. ∃xP (x), ∀x(P (x) → R(x, x)) ⊧ ∃x(P (x) ∧ ∀yR(x, y)). Esercizio 5 Verificare che i seguenti insiemi di formule non sono soddisfacibili:

1. {∀x∀y(Q(x) ∧ R(x) → P (y)), ∃xQ(x), ∀xR(x) → ∀yQ(y)};

2. {∃xP (x) ∧ ∃x¬P (x), ∃xP (x) → ∀x¬P (x)}

3. {¬∀x(P (x) → Q(x)), ¬∃xP (x), ¬∃xQ(x)}

4. {∃x∃y(Rx, y) ∨ R(y, x)), ¬∃x∃yR(x, y)}. Esercizio 6 Verificare che i seguenti insiemi di formule sono soddisfacibili:

1. {∃xP (x), ∃xQ(x), ¬∀x(P (x) ∨ Q(x)};

2. {∀x∀y(Q(x) ∧ R(x) → P (y)), ∃xQ(x), ¬(R(a) → ∀yP (y))};

3. {∀x∀y(Q(x) ∧ R(x) → P (y)), ∃xQ(x), ¬∀y(P (y) → ∃xR(x))};

4. {∀x∃yR(x, y), ¬∀zR(z, z)}. Esercizio 7 Ricordiamo che una relazione R è:

• riflessiva se e solo se ∀xR(x, x);

• irriflessiva se e solo e ∀x¬R(x, x);

• simmetrica se e solo se ∀x∀y(R(x, y) → R(y, x));

• asimmetrica se e solo se ∀x∀y(R(x, y) → ¬R(y, x));

• antisimmetrica se e solo se ∀x∀y(R(x, y) ∧ R(y, x) → x = y);

• transitiva se e solo se ∀x∀y∀z(R(x, y) ∧ R(y, z) → R(x, z));

• intransitiva se e solo e ∀x∀y∀z(R(x, y) ∧ R(y, z) → ¬R(x, z)).

Verificare che: 1. ogni relazione asimmetrica è irriflessiva;

2. ogni relazione asimmetrica è antisimmetrica;

3. ogni relazione irriflessiva e transitiva è asimmetrica;

4. ogni relazione intransitiva è irriflessiva;

5. ogni relazione simmetrica e antisimmetrica è transitiva;

6. ogni relazione transitiva e intransitiva è asimmetrica;

7. ogni relazione transitiva e irriflessiva è asimmetrica;

8. non è detto che una relazione transitiva e simmetrica sia anche riflessiva.