1.1 logica

Se, come diceva Galileo, la matematica è il linguaggio della natura, è importante che la matematica sia essa stessa espressa in un linguaggio che risulti essere il più possibile oggettivo e non ambiguo. La logica è la disciplina matematica che si occupa dello studio e della formalizzazione del linguaggio matematico. In questo capitolo riassumiamo in maniera sintetica ed intuitiva alcuni concetti e contemporaneamente fissiamo le notazioni che verranno utilizzate nel seguito.

La logica studia i sistemi formalisistemi formali (anche detti sistemi logico-deduttivi o sistemi assiomatici) che sono delle descrizioni meccaniche, non ambigue, di un linguaggio formale. Parliamo al plurale di sistemi formali in quanto ogni ambito della matematica (o di altre scienze) potrebbe sviluppare un proprio sistema formale specializzato per quell’ambito. Il primo sistema formale è stato sviluppato da Euclide per descrivere le proprietà di punti, rette e circonferenze del piano (la geometria euclidea). Al tempo di Euclide la formalizzazione era ancora intuitiva e incompleta, la formalizzazione moderna di tale sistema è stata completata da Hilbert, dopo duemila anni. Peano ha introdotto un sistema assiomatico per descrivere le proprietà dei numeri naturali. Dedekind ha individuato gli assiomi per descrivere i numeri reali. Cantor ha introdotto la teoria degli insiemi all’interno della quale è stato possibile includere tutte le altre teorie matematiche. Tale teoria è stata formalizzata da Zermelo e Fraenkel ed è questa la teoria che useremo nel nostro corso.

Tutti i sistemi formali descrivono un linguaggio. Per descrivere un linguaggio dobbiamo dire innanzitutto quali sono i simbolisimboli di quel linguaggio. In generale possiamo pensare ai simboli come alle lettere (o caratteri, nel linguaggio dell’informatica) che possono essere utilizzati per comporre le frasi. Simboli tipici delle teorie matematiche sono ad esempio: x, y, 5, 7, +, =, ), : etc. Nei linguaggi informatici i simboli corrispondono ai caratteri presenti sulla tastiera di un computer. Nelle lingue naturali si prenderebbero come simboli le singole lettere dell’alfabeto a cui aggiungere eventualmente i caratteri per la punteggiatura. Una sequenza finita di simboli si chiama formulaformula (potremmo anche chiamarle frasi). Ad esempio: x7)+ potrebbe essere una formula formata da quattro simboli. Tra tutte le formule un sistema formale deve individuare quelle che si potrebbero chiamare formule ben formate ovvero le formule a cui effettivamente vogliamo dare significato. Ad esempio la formula potrebbe essere una formula ben formata perché siamo in grado di dargli un significato. Il sistema formale non dà un significato alle formule ben formate (il significato è una estrapolazione della nostra mente) ma semplicemente deve dare delle regole per determinare quali siano le formule ben formate e quali no. Visto che ogni simbolo che utilizziamo può essere rappresentato al computer, possiamo pensare alle formule come alle stringhe dei linguaggi di programmazione e possiamo pensare che il sistema formale deve descrivere un algoritmo (cioè un procedimento meccanico) in grado di determinare se una formula è ben formata oppure no. Tra le formule ben formate il sistema formale deve infine specificare quali siano i teoremi. Di nuovo questo deve essere fatto mediante un algoritmo puramente meccanico in modo da garantire che i teoremi risultino oggettivi e universali: non ci può essere disaccordo sulla validità di un teorema, eventualmente ci può essere disaccordo sulla interpretazione di tale teorema. Tipicamente i sistemi formali sono deduttivi. Nei sistemi deduttivi si identificano alcune formule che vengono chiamate assiomi e che vengono immediatamente riconosciuti come teoremi. Ad esempio vedremo che il primo assioma della teoria degli insiemi è che si potrebbe leggere

esiste un insieme per il quale nessun è elemento di

ed esprime l’esistenza dell’insieme vuoto. Oltre agli assiomi in un sistema deduttivo vengono specificate delle regole di inferenza cioè dei modi in cui le formule possono essere modificate o composte in modo tale che se le formule di partenza sono teoremi anche la formula ottenuta lo è. I sillogismi di Aristotele possono essere utilizzati come esempi di regole di inferenza. Supponiamo che le formule "Socrate è un uomo" e "l’uomo è un animale" siano entrambe teoremi. Allora possiamo pensare di definire una regola di inferenza che mi dice che se "X è un Y" è un teorema e "Y è uno Z" è un teorema allora anche "X è uno Z" è un teorema. Con questa regola di inferenza è quindi possibile dedurre che "Socrate è un animale" è un teorema. E’ chiaro che se le regole formali possono essere definite meccanicamente tramite un algoritmo allora anche i teoremi possono essere determinati meccanicamente mediante un algoritmo. La ricerca in matematica consiste nell’esplorare lo spazio delle formule ben formate per determinare quali siano effettivamente teoremi. Dare la dimostrazionedimostrazione di un teorema significa esibire tutta la catena delle formule e delle regole di inferenza che permettono di ottenere il teorema a partire dagli assiomi.

1.1.1 proposizioni, operatori logici

Tutto questo è un processo meccanico, ma in realtà è ovvio che i sistemi formali vengono definiti in modo tale da aver per noi un qualche tipo di significato intuitivo. In tal modo la ricerca delle dimostrazioni non è un processo puramente meccanico ma segue delle linee di pensiero che possono richiedere intuizione, inventiva e anche senso estetico. Tipicamente a livello intuitivo vogliamo assegnare un valore di verità alle formule ben formate: vorremmo cioè dire che alcune formule sono verevero ed altre sono falsefalso. In tal caso le formule ben formate vengono usualmente chiamate proposizioniproposizioni (nel linguaggio naturale diremmo: affermazioni). Un esempio di proposizione (falsa) potrebbe essere: 2+2=5.

E’ possibile combinare più proposizioni mediante gli operatori logici. Se e sono proposizioni si può costruire la proposizione chiamata congiunzione logicacongiunzione. Tale proposizione si può leggere “ e ” ed è una proposizione che risulta essere vera solamente nel caso in cui sia che siano vere (si veda la tabella 1.1 per un riassunto schematico). Spesso la congiunzione logica è sottointesa: se si fa un elenco di proposizioni si intende usualmente la loro congiunzione cioè si intende che devono essere tutte vere. La disgiunzione logicadisgiunzione denotata con si può leggere “ o ” ed è una proposizione che è vera se almeno una tra e è vera. La negazione logicanegazione denotata con è una proposizione che si può leggere “non ” che è vera quando è falsa ed è falsa quando è vera.

Operatori logici molto utilizzati sono le implicazioniimplicazioni. La proposizione si può leggere “ implica ” e significa che è vera se è vera. Non si confonda il valore di verità di con il valore di verità di . Se è vera allora è vera o falsa a seconda che sia vera o falsa. Ma se è falsa allora l’implicazione è vera indipendentemente dal valore di . In effetti è equivalente a perché per la verità di basta che sia vera (quando è vera) oppure che sia falsa.

La freccia inversa si può utilizzare per invertire l’implicazione: è equivalente a . Se valgono entrambe le implicazioni è facile convincersi che e devono avere lo stesso valore di verità: diremo quindi che sono equivalenti e scriveremo .

Nella tabella 1.1 sono riportati tutti i valori di verità che si possono ottenere combinando tra loro due proposizioni. Nella tabella 1.2 sono riportate alcune proprietà di tali operatori: queste proprietà possono essere comprese interpretando il loro significato ma possono anche essere dedotte meccanicamente. Per verificare meccanicamente la validità di una di queste espressioni logiche è sufficiente fare una tabella in cui si inseriscono tutti i possibili valori di verità di , ed (in totale saranno casi) e per ognuno di questi si dovrà calcolare il valore di verità di ogni operazione svolta e verificare che ogni espressione completa assume il valore (vero). Diremo che queste sono tautologie tautologiaovvero espressioni logiche la cui validità non dipende dal valore di verità dei suoi termini.

F F V F F V V V
F V V F V V F F
V F F F V F V F
V V F V V V V V
Tabella 1.1: La tabella di verità degli operatori logici. significa falso, significa vero.

non contraddizione
terzo escluso
doppia negazione
simmetria
formule di De Morgan
proprietà distributiva
antisimmetria
implicazione contropositiva
controesempio
dimostrazione per assurdo
Tabella 1.2: Alcune proprietà degli operatori logici. Queste proposizioni sono tutte vere qualunque siano i valori di verità delle proposizioni e . In particolare le equivalenze logiche ci dicono che le proposizioni ai due lati dell’equivalenza assumono sempre lo stesso valore di verità e quindi sono interscambiabili.

Per definire formalmente la logica del calcolo proposizionale dobbiamo avere un sistema sottostante che ci dice chi sono le proposizioni di base, ovvero i termini che possiamo sostituire al posto di , , . Queste saranno proposizioni (ovvero formule ben formate). Una volta definite le proposizioni di base, ogni formula della forma , , , , e è anch’essa una proposizione (ovvero è ben formata) se e lo sono. Il sistema formale utilizza i simboli: oltre a tutti i simboli che servono per comporre le proposizioni di base.

Il caso più semplice possibile è quello in cui abbiamo solamente due proposizioni di base e e due assiomi: e . L’interpretazione del sistema è che è vero mentre è falso.

Le regole di inferenza del calcolo delle proposizioni possono essere date in modi diversi. regole di inferenzaProviamo a spiegare (senza troppi formalismi) il sistema che viene chiamato deduzione naturale. Questo sistema presenta per ognuno degli operatori logici (negazione, congiunzione, disgiunzione, implicazione) due regole formali: una che permette l’introduzione dell’operatore e una che permette l’eliminazione l’operatore.

Le regole più semplici sono quelle che riguardano la congiunzione logica. Se e sono teoremi possiamo dedurre che anche è un teorema (introduzione della congiunzione). introduzione congiunzioneViceversa se è un teorema possiamo dedurre che sia che sono teoremi (eliminazione della congiunzione). eliminazione congiunzioneAd esempio se abbiamo il teorema e il teorema allora possiamo dedurre che è un teorema. Viceversa se è un teorema allora possiamo dedurre che è un teorema.

Anche l’introduzione della disgiunzione logica è una regola molto semplice: se è un teorema allora anche e sono teoremi, qualunque sia la proposizione . introduzione disgiunzioneAd esempio se è un teorema possiamo dedurre che anche è un teorema. La regola di eliminazione della disgiunzione è leggermente eliminazione disgiunzionepiù complicata. Se è un teorema e se entrambi e sono teoremi, possiamo dedurre che è un teorema. Ad esempio se abbiamo i teoremi: allora possiamo dedurre che è un teorema.

Per quanto riguarda l’implicazione logica, la regola di eliminazione si chiama modus ponens ed è forse la più importante modus ponensdelle regole di inferenza. La regola ci dice che se abbiamo il teorema e il teorema possiamo affernare che anche è un teorema. Ad esempio se abbiamo dimostrato e abbiamo dimostrato allora possiamo dedurre . Questa regola formale dà significato all’implicazione logica.

La regola di introduzione della implicazione è più complicata introduzione implicazioneda formalizzare e richiede l’introduzione di un nuovo concetto: il contesto dimostrativo. contesto dimostrativoUn contesto è in pratica un nuovo sistema formale che eredita tutti gli assiomi e le regole formali del sistema formale originario ma con delle proprietà in più che permettono tipicamente di ottenere teoremi che non era possibile ottenere nel sistema formale originale. Per l’introduzione dell’implicazione logica la regola è la seguente. Per poter affermare che è un teorema introduciamo un nuovo contesto in cui tutti i teoremi già dimostrati sono assiomi e inoltre anche è un assioma aggiuntivo. Se in questo contesto riusciamo ad ottenere come teorema allora possiamo dire che è un teorema nel sistema formale originale. Si noti che potrebbe non essere un teorema nel contesto orginale, lo è solo nel contesto ipotetico in cui abbiamo supposto (per ipotesi, appunto) che fosse un teorema.

Proviamo per esempio a dimostrare la regola più controversa delle tavole di verità ovvero che (dove sta per falso e sta per vero). Quello che dobbiamo fare è verificare che se è un teorema (cioè è falso) e se è un teorema (cioè è vero) allora è un teorema. Dovremmo usare la regola di introduzione dell’implicazione logica. Dunque supponiamo per ipotesi che sia un teorema. Visto che era un teorema nel contesto originale rimane un teorema nel contesto ipotetico in cui abbiamo supposto che sia un assioma. Possiamo quindi, fuori dal contesto, dedurre come volevasi dimostrare.

Ad esempio al posto di possiamo mettere e al possiamo mettere . Vorremo allora dimostrare che è un teorema. Proviamo a farlo formalmente con tutti i dettagli.

Supponiamo di avere un sistema formale contenente i simboli , , , oltre che tutti i simboli della logica proposizionale (ovvero , , , , e ). Chiamiamo costanti i simboli e . Supponiamo che tutte le formule della forma e siano proposizioni (formule ben formate) se al posto di e mettiamo qualunque costante. Supponiamo che sia un sinonimo di , Supponiamo infine che sia un assioma se al posto di mettiamo qualunque costante.

Fuori dal sistema formale, nell’esibire una dimostrazione, faremo un elenco dei nostri teoremi, numerando ogni riga per poterci fare riferimento. Usiamo le parentesi graffe e per racchiudere i contesti dimostrativi. Tra parentesi quadre indichiamo le regole formali che stiamo utilizzando.

Teorema 1.1 (esempio di dimostrazione formale). .

Dimostrazione. □

Ritorniamo alle regole di inferenza del calcolo proposizionale, in particolare alla negazione logica. rimozione negazionePer la rimozione la regola è quella della doppia negazione: se è un teorema allora anche è un teorema. Ad esempio se è un teorema allora anche è un teorema. introduzione negazioneLa regola di introduzione della negazione logica è la dimostrazione per assurdo. Se introduciamo un contesto formale in cui assumiamo (per assurdo) che sia un teorema e, nel contesto, riusciamo ad ottenere una contraddizione (ad esempio ) allora possiamo affermare che (fuori dal contesto) è un teorema.

Ad esempio se è un teorema possiamo dimostrare che anche è un teorema. Infatti supponiamo per assurdo . Allora, tramite eliminazione della doppia negazione possiamo dedurre . Ma questo è in contraddizione con . Dunque abbiamo dimostrato che .

Le regole formali che abbiamo introdotto sono sufficienti per dimostrare la validità delle tabelle di verità degli operatori logici.

Esercizio 1.2. Si provino ad utilizzare le regole formali di inferenza del calcolo proposizionale per dimostrare la validità delle tavole di verità.

1.1.2 predicati, quantificatori

Un predicatopredicato è una proposizione che contiene una o più variabili il cui valore di verità, quindi, può dipendere dal valore assegnato alle variabili. Un esempio di predicato è che risulta essere vero se e falso altrimenti.

Le variabili non sono altro che simboli del sistema formale. Usualmente vengono utilizzate le ultime lettere dell’alfabeto. Siccome le lettere dell’alfabeto sono in numero finito e visto che vogliamo invece avere la possibilità di introdurre sempre nuove variabili, decidiamo che una variabile può essere composta da una sequenza di più simboli. Si può ad esempio usare l’apice: , , oppure usare una sequenza di lettere: , per avere una quantità illimitata di nomi diversi a disposizione.

Se un predicato dipende da una o più variabili queste si chiamano variabili liberevariabili libere. E’ possibile chiudere una variabile libera mediante un quantificatore. Il quantificatore universalequantificatore universale denotato col simbolo serve ad affermare che il predicato è vero per ogni possibile valore della variabile quantificata. Ad esempio la proposizione significa: “per ogni si ha ” ed è una proposizione falsa. Il quantificatore rende muta la variabile del predicato nel senso che il valore di verità della proposizione non dipende più dal valore di quella variabile, che non è più una variabile libera ma funge solo da segnaposto. In effetti se cambio nome ad una variabile muta il valore di verità non cambia. Ad esempio scrivere è equivalente a .

Il quantificatore esistenzialequantificatore esistenziale denotato col simbolo serve ad affermare che il predicato è vero per almeno un valore della variabile quantificata. Ad esempio la proposizione significa: “esiste almeno un per cui risulta ”. Quello che si ottiene è una proposizione in cui la variabile è muta. In questo caso la proposizione è vera in quanto per il predicato è vero.

Un predicato può dipendere da più variabili ed è quindi possibile inserire più quantificatori. In tal caso l’ordine dei quantificatori può essere rilevante. Delle seguenti proposizioni la prima è vera, la seconda invece è falsa: Intuitivamente la prima affermazione ci dice che per ogni numero esiste un numero che differisce di da . La seconda ci dice che c’è un numero che differisce di da qualunque numero .

Tabella 1.3: Le formule di De Morgan per i quantificatori logici.

Risulta utile saper trasformare un quantificatore logico nell’altro per mezzo delle negazioni con le formule di De Morgan riportate nella tabella 1.3.

Spesso il quantificatore universale viene sottointeso. Ad esempio se si scrive si intende che tutte le variabili libere sono quantificate tramite quantificatore universale: . Il segno di interpunzione può essere omesso e una quantificazione può essere fatta contemporaneamente su più variabili. Potremo quindi scrivere: o anche . A volte, se non crea ambiguità, si potranno scrivere i quantificatori anche a fine frase

Una proposizione non può contenere variabili libere, altrimenti il suo valore di verità potrebbe dipendere da quelle variabili e non sarebbe quindi ben definito. costantiSi può però intendere che alcune variabili sono costanti, cioè rappresentano un oggetto ben preciso. Ad esempio nella proposizione si intende che è una costante, ovvero un ben preciso numero. Anche le cifre , , sono usualmente sempre intese come costanti.

Insieme al calcolo dei predicati si introduce usualmente anche il simbolo di uguaglianza =. Come viene definita l’uguaglianza dipende da come sono definiti gli oggetti trattati dal nostro sistema formale, cosa che noi faremo per la teoria degli insiemi nel prossimo paragrafo. Ma comunque venga definita l’uguaglianza si richiede che valgano i seguenti assiomi.

Assioma 1.3 (estensionalità). Se è un predicato in cui compaiono libere le variabili e e se allora in posso sostituire ad una o più occorrenze della variabile la variabile (e viceversa).

Assioma 1.4 (uguaglianza).

Anche per il calcolo dei predicati dobbiamo specificare le regole di inferenza per l’introduzione e l’eliminazione dei quantificatori.

eliminazione L’eliminazione del quantificatore universale è molto semplice. Se abbiamo un teorema della forma e se nel contesto dimostrativo è stata introdotta una costante , allora possiamo dedurre . introduzione Viceversa, per introdurre il quantificatore universale dobbiamo aprire un contesto dimostrativo in cui supponiamo che sia una costante di cui non abbiamo alcuna informazione (cioè non è usata come costante al di fuori del contesto). Se nel contesto riusciamo a dimostrarare una proposizione possiamo allora dedurre, fuori contesto, il teorema .

In pratica si dirà: fissato qualunque, abbiamo dimostrato quindi possiamo affermare che .

eliminazione Per quanto riguarda il quantificatore esistenziale la regola di eliminazione ci dice che se abbiamo un teorema della forma possiamo introdurre un contesto dimostrativo in cui è definita una costante che ha la proprietà . Se in tale contesto riesco ad ottenere un teorema che non dipende da allora quel teorema è valido anche fuori dal contesto. introduzione La regola di introduzione ci dice invece che se abbiamo un teorema della forma , con una qualunque costante, possiamo allora dedurre .

Come esempio enunciamo e dimostriamo formalmente un semplice teorema.

Teorema 1.5 (esempio di dimostrazione formale).

Dimostrazione. □