Dispense del corso di Linguaggi diprogrammazione e laboratorio:

Linguaggi formali

Francesco Sisini

Eccezionale: a chi trova e corrregge piu di 10 errori in regalo unpallone di cuoio se maschio o una bellssima bambola che parla e

dice solo tautologie se femmina. Tutti in caccia!!!

Indice

1 Basi della logica e altezze dell’intelletto 51.1 Le basi della logica . . . . . . . . . . . . . . . . . . . . . . . . . . 5

1.1.1 Il processo dicotomico di Platone e Aristotele - Metafisica 51.1.2 La matematica entra nell’analisi del linguaggio . . . . . . 61.1.3 I sillogismi . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

1.2 Le origini dei linguaggi formali . . . . . . . . . . . . . . . . . . . 91.2.1 Il sogno di Leibniz . . . . . . . . . . . . . . . . . . . . . . 91.2.2 La logica di Boole . . . . . . . . . . . . . . . . . . . . . . . 91.2.3 Il linguaggio formale di Frege . . . . . . . . . . . . . . . . 111.2.4 I Principia Mathematica . . . . . . . . . . . . . . . . . . . 121.2.5 Il programma di Hilbert . . . . . . . . . . . . . . . . . . . 121.2.6 Goedel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

1.3 Linguaggio proposizionale . . . . . . . . . . . . . . . . . . . . . . 151.3.1 Sistemi formali . . . . . . . . . . . . . . . . . . . . . . . . 151.3.2 Linguaggio e semantica . . . . . . . . . . . . . . . . . . . 171.3.3 Modelli e teorie . . . . . . . . . . . . . . . . . . . . . . . . 171.3.4 Sintassi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181.3.5 Semantica . . . . . . . . . . . . . . . . . . . . . . . . . . . 181.3.6 Considerazioni . . . . . . . . . . . . . . . . . . . . . . . . 191.3.7 Decidibilita della logica proposizionale . . . . . . . . . . 19

1.4 Sistemi deduttivi proposizionali: sistema assiomatico hilbertiano 191.4.1 Completezza e correttezza . . . . . . . . . . . . . . . . . . 20

Convenzioni tipografiche

Nel testo saranno utilizzate le convenzioni tipografiche di seguito elencate

grassetto usato per evidenziare i nuovi termini man mano che verranno introdottinel testo.

inclinato usato per evidenziare le espressioni sulle quali si vuol porre lattenzione.

monospaced usato per indicare linput/output del sistema (ci che digitato con la tastierae che visualizzato sullo schermo dal sistema), i nomi ed il contenuto deifile, gli indirizzi di pagine web e quelli di posta elettronica.

1

Glossario (da wikipedia)

Assioma In epistemologia, un assioma e una proposizione o un principio cheviene assunto come vero perche ritenuto evidente o perch fornisce il pun-to di partenza di un quadro teorico di riferimento.

L’insieme degli assiomi e dei concetti primitivi costituiscono il fondamen-to, il punto di partenza, o l’inizio, di ogni teoria deduttiva che si presenticome sistema assiomatico.

Un assioma in ambito geometrico viene chiamato postulato.

Un postulato si differenzia da un assioma in quanto introdotto per di-mostrare proposizioni che altrimenti non potrebbero essere dimostrate.In altri termini si pu definire come una semplicissima teoria ad hoc, ac-cettata grazie alla sua utilit.

In matematica il termine postulato invece ha il significato pi preciso di as-sioma non-logico, cio di assioma specifico di una particolare teoria matem-atica. Gli assiomi e i postulati, proprio per loro natura, non sono maidimostrati.

Assioma logico Sono formule valide, cio formule che sono soddisfatte da ognimodello (ovvero da ogni struttura) per ogni assegnamento delle variabili.In termini pi colloquiali, gli assiomi sono enunciati che sono veri in og-ni possibile universo, nell’ambito di ogni possibile interpretazione e conogni assegnamento di valori.

Per poter affermare che una formula un assioma logico, dobbiamo sapereche valida. Dunque dovrebbe essere necessario fornire una dimostrazionedella sua verit in ogni modello. Questo si trova in conflitto con la nozioneclassica di assioma e costituisce almeno una delle ragioni per le quali,in logica matematica, gli assiomi non sono considerati come enunciatiovviamente veri o evidenti di per s.

Gli assiomi logici, essendo mere formule, sono privi di ogni significa-to; il punto che quando sono interpretati in ogni universo, essi val-gono sempre, quali che siano i valori assegnati alle variabili. Dunquequesta nozione di assioma forse la pi vicina al significato che si intendeattribuire alla parola: gli assiomi sono veri, al di l di tutto.

Un esempio di assioma, utilizzato virtualmente in ogni sistema dedutti-vo, e:

Assioma di uguaglianza.

∀x(x = x)

Su questo esempio (dall’aspetto scarno), perch non cada nella vaghezzae in una cascata senza fine di nozioni primitive, si danno due possibilit:o si deve stabilire in partenza una nozione precisa di quello che intendi-amo con il segno = (ovvero per quello che conta, con l’espressione essere

2

uguale); oppure si deve imporre un utilizzo puramente formale e sintat-tico del simbolo = - e la logica matematica fa proprio questo, delegandogiustamente il significato di = alla teoria assiomatica degli insiemi.

Un altro esempio pi interessante :

Assioma di istanziazione universale. Data una formula φ in un linguag-gio del primo ordine L, una variabile x e un termine t che risulta sostitu-ibile per x in φ, la formula

∀xφ→ φxt e valida..

Questo assioma stabilisce semplicemente che se sappiamo che ∀xP(x)per qualche propriet P e t e un particolare termine nel linguaggio (ciorappresenta un particolare oggetto nella struttura che stiamo trattando),allora dovremo essere in grado di affermare P(t).

Un esempio simile :

Assioma di generalizzazione esistenziale. Data una formula phi in unlinguaggio del primo ordine L, una variabile x e un termine t che sosti-tuibile per x in phi la formula

φxt → ∃xφ

e valida.

Assioma non logico Nell’ambito di una teoria sono formule che svolgono ilruolo delle assunzioni specifiche della teoria stessa. Si possono svilup-pare le analisi di due differenti strutture, per esempio i numeri naturalie gli interi, servendosi degli stessi assiomi logici; gli assiomi non-logicihanno il compito di catturare quello che specifico di una particolare strut-tura (o di una specie di strutture, come i gruppi algebrici). Dunque gli as-siomi non-logici, contrariamente agli assiomi logici, non sono tautologie.Termine spesso considerato sinonimo di assiomi non-logici postulato.

Quasi ogni teoria matematica moderna parte da un dato sistema di as-siomi non-logici. Si pensava che in linea di principio ogni teoria potesseessere assiomatizzata in questo modo e potesse essere formalizzata finoa un puro linguaggio di formule logiche. Questa prospettiva si rivelataimpossibile.

Da questo segue il ruolo degli assiomi non-logici, che devono semplice-mente costituire un punto di partenza in un sistema logico. Dato che sonofondamentali nello sviluppo di una teoria, in genere risulta opportunoche nel discorso matematico essi siano chiamati semplicemente gli assio-mi della teoria, ma, va ribadito, non per esprimere che essi sono enunciativeri e neppure per significare che essi sono assunzioni dotate di verit.Un esempio ben chiaro: in alcuni gruppi l’operazione di moltiplicazionecommutativa, in altri non lo .

Dunque un assioma una base elementare per un sistema logico formalee insieme alle regole di inferenza definisce un sistema deduttivo.

3

proposizione

Concetto primitivo In molte presentazioni di nozioni matematiche per con-cetto primitivo o nozione primitiva si intende un concetto che, per lapropria semplicit ed intuitivit, si rinuncia a definire mediante termini econcetti gi definiti all’interno di un sistema formale, e che al contrario sisceglie di sfruttare per formulare la definizione di altri concetti; pertantoun concetto primitivo si accetta senza spiegazioni perch il suo significatoovvio.

In molte esposizioni della teoria degli insiemi, l’insieme stesso e consid-erato un concetto primitivo. Infatti e pressoch impossibile darne unadefinizione che non ricorra a impegnative nozioni della logica matem-atica senza usare termini come lista, complesso di, aggregato, raggrup-pamento, ecc. che, in realta++, non sarebbero altro che sinonimi di taleconcetto.

Anche molte esposizioni della geometria fanno riferimento a entit fon-damentali che svolgono il ruolo dei concetti primitivi. Nella geometriaeuclidea sono il punto, la retta e il piano; questi di solito vengono sugger-iti passando da una visione di entit sensibili ad una visione immagina-tiva con un processo di idealizzazione che conduce ad entit formali conil ruolo di modelli delle corrispondenti sensibili. Per esempio il concet-to di punto viene suggerito dall’osservazione di un granello di sabbia odalla punta di uno spillo; il concetto di retta da un sottile filo di seta o daun raggio di luce; il concetto di piano dalla superficie tranquilla di unospecchio d’acqua.

4

Capitolo 1

Basi della logica e altezzedell’intelletto

1.1 Le basi della logica

1.1.1 Il processo dicotomico di Platone e Aristotele - Metafisica

Il processo dicotomico nasce dal pensiero che per poter produrre una correttadefinizione di una idea (Platone) o di un concetto (Aristotele) si debba fornireuna corretta relazione tra il concetto stesso e che si vuol definire e altri concettiche si danno per definiti. L’esempio tipitco e la definizione del concetto uo-mo. Un uomo puo essere definito come un vivente, animale, terrestre e bipede.Come di giunge a questa definizione anziche alla definizione eretto, onnivoro,intelligente e sensibile?Il procedimento consiste nel riconoscere in prima istanza l’insieme di appartenezadel concetto (il suo genere) poi nel classificare il concetto secondo uno deglielementi di tale insieme e ripere questo procedimento fino ad una completadefinizione. Per esempio, l’uomo appartiene anzi tutto al genere dei viventi,quindi questo l’insieme di partenza. L’insieme dei viventi contiene due ele-menti (senza pretesa di precisione biologica) gli animali e i vegetali. L’uomoe un animale quindi diciamo vivente di specie animale. L’insieme degli ani-mali di divide in volatili, acquatici e terrestri. L’insieme dei terrestri si dividein stiscianti, bipedi, quadrupedi, a sei zampe e a otto zampe. L’uomo e bipedee siccome e l’unico bipede (senza sempre pretese di precisione biologica) allo-ra la sequenza dicotomica vivente-animale-bipede e una definizione correttadi uomo. Un risultato di questo processo e la definizione di gerarchie la cuirelazione d’ordine si basa sull’inclusione (si noti come la definizione di ger-archia sia ripresa nel concetto di ereditarieta). Se un dato insieme (l’insiemedegli animali terrestri) e incluso in un altro insieme (insieme degli animali) al-lora il primo e di ordine gerarchico superiore al secondo. Secondo Aristoteleper dare una definizione di un concetto e necessario che questa porti ad un in-

5

sieme che ha esattamente la stessa estensione del concetto che si vuol definire.Per esempio il concetto di uomo (inteso come essere umano) si puo applicarea tutti gli abitanti umani della Terra quindi ad un ben definito numero. Ladefinizione di uomo deve identificare un insieme cha abbia la stessa estensione.La definizione animale terrestre bipede biondo non ha la stessa estensione delconcetto uomo. Sempre secondo Aristotele per produrre una definizione cor-retta di un concetto si iscrive il concetto nel genere immediatamente superiore epoi se ne da una nota caratteristica che lo distingue: uomo→ animale-terrestrebipede (si noti l’analogia con il namespace). Le definizioni vengono date informa di predicati: l’uomo e un animale terrestre e un predicato.

1.1.2 La matematica entra nell’analisi del linguaggio

Forziamo un po’ la storia e reinterpretiamo il passato a uso del presente e,senza pretesa di rigore storico, possiamo affermare che gli sofrzi di Platone eAristotele nascevano dall’obiettivo di analizzare il linguaggio naturale (nel lorocaso la lingua greca), ricerca che sarebbe risultata poi nella logica. Il problemarisiedeva nel fatto che per analizzare il linguaggio naturale si faceva ricorso allinguagio stesso e quindi la dimostrazione di quali costrutti linguistici fosserecoerenti e quali no era comunque affetta da una difficolta insormontabile difondo, la mancanza di uno strumento di analisi la cui coerenza fosse riconosci-uta a priori. Lo sforzo di Aristotele di identificare il processo di definizionedelle categorie con le operazioni matematiche sugli insiemi fornisce esatta-mente questo strumento. La matematica, la cui coerenza non aveva bisognodi dimostrazione (si parlava di aritmetica elementare e geometrica descrittiva)poteva essere usata per analizzare il linguaggio, esisteva quindi uno strumentoesterno al linguaggio che permetteva di verificare, come vedremo ora, se i ra-gionamenti espressi attraverso il linguaggio erano o meno verita matematiche.In questo modo viene inventata la logica.

1.1.3 I sillogismi

Sillogismo significa sostanzialmente concatenazione di ragionamenti o ragion-amento concatenato. Il modo di ragionare porposto con i sillogismo si basa sulconcetto intuitivo di insieme, di inclusione, di intersezione e di esclusione. Ilsuccesso della formulazione dei sillogismi e che la coerenza di ogni sillogismoe verificabile semplicemente in termini della coereza delle relazioni matem-atiche che il sillogismo esprime.Aristotele introduce i sillogismi relativamente a tre concetti che indica comeil minore, il medio e il maggiore. Ogni sillogismo e composto da due premesse,dette maggiore e minore, e una conclusione. Il termine maggiore e minorecompaiono nella conclusione del sillogismo come predicato e soggetto mentreil medio no. Per esempio nella conclusione:

tutti gli studenti fanno i furbi

6

furbi e un predicato, gli studenti sono il soggetto mentre il medio non compare.Il sillogismo completo poteva essere:

tutti gli studenti sono giovani,tutti i giovani fanno i furbi,

tutti gli studenti fanno i furbi.

I tipi di proposizioni usati nei sillogismo aristotelici sono quattro e si identifi-cano con le prime quattro vocali:

A Tutti i S sono P (universale affermativa)

E Tutti i S non sono P (universale negativa)

I Alcuni S sono P (particolare affermativa)

O Alcuni S non sono P (particolare negativa)

La combinazione di tipi all’interno di un sillogismo (i.e. AAA, AEA, AIO ecc.)viene detta modo. Ci sono quindi in totale 43 diversi modi in cui puo presentarsiun sillogismo.

Le proposizioni formanti un sillogismo si classificano in figure e dipendonodalla posizione che ha il termine medio nelle premesse:

prima figura : il termine medio e soggetto della premessa maggiore e predica-to della premessa minore;

seconda figura : il termine medio e predicato di entrambe le premesse;

terza figura : il termine medio e soggetto di entrambe le premesse;

quarta figura : il termine medio e predicato della premessa maggiore e sogget-to della premessa minore.

Ci sono quindi 64 modi diversi per ogni figura, in totale con i vincoli postifin’ora si possono formulare 44 sillogismi distinti. In realta solo un sottogruppolimitato e considerato valido in logica. Per capire come selezionare i sillogismivalidi dobiamo introdurre il concetto di termine distribuito. In una proposizionedi un sillogismo i due termini sogetto e predicato sono detti ciascuno distribuitoo non distribuito a seconda che tutti o solo alcuni dei membri della classe iden-tificata dal termine sono interessati o meno dalla proposizione. In particolareun termine di dice distribuito se se e il soggetto di una proposizione universale(Tutti gli S sono P, Nessun S e P) o predicato di una negativa (Nessun S e P,Qualche S non e P).

Essendoci in ogni proposizione un soggetto e un predicato esistono 4 possi-bili combizazioni di distribuzione. Le distribuzioni per i 4 tipi di proposizionisono: Secondo la teoria di distribuzione dei termini, un sillogismo e valido senessun termine che non e distribuito nelle premesse non lo e nenache nelleconclusioni.

7

Tipo Propsizione DistribuzioneSoggetto Predicato

A Tutti i S. sono P. Distribuito Non distribuitoE Tutti S. non sono P. Distribuito DistribuitoI Alcuni S. sono P. Non distribuito Non distribuitoO Alcuni S. non sono P. Non distribuito Distribuito

Prima figura: AAA -1 (Barbara)EAE -1 (Celarent)AII -1 (Darii)EIO -1 (Ferio)

Seconda figura: AEE -2 (Camestres)EAE -2 (Cesare)AOO -2 (Baroco)EIO -2 (Festino)

Terza figura: AII -3 (Datisi)AAI -3 (Daratpti)IAI -3 (Disarmis)EIO -3 (Ferison)OAO -3 (Bocardo)EAO -3 (Felapton)

Quarta figura: AEE -4 (Camenes)IAI -4 (Dimaris)EIO -4 (Fresison)EAO -4 (Fesapo)

Esempio: prima figura BARBARA:

Tutti i gatti sono feliniTutti i soriani gatti

Tutti i soriani sono felini.

Esempio: seconda figura BAROCO:

Tutti i gatti sono feliniAlcuni animali non sono feliniAlcuni animali non sono gatti.

Esempio: terza figura DATISI:

Tutti i gatti sono feliniAlcuni gatti sono animali glabri

Alcuni animali glabri sono felini.

Esempio: quarta figura FRESISON:

8

Tutti i gatti non sono fumatoriAlcuni gatti sono bevitori

Alcuni bevitori non sono fumatori.

Esercitazioni

1. Produrre un sillogismo valido per per le quattro figure, in particolare:Celarent, Festino, Disarmis e Camene.

1.2 Le origini dei linguaggi formali

1.2.1 Il sogno di Leibniz

Io penso che mai le controversie possono essere

condotte a termine e che mai si pu imporre

silenzio alle sette se

non siamo ricondotti dai

ragionamenti complicati ai calcoli semplici, dai

vocaboli di significato in

certo e vago a caratteri

determinati

[...]

Si deve fare in modo

che ogni paralogismo non

sia nullaltro che un errore di calcolo

[...]

Fatto ci , quando sorgano controversie non ci

sar pi bisogno di dispute fra due filosofi di

quanto non ce ne sia fra due computisti.

Baster infatti prendere la penna, sedersi

allabaco e dirsi vicendevolmente: calcoliamo!

Gottfried W. Leibniz

1.2.2 La logica di Boole

La logica di Boole era un nuovo ramo della matematica da sviluppare usandoi consueti metodi della matematica tra i quali il ragionamento logico. La logicadi Boole per essere sviuppata richiede quindi l’uso della logica. L’idea di basee che i valori logici VERO e FALSO possono essere rappresentati da numeri eche i connettivi logici possono essere degli operatori algebrici che agiscono suquesti numeri. Boole introduce l’algebra costituita da l’insieme K = {0, 1} egli operatori ∗, + e ! che rappresentano la congiunzione, la disgiunzione e lanegazione.

x: la classe X

1− x: la classe non-x (tutti i memb ri del dominio che non sono x)

9

xy: la classe i cui membri sono sia x che y

x + y: la classe i cui membri sono X o Y

xy = yx: proprieta commutativa del prodotto

x + y: =y+x proprieta commutativa della addizione

z(x + y) = zx + zy: proprieta distributiva della moltiplicazione rispetto all’ad-dizione

x2 = x: idempotenza, da cui deriva la non contradditorieta: x(x− 1) = 0

Nell’algebra di Boole si costruiscono espressioni o funzioni Booleane usan-do variabili che hanno valore in K e gli operatori sopra visti. Un esempio difunzione booleana costruita usando una espressione booleana e la seguente:

y = A ∗ (B + C) + A (1.1)

y A B C1 1 1 11 1 1 01 1 0 11 1 0 00 0 1 10 0 1 00 0 0 1

0 0 0

I valori della funzione y sono riportati nella tabella sopra. A cosa serve l’al-gebra di Boole e a cosa non serve? L’algebra di Boole permette di esprimerematematicamente alcune forme di ragionamento. Prediamo l’esempio di unamamma che raccomanda il figlio circa l’uso dell’obrello:

• Se stai in casa non serve l’ombrello

• Se esci ed e nuvolo oppure piove prendi l’ombrello

• Se esci e fa bello ma programmi di restare fuori per piu di due ore prendil’ombrello

La madre ha richiesto al figlio di eseguire costantemente una verifica riguar-do alla necessita o meno di prendere l’obrello. Il figlio dovrebbe far uso delragionamento e prendere questa decisione. Fino alla definizione o costruzionedell’algebra di Boole, per predere questa decisione era necessario ragionare.

10

Con l’algebra di Boole, il ragionamento precedente si sintetizza nella funzioneombrello come segue:

ombrello =!casa ∗ ((nuvolo + piove) + (!nuvolo ∗ f uorialungo)) (1.2)

Proposizioni esistenziali come: esiste un numero tra i reali il cui quadrato sia−1 non sono modellabili come espressioni booleane ne proposzioni universalicome ogni numero naturale e la somma di quattro quadrati di numeri natu-rali?. Vediamo un esempio con uno dei sillogismo visti prima: Esempio: primafigura BARBARA:

Tutti i gatti sono feliniTutti i soriani gatti

Tutti i soriani sono felini.

Se usiamo la variabile x per indicare lo stato di gatto, la y quello di felino e laz quello di soriano, possiamo riscrivere la prima proposizione come: x = xy,la seconda diventa z = zx e quindi z = zxy. L’equazione x = xy ha comesoluzioni: {0,0}, {0,1} e {1,1} il che equivale a dire che se x = 1 allora y = 1cioe la prima delle proposizioni. Analogamente la seconda e la terza ci portanoa dimostrare z = 1, cioe se z e un soriano, allora z e un felino.

Per modellare queste domande era necessario un formalismo logico piuesteso.

1.2.3 Il linguaggio formale di Frege

L’obiettivo di Frege era di dimostrare che tutta la matematica poteva esserebasata sulla logica. Vale a dire che la matematica sia una conseguenza logicadi asserzioni considerate vere (assiomi non logici).

Questo obiettivo richiedeva di rinunciare ai risultati ottenuti dalla logicaAristotelica che si fondava sulle verita matematiche. Se vogliamo dimostrareche la matematica ha una coerenza logica non possiamo usare la matematciaper dimostrare la logica.

Per dimostrare che la matematica era una teoria logica aveva prima bisog-no di sviluppare la logica senza usare la logica stessa, cioe diversamente dacome avevano fatto Boole e Aristotele. La soluzione per Frege fu di creare unlinguaggio artificiale con proprie regole sintattiche. Queste idee vennero pub-blicate nel suo libro Begriffsschrift. L’idea di base era di presentare le inferenzelogiche come operazioni meccaniche condotte per mezzo di regole che riguar-davano solo la configurazione in cui erano disposti i simboli. Gli elementidell’ideografia di Frege sono:

∀: quantificatore universale

∃: quantificatore esistenziale

⊃: l’implicazione

∨: disgiunzione

11

∧: congiunzione

¬: negazione

usando l’ideografia i tipi AEIO possono essere riscritti come:

• ∀x (S(x) ⊃ P(x))

• ∀x (S(x) ⊃ ¬P(x))

• ∃x (S(x) ∧ P(x))

• ∃x (S(x) ∧ ¬P(x))

∃x : x2 = −1 ∀x∃a, b, c, d : a2 + b2 + c2 + d2 = xPer esempio consideriamo la seguente regola: siano dati i due enunciati A

e B della Begriffsschrift, se se A e asserito (asserire A significa intuitivamenteconsiderare A vero) ed e asserito anche A ⊃ B allora e asserito anche B:

` (A ⊃ B)` A

` B

L’aspetto chiave di questa regola e che per applicarla non c’e bisogno di capireil significato di ⊃. Rispetto all’algebra di Boole Frege realizza una logica nonbasata sulla matematica. La logica di Frege ha pero un limite, nel caso che unadata proposizione non si riesca a dimostrare vera rimane il dubbio se essa siafalsa o se semplicemente se non si sia trovato il modo di dimostrarla vera. Nonfornisce una procedura per dimostrare una asserzione.Per raggiungere il suo obiettivo, Frege, intendeva costruire una teoria dei nu-meri basata solo sulla logica. Frege voleva definire i numeri naturali comeproprieta degli insiemi e in questo modo non avrebbe fatto uso di concettimatematici. Purtroppo la sua fondazione fu dimostrata autocontradditoria daBertrnad Russel.

1.2.4 I Principia Mathematica

Bertrand Russel e Alfred North Whitehead riprendono il proposito di Frege diformalizzare la matematica in termini puramente logici e codificano i PrincipiaMathematica. In questa opera gli autori codificano i principi matematici par-tendo da un insieme definiti di assiomi (non logici) e di regole di inferenza. Illoro obiettivo era di completare l’opera di Frege evitando l’uso della teoria deisottoinsiemi che lo avevano portato ai paradossi indicati da Russel.

1.2.5 Il programma di Hilbert

Hilbert, come Frege e Russel, provo a definire i numeri in termini logici maabbandono questo proposito pur continuando a considerare la logica simbol-ica un elemento cruciale. Egli aveva un programma che prevedeva che sia la

12

matematica che la logica sarebbero state sviluppate insieme come linguaggiosimbolico. Tale linguaggio (sommma dei due linguaggi) era puramente for-male e poteva essere visto sia dall’interno che dall’esterno. La visione dall’in-terno consisteva nell’interpretazione del linguaggio a livello semantico, quindicon cognizione di causa. La visione dall’esterno prescindeva dal significato e silimitava alle regole sintattiche del linguaggio. L’idea di Hilbert era che con untale linguaggio fosse impossibile arrivare a dimostrare una asserzione (per es-empio una formula) e a dimostrarne anche la sua negazione. Questo approcciodi Hilbert fu criticato da Poincare e Brower che sostenevano che da una provadi non contradditorieta basata sugli stessi metodi che avrebbe dovuto garan-tire, non sarebbe risultato nulla di interessante. Questo suggerı ad Hilbert disviluppare una teoria della dimostrazione basata su metodi matematici non at-taccabili.Hilbert si chiedeva se le regole deduttive di Frege fossere complete, cioe sichiedeva se date delle premesse corrette esistevano tutte le regole che ci per-mettono di inferire le giuste conclusioni. Questo e come chiedersi se ci sianodelle verita non dimostrabili in quanto mancano gli strumenti formali per di-mostrarle:

Occhio: nella realta quotidiana siamo abituatia questo, per esempio ci sonoazioni che vengono compiute, come un crimine, ma di cui non e possibile iden-tificare un colpevole. Se un crimine e stato compiuto allora un colpevole esistema questo non vuol dire che il sistema investigativo sia in grado di trovarlo.

Hilbert credeva e voleva dimostrare che il sistema di Frege era completo (oalmeno completabile). Dire che il sistema e completo significa che se date certepremesse e data una conclusione, questa risulta vera ogni qual volta sono verele premesse, allora e possibile passare dalle premesse alla conclusione usandole regole di Frege (ora regole Frege-Russel-Hilbert). In parole semplici la prob-lematica riguarda il riuscire a dimostrare che una certa inferenza e vera quandoessa e e evidente all’intelletto umano. In questo caso diciamo che l’inferenzae dimostrabile vera dall’interno (cioe dall’interno del sistema) e che vogliamodimostrarla vera dall’esterno, cioe per mezzo delle regole da cui il sistema edefinitito.

1.2.6 Goedel

La prova che il sistema di Frege era completo fu fornita da Goedel e come rilevolui stesso il suo risultato non era che una consegueza dei risultati contenuti inun articolo del logico Thoralf Skolem. Si era quindi dimostrata la completez-za di un sistema formale (il sistema logico di Frege) utilizzando dei metodimatematici meccanici.Il secondo problema che Goedel si trovo ad affrontare fu la ricerca prova chela matematica non e contradditoria. Questo problema era stato posto sempreda Hilbert. Questa prova doveve essere portata senza far ricorso alle stesseverit matematiche che si volevano dimostrare vere. Questo significava consid-

13

erare un sistema formale dall’esterno anziche dall’interno, non si poteva infattifar ricorso ai metodi matematici per dimostrare che essi stessi non erano con-tradditori. La differenza tra interno ed esternp consiste nel valutare il sistemafacendo uso o meno dell’intelletto.Goedel analizzo la problematica di considerare un sistema logico formale dal-l’esterno invece che dall’interno (lo stesso che aveva fatto Frege con la solalogica) e penso quindi che questo compito richiedeva di sviluppare la stessamatematica all’interno di un sistema logico formale. Visto dall’esterno un sis-tema logico formale consiste in siboli e stringhe di simboli e da relazioni traqueste, dall’interno invece stringhe e simboli rappresentano proposizioni suglioggetti matematici come in numeri natuarali. Una idea importante di Goedelfu quella di rappresentare le stringhe di siboli del sistema formale (cioe dellamatematica vista dall’esterno) per mezzo degli stessi numeri naturali.

14

1.3 Linguaggio proposizionale

1.3.1 Sistemi formali

Una logica Λ puo essere definita come segue:

• Un alfabetoA detto alfabeto di Λ. L’alfabeto deve essere non vuoto, finitoo al piu numerabile. Una sequenza finita di siboli di A e detta essere unaespressione di Λ.

• Un sottoinsieme F delle formule di Λ detto l’insieme delle formule benformate.

• Un sottoinsieme Ax di F , detto insieme degli assiomi logici o semplice-mente assiomi di Λ.

• Un insieme finitoR di relazioni R1, ..., Rn di formule di Λ dette regole diinferenza. Si richiede inoltre che per ciascuna regola Ri esista un unico in-tero positivo j tale che per ogni insieme costituito da j formule (premesse)e per ogni formula A si puo effettivamente decidere se le j formule sonoin relazione Ri con A oppure no. In caso positivo, A e detta conseguenzadiretta delle j formule mediante Ri.

Le regole di inferenza possono essere scritte come segue:

A1...An

A

Le formule scritte sopra la riga sono dette premesse mentre quella sotto e dettaconclusione. Un esempio di regola di inferenza e il modus ponens (MP), in questocaso abbiamo due formule che costituiscono le premesse e una conclusione.Consideriamo che l’alfabeto sia costituito dalle lettere dell’alfabeto e dal sim-bolo della freccia. Rispetto al formalismo precedente definiamo le premesse A1e A2 come: A1 = P → C, A2 : P, la conclusione A = C. La regola si esprimecome:

P→ C, PC

Una seconda regola di inferenza e la sostituzione uniforme (SU)

F[p]F[X/p]

Teoremi e dimostrazioni

Una dimostrazione o prova in Λ e un insieme di formule A1, ..., An. Perche siauna dimostrazione ognuna delle Ai deve essere o un assioma di Λ, cioe ap-partenere a Ax oppure essere una conseguenza diretta di alcune delle formuleche precedono mediante una delle regole diR.L’ultima formula An e detta teorema. Indichiamo con ` A che A e un teoremadi Λ.

15

I teoremi sono quindi delle conseguenze formali degli assiomi logici

Se si assumono come assiomi le seguenti formule:

A→ (B→ A)(A→ (B→ C))→ ((A→ B)→ (A→ C)))(¬A→ ¬B)→ (B→ A)equivalente a:((B→ ¬A)→ ((B→ A)→ ¬B)

si ha che i teoremi della logica sono i seguenti:

A→ Alegge dell’identita¬(¬A)↔ Alegge della doppia negazioneA ∨ ¬Alegge del terzo escluso¬(A ∧ ¬A)legge di non contraddizione(A→ B)↔ (¬B→ ¬A)legge di contrapposizione(A ∧ (A→ B))→ Bmodus ponens o legge di disgiunzione(¬B ∧ (A→ B))→ ¬Amodus tollens(A→ B) ∧ (B→ C)→ (A→ C)sillogismo ipotetico oppure noto come propriet transitiva dell’implicazione o legge di modus barbara o legge di deduzione a catenaA ∧ (B ∧ C)↔ (A ∧ B) ∧ Cpropriet associativa di ∧A ∨ (B ∨ C)↔ (A ∨ B) ∨ Cpropriet associativa di ∨A ∧ B↔ B ∧ Apropriet commutativa di ∧A ∨ B↔ B ∨ Apropriet commutativa di ∨A ∧ (B ∨ C)↔ (A ∧ B) ∨ (A ∧ C)propriet distributiva della congiunzione rispetto alla disgiunzioneA ∨ (B ∧ C)↔ (A ∨ B) ∧ (A ∨ C)propriet distributiva della disgiunzione rispetto alla congiunzioneA ∧ ¬A→ Bprima legge di Pseudo Scoto[4] o ex falso quodlibetA→ (¬A→ B)seconda legge di Pseudo ScotoA ∧ B↔ ¬(¬A ∨ ¬B)prima legge di De MorganA ∨ B↔ ¬(¬A ∧ ¬B)seconda legge di De Morgan((A→ B)→ A)→ Alegge del Pollice(¬A→ A)→ Aconsequentia mirabilis

Diverso e il caso in cui una formula A discenda da una serie di premesse(altre formule) che sono assunte. Se per esempio si assumono le formule (Γ)B1, ..., Bn ⊆ F e da queste si ha che l’insieme di formule A1, ..., An e tale che og-ni formula o appartiene agli assiomi, o conseguenza delle formule precedenti oappartiene a Γ. Detta A l’ultima formula di A1, ..., An scriviamo: B1, ..., Bn ` A.L’insieme di tutte le formule che possono essere dedotte da Γ e detto chiusuradeduttiva e si indica con Cn(Γ). La definizione di chiusura deduttiva e quindi:

Cn(Γ) = A|Γ ` A

.Fin’ora non abbiamo posto sulle formule A1, ..., An la richiesta che esse sianovere. Abbiamo quindi sviluppato un sistema deduttivo indipendente da cio. Pri-ma di proseguire analizziamo anche gli aspetto legati al valore di verita delleformule.

16

1.3.2 Linguaggio e semantica

Il linguaggio L della logica Λ e l’insieme F delle formule ben formate. Ciponiamo l’ obiettivo di chiarire in modo formale come il significato degli ele-menti di F sia esteso alle formule apparteneti ad F per mezzo dei costrutturidel linguaggio. Centrare questo obiettivo significa dotare il linguaggio di unasemantica. Vediamo un esempio. Consideriamo l’alfabeto

A = {soleggia, piove, tira− vento, nevica, f a− nebbia}+ {∧,∨}

. Definiamo le formule ben formate come tutte le formule composte da unnumero abitraro di elementi del primo insieme a patto che per ogni formulaformata da piu di uno di questi elemti, questi siano intercalati da un elementodel secondo insieme. Per esempio:

• soleggia : ben formata

• soleggia piove : non ben formata

• piove ∨ soleggia ∧ nevica : ben formata

A livello informale, possiamo dire che gli elementi del primo insieme sono leparole del linguaggio mentre quelli del secondo sono i costruttori. lo scopodella semantica e quello di attribuire un signiicato ad una proposizione costru-ita una volta noti i significati delle sinngole parole. Nella teoria dei linguaggiformali, per definire una semantica si considera un insieme B detto dei valoridi verita ed un suo sottoinsieme T che rappresenta il vero. Un esmpio tipi-co e B = {t, f }. La semantica e l’insieme di regole che permette di associareuna proposizione costruita ad un valore di B una volta che siano note le re-lazioni tra le singole proposizioni e gli elementi di B. Per esempio se piove evera (piove : t) e tira− vento e vera (tira− vento : t) le regole della semanticadebbono fornire il valore di verita della proposizione piove ∨ tira− vento.

1.3.3 Modelli e teorie

Un altro modo per definire una semantica e l’utilizzo dei modelli. In logicail termine modello viene usato diversamente che nellse scienze. Nella logicaun modello e la realta che viene appunto presa a modello. Alternativamenteal termine di realta possiamo usare il termine di struttura. Indichiamo unarealta o struttura con il simboloM. La strutturaM rappresenta una specificaconfigurazione del significato delle proposizioni che caratterizzano cio che sista esaminando. Supponiamo che una data formula A sia inclusa inM alloradiremo cheM modella A e scriviamoM |= A, se poi questa relazione e veraper tutti gliM allora diremo che A e valida.Esempio: consideriamo un tiro con un dado che in termini di modelli puoessere rappresentato come segue:risultato={6, 1}; {1, 6}; {5, 2}; {2, 5}; {4, 3}; {3, 4}La formula {6∧} ha quindi uno di questi a modello ma non e valida in quanto

17

esistono modelli in cui essa non verificata. La formula x ∧ (7− x) con 1 ≤x ≤ 6 e valida.

1.3.4 Sintassi

Diamo qui una definizione formale della sintassi della logica proposizionale.Definiamo anzitutto il suo alfabeto Σ come:

• I connettivi proposizionali ¬, ∨, ∧,→ e↔;

• Le costanti proposizionali > e ⊥;

• Un insime finito o numerabile di simboli che rappresentano proposizioniP = {A, B, C...Z};

• I simboli ( e );

Ora diamo una definizione induttiva delle formule ben formate di Σ comesegue:

• I simboli proposizionali e le costanti sono formule;

• Se A e una formula (¬A) e una formula;

• Se A e B sono due formule e ◦ e un connettivo, (A ◦ B) e una formula.

• I simboli ( e );

1.3.5 Semantica

Definiamo allora la semantica come un sistema di valutazione S:

• B = {0, 1}

• T = {1}

• Op = {Op¬,Op∨,Op∧,Op→,Op↔} con Op¬ : B 7→ B e Op◦ : B ×B 7→ B

Le funzioni Op sono definite analogamente ai corrispettivi operatori logici.Quello che ancora manca e un sistema per assegnare un valore di B ad unaformula (proposizione). Definiamo quindi l’assegnazione booleana V

V : P 7→ {1, 0}

18

1.3.6 Considerazioni

Gli aspetti interessanti di una logica Λ sono:

• la possibilita di stabilire se una data formula A sia o non sia un teoremadella logica

• la possibilita di stabilire se una data formula sia o non sia vera.

Un apparato deduttivoR si dice corretto se per ogni formula ben formata A siha che `R A implica |= A, questo significa che i teoremi devono essere delletautologie, cioe devono essre validi o in altri termini devono essere sempreveri.

Si dice invece che e completo (rispetto ad un insieme di formule Γ) se perogni formula ben formata A ∈ Γ si ha che |= A implica `R A, cioe ognitautologia deve essere dimostrabile a partire dagli assimoni della teoria.

1.3.7 Decidibilita della logica proposizionale

Una formula logica e decidibile se esiste una procedura effettiva per dimostrarese essa e valida, cioe se e o meno una tautologia. Nel caso in questione del cal-colo proposizionale, per verificare se una formula A e una tautologia bisognaverificare le tabelle di verita per ogni assegnazione ai simboli proposizionalipresenti in A (variabili). Se prendiamo l’assioma A → (B → A) abbiamo duesole variabili quindi 22 combinazioni:

A → B → A1 1 1 1 11 1 0 1 10 1 1 0 00 1 0 1 0

Il calcolo proposizionale e quindi sembre decidibile in quanto e banalmentesempre possibile produrre la tavola di verita di una qualsiasi formula e veri-ficare che il valore di verita del connettivo principale sia una colonna di 1 (o>).

1.4 Sistemi deduttivi proposizionali: sistema assiomati-co hilbertiano

Prendiamo come esempio ora un sistema composto dai seguneti assiomi:

• A→ (B→ A)

• (A→ (B→ C))→ ((A→ B)→ (A→ C)))

19

• (¬A→ ¬B)→ (B→ A)

e dalle seguenti regole di inferenza:

• P→ C, PC

• F[p]F[X/p]

Ora vediamo il teorema di deduzione: sia Gamma un insieme di formule propo-sizionali con A ∈ Γ e B ∈ Γ, si ha allora:

Γ, B ` A sse Γ ` B→ B

Vediamo che il teorema permette di spostare una formula da una parte all’al-tra della relazine ` inserendo o eliminado a seconda del caso il connettivo→.Una conseguenza rilevante di questo teorema e che esso ci permette di trattarele formule derivate da Γ come teoremi, infatti, posto Γ = {A1, ..., An} e datoΓ ` B possiamo sempre scrivere: ` A1 → (A2 → (...(An → B)...)).

Un insieme di formule Γ e detto consistente se e verificata una delle seguenicondizioni:

• Non esiste A tale che Γ ` A e Γ ` ¬A

• Esiste una proposzione A tale che Γ 0 A

1.4.1 Completezza e correttezza

La relazione tra completezza e correttezza riguarda la relazione tra i teoremi ele tautologie. Il sistema in questione e completo se ogni tautologia e dimostratacome teorema e altresı il sistema e corretto se ogni teorema e una tautologia. Ladimostrazione che il sistema hilbertiano proposizionale e corretto e completo eridotta alla dimostrazione delle relazione seguente:

`H A→ B sse |= A→ B

Per dimostrare la correttezza e sufficiente dimostrare:

• Gli schemi di assiomi iniziali sono tautologie

• MP e SU sono chiusi, cioe se le premesse delle regole MP e SU sonotautologie allora anche le conseguenze sono tautologie.

Per dimostrare la completezza invece la dimostrazione e piu complessa e quinon viene affrontata.

Il sistema hilbertiano proposizionale e quindi un sistema completo e corretto.

20