Esame di Logica Matematica - Soluzioni

(1)

Luglio 2008

Esercizi

1. Dimostrare che

¬∃x(M (x) ∧ C(x)) ∧ ∀x(P (x) → M (x)) ∧ ∃x(P (x) ∧ C(x)) |= ⊥

Soluzione: Sia F = ¬∃x(M (x) ∧ C(x)) ∧ ∀x(P (x) → M (x)) ∧ ∃x(P (x) ∧ C(x)) Allora 1) F |= ∃x(M (x) ∧ C(x))

F

∀x(P (x) → M (x)) P (x) → M (x)

P (x) ∧ C(x) 1

P (x) M (x)

P (x) ∧ C(x) 1

C(x) M (x) ∧ C(x)

∃x(M (x) ∧ C(x))

F

∃x(P (x) ∧ C(x))

∃x(M (x) ∧ C(x)) 1

2)

F Albero 1

∃x(M (x) ∧ C(x))

F

¬∃x(M (x) ∧ C(x))

⊥ 2. Decidere se

(∃xA(x) → ∀xB(x)) → ∀x(A(x) → B(x))

`

e una tautologia

Soluzione: Dimostriamo che ` (∃xA(x) → ∀xB(x)) → ∀x(A(x) → B(x)) A(x) 1

∃xA(x) ∃xA(x) → ∀xB(x) ²

∀xB(x) B(x) A(x) → B(x) 1

∀x(A(x) → B(x))

(∃xA(x) → ∀xB(x)) → ∀x(A(x) → B(x)) 2

3. Trasformare in clausole

(∀xA(x) → ∃x∀yB(x, y)) ∧ (∃x∃yB(x, y) ∨ ∃xA(z))

(2)

Soluzione: Le clausole sono:

{¬A(a), B(a, y)} {B(b, c), A(b)}

4. Descrivere tutti i modelli dell’enunciato

∀x(A(f (x)) → B(x))

Soluzione: L’enunciato `e vero in ogni modello D in cui per ogni x appartenente al dominio se f (x) ∈ A^D allora x ∈ B^D.