∀xA (I∀) ∀xA

Il calcolo di deduzione naturale NK per la logica dei predicati

A

∀xA (I∀) ∀xA

A[t/x] (E∀) se A non dipende da se t `e sostituibile

ipotesi contenenti per x in A x libera

A[t/x]

∃xA (I∃) ∃xA

[A] ....

B

B (E∃)

se t `e sostituibile se x non occorre libera in B per x in A n´e in alcuna ipotesi

da cui dipendono ∃xA o B (eccetto A stessa) NK `e corretto e completo:

Correttezza : se S ⊢ _NK A allora S |= A.

Completezza : se S |= A allora S ⊢ A

Eliminazione del quantificatore universale (istanziazione)

∀xA

A[t/x] (E∀)

se t `e sostituibile per x in A Se una propriet`a vale per tutti, vale anche per ciascuno

Senza la restrizione si potrebbe ad esempio derivare (scorrettamente):

∀x∃y (x < y)

∃y (y + 1 < y)

Introduzione del quantificatore universale (generalizzazione)

A

∀xA (I∀)

se A non dipende da ipotesi contenenti x libera Sia x un “qualsiasi oggetto del dominio”; .... vale A(x).

Quindi per ogni x vale A(x).

x non deve occorrere in nessuna ipotesi da cui dipende la conclusione A(x), altrimenti non sarebbe “qualsiasi”.

Senza la restrizione su (I∀) si potrebbe ad esempio derivare (scorrettamente):

[A]

∀xA (I∀) : NO!

A→∀xA (I→)

∀x(A→∀xA) (I∀)

∀x(A→∀xA) non `e valida: `e equivalente a ∃xA→∀xA.

Esempi

1. Tutti i milanesi sono italiani 2. Tutti gli italiani sono europei QUINDI: tutti i milanesi sono europei

[m(x)]

∀x(m(x)→it(x))

m(x)→it(x) (E∀)

it(x) (E→) ∀x(it(x)→e(x))

it(x)→e(x) (E∀)

e(x) (E→)

m(x)→e(x) (I→)

∀x(m(x)→e(x)) (I∀) 1 1. ∀x(m(x)→it(x)) ipotesi 2 2. ∀x(it(x)→e(x)) ipotesi 1 3. m(x)→it(x) E∀(1) 2 4. it(x)→e(x) E∀(2)

5 5. m(x) ipotesi

1,5 6. it(x) E→(3, 5)

1,2,5 7. e(x) E→(4, 6)

1,2 8. m(x)→e(x) I→(7, 5), scarica 5

1,2 9. ∀x(m(x)→e(x)) I∀(8)

1. Non esiste nessun numero naturale minore di zero QUINDI: tutti i numeri naturali minori di zero sono dispari

[minore(x, zero)] ⁽¹⁾

∀x¬ minore(x, zero)

¬ minore(x, zero) (E∀)

⊥ (E¬)

dispari(x) (E 1 ⊥)

minore(x, zero)→dispari(x) (I→) ⁽¹⁾

∀x(minore(x, zero)→dispari(x)) (I∀)

Nota: la premessa dell’applicazione di I∀ non dipende dall’ipotesi minore(x, zero) (1), precedentemente scaricata da I→.

1 1. ∀x¬ minore(x, zero) ipotesi

2 2. minore(x, zero) ipotesi

1 3. ¬ minore(x, zero) E∀(1)

1,2 4. ⊥ E¬(2, 3)

1,2 5. dispari(x) E ₁ ⊥(4)

1 6. minore(x, zero)→dispari(x) I→(5)

1 7. ∀x(minore(x, zero)→dispari(x)) I∀(6)

Nota: la riga 6 dipende solo dalla riga 1, che non contiene x libera.

Introduzione del quantificatore esistenziale A[t/x]

∃xA (I∃)

se t `e sostituibile per x in A Senza restrizione la regola non sarebbe corretta.

Ad esempio, sia A = ∀y(x = y) e t = y.

Quindi A[t/x] = ∀y(y = y)

∀y(y = y)

∃x∀y(x = y) (I∃) : NO!

Eliminazione del quantificatore esistenziale (regola del testimone)

∃xA

[A] ....

B

B (E∃)

se x non occorre libera in B n´e in nessuna delle ipotesi da cui dipendono ∃xA e B, eccetto A stessa.

Se ∃xA, posso dare un nome a un tale x (x `e un “testimone”)

“sappiamo che esiste un oggetto x tale che A(x). Sia allora x un tale oggetto, e ragioniamo su x. ... Ne deduciamo che `e vero B. Quindi B `e vero.”

Il “nome” x non deve essere utilizzato per altri scopi: non dobbiamo fare nessun’altra assunzione su x.

Inoltre, x deve essere utilizzato solo temporaneamente, e non deve occorrere nella conclu-

sione B.

Eliminazione del quantificatore esistenziale (II)

Se x potesse comparire nella conclusione, potremmo derivare ad esempio: ∃xA→∀xA:

[∃xA] ⁽¹⁾ [A] ⁽²⁾

A (E∃) ^[2] : NO!

∀xA (I∀)

∃xA→∀xA (I→) ^[1]

Se x potesse comparire in altre ipotesi da cui dipende B, si potrebbe derivare, ad esempio:

∃x p(x) ⊢ ∀x (q(x)→∃x (p(x) ∧ q(x))):

∃x p(x)

(1) [p(x)] [q(x)] ⁽²⁾

p(x) ∧ q(x) (I∧)

∃x (p(x) ∧ q(x)) (I∃)

∃x (p(x) ∧ q(x)) (E∃) ^[1] : NO!

q(x)→∃x (p(x) ∧ q(x)) (E→) ^[2]

∀x (q(x)→∃x (p(x) ∧ q(x))) (I∀) Ma ∃x p(x) 6|= ∀x (q(x)→∃x (p(x) ∧ q(x)))

Si ricordi che:

∀x (q(x)→∃x (p(x) ∧ q(x))) ↔ ∃x q(x)→∃x (p(x) ∧ q(x)).

Eliminazione del quantificatore esistenziale:

scrittura con scatole di derivazione n ∃xA

Π

n ₁ A Ipotesi ... ... ...

n ₂ B ...

scatola E∃

m B E∃(Π)

Esempio

1. Esiste un numero intero minore di zero

2. Tutti i numeri interi minori di zero sono minori di uno QUINDI: esiste un numero intero minore di uno

∃x minore(x, 0), ∀x(minore(x, 0)→minore(x, 1)) ⊢ ∃x minore(x, 1)

∃x minore(x, 0)

[minore(x, 0)] ⁽¹⁾

∀x(minore(x, 0)→minore(x, 1))

minore(x, 0)→minore(x, 1) (E∀)

minore(x, 1) (E→)

∃x minore(x, 1) (I∃)

∃x minore(x, 1) (E∃) ^[1]

1. ∃x minore(x, 0) ipotesi

2. ∀x(minore(x, 0)→minore(x, 1)) ipotesi 3. minore(x, 0)→minore(x, 1) E∀(2)

Π

4. minore(x, 0) ipotesi 5. minore(x, 1) E→(3, 4) 6. ∃x minore(x, 1) I∃(5)

scatola E∃

7. ∃x minore(x, 1) E∃(Π)

Esercizio. Formalizzare il seguente ragionamento e dire che cosa c’`e di sbagliato:

Per ogni numero naturale, c’`e qualche numero pi`u grande. Pertanto, sia n un numero arbitrario: n deve essere inferiore a qualche altro numero. Sia m un tale numero. Si ha n < m. Poich´e n `e arbitrario, si ha che ogni numero `e pi`u piccolo di m. Perci`o esiste un numero pi`u grande di tutti.

Esercizi.

Dimostrare mediante il calcolo di deduzione naturale la validit`a delle formule riportate a pagina 77 del libro di testo.

Considerare tutte le formule valide dell’esercizio K a pagina 92 e seguenti del libro di testo, e dimostrarne la validit`a mediante il calcolo di deduzione naturale.

Considerare tutti i ragionamenti corretti dell’esercizio L a pagina 92 e seguenti del libro di

testo, e dimostrarne la correttezza mediante il calcolo di deduzione naturale.

Utili regole derivate: eliminazione di ¬∀

¬∀xA

∃x¬A (E¬∀)

1. ¬∀xA ipotesi

Π ₁

2. ¬∃x¬A ipotesi

Π ₂

3. ¬A ipotesi 4. ∃x¬A I∃(3) 5. ⊥ E¬(2, 4)

scatola E ₂ ⊥

6. A E ₂ ⊥(Π ₂ )

7. ∀xA I∃(6)

8. ⊥ E¬(1, 7)

scatola E ₂ ⊥

9. ∃x¬A E ₂ ⊥(Π ₁ )

Utili regole derivate: eliminazione di ¬∃

¬∃xA

∀x¬A (E¬∃)

1. ¬∃xA ipotesi

Π ₁

2. ¬∀x¬A ipotesi

Π ₂

3. A ipotesi 4. ∃xA I∃(3) 5. ⊥ E¬(1, 4)

scatola I¬

6. ¬A I¬(Π ₂ )

7. ∀x¬A I∃(6)

8. ⊥ E¬(2, 7)

scatola E ₂ ⊥

9. ∀x¬A E ₂ ⊥(Π ₁ )

Il paradosso di Russell Assioma di comprensione (Frege):

Per ogni propriet`a o concetto P esiste l’insieme x di tutti gli oggetti che godono di P Per ogni propriet`a P :

∃x∀y(y ∈ x ≡ P (y)) Russell: sia P (y) = _def ¬(y ∈ y)

∃x∀y(y ∈ x ≡ y 6∈ y) Sia ora x l’insieme tale che ∀y(y ∈ x ≡ y 6∈ y). x ∈ x ?

Assumiamo di avere una derivazione Π ₁ di ∀y(y ∈ x ≡ ¬y ∈ y) ⊢ ¬(x ∈ x) e una derivazione Π 2 di ∀y(y ∈ x ≡ ¬y ∈ y) ⊢ x ∈ x.

Allora la seguente sarebbe una derivazione di ∃x∀y(y ∈ x ≡ y 6∈ y) ⊢ ⊥:

∃x∀y(y ∈ x ≡ y 6∈ y)

[∀y(y ∈ x ≡ ¬y ∈ y)] ⁽¹⁾ ...

(Π ₁ ) ...

¬(x ∈ x)

[∀y(y ∈ x ≡ ¬y ∈ y)] ⁽¹⁾ ...

(Π ₂ ) ...

x ∈ x

⊥ (E¬)

⊥ (E∃) ^[1]

Il paradosso di Russell (II) Ricordiamo che A ≡ B `e un’abbreviazione di (A→B) ∧ (B→A).

La derivazione seguente `e la derivazione Π ₁ di ∀y(y ∈ x ≡ ¬y ∈ y) ⊢ ¬(x ∈ x):

[x ∈ x] ⁽²⁾

[x ∈ x] ⁽²⁾

∀y(y ∈ x ≡ ¬y ∈ y)

(x ∈ x→¬x ∈ x) ∧ (¬x ∈ x→x ∈ x) (E∀)

x ∈ x→¬x ∈ x (E∧)

¬x ∈ x (E→)

⊥ (E¬)

¬(x ∈ x) (I¬) ^[2]

E quella seguente `e la derivazione Π 2 di ∀y(y ∈ x ≡ ¬y ∈ y) ⊢ x ∈ x:

[¬x ∈ x] ⁽³⁾

[¬x ∈ x] ⁽³⁾

∀y(y ∈ x ≡ ¬y ∈ y)

(x ∈ x→¬x ∈ x) ∧ (¬x ∈ x→x ∈ x) (E∀)

¬x ∈ x→x ∈ x (E∧)

x ∈ x (E→)

⊥ (E¬)

x ∈ x (E ² ⊥) ^[3]