Logica, discorso e conoscenza

Logica, discorso e conoscenza

Primo modulo:

Logica e verit` a (matematica) ovvero Logica, deduzione, verit` a

Lezioni 1, 2 e 3

Simone Martini

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

martini@cs.unibo.it

Collegio Superiore

Ottobre–novembre, 2006

Outline

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

2 Seconda lezione: il linguaggio formale

Formalizzazione di semplici propriet` a aritmetiche

3 Terza lezione: verit` a e validit` a

Formule vere dovunque e vere in classi di modelli

Cos’` e la logica?

Ars directiva ipsius actus rationis, per quam scilicet homo in ipso actu rationis ordinate et faciliter et sine errore procedat.

[Tommaso d’Aquino, An. posteriora, I, 1]

La parte della filosofia che studia quali sono le leggi del pensare, che assicurano ad esso validit` a conoscitiva.

Si chiama logica formale lo studio in abstracto dei procedimenti seguiti dal pensiero nella formazione dei concetti, dei giudizi, dei ragionamenti, indipendentemente dai contenuti cui esso si pu` o volta a volta applicare.

[Lamanna-Adorno, Diz. di termini losoci, 1971]

Cos’` e la logica?

Riflessione razionale sulle strutture (soprattutto formali) del ragionamento

I

Fascinazione per la ragione

I

Consapevolezza di ragionamenti fallaci

I

Circoscrivere il corretto (e.g., la Scolastica)

I

Circoscrivere il dicibile (e.g., Wittgenstein)

Cos’` e la logica matematica?

Un settore della matematica che usa tecniche matematiche per indagare il ragionamento (matematico)

In particolare i concetti di

I

Dimostrazione

I

Consistenza

I

Teoria

I

Verit` a

all’interno della conoscenza matematica.

Da Aristotele (384 – 322 a.C.)

a Pietro Ispano (circa 1215–1277)

Aristotele e la scolastica

Enunciazione vs Argomentazione

(proposizione vs dimostrazione, inferenza) Proposizione:

Discorso completo che esprime un oggetto complesso sul quale pu` o essere portato un giudizio (“vero” o “falso”)

I

Affermative universali (A): Ogni uomo ` e mortale

I

Affermative particolari (I): Qualche uomo ` e filosofo

I

Negative universali (E): Nessun uomo ` e un angelo

I

Negative particolari (O): Qualche chiaccherone non ` e noioso

I

(Singolari: Socrate ` e un uomo, caso particolare di A)

e delle loro relazioni reciproche (conversione)

Analizziamo una proposizione

Nessun intento filologico relativo alla logica aristotelica!

In particolare: non conosce la quantificazione individuale

concetti singolari (termini: Socrate) che designano individui concetti universali (variabili quantificate universalmente: ogni uomo)

concetti particolare (variabili quantificate esistenzialmente:

qualche uomo)

giudizio affermativo o negativo (tutti gli uomini, nessun uomo) predicati: ` e un angelo

una proposizione (semplice) risulta dalla predicazione relativa

a (su un) un concetto: ogni uomo ` e mortale

Inferenza: la conversione

Inferenza: il sillogismo

Un sillogismo (di prima figura, “in BArbArA”):

I

Ogni uomo ` e mortale

I

Ogni neonato ` e un uomo

I

dunque: Ogni neonato ` e mortale La struttura generale della prima figura:

Premessa maggiore: (M, T ) Premessa minore : (t, M) Conclusione (dunque:) (t, T ) Variando la disposizione di T , t, M nelle premesse si ottengono le quattro figure

Per ogni figura, si ottengono i diversi modi, a seconda se le premesse siano di tipo A, E, I, O

Non tutti i modi sono legittimi, quanto alla validit` a

dell’inferenza

Il sillogismo, 2

Un sillogismo (di seconda figura, “in BArOccO”):

I

Ogni uomo stolto ` e noioso

I

Qualche chiaccherone non ` e noioso

I

dunque: Qualche chiaccherone non ` e stolto La struttura generale della seconda figura:

Premessa maggiore: (T , M) Premessa minore : (t, M) Conclusione (dunque:) (t, T ) Un “sillogismo” scorretto (di prima figura, EAA)

I

Alcuni uomini sono santi

I

I criminali sono uomini

I

dunque: I criminali sono santi

(In prima figura) sit minor affirmans, nec maior particularis

Una prima morale (dal punto di vista moderno)

Sillogismo valido (corretto):

I

costruito in uno dei 19 modi legittimi (delle quattro figure) Sillogismo vero:

I

sillogismo valido nel quale entrambe le premesse sono vere

I

impone la verit` a della conclusione

La correttezza dipende dalla struttura formale del sillogismo La verit` a della conclusione ` e ipotetica: subordinata alla verit` a delle premesse (e alla correttezza del sillogismo)

Semantica a varˆı livelli

I

Termini = ⇒ individui

I

Proposizioni = ⇒ valori di verit` a

I

Sillogismi = ⇒ relazioni ipotetiche tra valori di verit` a

Esercizio

La terza figura: (M, T ), (M, t) dunque (t, T ).

Un sillogismo di terza figura in Darapti:

I

Un centauro ` e un uomo-cavallo

I

Un centauro ` e un essere immaginario

I

Dunque, qualche essere immaginario ` e un uomo-cavallo Si tratta di un sillogismo legittimo per la scolastica Si trovi una sua applicazione fallace

Da cosa dipende la fallacia?

(Per chi conosce un po’ di simbologia formale)

Si formalizzi Darapti e si discuta la sua correttezza nel

contesto logico-formale

I paradossi

Abbiamo sognato [il mondo] resistente, misterioso, visibile, ubiquo

nello spazio e fermo nel tempo; ma abbiamo ammesso nella sua

architettura tenui ed eterni interstizi di assurdit` a, per sapere che ` e

finto. [J. L. Borges, La perpetua corsa di Achille e la tartaruga]

Il mentitore

Cretenses semper mendaces.

[Ad Titum 1, 12]

Epimenide di Creta: “[Tutti] i Cretesi sono bugiardi”

E un paradosso? `

Basta che esista un cretese che dice la verit` a e la frase ` e falsa.

Eubulide di Mileto: “Io sto mentendo in questo momento”

La chiave: autoriferimento

Gottfried Wilhelm Leibniz

1646-1716

characteristica universalis

ars combinatoria

Leibniz e la characteristica universalis

Id (. . . ) efficiendum est, ut omnis paralogismus nihil aliud sit quam error calculi (. . . ). Quo facto, quando orientur controversiae, non magis disputatione opus erit inter duos philosophos, quam inter duos computistas. Sufficiet enim calamos in manus sumere sedereque ad abacos, et sibi mutuo (. . . ) dicere: calculemus!

[t. VII, 200]

1

Linguaggio formale: Descrizione esatta ed univoca dei concetti

2

Inferenza combinatoria, puramente sintattica (da computistae)

3

Propriet` a fondamentali:

I

Correttezza: non sono possibili paralogismi, da prop vere a prop vere

I

Completezza: tutti i paralogismi sono errori di calcolo;

forzando un po’ la mano: ogni prop vera ` e ottenibile per

calcolo

Intermezzo:

Argomentazioni vs Conclusioni

Leibniz insiste sulla completezza per le argomentazioni (fallaci) La logica moderna insister` a (soprattutto) sulla completezza per le conclusioni (corrette e/o vere)

I

Sistemi formali completi: esprimono tutte le proposizioni vere (su un certo dominio)

I

Per ciascuna di esse ` e sufficiente una argomentazione (dimostrazione)

I

Dimostrazioni in formati molto vincolati, non “naturali”

La crisi dei fondamenti:

Bertrand Russell (1872 – 1970)

Gottlob Frege (1848 – 1925)

La crisi dei fondamenti della matematica

La matematica si credeva immune dai paralogismi Alla fine del XIX secolo scopre, con sorpresa, di esserne contagiata essa stessa

I

Russell scrive a Frege:

Un insieme ` e normale se non contiene se stesso.

Sia N l’insieme di tutti e soli gli insiemi normali.

N `e normale?

I

Frege risponde a Russell:

Solatium miseris socios habuisse malorum

I

Perch´ e tanta drammaticit` a?

I

I ragionamenti per assurdo sono presenti sin da Euclide

I

Russell non ha semplicemente dimostrato che N non esiste?

La formalizzazione della matematica

Per costruire N si usano solo operazioni elementari di comprensione

Occorre limitare quelle

Necessit` a di un linguaggio formale preciso (e dalla semantica precisa)

Per tagliare un capello in quattro

David Hilbert (1862-1943)

Il progetto di Hilbert per la consistenza

Come essere sicuri che anche con tale linguaggio formale i paradossi non si presentino?

Individuare un nucleo di base cui ridurre tutta la restante matematica

L’aritmetica formalizzata

Indagare il nucleo con strumenti (matematici, anzi aritmetici) cos`ı semplici da non sollevare dubbi sulla loro consistenza Dimostrare cos`ı che il nucleo ` e (auto-)consistente

Cruciale: la struttura dei numeri naturali

Kurt G¨ odel (1906-1978)

G¨ odel: successi e insuccessi hilbertiani

Il teorema di completezza (“sintattica”), 1927

I

Ogni proposizione vera in tutti i modelli ` e derivabile nel sistema formale

Il teorema di incompletezza (“semantica”), 1930

I

Vi sono proposizioni vere nella struttura dei numeri naturali che non sono derivabili nel sistema formale

I

Tra di esse c’` e la proposizione che esprime la consistenza del sistema formale

Gran parte del corso sar` a dedicata a chiarire questi due enunciati. . .

Cio` e: cosa sono i “modelli”?

E cosa significa lo scarto tra “vero in tutti i modelli” e “vero

in una struttura particolare”?

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

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: ¬

Per ogni n, l’inverso ` e unico

8n8m 1 8m 2 (n + m 1 = 0) ∧ (n + m 2 = 0) → m 1 = m 2

Nuovi operatori che trasformano proposizioni: ∧, →

Alcune bipartizioni

1

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

2

Proposizioni vs Quantificazione

3

Sintassi vs Semantica

4

Linguaggio vs Metalinguaggio

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

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 con connettivi: congiunzione, disgiunzione, implicazione, negazione, ecc.

I

Proposizioni che contengono individui generici, possono dar luogo ad altre proposizioni mediante quantificazione:

universale, esistenziale

3

Sintassi vs Semantica

4

Linguaggio vs Metalinguaggio

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)

4

Linguaggio vs Metalinguaggio

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)

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 t 1 , . . . , t n sono termini, allora f (t 1 , . . . , t n ) ` e un termine

4

Nient’altro ` e un termine

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 1 e t 2 sono termini, allora t 1 = t 2 ` e una formula

2

Se P ⁿ ` e un simbolo di predicato n-ario e t <sub>1</sub> , . . . , t <sub>n</sub> sono termini, allora P(t 1 , . . . , t n ) ` e una formula

3

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

4

Se A ` e una formula, e n ` e una variabile, allora 8n(A) e 9n(A) sono formule

5

Nient’altro ` e una formula

Un linguaggio

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

Il linguaggio della somma: L gruppo

I

Simboli di costante: {0}

I

Simboli di funzione: {+ ² }

I

Simboli di predicato: ; Esempi di termini:

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

n = n, 0 + 0 = m, n = m ∧ m = n, n = m ∧ m = p → n = p

Altri linguaggi

Il linguaggio di somma e prodotto: L anello

I

Simboli di costante: {0, 1}

I

Simboli di funzione: {+ ² ,  ² }

I

Simboli di predicato: ;

Il linguaggio di zero e successore: L succ

I

Simboli di costante: {0}

I

Simboli di funzione: {s ¹ }

I

Simboli di predicato: ; Il linguaggio dell’aritmetica: L PA

I

Simboli di costante: {0}

I

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

I

Simboli di predicato: ;

Una semantica “canonica”?

Ricordiamo L gruppo :

I

Simboli di costante: {0}

I

Simboli di funzione: {+ ² }

I

Simboli di predicato: ;

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

8n(n = n), 8n(n + 0 = n), 8n8m8p(n = m ∧ m = p → n = p) e che altre sono “false”: 8m(0 + 0 = m), 9n8m(n + m = 0) 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

Sintassi e semantica per un linguaggio

Prendiamo L +,s :

I

Simboli di costante: {0}

I

Simboli di funzione: {s ¹ , + ² }

I

Simboli di predicato: ;

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

che stabilisce una data interpretazione

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 ( , ) = 

Verit` a in una interpretazione

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

` e una formula nel linguaggio L +,s

P ` e

I

vera in N

I

falsa in Z

I

falsa in S = {}

Esercizio:

I

Si consideri l’insieme {0, 1}

I

Si diano due diverse interpretazioni di L +,s su tale insieme

I

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

Intermezzo: Linguaggi del prim’ordine e di ordine superiore

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

I

quantificazione solo su variabili individuali

I

cio` e, semanticamente, solo su elementi del dominio Un linguaggio si dice del secondo ordine, se:

I

permette la quantificazione anche su variabili di predicato

I

cio` e, semanticamente, anche su sottoinsiemi del dominio

I

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

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

Informatica, figlia della logica

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: =

I

Simboli ausiliari: (, ), , (virgola)

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 t 1 , . . . , t n sono termini, allora f (t 1 , . . . , t n ) ` e un termine

4

Nient’altro ` e un termine

Le formule sono definite induttivamente come segue:

1

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

2

Se P ⁿ ` e un simbolo di predicato n-ario e t <sub>1</sub> , . . . , t <sub>n</sub> sono termini, allora P(t 1 , . . . , t n ) ` e una formula

3

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

4

Se A ` e una formula, e n ` e una variabile, allora 8n(A) e 9n(A) sono formule

5

Nient’altro ` e una formula

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.

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 _ρ )

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 1 , . . . , t n )]] ^A _ρ = V sse P D ([[t 1 ]] ^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]} = V

[[ 9x(A)]] ^A ρ = V sse esiste un d 2 D, [[A]] ^A _{ρ[x ←d]} = V

Verit` a in un’interpretazione

Sia A una formula sul linguaggio L Σ

Sia A una interpretazione per L Σ

A ` e vera in A sse 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 linguaggio L +,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 canonica dei 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 qualsiasi A, queste formule sono vere

in A

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 dipende dall’interpretazione perch´ e dipende da come si associano oggetti semantici ai simboli

La semantica del livello logico ` e invece fissata nella 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 formula A ` e valida sse per ogni interpretazione A, 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

11

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

Alcune leggi logiche quantificate

1

( 8xP) → (9xP)

2

9x8yP → 8x9yP

3

8xP ↔ ¬9x¬P

4

9xP ↔ ¬8x¬P

Procedimento di decisione?

Legge proposizionale

I

Tavola di veri` a

I

Meccanizzabile (ma richiede tempo esponenziale) Legge quantificata

I

Ragionare a partire dalla definizione

I

Meccanizzabile?

Intermezzo: logica classica e altre logiche

La logica che descriviamo viene detta classica

Sono state studiate logiche diverse, il cui insieme di leggi ` e un sottinsieme proprio di quello della logica classica

Corrispondono a diverse semantiche dei connettivi (e dei quantificatori)

Ricordiamo le logiche

I

minimale

I

intuizionista

E.g., per l’intuizionista le leggi proposizionali da 8 in poi (e le

3 e 4 delle leggi quantificate) non sono valide

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) `e conseguenza logica di (1) e (2)

Conseguenza logica formule chiuse

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

P ` e conseguenza logica di Γ (scrivi: Γ |= P) sse

per ogni interpretazione A, se A |= Γ, 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 ` e conseguenza logica di Γ (scrivi: Γ |= P) sse

per ogni interpretazione A, 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.)

L’insieme Ord

Sia L Ord il linguaggio senza costanti o funzioni e col solo simbolo di predicato M

Sia Ord il seguente insieme di formule su L Ord : 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, antisimmetrico e transitivo.

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

Se A `e un modello di Ord, deve avere un ordine

Alcuni modelli di Ord

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

Molte altre interpretazioni

I

D 0 : D = {0, 1}, M ^D

(0, 0) = V , M ^D

(1, 1) = V

I

D 1 : D = {0, 1}, M ^D

(0, 0) = V , M ^D

(1, 1) = V , M ^D

(0, 1) = V

I

D 2 : D = {0, 1}, M ^D

(0, 0) = V , M ^D

(1, 1) = V , M ^D

(1, 2) = V

Ci sono infiniti modelli 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: L gruppo = {,  ² }; 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 caso i 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

necessariamente una quantit` a infinita di modelli (ciascuno di

essi con un dominio di cardinalit` a infinita)

“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

Dov’` e finito “il mentitore”?

“Questa frase ` e falsa”

Non ` e una proposizione, perch´ e una teoria non parla delle proprie frasi

N´ e tantomeno della loro verit` a

Il mentitore presuppone una metateoria riflessa nella teoria

O no?