• un insieme di assiomi

Sistemi di inferenza

Consentono di derivare formule da altre formule: formalizzazione del ragionamento.

Un sistema di inferenza `e costituito da:

• un insieme di assiomi

• un insieme di regole di inferenza, che consentono di derivare formule da altre formule.

A derivabile da S nel sistema X: S ⊢ _X A Propriet`a fondamentale:

S ⊢ _X A sse S |= A

Il calcolo di deduzione naturale NK

• Assiomi: Ø

• Regole di inferenza: una regola di introduzione e una regola di eliminazione per ogni connettivo logico + regole per ⊥

Regole di inferenza:

A 1 , ..., A n

C Derivazione:

A ₁ A ₂ B ₁

A ₃ B ₂ D ₁

A ₄ A ₅ B ₃ D ₂ C

A ₁ , ..., A ₅ : ipotesi da cui dipende la conclusione C Alcune regole consentono di “scaricare” ipotesi:

A 1 [A 2 ] B ₁

A ₃ B ₂ D ₁

A 4 [A 5 ]

B ₃

D ₂

C

Le regole di NK proposizionale

connettivo Regola di introduzione Regola di eliminazione

Nome Regola Nome Regola

∧ (I∧) A B

A ∧ B (E∧) A ∧ B

A

A ∧ B B

∨ (I∨) A

A ∨ B

B

A ∨ B (E∨)

[A] [B]

... ...

A ∨ B C C C

→ (I→)

[A] ...

B A→B

(E→) A A→B

B

connettivo Regola di introduzione Regola di eliminazione

Nome Regola Nome Regola

¬ (I¬)

[A] ...

⊥

¬A

(E¬) A ¬A

⊥

⊥ (E ₁ ⊥) ⊥

A

⊥ (E ₂ ⊥)

[¬A] ...

⊥

A

Regole che non scaricano ipotesi

Regole di introduzione e eliminazione della congiunzione A B

A ∧ B (I∧)

La regola ` e corretta: in qualsiasi interpretazione in cui sono vere entrambe le premesse, `e vera anche la conclusione.

A ∧ B

A (E∧) A ∧ B

B (E∧)

Entrambe le regole sono corrette: in qualsiasi interpretazione in cui `e vera la premessa, `e vera anche la conclusione di ciascuna regola.

Regole di introduzione della disgiunzione (indebolimento):

A

A ∨ B (I∨) B

A ∨ B (I∨)

Entrambe le regole sono corrette: in qualsiasi interpretazione in cui `e vera la

premessa, `e vera anche la conclusione di ciascuna regola.

Regola di eliminazione dell’implicazione (Modus Ponens o MPP):

A A→B

B (E→) C’`e il sole Se c’`e il sole, allora fa caldo Fa caldo

La regola ` e corretta: sia M una qualsiasi interpretazione tale che M |= A e M |= A→B. Poich´e queste due ipotesi non sono compatibili con M 6|= B, si deve avere M |= B.

Regola di eliminazione della negazione: da A e ¬A segue l’assurdo.

A ¬A

⊥ (E¬)

Poich´e ¬A ↔ A→⊥, questa regola `e un “caso particolare” di E→.

Prima regola di eliminazione del falso

⊥

A (E ₁ ⊥)

Ex falso quodlibet = dal falso segue qualunque cosa.

La regola ` e corretta: se la regola non fosse corretta, esisterebbe un’interpretazione

M tale che M |= ⊥ e M 6|= A. Poich´e nessuna interpretazione soddisfa ⊥, la regola `e

corretta.

Ragionamento per assurdo Regola di introduzione della

negazione

[A] ....

⊥

¬A (I¬)

Se dall’ipotesi che A sia vero si deriva un assurdo, allora A `e falso.

La conclusione ¬A deriva dalla sottoderiva- zione di ⊥ da A.

Seconda regola di eliminazione del falso

[¬A] ....

⊥

A (E ₂ ⊥)

Se dall’ipotesi che A sia falso si deriva un assurdo, allora A `e vero.

La conclusione A deriva dalla sottoderiva- zione di ⊥ da ¬A.

La conclusione (¬A o A) dipende da tutte le ipotesi da cui dipende ⊥ nel- la sottoderivazione, tranne (eventualmente) quella indicata tra parentesi quadre (A o ¬A), che viene scaricata.

Quindi:

Se da un insieme di ipotesi S ∪ A si deriva

⊥, allora da S si pu`o derivare ¬A:

S, A ⊢ ⊥ S ⊢ ¬A

Se da un insieme di ipotesi S ∪ ¬A si deriva

⊥, allora da S si pu`o derivare A:

S, A ⊢ ⊥

S ⊢ ¬A

Esempio

Se Antonio non va alla stazione, non incontra Anna. Ma Antonio incontra Anna. Quindi va alla stazione.

Ragionamento: assumiamo (per assurdo) che Antonio non vada alla stazione. Allora dal- l’ipotesi “se Antonio non va alla stazione, non incontra Anna” si avrebbe che Antonio non incontra Anna. Ma questo contraddice il fatto che invece Antonio incontra Anna (assurdo).

Quindi l’ipotesi che Antonio non vada alla stazione `e falsa: Antonio va alla stazione.

La conclusione (Antonio va alla stazione) non dipende dall’ipotesi (scaricata con la riduzione all’assurdo) “Antonio non va alla stazione”.

“Antonio va alla stazione” = p

“Antonio incontra Anna” = q ¬p→¬q, q ⊢ p

q

[¬p] ¬p→¬q

¬q (E→)

⊥ (E¬)

p (E ² ⊥)

Rappresentazioni alternative delle derivazioni Scrittura lineare

ipotesi riga formula regola da ...

1 1. ¬p→¬q ipotesi

2 2. q ipotesi

3 3. ¬p ipotesi

1, 3 4. ¬q E→(1, 3)

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

1, 2 6. p E ₂ ⊥(5) - scarica 3

La prima colonna della riga n indica i nu- meri di riga delle formule da cui dipende la formula della riga n stessa.

Quando si applicano regole che non sca- ricano ipotesi, la conclusione dipende dal- l’unione delle formule da cui dipendono le premesse.

Righe 1, 2, 3: regola di assunzione: in qualunque punto della derivazione si pu`o assumere

una qualsiasi formula, che dipende da se stessa.

Scatole di derivazione

riga formula regola da ...

1. ¬p→¬q ipotesi

2. q ipotesi

Π

3. ¬p ipotesi 4. ¬q E→(1, 3) 5. ⊥ E¬(2, 4)

scatola E ₂ ⊥

6. p E ₂ ⊥(Π)

Le formule di ogni (sotto)derivazione dipendono da tutte le ipotesi della

(sotto)derivazione stessa + tutte le ipotesi

delle derivazioni che la includono.

Regola di eliminazione della disgiunzione: ragionamento per casi

A ∨ B

[A] ....

C

[B] ....

C C

“I casi sono due: A oppure B. Se vale A allora vale C; anche se vale B vale C. Quindi C vale comunque.”

La conclusione C deriva da:

• la formula A ∨ B (che a sua volta dipende da un insieme di ipotesi S 0 )

• la sottoderivazione di C che dipende da A (ed eventualmente altre ipotesi S ₁ )

• la sottoderivazione di C che dipende da B (ed eventualmente altre ipotesi S ₂ ) La conclusione C di (E∨) dipende da S ₀ ∪ S ₁ ∪ S ₂ :

• tutte le ipotesi da cui dipende A ∨ B;

• tutte le ipotesi da cui dipende C nella prima sottoderivazione, eccetto (eventualmente) A;

• tutte le ipotesi da cui dipende C nella seconda sottoderivazione, eccetto (eventualmente) B.

S ⊢ A ∨ B S , A ⊢ C S , B ⊢ C

Esempio 1. Almeno uno tra Antonio e Giorgio `e colpevole;

2. Antonio non lavora mai senza la complicit`a di Giorgio.

Giorgio `e colpevole

Ragionamento: se vale (1) allora si hanno 2 casi:

Caso 1: Antonio `e colpevole. Ma se vale (2), in questo caso anche Giorgio `e colpevole.

Caso 2: Giorgio `e colpevole.

In tutti e due i casi Giorgio `e colpevole. Quindi Giorgio `e colpevole comunque.

“Antonio `e colpevole” = p

“Giorgio `e colpevole” = q p ∨ q, p→q ⊢ q

p ∨ q

[p] p→q

q (E→) [q]

q (E∨)

La conclusione q dipende solo da p ∨ q e p→q.

Si noti che la foglia (ipotesi) q `e una derivazione di q da q.

Scrittura lineare ipotesi riga formula regola da ...

1 1. p ∨ q ipotesi

2 2. p→q ipotesi

3 3. p ipotesi

2, 3 4. q E→(2, 3)

5 5. q ipotesi

1, 2 6. q E ∨ (1, 4, 5) - scarica 3 e 5 Scatole di derivazione

riga formula regola da ...

1. p ∨ q ipotesi

2. p→q ipotesi

Π 1 3. p ipotesi

4. q E→(2, 3) scatola E∨

Π ₂ 5. q ipotesi scatola E∨

Regola di introduzione dell’implicazione (Prova Condizionale)

Per dimostrare che “se A, allora B” segue da S, assumiamo che siano vere A e tutte le formule in S, e dimostriamo che allora vale B

[A] ...

B A→B

Se S, A ⊢ B, allora S ⊢ A→B

Esempio

1. Se A. non ha incontrato B. la notte scorsa, allora B. `e colpevole;

2. Se B `e colpevole, allora il delitto `e avvenuto dopo la mezzanotte.

Se A. non ha incontrato B. la notte scorsa, allora il delitto `e avvenuto dopo la mezzanotte Ragionamento: assumiamo (1) e (2).

Assumiamo inoltre che A non abbia incontrato B la notte scorsa.

Per (1) allora B `e colpevole.

E per (2) il delitto `e avvenuto dopo la mezzanotte.

Quindi SE .... ALLORA ....

Formalizzazione e derivazione

“A non ha incontrato B la n.s.” = A

“B `e colpevole” = B

“il delitto `e avvenuto dopo la m.” = C

A→B, B→C ⊢ A→C

(transitivit`a dell’implicazione)

[A] A→B

B (E→)

B→C

C (E→)

A→C (I→) Scrittura lineare:

ipotesi riga formula regola da ...

1 1. A→B ipotesi

2 2. B→C ipotesi

3 3. A ipotesi

1, 3 4. B E→(1, 3)

1, 2, 3 5. C E→(2, 4)

1, 2 6. A→C I→(5) - scarica 3

Osservazioni

1. Le regole possono consentire di scaricare ipotesi, ma non ci obbligano a farlo.

Ad esempio, sarebbe comunque corretto: A, B, C ⊢ D A, B, C ⊢ A→D

2. Un albero di derivazione pu`o contenere pi`u occorrenze di una stessa ipotesi A. Appli- cando una regola di inferenza che lo consente, si possono scaricare

• solo alcune occorrenze di A (una o pi`u)

• tutte le occorrenze di A

• nessuna occorrenza di A: questo pu`o accadere, ad esempio, quando la premessa della regola non dipende da A....

3. Infatti la formula “scaricata” potrebbe anche non comparire tra le ipotesi da cui dipende la premessa.

La formulazione corretta (ad esempio) della regola I→ sarebbe:

S ⊢ B

S − {A} ⊢ A→B

Ed infatti possiamo derivare che B ⊢ A→B con una sola applicazione di I→:

B (I→) B ⊢ B

Cavalieri e furfanti A dice: “Io sono un furfante oppure B `e un cavaliere”.

Cosa sono A e B?

Formalizzazione:

“A `e un cavaliere” = A (“A `e un furfante” = ¬A)

“B `e un cavaliere” = B (“B `e un furfante” = ¬B) Sappiamo che:

se A `e un cavaliere allora quello che dice `e vero, e se `e un furfante quello che dice `e falso.

Quello che A dice `e: ¬A ∨ B ^′′ . Ipotesi:

1) A→¬A ∨ B

2) ¬A→¬(¬A ∨ B) Problemi:

a) A→¬A ∨ B, ¬A→¬(¬A ∨ B) ⊢ A ? b) A→¬A ∨ B, ¬A→¬(¬A ∨ B) ⊢ ¬A ? c) A→¬A ∨ B, ¬A→¬(¬A ∨ B) ⊢ B ? d) A→¬A ∨ B, ¬A→¬(¬A ∨ B) ⊢ ¬B ?

Importante: l’unico modo (generale) per dimostrare che una formula F non `e derivabile

da un insieme S di formule in un sistema di inferenza corretto consiste nel dimostrare che

S 6|= F :

Derivazioni

A→¬A ∨ B, ¬A→¬(¬A ∨ B) ⊢ A [¬A]

¬A ∨ B (I∨) [¬A] ¬A→¬(¬A ∨ B)

¬(¬A ∨ B) (E→)

⊥ (I⊥)

A (E 2 ⊥)

Sia Π la derivazione mostrata sopra. Allora quella che segue `e una derivazione di:

A→¬A ∨ B, ¬A→¬(¬A ∨ B) ⊢ B

...

Π ...

A ...

Π ...

A A→¬A ∨ B

¬A ∨ B (E→)

[¬A] ⁽¹⁾

[B] ⁽²⁾ [¬B] ⁽³⁾

⊥ (E¬)

¬A (E ₁ ⊥)

¬A (E∨) ^[1,2]

⊥ (I⊥)

B (E ₂ ⊥) ^[3]

¬A ∨ B ¬B

Utili regole derivate

Regola derivata: se esiste una derivazione A ₁ , ..., A _n ⊢ B, allora si pu`o utilizzare A ₁ ... A _n

B come regola derivata.

Modus Tollens (MTT): A→B ¬B

¬A

Se A. `e un furfante, A. mente; A. non mente A. non `e un furfante

Giustificata dal fatto che A→B, ¬B ⊢ ¬A [A] ⁽¹⁾ A→B

B (E→)

¬B

⊥ (E¬)

¬A (I¬) ^[1]

Osservazione: numeriamo ciascuna ipotesi che viene scaricata e indichiamo il numero

corrispondente in apice al nome della regola che la scarica.

Doppia Negazione (DN): ¬¬A

A e A

¬¬A Giustificate dal fatto che ¬¬A ⊢ A e A ⊢ ¬¬A

(1) [¬A] ¬¬A

⊥ (E¬)

A (E ₂ ⊥) ^[1]

A [¬A]

⊥ (E¬)

¬¬A (I¬)

Esempio

1. Se A. non ha incontrato B. la notte scorsa (A), allora B. `e colpevole (B) 2. Se il delitto `e avvenuto dopo la mezzanotte (C), allora B. non `e colpevole

Se A. non ha incontrato B. la notte scorsa, allora il delitto non `e avvenuto dopo la mezzanotte A→B, C→¬B ⊢ A→¬C

1 1. A→B ipotesi 2 2. C→¬B ipotesi 3 3. A ipotesi

1,3 4. B E→, da 1 e 3 1,3 5. ¬¬B DN, da 4

1,2,3 6. ¬C MTT, da 2 e 5

1,2 7. A→¬C I→, da 6, scarica 3

Eliminazione di ∨:

A ∨ B ¬A B

A ∨ B ¬B A

A ∨ B

(1) [A] ¬A

⊥ (E¬)

(2) [B] [¬B] ⁽³⁾

⊥ (E¬)

⊥ (E∨) ^[1,2]

B (I ₂ ⊥) ^[3]

Terzo escluso: ⊢ A ∨ ¬A [¬A] ⁽¹⁾

A ∨ ¬A (I∨)

[¬(A ∨ ¬A)] ⁽²⁾

⊥ (E¬)

A (E ₂ ⊥) ^[1]

A ∨ ¬A (I∨)

[¬(A ∨ ¬A)] ⁽³⁾

⊥ (E¬)

A ∨ ¬A (E ₂ ⊥) ^[2,3]

Correttezza e completezza

Sia NK che il sistema Hilbertiano sono corretti e completi rispetto alla semantica della logica proposizionale:

• Se S ⊢ A allora S |= A: correttezza

• Se S |= A allora S ⊢ A: completezza

Esercizio: Dimostrare la correttezza delle regole di NK che consentono di scaricare ipotesi.

Sostituibilit`a nelle derivazioni:

Se S ⊢ A allora S[B/p] ⊢ A[B/p]

Chiusura deduttiva di S: T (S) = {A | S ⊢ A}

T (S) `e anche chiamata la teoria di S e le formule di S sono gli assiomi della teoria

Esercizi: vedi libro di testo, pagina 59 e seguenti.