logica matematica

Sintassi e semantica

Le espressioni di un discorso deduttivo possono essere considerate o sintatticamente, cioè formalmente come oggetti grafici combinabili tra loro, o semanticamente, cioè in relazione al loro significato. La parte sintattica di una teoria logica si chiama calcolo logico. L’aspetto semantico di una teoria logica è invece la trattazione del significato o interpretazione dei suoi simboli. L’interpretazione è una rappresentazione (applicazione) dei simboli sugli elementi di certi insiemi costituenti un universo (o dominio). Una interpretazione può soddisfare o meno un enunciato del linguaggio logico. In altri termini, la semantica fa in modo che il calcolo logico parli di certi oggetti conferendo un certo significato alle espressioni. Se a un linguaggio logico si associa un’interpretazione, si costituisce un sistema logico; la coppia di un calcolo logico e di un sistema costituisce una logica.

Sistema formale

Formalizzare una teoria significa sostituire le espressioni del linguaggio naturale con i segni di un linguaggio artificiale. Con la formalizzazione si ha il vantaggio di ‘visualizzare’ tutte le concatenazioni e le deduzioni formali coinvolte; si evita inoltre il pericolo che l’uso dei vocaboli naturali, richiamando alla mente proprietà non esplicitamente dichiarate, le faccia inavvertitamente adoperare nel contesto della teoria. Pertanto, nella costruzione di una determinata logica innanzitutto se ne stabilisce il linguaggio, che è basato su un adeguato insieme di simboli fondamentali detto alfabeto; una sequenza di tali simboli si dice espressione: certe espressioni assoggettate a delle regole di formazione sono dette formule ben formate. Dopo aver fissato il linguaggio, si costituisce il calcolo della logica in studio, fissando un insieme di postulati P costituito da assiomi e regole di inferenza; applicando queste regole si possono ottenere, a partire dagli assiomi, mediante le dimostrazioni, le formule dimostrabili, dette anche teoremi o tesi logiche. Per dimostrazione di un teorema H in un determinato calcolo logico s’intende una sequenza finita di formule di quel calcolo, ognuna delle quali o è un assioma o è ottenuta da formule precedenti mediante l’applicazione di una delle regole di inferenza, mentre l’ultima formula della sequenza è H. Con la notazione ⊢ H si abbrevia l’asserzione «la formula H è un teorema, ossia è formula finale di una dimostrazione». Nelle teorie deduttive particolari, cioè relative a determinate scienze deduttive, oltre che di dimostrazione, si parla anche di derivazione da un insieme di formule, dette assunzioni, le quali possono essere la formalizzazione degli assiomi specifici di quella scienza; se M è un insieme di formule, si abbrevia M ⊢ H l’asserzione «la formula H è derivabile dalle assunzioni M, ossia è formula finale di una derivazione dalle assunzioni M»; le formule occorrenti nel corso della derivazione possono essere anche qualcuna delle assunzioni stesse. L’insieme di tutte le tesi logiche si indica con D_p(∅), per sottolineare che esse sono ottenute a partire dai soli postulati P. Qualora si consideri un insieme M di assunzioni, allora le formule che da esse si ottengono mediante derivazione costituiscono l’insieme D_p(M). Ovviamente, D_p(∅) è l’insieme delle formule che appartengono a tutti i D_p(M) (con M qualsiasi). Per determinare una semantica e costituire quindi un sistema logico si definisce il concetto di interpretazione del linguaggio (su un universo): un’interpretazione di un linguaggio (su un universo) è una rappresentazione o applicazione dei simboli dell’alfabeto del linguaggio su individui dell’universo, su insiemi di individui dell’universo, e su W = {V, F}, in modo che a ogni formula risulti associato un valore di verità (il valore vero, simbolizzato da V, o il valore falso, simbolizzato da F). Se un’interpretazione associa a una formula H il valore V, allora essa si dice modello di H. Fissato un insieme M di formule del linguaggio, dette premesse, si definisce la relazione di conseguenza: una formula H si dice conseguenza logica delle premesse M se e solo se ogni interpretazione che è modello di tutte le premesse è modello anche di H. L’insieme di tutte le conseguenze di M si indica con il simbolo C(M). Si scrive M ⊨ H per esprimere il fatto che H è una conseguenza delle premesse M; si scrive ⊨ H per indicare che ogni interpretazione è modello di H. L’insieme delle formule comuni a tutti i C(M) (con M qualsiasi), il quale simbolicamente può indicarsi con C(∅) (in quanto insieme delle conseguenze dell’insieme vuoto di premesse ∅), si dice insieme delle identità logiche o tautologie o formule (universalmente) valide. Se una formula H ammette almeno un modello si dice soddisfacibile. A proposito dei simboli bisogna distinguere l’uso che si fa di essi nella logica e la menzione che se ne fa nella metalogica. Ciò può avvenire convenendo di racchiudere i simboli nel secondo caso tra virgolette e stabilendo di usarli in modo autonomo, cioè come designazioni di sé stessi. La distinzione tra il linguaggio logico (detto anche linguaggio-oggetto) e il linguaggio usato nella metalogica (detto anche metalinguaggio) è indispensabile per evitare le antinomie semantiche, come, per es., quella del mentitore che può essere formulata nel seguente modo: dato l’enunciato «il presente enunciato è falso», risulta che questo enunciato è vero esattamente se è falso. L’antinomia dipende dall’applicazione del predicato «è falso» a un enunciato appartenente allo stesso linguaggio a cui il predicato appartiene, ed è perciò evitabile usando tale predicato in un metalinguaggio in cui lo si possa applicare soltanto a enunciati di un linguaggio-oggetto opportunamente menzionati.

Teoria del significato

Tale teoria ha per scopo di precisare il valore da attribuire alle parole, già usate, vero e falso e ad alcuni concetti a esso strettamente collegati. Frege, come si è già accennato, nel suo Über Sinn und Bedeutung (1892) espone in proposito una teoria oggi quasi universalmente accettata. A ogni espressione linguistica si può attribuire un significato intensionale, detto anche intensione o senso o connotazione, e un significato estensionale, detto anche estensione o significato (in senso stretto) o denotazione. Per es., al nome individuale ‘Roma’ può corrispondere come significato intensionale il concetto individuale di ‘capitale d’Italia’ oppure di ‘città fondata nel 753 a.C. da Romolo e Remo’, ecc., con cui si forniscono dei connotati caratteristici del termine ‘Roma’; come significato estensionale, a ‘Roma’ corrisponde invece esattamente quell’individuo che è la città di Roma. Così, al predicato ‘è uomo’ può corrispondere il significato intensionale ‘è animale ragionevole’, e come significato estensionale, l’insieme costituito da tutti gli uomini. A un enunciato corrisponde come significato intensionale il senso della frase stessa, mentre (con Frege, Carnap, Church e la maggior parte dei logici contemporanei) gli si fa corrispondere come significato estensionale il valore di verità: vero o falso (simbolicamente, uno dei due elementi dell’insieme W = {V, F}). Pertanto, enunciati con valori intensionali diversissimi (come, per es., ‘Aristotele è un filosofo’ e ‘4 + 5 = 9’) hanno lo stesso significato estensionale: V. Una l. può essere intensionale (cioè costruita su base intensionale) o estensionale. S’intuisce subito che le logiche estensionali sono operativamente più semplici e meglio si adattano all’uso che di esse si fa nelle teorie matematiche (è immediata, per es., la loro interpretazione insiemistica). Le logiche più usate, e in partic. quelle che qui ricorderemo, sono appunto logiche estensionali. Nella presentazione delle teorie logiche si segue questo criterio: si espone dapprima una logica degli enunciati, cioè la logica più elementare che analizza solo gli enunciati composti (molecole), ma non la costituzione interna di ciascun enunciato semplice (atomo) considerato come indivisibile. Poi si espone una logica dei predicati del primo ordine, che analizza anche la costituzione di ciascun enunciato semplice, formato da soggetto e predicato, e ammette, per i soli soggetti, la quantificazione, cioè la considerazione quantitativa di essi. Successivamente, dopo aver esposto la logica dei predicati del primo ordine con identità, si tratta la logica dei predicati del secondo ordine, che consente anche la quantificazione dei predicati. Si farà poi un cenno ai principali problemi comuni a tutte le logiche. Tra i vari tipi di calcoli logici sarà presentato quello esposto da Hilbert e Bernays nelle Grundlagen der Mathematik (2 voll., 1934-39).

La logica degli enunciati

Linguaggio. Alfabeto: è costituito da certi simboli detti variabili enunciative (che si denotano con le lettere p, q, r, ...) e dai seguenti simboli che sono detti connettivi: ¬ (connettivo monoargomentale), ⋀, ⋁, →, ↔ (connettivi biargomentali). I connettivi intuitivamente significano rispettivamente: non, e, o (nel senso non esclusivo del latino vel), implica, equivale; essi sono detti rispettivamente: negazione, congiunzione, disgiunzione, condizionale (o implicazione), bicondizionale (o doppia implicazione). Formule: sono le stesse variabili enunciative; inoltre se H e K sono formule, lo sono anche ¬ H e H c K, dove c sta per uno qualsiasi dei connettivi biargomentali; e niente altro è una formula della logica degli enunciati. Assiomi del calcolo enunciativo:

[A1] p → (q → p)

[A2] [p → (p → q)] → (p → q)

[A3] (p → q) → [(q → r) → (p → r)]

[A4] p ∧ q → p

[A5] p ∧ q → q

[A6] (p → q) → [(p → r) → (p → q ∧ r)]

[A7] p → p ∨ q

[A8] q → p ∨ q

[A9] (p → r) → [(q → r) → (p ∨ q → r)]

[A10] (p ↔ q) → (p → q)

[A11] (p ↔ q) → (q → p)

[A12] (p → q) → [(q → p) → (p ↔ q)]

[A13] (p → q) → (¬ q → ¬ p)

[A14] p → ¬ ¬ p)

[A15] ¬ ¬ p → p).

Regole di inferenza del calcolo enunciativo: a) regola di separazione (o modus ponens): in una dimostrazione o derivazione in cui occorrano sia la formula K sia la formula K → H può essere aggiunta, dopo queste, la formula H, ottenendo ancora una dimostrazione; b) regola di sostituzione: in una dimostrazione o derivazione in cui occorra la formula H può essere aggiunta, dopo H, la formula H(p∣K), che si ottiene sostituendo in H tutte le occorrenze della variabile p con la formula K, ottenendo ancora una dimostrazione. Esempi di teoremi del calcolo enunciativo:

[T1] (p → q) ↔ (¬ p ∨ q)

(legge di Filone Megarico)

[T2] ¬ (p ∧ q) ↔ (¬ p ∨ ¬ q)

(3ª legge di De Morgan)

[T3] p → (¬ p → q) (legge di Duns Scoto).

Sistema della logica degli enunciati. Interpretazione dei simboli del linguaggio: un’interpretazione I è una rappresentazione, cioè un’applicazione, delle variabili enunciative nell’insieme dei valori di verità W = {V, F}, e dei connettivi ¬, ⋀, ⋁, →, ↔ rispettivamente sulle funzioni di verità Non, Et, Vel, Seq, Aeq definite la prima su W e le altre sul prodotto W×W e a valori in W mediante la tabella:

Non(V) = F; Non(F) = V.

Et(V, V) = V; Et(V, F) = F; Et(F, V) = F;

Et(F, F) = F.

Vel(V, V) = V; Vel(V, F) = V; Vel(F, V) = V;

Vel(F, F) = F.

Seq(V, V) = V; Seq(V, F) = F; Seq(F, V) = V;

Seq(F, F) = V.

Aeq(V, V) = V; Aeq(V, F) = F; Aeq(F, V) = F;

Aeq(F, F) = V.

Così, ciascuna interpretazione I permette di associare a ogni formula H della logica degli enunciati un valore che si denota con I(H) appartenente all’insieme W, cioè V o F. Se un’interpretazione I associa a una certa formula H il valore V, si dice che I è modello di H o che I soddisfa H. H è una formula valida o una tautologia o un’identità se e solo se ogni interpretazione I è modello di H; è soddisfacibile se e solo se ammette almeno un modello.

Tavole di verità. È sempre possibile decidere se una formula del linguaggio enunciativo è valida o no, se è soddisfacibile o no, mediante le cosiddette tavole di verità. Data una formula del linguaggio enunciativo, per es., H = (p → q) ⋀ p, costituita a partire dalle variabili enunciative p e q, sono possibili tante interpretazioni di essa quante sono quelle che possono darsi alla coppia (p, q). Esse sono le seguenti: l’interpretazione I₁ che assegna il valore V sia a p che a q, l’interpretazione I₂ che assegna a p il valore V e a q il valore F, l’interpretazione I₃ che assegna a p il valore F e a q il valore V, e l’interpretazione I₄ che assegna il valore F sia a p che a q. Per decidere se ciascuna delle 4 interpretazioni è modello di H, si costruisce la tavola di verità nel seguente modo:

Cioè si riportano innanzitutto su quattro righe le diverse interpretazioni I₁, I₂, I₃, I₄ indicate a sinistra della linea verticale nelle colonne contrassegnate in basso con a e b. Poi le stesse interpretazioni si trascrivono anche a destra della linea verticale nelle colonne ancora contrassegnate con a e b. A questo punto è già possibile costruire la colonna contrassegnata in basso con c, tenendo conto dell’interpretazione data di → sulla funzione Seq. Infine, confrontando i valori indicati nella colonna c e nell’ultima colonna a si possono ottenere (tenendo conto dell’interpretazione data di ⋀ sulla funzione Et) i valori della colonna d, che sono i valori associati da ciascuna interpretazione all’intera formula H. Si vede così che I₁ è modello di H, mentre non lo sono I₂, I₃, I₄, le quali associano a H il valore F. Quindi H è soddisfacibile ma non valida. Si verifica subito con tale metodo che ogni assioma e ogni teorema è sempre valido.

Logica dei predicati del primo ordine

Linguaggio. Alfabeto: comprende i seguenti simboli: le variabili individuali (x, y, z, ...), le variabili predicative p^k_i (dove k è un numero naturale che indica il numero dei posti della variabile predicativa, e i è un numero naturale che differenzia le variabili predicative; k e i si possono sottintendere; le variabili predicative a zero posti sono dette variabili enunciative; sia per le variabili predicative sia per quelle enunciative, se non vi è possibilità di equivoco, si usano anche i simboli P, Q, R, ...), i connettivi enunciativi e inoltre due quantificatori, il quantificatore universale ∀x e il quantificatore esistenziale ∃x (che significano rispettivamente «per tutti gli x» e «esiste almeno un x tale che»). Formule: sono formule le variabili enunciative, sono formule le variabili predicative p^k_i seguite da k variabili individuali; inoltre, se H e K sono formule, allora sono formule anche ¬H, H c K (dove c indica un qualsiasi connettivo biargomentale), ∀xH (dove si dice che H è il campo d’azione del quantificatore ∀x), ∃xH (dove si dice che H è il campo d’azione del quantificatore ∃x); nient’altro è una formula della logica dei predicati del primo ordine. Una variabile individuale si dice libera in una formula se non cade sotto l’azione di un quantificatore, altrimenti si dice vincolata. Una formula che contenga qualche variabile libera si dice formula aperta, o funzione proposizionale, altrimenti si dice formula chiusa. Ogni formula aperta può essere trasformata in formula chiusa premettendo a essa tanti quantificatori quante sono le sue variabili libere. Assiomi del calcolo predicativo del primo ordine: sono i 15 assiomi della logica enunciativa e i due seguenti:

[A16] ∀x Px → Py

[A17] Py → ∃x Px.

Regole di inferenza del calcolo predicativo del primo ordine:

[R1] Regola di separazione: (➔ sopra), La logica degli enunciati.

[R2] Regole di sostituzione: per le variabili individuali, per le variabili enunciative e per le variabili predicative (regole che sono formulate in modo analogo a come è stata formulata la regola di sostituzione per le variabili enunciative nel calcolo degli enunciati; si noti che, in partic., mediante le regole di sostituzione per le variabili enunciative, nei primi 15 assiomi si possono rimpiazzare le variabili enunciative p, q, r, ... con formule qualsiasi H, K,... del linguaggio predicativo di primo ordine).

[R3] Regola di generalizzazione: in una dimostrazione o derivazione in cui occorra la formula H→K(x), può essere aggiunta la formula H→ ∀xK(x), ottenendo ancora una dimostrazione, purché x non sia libera in H.

[R4] Regola di particolarizzazione: in una dimostrazione o derivazione in cui occorra la formula K(x)→H può essere aggiunta la formula ∃xK(x)→H, ottenendo ancora una dimostrazione, purché x non sia libera in H. Esempi di teoremi del calcolo dei predicati del primo ordine:

[T4] ∀x Px ↔ ¬ ∃x ¬ Px

(Iª legge generalizzata di De Morgan)

[T5] ∀x ∀y Pxy ↔ ∀y ∀x Pxy

[T6] ∃x ∃y Pxy ↔ ∃y ∃x Pxy

[T7] ∃x ∀y Pxy ↔ ∀y ∃x Pxy

(leggi di permutabilità dei quantificatori).

Sistema della logica dei predicati del primo ordine

Preso un insieme non vuoto α, si dice universo o struttura su α, e si denota con U(α), la successione di insiemi α, W = {V, F}, α₁, α₂, α₃, ..., dove α è l’insieme non vuoto dato, detto dominio degli individui dell’universo, W = {V, F} è l’insieme dei valori di verità, e, per i = 1, 2, 3, ..., α_i è l’insieme di tutte le possibili relazioni a i posti su α, ossia di tutti i possibili attributi i-adici su α. Dalla definizione data segue che l’universo U(α) è determinato appena sia fissato il dominio α dei suoi individui, indipendentemente dagli altri insiemi della successione. Ciò giustifica il fatto che si parli semplicemente di universo su α ed è in relazione con la nostra concezione estensionale della logica. Anzi, la struttura di un universo non dipende neppure dalla natura degli elementi di α, ma solo dal loro numero, cioè dalla cardinalità di α: due insiemi equipotenti α e α′, danno origine a due universi U(α) e U(α′) che per la definizione data sono strutturalmente identici. Dato un universo su un insieme non vuoto α, si dice α-interpretazione dei simboli di un linguaggio predicativo, e si indica con I_α, una rappresentazione o applicazione dei simboli del linguaggio sull’universo dato, in modo tale che: (1) a ciascuna variabile individuale è assegnato un elemento di α; (2) a ciascuna variabile enunciativa è assegnato un elemento di W; (3) a ciascuna variabile predicativa P a k posti è assegnato un elemento di α_k; (4) a ciascun connettivo è assegnata la corrispondente funzione di verità; (5) a ciascun quantificatore è assegnata la corrispondente funzione di quantificazione. Ai quantificatori ∀x e ∃x corrispondono infatti le funzioni di quantificazione Om e Ex rispettivamente. Queste sono definite sui sottoinsiemi non vuoti di W e hanno valori in W mediante la tabella:

Om ({V}) = V; Om ({V, F}) = F; Om ({F}) = F

Ex ({V}) = V; Ex ({V, F}) = V; Ex ({F}) = F.

Così, ogni α-interpretazione permette di associare a ogni formula del linguaggio predicativo uno dei due valori di verità; denotiamo con I_α (H) il valore che la α-interpretazione Iα assegna alla formula H. Estendiamo alla logica dei predicati definizioni già date per quella degli enunciati. Una α-interpretazione I_α si dice modello della formula H se e solo se I_α (H) = V, cioè se e solo se assegna alla formula il valore vero. Viceversa, una formula H si dice α-soddisfacibile se e solo se esiste un’α-interpretazione che è suo modello. Una formula H si dice α-valida se e solo se ogni α-interpretazione è suo modello. Le ultime due definizioni si generalizzano riferendole a un qualsiasi universo. Tutte le definizioni date si estendono al caso di un insieme di formule, per es. un insieme di assiomi o un intero sistema assiomatico. Allo scopo di chiarire come si ottiene il valore di una formula quantificata, introduciamo il concetto di reinterpretazione in I_α della variabile x con l’individuo a di α. Si tratta di una nuova α-interpretazione coincidente con I_α in tutto, tranne nel fatto che applica x in a an- ziché in I_α(x). Allora il valore associato da I_α a una formula del tipo ∀xH sarà V se e solo se tutte le reinterpretazioni in I_α(H) della variabile x con un individuo di α hanno valore V; sarà F se e solo se almeno una di tali reinterpretazioni ha valore F. Il valore associato da I_α a una formula del tipo ∃xH sarà V se e solo se almeno una reinterpretazione in I_α(H) di x con un individuo di α ha valore V; sarà F se e solo se non ne esiste nessuna con valore V.

Logica dei predicati del primo ordine con identità

Linguaggio. È quello della logica del primo ordine con l’aggiunta, nell’alfabeto, del simbolo =, che va sempre interpretato con il significato di ‘è identico a’, e, tra le espressioni, di quelle del tipo x = y. Assiomi: sono quelli precedenti e inoltre

[I1] x = x (riflessività)

[I2] x = y → (Px → Py).

Esempi di teoremi:

[T8] x = y → y = x (simmetria)

[T9] x = y → (y = z → x = z (transitività).

Una formula del linguaggio predicativo si dice in forma normale prenessa se tutti i quantificatori si trovano all’inizio e, quindi, tutti i connettivi all’interno del campo di azione di quelli. La sequenza iniziale dei quantificatori si dice, in tal caso, prefisso, mentre la parte restante dell’espressione si dice matrice. Una formula chiusa e in forma normale prenessa si dice in forma normale totalmente prenessa. Valgono i seguenti teoremi. Teorema sintattico delle forme normali prenesse: per ogni formula H esiste una formula H′ in forma normale prenessa tale che sia dimostrabile l’espressione H ↔ H′. Dal teorema di validità (➔ oltre) segue anche il teorema semantico delle forme normali prenesse: per ogni espressione H della logica dei predicati del primo ordine (anche con identità) esiste un’espressione H′ in forma normale prenessa tale che sia valida la formula H ↔ H′. Teorema sintattico della chiusura universale: ogni formula H è dimostrabile se e solo se è dimostrabile ∀x ∀y ... ∀z H (dove x, y, ..., z sono tutte e solo le variabili libere contenute in H). Teorema sintattico della chiusura esistenziale: ogni formula H è dimostrabile se e solo se è dimostrabile ∃x ∃y ... ∃z H (con le stesse precisazioni circa la x, y, ..., z). Teorema semantico della chiusura universale: ogni espressione H è α-valida se e solo se è α-valida ∀x ∀y ... ∀z H (x, y, ..., z, come sopra). Teorema semantico della chiusura esistenziale: ogni formula H è α-soddisfacibile se e solo se è α-soddisfacibile ∃x ∃y ... ∃z H (x, y, ..., z, come sopra). Teoremi sintattici delle forme normali totalmente prenesse: per ogni formula H, (1) esiste una formula H′ in forma normale totalmente prenessa tale che H è dimostrabile se e solo se è dimostrabile H′; (2) esiste una formula H′ in forma normale totalmente prenessa tale che è dimostrabile ¬ H se e solo se è dimostrabile ¬ H′. Teoremi semantici delle forme normali totalmente prenesse: per ogni formula H, (1) esiste una formula H′ in forma normale totalmente prenessa tale che H è α-soddisfacibile se e solo se H′ è α-soddisfacibile; (2) esiste una formula H′ in forma normale totalmente prenessa tale che H è α-valida se e solo se H′ è α-valida. Una formula predicativa si suol dire in forma normale di Skolem di prima specie se essa è in forma normale totalmente prenessa e inoltre tutti i suoi quantificatori esistenziali precedono quelli universali; se, invece, tutti i quantificatori universali precedono quelli esistenziali, la formula si dice in forma normale di Skolem di seconda specie. Valgono i seguenti teoremi. Teoremi sintattici delle forme normali di Skolem: per ogni formula H, (1) esiste una forma normale di Skolem di prima specie H′ tale che H è dimostrabile se e solo se è dimostrabile H′; (2) esiste una forma normale di Skolem di seconda specie H′ tale che ¬ H è dimostrabile se e solo se è dimostrabile ¬ H′. Teoremi semantici delle forme normali di Skolem: per ogni formula H, (1) esiste una forma normale di Skolem di prima specie H′ tale che H è α-valida se e solo se H′ è α-valida; (2) esiste una forma normale di Skolem di seconda specie H′ tale che H è α-soddisfacibile se e solo se H′ è α-soddisfacibile. Le teorie deduttive formalizzate che hanno, come supporto logico, una logica non superiore a quella del primo ordine con identità (quali sono, per es., la teoria dei semiordini e quella dei gruppi) si dicono teorie elementari. I concetti di dimostrazione e di derivabilità sono naturalmente applicabili rispettivamente alla logica fin qui esposta e alle teorie elementari. Si pone, quindi, il problema di sapere se è possibile stabilire una relazione tra un concetto e l’altro, se cioè, dato un insieme di formule chiuse M e una formula H, esiste una formula K tale che H è derivabile da M se e solo se K è dimostrabile (problema sintattico di riduzione). L’analogo problema semantico di riduzione consiste nel chiedersi se, dato un insieme di formule M e una formula H, esiste una formula K tale che H è conseguenza di M se e solo se K è valida. Le due questioni ammettono risposte affermative. Il problema sintattico di riduzione è risolto mediante i seguenti teoremi. (1) Teorema sintattico di deduzione o di Herbrand e Tarski:

M ⋂ {H′} ⊢ H se e solo se M ⊢ H′ → H.

Corollario

{H₁ ,..., H_n} ⊢ H se e solo se ⊢ H₁ ∧ ... ∧ H_n → H.

(2) Teorema sintattico di finitezza: una formula H è derivabile da un insieme di assunzioni M se e solo se essa è derivabile da un sottoinsieme finito di M. (3) Teorema sintattico di riduzione: dati un insieme di assunzioni M e una formula H, esiste una formula K tale che H è derivabile da M se e solo se K è dimostrabile.

Il problema semantico di riduzione è risolto in modo analogo basandosi sui teoremi seguenti. (1) Teorema semantico di deduzione:

M ⋂ {H′} ⊨ H se e solo se M ⊨ H′ → H.

Corollario:

{H₁ ,...., H_n} ⊨ H se e solo se ⊨ H₁ ∧ ... ∧ H_n → H.

(2) Teorema semantico di finitezza: una formula H è conseguenza di un insieme di premesse M se e solo se essa è conseguenza di un sottoinsieme finito di M. (3) Teorema semantico di riduzione: dati un insieme di premesse M e una formula H, esiste una formula K tale che H è una conseguenza di M se e solo se K è valida.

Logica dei predicati del secondo ordine

Linguaggio. Alfabeto: è quello della logica dei predicati del primo ordine. Formule: oltre quelle della logica dei predicati del primo ordine, anche quelle del tipo ∀ PH e ∃ P H. Assiomi: ai precedenti si aggiungono:

[A18] ∀ P H → H(P|Q)

[A19] H(P|Q) → ∃ P H.

Regole di inferenza: quelle di generalizzazione e di particolarizzazione si estendono anche alle variabili predicative. Sistema. Le definizioni di interpretazione, di valore, di modello, sono simili a quelle già date a proposito della logica dei predicati del primo ordine.

I problemi fondamentali della logica matematica

Problema di validità. Una logica si dice valida in senso generale se e solo se l’insieme di tutte le tesi derivanti da un qualsiasi insieme di assunzioni M è contenuto nell’insieme di tutte le conseguenze delle premesse M. In simboli: D_p(M) ⊆ C(M). Una logica si dice valida in senso speciale se e solo se D_p(∅) ⊆ C(∅). Per ciascuna delle logiche sopra presentate si dimostra il teorema di validità, ossia si dimostra che esse sono valide sia in senso speciale che generale. Problema di adeguatezza o completezza: una logica si dice semanticamente completa in senso generale se e solo se l’insieme di tutte le conseguenze di un qualsiasi insieme di premesse M è contenuto nell’insieme di tutte le tesi derivanti dall’insieme di premesse M. In simboli: C(M) ⊆D_p(M). Una logica si dice semanticamente completa in senso speciale se e solo se C(∅) ⊆ D_p(∅). Per la logica degli enunciati e per quella del primo ordine (anche con identità) si dimostra il teorema di completezza, ossia si dimostra che sono semanticamente complete sia in senso speciale che generale. Per tali logiche, tenuto conto anche del teorema di validità, sussiste l’identità: D_p(M) = C(M). Dal teorema d’incompletezza di Gödel segue che, invece, la logica dei predicati del secondo ordine non è semanticamente completa. Lo stesso teorema di Gödel stabilisce che, per teorie formalizzate sufficientemente potenti (come quelle che formalizzano l’aritmetica o l’analisi), vi sono formule che sono vere quando vengono interpretate in maniera standard (e dunque corrispondono a delle verità dell’aritmetica o dell’analisi) ma non sono derivabili dagli assiomi; recentemente sono stati trovati teoremi della pratica matematica in aritmetica che non sono derivabili dagli assiomi della teoria dei numeri nella logica del primo ordine, e anche teoremi della pratica matematica in analisi che non sono derivabili in particolari potenti teorie formalizzate che estendono quella dei numeri naturali. Problema della decisione: una formula H di un linguaggio logico si dice decidibile se e solo se è possibile stabilire in un numero finito di passi se essa è valida oppure no. Tenuto conto del teorema di validità, si vede subito che il metodo delle tavole di verità fornisce un facile procedimento di decisione per quel che riguarda l’ambito del linguaggio della logica degli enunciati. Le cose stanno in tutt’altro modo quando si passa al linguaggio della logica dei predicati. Nel 1936 Church ha dimostrato che già al livello predicativo del primo ordine il problema della decisione non ammette una soluzione generale; solo per alcune classi di formule particolari tale decisione è possibile. Il teorema d’incompletezza di Gödel e questo teorema di Church segnano il fallimento del sogno leibniziano di risolvere meccanicamente ogni disquisizione logica, nonché dello stesso programma formalista di Hilbert.