Matteo Basei

Una collezione di piccoli programmi realizzati a scopo didattico.

Storia della logica

La logica è l'arte del logos, del pensiero, del linguaggio.

Gli antichi greci

Talete di Mileto (a cavallo tra il VII e il VI secolo a.C.) è considerato il primo filosofo greco. È il più importante tra i cosiddetti "sette sapienti", considerati dai posteri gli iniziatori della cultura greca. Fa parte della scuola di Mileto insieme a Anassimandro e Anassimene. La ricerca dell'archè, il principio, l'origine. Si abbandonano i miti, le cosmogonie e si inizia a studiare la matematica e l'astronomia. Inizia l'interesse per la ricerca delle dimostrazioni logiche.

Per i Pitagorici (VI secolo a.C.) tutto è numero (intero, razionale).

I Sofisti (V secolo a.C.) si occupano di dialettica e retorica, ma a loro non era ben chiaro nemmeno il concetto di negazione. Non erano interessati alla ricerca della verità, ma allo studio delle tecniche per vincere in una conversazione.

Parmenide di Elea (~527 a.C. - 450 a.C.) fonda la scuola eleatica di cui faranno parte anche Zenone di Elea e Melisso di Samo. Primo ad introdurre il problema dell'Essere (che è e non può non essere).

Zenone di Elea (489 a.C. - 431 a.C.) è famoso per i suoi paradossi. Si ritiene che il più antico paradosso sia il paradosso del mentitore, formulato originariamente da Epimenide di Creta (Cnosso, VII secolo a.C.) nella forma "tutti i Cretesi sono bugiardi", in cui però non c'è alcun paradosso (evidentemente l'affermazione è falsa ed Epimenide è un bugiardo), mentre la formulazione corretta ("io sto mentendo") sembra essere stata formulata successivamente da Eubulide di Mileto (IV secolo a.C.). Zenone sembre quindi essere stato il primo a formulare paradossi, e per di più li utilizzava già per dare quelle che oggi chiamiamo dimostrazioni per assurdo. Il cosiddetto paradosso di "Achille e la tartaruga" ad esempio viene usato per sostenere che il movimento è un'illusione. Resisterà per più di duemila anni e sarà risolto solo grazie alla dimostrazione dell'esistenza di serie convergenti.

Socrate (~470 a.C. - 399 a.C.), a differenza dei Sofisti, che definiva "prostituti della cultura", considerava la filosofia una ricerca senza utilità pratica, per il puro desiderio di conoscenza. Non lascia nulla di scritto della sua filosofia, che è esposta tramite dialoghi, che debbono rimanere aperti perché non vuole mettere la parola fine ai ragionamenti in essi contenuti. Fu maestro di Platone.

Platone (~428 a.C. - ~348 a.C.) principio di non contraddizione Già Platone sottolinea che il verbo essere non può essere assoluto, ma relativo ad un soggetto (intuisce quindi il concetto di predicato), e si rende quindi conto, a differenza di molti venuti ben dopo di lui, che il problema dell'Essere è un non problema (o un problema dialettico e non logico-filosofico). Fu maestro di Aristotele.

Aristotele (~384 a.C. - 322 a.C.) scuola peripatetica primo studio sistematico della logica quantificatori (quadrato delle opposizioni) sillogismi sillogismi modali (con parecchi errori) Nella Metafisica, riflettendo su categorie, predicati e autoreferenza, anticipa in qualche modo il paradosso di Russell.

Euclide (IV - III secolo a.C.) per la prima volta un metodo assiomatico (quindi le verità non sono assolute, ma relative agli assiomi)

Stoici (III secolo a.C.) Completamente dimenticati, li conosciamo solo grazie alla critica di Sesto Empirico. Studio completo dei connettivi con l'utilizzo delle tavole di verità. La logica proposizionale moderna, da Boole in poi, è praticamente identica.

Zenone di Cizio

Crisippo di Soli

Gli scolastici

Filosofi cristiani medioevali. Studiano gli antichi greci. Rielaborano indipendentemente la logica dei connettivi (non conoscendo nulla degli stoici). Introducono lo studio delle cosiddette proprietates terminorum, che sono i primi germi della logica dei predicati. Si concentrano però principalmente sui rapporti tra fede e ragione.

Anselmo d'Aosta (~1033 - 1109) Prova ontologica (poi ripresa da Tommaso d'Aquino, Cartesio, Kant e infine Godel).

Pietro Abelardo (1079 - 1142) dialettica, riscopre la logica proposizionale degli stoici

Tommaso d'Aquino (1225 - 1274)

Giovanni Duns Scoto (~1265 - 1308) paradosso dei punti di due circonferenze

Guglielmo di Ockham (1288 - 1347) Rasoio di Ockham “è futile fare con più mezzi ciò che si può fare con meno”

Il metodo scientifico

Galileo Galilei (1564 - 1642) paradosso dei quadrati perfetti

Cartesio (1596 - 1650) celebre per il suo "cogito ergo sum" (penso quindi sono) "dubium sapientiae initium" (il dubbio è l'origine della saggezza). Grazie ai suoi lavori sul sistema di riferimento che ora porta il suo nome (anticipato da Nicola d'Oresme e sviluppato indipendentemente anche da Fermat) ci mostra come il pensiero pitagorico (tutto è numero) e quello di Euclide (tutto è geometria) sono in realtà due facce della stessa medaglia.

Gottfried Wilhelm von Leibniz (1646 - 1716) che insieme a Newton ha iniziato lo sviluppo del calcolo infinitesimale, pur non avendo dato alcun contributo specifico alla logica, ha ispirato i logici e i matematici da Boole fino a Hilbert. Con il suo Trattato sull'arte combinatoria del 1666 cerca di sviluppare un linguaggio universale simbolico per tradurre in formula ogni problema. Le verità logiche sono verità in tutti i mondi possibili (anticipa il concetto moderno di tautologia).

La logica matematica

George Boole (1815 - 1864) nel 1847 pubblica L'analisi matematica della logica: not A = 1 - A A and B = A * B generalizzate per 2^n elementi. I connettivi degli stoici e i sillogismi dei peripatetici non sono teorie contrapposte, ma le stesse regole applicate ai connettivi e ai quantificatori. Pone le basi per la logica matematica e sviluppa idee che successivamente saranno largamente utilizzate in probabilità, elettronica digitale e informatica.

Augustus De Morgan (1806 - 1871) 1847 - Formal Logic Leggi di De Morgan not (A or B) = (not A) and (not B) not (A and B) = (not A) or (not B) Algebra delle relazioni (su cui torneranno poi Peirce, Schroder e Tarski) i sillogismi possono essere espressi con il linguaggio delle relazioni

Charles Sanders Peirce (1839 - 1914)

Friedrich Wilhelm Karl Ernst Schröder (1841 - 1902)

Julius Wilhelm Richard Dedekind (1831 - 1916)

Georg Ferdinand Ludwig Philipp Cantor (1845 - 1918) Insieme a Dedekind chiude il cerchio Pitagora - Euclide - Cartesio riconducendo i numeri reali all'aritmetica (quindi i pitagorici in un certo senso avevano ragione, mancava loro il concetto di infinito). Anticipa il paradosso di Russell in una lettera a Dedekind.

Giuseppe Peano (1858 - 1932) linguaggio della logica Anticipa il paradosso di Russell in una lettera a Hilbert.

David Hilbert (1862 - 1943) Grande matematico che insegue il sogno logicista di Leibniz. 1899 - Grundlagen der Geometrie riscrive in modo rigoroso gli Elementi di Euclide 1900 - Il secondo dei 23 problemi era la consistenza dell'aritmetica. 1928 - Entscheidungsproblem (risolto poi da Turing e Church)

Luitzen Brouwer Logica intuizionista (le dimostrazioni di esistenza come il teorema della base di Hilbert non sono accettate).

Gottlob Frege (1848 - 1925) Considerato tra i più grandi logici di tutti i tempi insieme ad Aristotele e Godel. Studia la logica delle relazioni (predicati a più variabili) che estendono e rendono obsoleti i sillogismi di Aristotele. Nel 1879 pubblica l'Ideografia (Begriffsschrift). Analisi assiomatica che poi Godel dimostra essere completa. 1884 - Die Grundlagen der Arithmetik

Bertrand Russell (1872 - 1970) cercando di fondare la matematica sulla pura logica attraverso la teoria degli insiemi giunge nel 1901 al paradosso che ora porta il suo nome (il celeberrimo paradosso di Russell, appunto), infrangendo il sogno di Frege. Scopre che gli assiomi di comprensione non ristretta portano all'insieme degli insiemi che non appartengono a se stessi che è contraddittorio, quindi la teoria degli insiemi, e di conseguenza la matematica, non può essere derivata a partire dalla pura logica. Nel 1910, insieme a Alfred North Whitehead, pubblica il primo volume dei Principia Mathematica, in cui gli autori aggirano il problema con l'artificiosa teoria dei tipi: gli elementi di un insieme sono tipi di livello inferiore rispetto all'insieme stesso. Insiemi di livello differente non possono mischiarsi.

Ludwig Wittgenstein (1889 - 1951) Allievo di Russell che successivamente si discosta dalle sue idee (solo apparentemente in realtà, vedi Post). 1921 - Tractatus Logico-Philosophicus Introduce le tabelle di verità (giù usate però a quanto pare addirittura dagli stoici e comunque introdotte indipendentemente anche da Peirce e Post). Le tautologie (formule proposizionali sempre vere indipendentemente dai valori di verità delle proposizioni che contengono).

Emil Post (1897 - 1954), nella sua tesi di laurea del 1921 (lo stesso anno in cui Wittgenstein pubblica il suo Tractatus), dimostra che nella logica proposizionale, e in particolare nei Principia Mathematica, tutte le tautologie sono dimostrabili (quindi un teorema di completezza per la logica proposizionale). In altre parole i punti di vista contrapposti di Russell (fondare la logica sulla dimostrabilità sintattica) e Wittgenstein (fondarla sulla verità semantica) sono in realtà equivalenti. Introduce indipendentemente da Wittgenstein le tabelle di verità.

La logica moderna

Kurt Godel (1906 - 1978) va oltre e, sempre nella sua tesi di laurea, questa volta nel 1929, dimostra il teorema di completezza per la logica dei predicati: anche nella logica dei predicati tutte le verità sono dimostrabili (quindi equivalenza sintassi-semantica anche per i predicati). Nel 1930 pubblica i due teoremi di incompletezza di Godel. Primo teorema: se un sistema assiomatico contenente l'aritmetica è consistente allora è incompleto. Secondo teorema: un sistema assiomatico contenente l'aritmetica non può provare la propria consistenza. Se Russell aveva infranto il sogno di ricondurre la matematica alla logica attraverso la teoria ingenua degli insiemi, Godel mette definitivamente fine al più ampio sogno di ricondurre in qualche modo la matematica alla pura logica.

Jan Lukasiewicz (1878 - 1956) Studio formale dei sillogismi. Logica a più valori.

Stephen Cole Kleene (1909 - 1994) Star di Kleene: se A è un insieme di simboli, A* sono tutte le parole finite costruibili con tale alfabeto. Espressioni regolari: inventate per descrivere i neuroni artificiali di McCulloch-Pitts.

Clarence Irving Lewis (1883 - 1964) 1932 - Symbolic Logic Logica modale.

Alfred Tarski (1902 - 1983) Nel 1934 da la definizione di verità di un linguaggio attraverso un meta linguaggio. Nel 1936 utilizzando gli strumenti introdotti da Godel dimostra il teorema di indefinibilità di Tarski: un sistema assiomatico contenente l'aritmetica non può definire la propria verità, cioè in esso non può esistere una formula ben formata T(g(x)) vera se e solo se x è vera. Risolve quindi il paradosso del mentitore (un linguaggio non può parlare della propria verità).

Alonzo Church (1903 - 1995) Nel 1936 formula il lambda calcolo, equivalente alla macchina di Turing, che ispirerà la programmazione funzionale.

Alan Turing (1912 - 1954) Insieme a Chruch fonda la teoria della computabilità. Nel 1936 pubblica On Computable Numbers, with an Application to the Entscheidungsproblem in cui introduce la macchina di Turing e risolve negativamente l'Entscheidungsproblem. La logica proposizionale è completa e decidibile, mentre la logica predicativa è completa, ma non decidibile.

Noam Chomsky (1928) Grammatica generativa. Gerarchia di Chomsky (macchine di Turing, automi a pila, automi a stati finiti, espressioni regolari).

Saul Kripke (1940) Riprende l'idea dei mondi possibili di Leibniz e introduce la semantica relazionale per la logica modale.