T1: Logica, discorso e conoscenza

T1: Logica, discorso e conoscenza

Primo modulo:

Logica classica

ovvero

Deduzione formale vs verit`a:

un’introduzione ai teoremi limitativi

Simone Martini

Dipartimento di Scienze dell’Informazione Alma mater studiorum – Universit`a di Bologna

martini@cs.unibo.it

Outline

1 Prima lezione: la logica dall’informale al formale Pillole di storia (e problemi) della logica

2 Seconda lezione: Linguaggi del prim’ordine Logica proposizionale; linguaggi predicativi

1 Terza lezione: verit`a e validit`a

Formule vere dovunque e vere in classi di modelli

2 Quarta lezione: dimostrazioni Sistemi formali per la derivabilit`a

5 Quinta lezione: l’aritmetica di Peano Un sistema di assiomi; propriet`a

Outline

1 Prima lezione: la logica dall’informale al formale Pillole di storia (e problemi) della logica

2 Seconda lezione: Linguaggi del prim’ordine Logica proposizionale; linguaggi predicativi

1 Terza lezione: verit`a e validit`a

Formule vere dovunque e vere in classi di modelli

2 Quarta lezione: dimostrazioni Sistemi formali per la derivabilit`a

5 Quinta lezione: l’aritmetica di Peano Un sistema di assiomi; propriet`a

6 Sesta lezione: i teoremi limitativi

Verit` a in un’interpretazione

Sia A una formula sul linguaggio LΣ

Sia A una interpretazione per LΣ

A `e vera in Asse per ogni ρ, [[A]]^A_ρ =V In simboli: A |= A

Leggi: A `e un modello di A Si estende ad insiemi di formule Γ :

A |= Γ sse per ogni A 2 Γ, si ha A |= A

Esempi (gi` a visti)

P =8n ¬(s(n) = 0)

`e una formula nel linguaggioL+,s

N, Z, {} sono tutte interpretazioni per L+,s

N |= P Z 6|= P {} 6|= P

Formule vere in ogni interpretazione?

Dicemmo:

I Siamo tentati di dire che alcune sue formule sono “vere”:

8n(n = n), 8n(n + 0 = n), 8n8m8p(n = m ∧ m = p → n = p)

I e che altre sono “false”: 8m(0 + 0 = m), 9n8m(n + m = 0)

I “verit`a” e “falsit`a” pre-suppongono un’interpretazione canonicadei simboli del linguaggio

I Nessuna formula `e “vera” o “falsa” in assoluto, ma solo in riferimento ad una specifica interpretazione (cio`e una semantica) del linguaggio

Siamo sicuri?

Consideriamo P → P, o 8x(x = x)

Per una interpretazione qualsiasiA, queste formule sono vere

Leggi logiche

Il linguaggio ha due livelli:

1 Livello logico comune: connettivi, quantificatori ecc.

2 Livello specifico: aspetti specifici del dominio

La semantica del livello specifico dipendedall’interpretazione perch´e dipende da come si associano oggetti semantici ai simboli

La semantica del livello logico `e invece fissatanella nozione di

“funzione semantica”, [[ ]]

E.g., [[A∧ B]]^A_ρ =V sse [[A]]^A_ρ =V e [[B]]^A_ρ =V [[t₁=t₁]]^A_ρ =V sse [[t₁]]^A_ρ = [[t₂]]^A_ρ

Validit` a

Una formulaA `e validasse per ogni interpretazioneA, si ha A |= A

|= A

Le formule valide sono “leggi logiche”

La loro verit`a non dipende dal dominio, ma dalla semantica dei connettivi e dei quantificatori

Questa semantica `e per noi “connaturata” (“built-in”) alla logica che stiamo descrivendo

Alcune leggi logiche proposizionali

1 P → P

2 P → (Q → P) a fortiori

3 P ∧ Q → P

4 P → ¬¬P doppia negazione debole

5 (P → Q) → (¬Q → ¬P) tollendo tollens

6 P → (¬P → ¬Q) legge debole di Duns Scoto

7 P → (¬P → Q) legge forte di Duns Scoto

8 P ∨ ¬P terzo escluso

9 ¬¬P → P doppia negazione forte

10 (P → Q)↔(¬P ∨ Q) legge di Filone Megarico

→ Q) → P) → P

Alcune leggi logiche quantificate

1 (8xP) → (9xP)

2 9x8yP → 8x9yP

3 8xP ↔¬9x¬P

4 9xP ↔¬8x¬P

Procedimento di decisione?

Legge proposizionale

I Alberi semantici (tableaux)

I Tavola di veri`a

I Meccanizzabile (ma richiede tempo esponenziale)

I Il problema “decidere se una formula A `e una tautologia” `e coNP-completo.

Se P 6= NP, `e intrinsecamente esponenziale Legge quantificata

I Ragionare a partire dalla definizione:

difficile per via delle quantificazioni

I Meccanizzabile?

Una validit` a “condizionata”?

Consideriamo le due formule

1 8n(n + 0 = n)

2 8n8m(n + m = m + n)

8n(0 + n = n) `e certamente vera tutte le volte che(1) e (2) sono vere

Pi`u precisamente:

In ogni interpretazione che `e un modello di (1) e (2), anche 8n(0 + n = n) `e vera

Diciamo che 8n(0 + n = n) `econseguenza logicadi (1) e (2)

Conseguenza logica formule chiuse

Sia Γ un insieme di formule chiuse e P una formula.

P `econseguenza logicadi Γ (scrivi: Γ |= P) sse

per ogni interpretazioneA, seA |= Γ, allora A |= P.

P `e necessariamente vera laddove le formule di Γ sono vere.

Conseguenza logica caso generale

Sia Γ un insieme di formule e P una formula.

P `econseguenza logicadi Γ (scrivi: Γ |= P) sse

per ogni interpretazioneA, e per ogni ambiente ρ su A:

per tutte le Q 2 Γ [[Q]]^Aρ =V =⇒ [[P]]^Aρ =V P `e necessariamente vera laddove le formule di Γ sono vere, nello stesso ambiente.

Centralit` a della conseguenza logica

La matematica `e incentrata su questa nozione

La logica del novecento nasce per chiarire questa nozione Un insieme di formule caratterizza (assiomatizza) una certa nozione matematica (gli ordini parziali, i gruppi, gli anelli ecc.) Si studiano i teoremi che valgono per tutte quelle strutture (tutti i gruppi, tutti gli anelli, tutti gli ordini parziali ecc.)

Un esempio sul linguaggio del successore

SiaL0,succ il linguaggio di zero e successore.

Sia G il seguente insieme di formule:

8a8b [succ(a) = succ(b) → a = b]

8a [succ(a) 6= 0]

Ogni modello di G (ogni interpretazioneA tale che A |= G) contiene un numero infinito di elementi.

Ma non c’`e grande struttura. P.e. G 6|= 8x9yx = succ(y).

L’insieme Ord

SiaLOrd il linguaggio senza costanti o funzioni e col solo simbolo di predicato M

Sia Ord il seguente insieme di formule suLOrd : 8xM(x, x)

8x8y(M(x, y) ∧ M(y, x) → x = y) 8x8y8z(M(x, y) ∧ M(y, z) → M(x, z)

Ord esprime che M `e un predicato (binario)riflessivo, antisimmetricoe transitivo.

Cio`e M `e una relazione d’ordine.

SeA `e un modello di Ord, deveavere un ordine

Alcuni modelli di Ord

N |= Ord Z |= Ord {} |= Ord

Molte altre interpretazioni

I D0: D ={0, 1}, M^D0(0, 0) = V , M^D0(1, 1) = V

I D1: D ={0, 1}, M^D1(0, 0) = V , M^D1(1, 1) = V ,M^D1(0, 1) = V

I D2: D ={0, 1}, M^D2(0, 0) = V , M^D2(1, 1) = V ,M^D2(1, 2) = V Ci sono infinitimodelli di Ord !

La teoria degli ordini parziali

Un modello di Ord `e un ordine parziale

Le conseguenze logiche di Ord sono le propriet`a che valgono per tutti gli ordini parziali

Th(Ord ) ={P | Ord |= P}

La teoria degli ordini parziali `e costituita da tutte quelle formule che sono conseguenza logica di Ord , cio`e che sono vere in ogni ordine parziale.

Conseguenze di formule “logiche”

Consideriamo il linguaggio puro (no costanti, no variabili, un insieme numerabile di simboli di predicato)

La conseguenza logica ha senso anche in questo caso A, A→ B |= B

B non `e certo una legge logica. . .

¬B(c), 8x(A(x) → B(x)) |= ¬A(c)

I gruppi

Un gruppo `e un insieme con un’operazione binaria associativa L’operazione ha un elemento neutro

Ogni elemento ha un inverso

Il linguaggio: Lgruppo ={, ²}; nessun predicato.

Sia Grp l’insieme delle quattro formule seguenti:

8x8y8z[(x  y)  z = x  (y  z)]

8x(  x) = x) e anche 8x(x  ) = x) 8x9y(x  y = 0) ∧ (y  x = 0)

La teoria dei gruppi

Le conseguenze logica di Grp sono i teoremi sui gruppi Th(Grp) ={P | Grp |= P}

Modelli di Grp sono Z con la somma; Q con il prodotto; R con il prodotto ecc. ecc.

Quanti sono i modelli di una teoria?

1 Ci sono solo modelli finiti (il cui dominio `e finito)

I Linguaggio con una sola costante, diciamo 0

8x(x = 0) ha un solo modello, quello con un solo elemento

I Linguaggio con due sole costanti, diciamo 0 e 1

8x(x = 0 ∨ x = 1) ∧ ¬(0 = 1) ha un solo modello, quello con un due elementi

I In questo casoi modelli di tali formule sono in numero finito (uno solo, in entrambi i casi)

2 Ci sono (anche) modelli infiniti (il cui dominio `e infinito)

I Linguaggio con una sola costante (0) ed un simbolo di funzione s¹

I 8x¬(x = s(x)) ha modelli sia finiti (per esempi con due elementi) sia infiniti (cio`e di cardinalit`a infinita)

I In questo caso `e possibile dimostrare che esistono

Quanti sono i modelli di una teoria?

1 Ci sono solo modelli finiti (il cui dominio `e finito)

I Linguaggio con una sola costante, diciamo 0

8x(x = 0) ha un solo modello, quello con un solo elemento

I Linguaggio con due sole costanti, diciamo 0 e 1

8x(x = 0 ∨ x = 1) ∧ ¬(0 = 1) ha un solo modello, quello con un due elementi

I In questo casoi modelli di tali formule sono in numero finito (uno solo, in entrambi i casi)

2 Ci sono (anche) modelli infiniti (il cui dominio `e infinito)

I Linguaggio con una sola costante (0) ed un simbolo di funzione s¹

I 8x¬(x = s(x)) ha modelli sia finiti (per esempi con due elementi) sia infiniti (cio`e di cardinalit`a infinita)

I In questo caso `e possibile dimostrare che esistono

Quanti sono i modelli di una teoria?

1 Ci sono solo modelli finiti (il cui dominio `e finito)

I Linguaggio con una sola costante, diciamo 0

8x(x = 0) ha un solo modello, quello con un solo elemento

I Linguaggio con due sole costanti, diciamo 0 e 1

8x(x = 0 ∨ x = 1) ∧ ¬(0 = 1) ha un solo modello, quello con un due elementi

I In questo casoi modelli di tali formule sono in numero finito (uno solo, in entrambi i casi)

2 Ci sono (anche) modelli infiniti (il cui dominio `e infinito)

I Linguaggio con una sola costante (0) ed un simbolo di funzione s¹

I 8x¬(x = s(x)) ha modelli sia finiti (per esempi con due elementi) sia infiniti (cio`e di cardinalit`a infinita)

I In questo caso `e possibile dimostrare che esistono

“Difficolt` a” della conseguenza logica

Se Γ ha (anche) modelli infiniti (col dominio infinito) Allora Γ ha infiniti modelli (non `e un gioco di parole. . . ) (Tale infinito `e di una cardinalit`a estremamente grande) L’insieme delle conseguenze logiche di Γ caratterizza cos`ı il comportamento di una collezione vastissima di interpretazioni Come stabilire allora una conseguenza logica?

Non possiamo ragionare su questa (enorme) collezione di modelli!

Alla ricerca di metodi sintattici

Dimostrazioni come oggetti formali

Un linguaggio L

Un insieme di formule suL, gli assiomi Un insieme di regole di inferenza

Un insieme di (meta-)regole (sintattiche, combinatorie, effettive) che spiegano come le regole di inferenza permettono di “dedurre” nuove formule a partire da formula gi`a dedotte Unteorema`e una formula dedotta dagli assiomi con una serie (finita) di applicazioni delle regole di inferenza

Nessun riferimento ad una specifica semantica o modello inteso

Sistemi formali

Pluralit`a di “tipi” di sistemi formali:

alla Hilbert (assiomi e regole)

il pi`u antico; comodo per parlare dei modelli di una teoria deduzione naturale (Gentzen, 1934)

studio delle dimostrazioni come oggetti formali sequenti (Gentzen, 1934)

studio delle dimostrazioni, dimostrazioni di consistenza tableaux (Beth, 1955)

ricerca di dimostrazioni (in realt`a: refutazioni) risoluzione (Robinson, 1963)

ricerca di dimostrazioni (in realt`a: refutazioni) reti di dimostrazione (Girard, 1987)

Esempio: logica positiva dell’implicazione alla Hilbert

(Schemi di) assioma

1 A→ (B → A) assioma K

2 (A→ (B → C)) → ((A → B) → (A → C)) assioma S Regola di inferenza

P → Q P

Q modus ponens Meta-regole

1 Ogni istanza di un assioma `e un assioma

2 Una derivazione `e una sequenza di formule P0,P1, . . . ,Pn

dove ogni Pi `e:

F un assioma, oppure

Una derivazione

Vogliamo dimostrare A→ A

Una derivazione

Vogliamo dimostrare A→ A

(1) (A→ (B → C)) → ((A → B) → (A → C))

sostituiamo Aal posto di C assioma S

Una derivazione

Vogliamo dimostrare A→ A

(1) (A→ (B →A))→ ((A → B) → (A →A))

sostituiamo (A→ A) al posto di B assioma S

Una derivazione

Vogliamo dimostrare A→ A

(1) (A→ ((A→ A)→ A)) → ((A →(A→ A))→ (A → A)) assioma S

Una derivazione

Vogliamo dimostrare A→ A

(1) (A→ ((A → A) → A)) → ((A → (A → A)) → (A → A)) assioma S (2) A→ (B → A)

sostituiamo (A→ A) al posto di B assioma K

Una derivazione

Vogliamo dimostrare A→ A

(1) (A→ ((A → A) → A)) → ((A → (A → A)) → (A → A)) assioma S (2) A→ ((A→ A)→ A)

assioma K

Una derivazione

Vogliamo dimostrare A→ A

(1) (A→ ((A → A) → A)) → ((A → (A → A)) → (A → A)) assioma S (2) A→ ((A → A) → A)

assioma K (3) (A→ (A → A)) → (A → A) MP, da (1) e (2)

Una derivazione

Vogliamo dimostrare A→ A

(1) (A→ ((A → A) → A)) → ((A → (A → A)) → (A → A)) assioma S (2) A→ ((A → A) → A)

assioma K (3) (A→ (A → A)) → (A → A) MP, da (1) e (2) (4) A→ (B → A)

sostituiamo Aal posto di B assioma K

Una derivazione

Vogliamo dimostrare A→ A

(1) (A→ ((A → A) → A)) → ((A → (A → A)) → (A → A)) assioma S (2) A→ ((A → A) → A)

assioma K (3) (A→ (A → A)) → (A → A) MP, da (1) e (2) (4) A→ (A→ A)

assioma K

Una derivazione

Vogliamo dimostrare A→ A

(1) (A→ ((A → A) → A)) → ((A → (A → A)) → (A → A)) assioma S (2) A→ ((A → A) → A)

assioma K (3) (A→ (A → A)) → (A → A) MP, da (1) e (2) (4) A→ (A → A)

assioma K

(5)A→ A MP, da (3) e (4)

Logica classica proposizionale, alla Hilbert

1 A→ (B → A)

2 (A→ (B → C)) → ((A → B) → (A → C))

3 B∧ C → B

4 B∧ C → C

5 B → (C → B ∧ C)

6 B → B ∨ C

7 C → B ∨ C

8 (B→ D) → ((C → D) → (B ∨ C → D))

9 (B→ C) → ((B → ¬C) → ¬B)

10 ¬B → (B → C)

∨ ¬A

Logica classica dei predicati, alla Hilbert

1 Gli assiomi proposizionali

2 (8xP(x)) → P(t)

3 P(t)→ 9xP(x)

4 8x(Q → P(x)) → (Q → 8xP(x))

5 8x(P(x) → Q) → (9xP(x) → Q)

6 Regole di inferenza

I modus ponens

I

P(x )

8xP(x) generalizzazione

Condizione aggiuntiva: In 4 e 5, Q non deve contenere x (libera)

Alberi semantici: regole predicative

8x A[x]^V A[t]V

8x A[x] ^F A[y ]F

9x A[x]^V A[y ] V

9x A[x]^F A[t] F

t termine generico; y fresca nel suo ramo.

Per l’uguaglianza: ad un ramo pu`o essere sempre aggiunto un nodo tra questi:

t = t V

t1 =s1∧ . . . ∧ tn=sn→ f (t1, . . . ,tn) =f (s1, . . . ,sn) V

Alberi semantici predicativi: esempio

8x(A[x] → B[x]) → (8xA[x] → 8xB[x])^F 8x(A[x] → B[x])^V

8xA[x] → 8xB[x]^F 8xA[x]^V 8xB[x]^F B[y]F

A[y ]V

A[y ]→ B[y]^V b

bb

"

"

"

A[y ]V B[y ]F

Le due regole centrali che “eliminano” 8 con y non possono essere scambiate! La y deve essere fresca nel ramo.

Altri sistemi logici

Diverso ruolo reciproco di assiomi e regole

Diversa nozione di dimostrazione (e.g., no successione di formule, ma oggetto grafico bidimensionale)

Un certo sistema formale S d`a luogo ad una propria nozione di derivazione `S

Equivalenza

Tutti i sistemi formali per la logica del prim’ordine sono equivalenti rispetto ai teoremi

cio`e, dati due sistemi formali S e S<sup>0</sup>, si ha Γ `S A sse Γ `S⁰ A

La deduzione naturale:

calcolo minimale per ∧ e →

Assiomi: nessuno Regole:

A B

A∧ B ∧I A∧ B

A ∧E1 A∧ B

B ∧E2

[A]....

B

A→ B → I A→ B A

B → E

Deduzione naturale:

un esempio di dimostrazione

` A ∧ B → B ∧ A [A∧ B]

A

[A∧ B]

B A∧ B → B ∧ A