T1: Logica, discorso e conoscenza

(1)

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

(2)

Outline

1

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

1

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

3

Terza lezione: verit` a e validit` a

Formule vere dovunque e vere in classi di modelli

4

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 I teoremi di G¨ odel e Church

7

Temi d’esame

(3)

Outline

1

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

1

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

3

Terza lezione: verit` a e validit` a

Formule vere dovunque e vere in classi di modelli

4

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

(4)

Alcune bipartizioni

1

Logica vs Dominio di indagine (e.g., aritmetica)

2

Proposizioni vs Quantificazione

3

Sintassi vs Semantica

4

Linguaggio vs Metalinguaggio

(5)

Bipartizioni, 1

1

Logica vs Dominio di indagine (e.g., aritmetica)

I Livello logico comune: rende conto degli aspetti generali del ragionamento (e.g., connettivi, quantificatori ecc.)

I Livello specifico: rende conto degli aspetti specifici del dominio che si formalizza (e.g.,N, Z, ecc.)

2

Proposizioni vs Quantificazione

3

Sintassi vs Semantica

4

Linguaggio vs Metalinguaggio

(6)

Bipartizioni, 2

1

Logica vs Dominio di indagine (e.g., aritmetica)

2

Proposizioni vs Quantificazione

I Nomi, variabili e funzioni denotano individui, che possono essere quantificati

I L’applicazione di predicati (e.g., =) a individui d`a proposizioni

I Proposizioni manipolate conconnettivi: congiunzione, disgiunzione, implicazione, negazione, ecc.

I Proposizioni che contengono individui generici, possono dar luogo ad altre proposizioni mediantequantificazione:

universale, esistenziale

3

Sintassi vs Semantica

4

Linguaggio vs Metalinguaggio

(7)

Bipartizioni, 3

1

Logica vs Dominio di indagine (e.g., aritmetica)

2

Proposizioni vs Quantificazione

3

Sintassi vs Semantica

I Sintassi

F I simboli usati

F I modi di comporli in “frasi” sensate

F I modi di derivare frasi (conclusioni) da frasi (ipotesi)

I Semantica

F Gli oggetti che i simboli denotano

F I valori di verit`a che corrispondono alle frasi

F La relazione di conseguenza tra la verit`a di certe frasi (ipotesi) e la verit`a di altre frasi (conclusioni)

(8)

Bipartizioni, 4

1

Logica vs Dominio di indagine (e.g., aritmetica)

2

Proposizioni vs Quantificazione

3

Sintassi vs Semantica

4

Linguaggio vs Metalinguaggio

I Linguaggio della logica

I (Meta-)linguaggio nel quale la logica `e descritta

I “0+1=0” `e un teorema dell’aritmetica

I Teoremi e metateoremi (o meglio: teoria e metateoria)

(9)

Le proposizioni

proposizione:

oggetto elementare del discorso, dotato di valore di verit` a, fissato un opportuno stato di cose.

I OK:

“Simone `e un professore”; “17 `e un numero pari”; “P=NP”.

I KO:

“Mangia la minestra!”; “Spero che sia femmina”.

I “Il Barbarossa era chiamato cos`ı per via del colore della sua barba”.

I “`E necessario che domani io venga”.

I “Questa frase `e falsa”.

(10)

I connettivi proposizionali

connettivi:

operatori che aggregano proposizioni in proposizioni pi` u complesse

I congiunzione: ∧

I disgiunzione: ∨

I negazione: ¬

I implicazione: →

I sono operatori “verofunzionali”:

Il valore di verit`a di una proposizione composta dipende in modo univoco dal valore di verit`a delle proposizioni che la compongono.

(11)

Interpretazione: tabelle di verit` a

[[ ¬A]]

^A

= V sse [[A]]

^A

= F

[[A ∧ B]]

^A

= V sse [[A]]

^A

= V e [[B]]

^A

= V

[[A ∨ B]]

^A

= V sse [[A]]

^A

= V oppure [[B]]

^A

= V

[[A → B]]

^A

= V sse [[A]]

^A

= F oppure [[B]]

^A

= V

(12)

Intermezzo: connettivi intensionali

I connettivi classici (“verofunzionali”) non esauriscono l’interesse

Alcuni costruttori (del linguaggio naturale, della matematica, dell’informatica, ecc.) dipendono anche da altri fattori:

I modali: “`E necessario che”, “`E possibile che”, “Da ora in poi”, ecc.

I costruttivi: “A or B” `e stabilito esibendo una prova di A oppure una prova di B, ecc.

I lineari: “A( B” `e stabilito da una dimostrazione di B che usa l’ipotesi A una e una sola volta, ecc.

I . . .

Logiche “non classiche”: intuizionista, lineare, modale,

temporale, ecc.

(13)

Sintassi: Alfabeto

Sia Σ un insieme (numerabile) di (simboli di) proposizione atomica: P, Q, . . .

L’alfabeto del linguaggio proposizionale L

Σ

` e dato da

I Simboli propri: Σ

I Connettivi: ¬, ∧, ∨, →

I Simboli ausiliari: (, ),

(14)

Sintassi: formule

Le formule proposizionali sono definite induttivamente come segue:

1 Ogni simbolo di proposizione atomica `e una formula

2 Se A e B sono formule, allora¬A, A ∧ B, A ∨ B, A → B sono formule

3 Nient’altro `e una formula

(15)

Interpretazione: formule

Sia A un’interpretazione dei simboli di proposizione atomica:

per ogni proposizione atomica P, A fissa se P `e vera (V ) o falsa (F ).

L’interpretazione si estende in modo canonico alle formule:

[[P]]

^A

= V sse P ` e V in A [[ ¬A]]

^A

= V sse [[A]]

^A

= F

[[A ∧ B]]

^A

= V sse [[A]]

^A

= V e [[B]]

^A

= V

[[A ∨ B]]

^A

= V sse [[A]]

^A

= V oppure [[B]]

^A

= V

[[A → B]]

^A

= V sse [[A]]

^A

= F oppure [[B]]

^A

= V

(16)

Tautologie

Alcune formule sono valide indipendentemente da A:

P → P

[P ∧ (P → Q)] → Q P ∨ ¬P

((P → Q) → P) → P

Una formula A ` e una tautologia sse ` e vera indipendentemente dal valore di verit` a assegnato alle sue componenti atomiche.

|= A

(17)

Conseguenza

Alcune formule sono conseguenza di altre:

Se P → Q e P sono vere, allora Q `e vera.

Se P ∧ Q, Q → R e S sono vere, allora R ∧ S `e vera.

Una formula A ` e conseguenza dell’insieme di formule Γ sse ogni interpretazione A che rende vere tutte le formule in Γ, rende vera anche A.

Γ |= A

Non esiste alcuna interpretazione A che rende vere

contemporaneamente Γ e ¬A: l’insieme di formule Γ, ¬A `e

(18)

Un sistema formale per la conseguenza.

Regole sintattiche per derivare solo tautologie/conseguenze.

Alberi semantici (o tableaux): refutazione.

Per cercare di stabilire che A ` e una tautologia, proviamo a

ipotizzare A falsa e cerchiamo di derivare una contraddizione, cio` e una formula B che dovrebbe essere contemporaneamente vera e falsa.

Procedura basata solo sulla struttura sintattica di A.

(19)

Un esempio

P → (P ∨ Q) `e un tautologia.

Supponiamo P → (P ∨ Q) falsa. Allora:

P ` e

vera

P ∨ Q `e falsa, cio` e:

P ` e falsa Q ` e falsa

contraddizione: abbiamo sia P

vera

che P ` e falsa

(20)

Alberi semantici

Alberi etichettati con coppie (A, V ) oppure (A, F ), dove A ` e una formula.

Costruiti secondo regole sintattiche sulla struttura di A.

Esempio:

P → P ∨ Q

^F

P

V

P ∨ Q

^F

P

F

Q

F

(21)

Alberi semantici: regole

A ∧ B

^V

A

V

B

V

A ∧ B

^F ll ,,

A

F

B

F

A ∨ B

^V cc

##

A

V

B

V

A ∨ B

^F

A

F

B

F

A → B

^V ll ,,

A

F

B

V

A → B

^F

A

V

B

F

¬A

^V

A

F

¬A

^F

A

V

(22)

Alberi semantici: costruzione

Quando si applica una regola, la formula viene marcata Le regole si applicano solo a formule non marcate Le regole si applicano a tutti i rami che passano per una formula

Un nodo etichettato con una formula atomica viene marcato Un ramo ` e chiuso se contiene A e ¬A

Un ramo chiuso non viene pi` u esteso

Un albero ` e chiuso se tutti i suoi rami sono chiusi

Un albero ` e terminato se tutti i suoi rami sono chiusi oppure

hanno tutte le formula marcate

(23)

Alberi semantici: propriet` a

Procedimento sintattico anche se infiorettato di semantica

` A significa “C’`e un albero chiuso di radice A

^F

” B

₁

, . . . , B

_n

` A significa “C’`e un albero chiuso di radice B

1

∧ . . . ∧ B

n

∧ ¬A

^V

”

Teorema (correttezza e completezza)

B

₁

, . . . , B

_n

` A sse B

₁

, . . . , B

_n

|= A

(24)

Alberi semantici: decisione

Teorema

C’` e un algoritmo per decidere se, data una qualsiasi formula A, vale ` A.

Per il teorema di completezza, abbiamo un algoritmo per decidere se A ` e una tautologia.

Il teorema non varr` a pi` u per le logiche predicative.

Se una formula A genera un albero terminato, ma non chiuso

dall’albero si ottiene un (contro-)modello per A.

(25)

Alberi semantici: (contro-)modelli

I rami aperti forniscono un’interpretazione per i simboli atomici.

Esempio:

A ∨ B → A A ∨ B → A

^F

A ∨ B

^V

A

F

ll ,,

A

V

A

V

A ∨ B → A

^V b

b

"

A ∨ B

^F

A

F

B

F

A

V

(26)

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

11

((P → Q) → P) → P legge di Pierce

(27)

Logica predicativa

(28)

Semplici propriet` a aritmetiche, 1

Il numero 0 ` e l’elemento neutro della somma Per ogni numero n, n + 0 = n

8n(n + 0 = n) Nomi di individui: 0

“Nomi” generici (variabili): n Un predicato (binario): =

L’applicazione di un predicato ad individui d` a una proposizione: n + 0 = n

Un’operazione che trasforma individui in individui: + Un quantificatore su individui (generici): 8

La relativizzazione della quantificazione (“ogni numero”) ` e

scomparsa

(29)

Semplici propriet` a aritmetiche, 2

Zero non ` e il successore di alcun numero (in N) 8n ¬(s(n) = 0)

Un altro simbolo di operazione (funzione): s

Un nuovo operatore che trasforma proposizioni in

proposizioni: ¬

(30)

Sintassi: termini

Fissiamo un insieme di (simboli di) costante (e.g., 0) Fissiamo un insieme di (simboli di) funzione (e.g., +, s), col loro numero di argomenti (“ariet` a”) (e.g., +

²

, s

¹

)

Assumiamo di avere una riserva infinita di nomi di variabili (n, m, x , y , . . .)

I termini sono definiti induttivamente come segue:

1 Ogni costante `e un termine

2 Ogni nome di variabile `e un termine

3 Se fⁿ`e un simbolo di funzione n-aria e t1, . . . ,tnsono termini, allora f (t₁, . . . ,t_n)`e un termine

4 Nient’altro `e un termine

(31)

Sintassi: formule

Fissiamo un insieme di (simboli di) predicato ciascuno col proprio numero di argomenti (“ariet` a”)

Il predicato di uguaglianza ` e sempre presente

Le formule sono definite induttivamente come segue:

1 Se t₁ e t₂sono termini, allora t₁=t₂`e una formula

2 Se Pⁿ`e un simbolo di predicato n-ario e t1, . . . ,tn sono termini, allora P(t₁, . . . ,t_n)`e una formula

4 Se A `e una formula, e n `e una variabile, allora8n(A) e 9n(A) sono formule

(32)

Un linguaggio

La definizione di linguaggio ` e parametrica nei simboli di costante, funzione e predicato. Tutto il resto ` e fissato.

Il linguaggio di zero e successore: L

succ

I Simboli di costante: {0}

I Simboli di funzione: {s¹}

I Simboli di predicato: ;

Esempi di termini:

0, s(0), s(n), s(s(0)), s(s(s(m))) Esempi di formule:

n = n, s(n) = m, n = m ∧ m = n, 8n; 9mm = s(n)

(33)

Altri linguaggi

Il linguaggio di somma e prodotto: L

anello

I Simboli di costante: {0, 1}

I Simboli di funzione: {+²,²}

Il linguaggio dell’aritmetica: L

PA

I Simboli di funzione: {s¹, +²,²}

Il linguaggio dei gruppi: L

gruppo

I Simboli di funzione: {+²}

;

(34)

Una semantica “canonica”?

Ricordiamo L

succ

:

I Simboli di funzione: {s¹}

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

8n(n = n), 8n ¬(s(n) = n),

8n8m8p(n = m ∧ m = p → n = p)

e che altre sono “false”: 8m(s(0) = m), 9n8m(s(m) = n) Ma non ` e cos`ı!

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

Nessuna formula ` e “vera” o “falsa” in assoluto, ma solo in

riferimento ad una specifica interpretazione (cio` e una

semantica) del linguaggio

(35)

Sintassi e semantica per un linguaggio

Prendiamo L

+,s

:

I Simboli di funzione: {s¹, +²}

Una semantica di L

+,s

sar` a costituita da:

I un insieme di individui (per interpretare i termini)

I in tale insieme saranno interpretati i simboli di costante e funzione

I simboli di predicato saranno interpretati come relazioni

I =`e sempre intepretato con l’identit`a

Indicheremo con [[ ]] la funzione dalla sintassi alla semantica

(36)

Diverse interpretazioni per L

^+,s

N :

I [[0]] =0^N

I [[s]] =successore^N

I [[+]] =+^N

Z:

I [[0]] =0^Z

I [[s]] =successore^Z

I [[+]] =+^Z

S = {} (l’insieme che contiene il solo elemento )

I [[0]] =

I [[s]] =succ, dove succ() =

I [[+]] =g, dove g (, ) =

(37)

Verit` a in una interpretazione

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

` e una formula nel linguaggio L

+,s

P ` e

I vera inN

I falsa inZ

I falsa in S ={}

Esercizio:

I Si consideri l’insieme{0, 1}

I Si diano due diverse interpretazioni diL+,s su tale insieme

I In modo che in una interpretazione P sia vera, nell’altra falsa

(38)

Intermezzo: Linguaggi del prim’ordine e di ordine superiore

La sintassi da noi descritta ` e detta del prim’ordine:

I quantificazione solo suvariabili individuali

I cio`e, semanticamente, solo su elementi del dominio

Un linguaggio si dice del secondo ordine, se:

I permette la quantificazione anche suvariabili di predicato

I cio`e, semanticamente, anche su sottoinsiemi del dominio

I Esempio: 8P8n(P(n)→P(n + 1))

(39)

Intermezzo:

Linguaggi di programmazione

L’esempio pi` u diffuso di linguaggi formali ` e quello dei linguaggi di programmazione

Semantica dichiarativa vs semantica imperativa

La “variabilit` a” della semantica ` e vitale per la coesistenza di

“implementazioni” diverse

(40)

Informatica, figlia della logica

(41)

Sintassi: Alfabeto

Sia Σ

_C

un insieme (numerabile) di simboli di costante Sia Σ

_F

un insieme (numerabile) di simboli di funzione Sia Σ

P

un insieme (numerabile) di simboli di predicato I tre insiemi appena definiti sono disgiunti

Sia Σ = Σ

C

[ Σ

F

[ Σ

P

L’alfabeto del linguaggio L

Σ

` e dato da

I Simboli propri: Σ

I Un insieme numerabile di simboli di variabile: x , y , . . .

I Connettivi: ¬, ∧, ∨, →

I Quantificatori: 8, 9

I Uguaglianza: =

(42)

Sintassi: Termini e Formule

I termini sono definiti induttivamente come segue:

1 Ogni costante `e un termine

2 Ogni nome di variabile `e un termine

3 Se fⁿ`e un simbolo di funzione n-aria e t1, . . . ,tnsono termini, allora f (t₁, . . . ,t_n)`e un termine

4 Nient’altro `e un termine

Le formule sono definite induttivamente come segue:

1 Se t1 e t2sono termini, allora t1=t2`e una formula

2 Se Pⁿ`e un simbolo di predicato n-ario e t1, . . . ,tn sono termini, allora P(t1, . . . ,tn)`e una formula

4 Se A `e una formula, e n `e una variabile, allora8n(A) e 9n(A) sono formule

5 Nient’altro `e una formula

(43)

Interpretazione: linguaggio

Dato un linguaggio L

Σ

una sua interpretazione ` e data da Un insieme D, detto dominio

Per ogni simbolo c 2 Σ

C

, un fissato elemento c

^D

2 D Per ogni simbolo f

^k

2 Σ

F

una fissata funzione f

^D

: D

ⁿ

→ D Per ogni simbolo P

^k

2 Σ

P

una fissata funzione

P

^D

: D

ⁿ

→ {V , F }

Un’interpretazione ` e data da (i) un dominio e (ii) un’associazione

di significato ai simboli propri.

(44)

Interpretazione: termini

Sia A un’interpretazione per un linguaggio L

Σ

.

L’interpretazione si estende in modo canonico ai termini:

Sia ρ un ambiente, cio` e una funzione ρ : Variabili → D [[c]]

^A_ρ

= c

^D

[[x ]]

^A_ρ

= ρ(x )

[[f (t

1

, . . . , t

n

)]]

^A_ρ

= f

^D

([[t

1

]]

^A_ρ

, . . . , [[t

n

]]

^A_ρ

)

(45)

Interpretazione: formule

Sia A un’interpretazione per un linguaggio L

Σ

.

L’interpretazione si estende in modo canonico alle formule:

Sia ρ un ambiente, cio` e una funzione ρ : Variabili → D [[t

₁

= t

₂

]]

^A_ρ

= V sse [[t

₁

]]

^A_ρ

= [[t

₂

]]

^A_ρ

[[P(t

₁

, . . . , t

_n

)]]

^A_ρ

= V sse P

_D

([[t

₁

]]

^A_ρ

, . . . , [[t

_n

]]

^A_ρ

) = V [[ ¬A]]

^A_ρ

= V sse [[A]]

^A_ρ

= F

[[A ∧ B]]

^Aρ

= V sse [[A]]

^A_ρ

= V e [[B]]

^A_ρ

= V

[[A ∨ B]]

^Aρ

= V sse [[A]]

^A_ρ

= V oppure [[B]]

^A_ρ

= V

[[A → B]]

^Aρ

= V sse [[A]]

^A_ρ

= F oppure [[B]]

^A_ρ

= V

[[ 8x(A)]]

^Aρ

= V sse per ogni d 2 D, [[A]]

^A_ρ[x_←d]