204SM - LOGICA 2020
Section outline
-
-
Questa dispensa termina con una breve esposizione sul calcolo delle relazioni diadiche, del quale vengono esposti: sintassi e semantica dei predicati, e da ultimo l'apparato deduttivo.
-
Qui, rispetto alla presentazione che precede, ci sono in piú: la definizione di logica booleana, un apparato deduttivo per il calcolo proposizionale, un apparato deduttivo per il calcolo delle relazioni diadiche.
-
-
Dalle due logiche presentate questa settimana passeremo alle logiche booleane. Quella proposizionale sarà il primo esempio di logica booleana, un concetto non ancora introdotto ma che entrerà in gioco molto presto.
-
Ci rifacciamo qui a un'esposizione assiomatica della logica proposizionale, desunta da un classico della logica di Alonzo Church. La parte di questi lucidi che riguarda la sintesi di circuiti va oltre il programma di quest'anno.
-
Viene completata qui un'esposizione della logica delle relazioni diadiche, della quale la settimana scorsa era stata presentata la semantica, alla luce della quale la nozione di derivabilità che verrà qui introdotta risulta piú chiara. Però la derivabilità qui introdotta non cattura appieno la consequenzialità logica introdotta per via semantica.
-
-
-
Esercizio: Il calcolo delle relazioni diadiche (o 'mappe') visto di recente ricade sotto la caratterizzazione di logica booleana presentato questa settimana?
Altro esercizio: Dimostrare il teorema di Lindenbaum senza far uso dell'ipotesi di comodo che l'insieme degli enunciati possa essere disposto in una successione. Serve, per questa dimostrazione piú generale, ricorrere al lemma di Zorn (lo conoscete?)
-
-
-
Si tratta per lo piú di esercizi che già comparivano nell'introduzione al 10.o problema di Hilbert riportata qui sopra; ma ce ne sono anche alcuni di nuovi.
-
Con una simile tecnica di riduzione, anche il problema della soddisfacibilità di enunciati della logica proposizionale (scritti impiegando liberamente tutti i connettivi usuali --- negazione, congiunzione, disgiunzione, implicazione materiale, biimplicazione) può venir ricondotto al problema della soddisfacibilità di enunciati scritti in forma 3CNF (congiunzioni di disgiunzioni di letterali, con esattamente tre letterali in ciascuna delle disgiunzioni).
-
(30/03/2021 h.9/11) Completamento dell'esposizione sulle logiche booleane: Logiche booleane minimali
-
Di questi esercizi i primi due sono *forse* impegnativi, ma il terzo è facilmente abbordabile.
Il nuovo esercizio che vi propongo riguarda, piú in generale, le logiche booleane: Stabilire se la logica algebrica delle relazioni diadiche (versione assiomatica) sia atteggiabile a logica booleana, ossia se essa soddisfi---definiti opportunamente, in essa, il falso e l'implicazione---il principio di deduzione e il principio di doppia negazione?
-
-
La famiglia degli insiemi diofantei esponenziali è forse piú ricca di quella degli insiemi diofantei polinomiali?
-
(13/04/2021 h.9--11; 14/04/2021 h.11-13) Funzioni ricorsive primitive e funzioni ricorsive generali. Loro rispettive specifiche tramite: (1) formule aritmetiche; (2) clausole di Horn
Il punto (1) viene esposto nella presentazione "D vs E" riportata sotto la lezione del 31 marzo, che qui sotto complementiamo con una breve rivisitazione del teorema cinese.
-
Ecco qui una dispensetta che collega il teorema cinese dei resti nella sua formulazione originaria al suo riadattamento di (Gödel e) Davis ai fini della rappresentazione aritmetica delle funzioni ricorsive primitive.
-
Una dispensetta di 2 o 3 pagine, che integra quanto già riportato nei lucidi "D vs E" della lezione del 31 marzo
-
Presentazione sulla specifica di funzioni ricorsive generali tramite clausole di Horn
-
Si tratta di un universo di Herbrand, il piú semplice fra quelli infiniti
-
Una dispensetta che ricalca fedelmente quanto visto nella presentazione che precede, ma di cui può tornarvi utile soprattutto il riepilogo sinottico riportato alla fine (pag.5).
-
-
Cinque presentazioni sono riportate qui sotto. Di queste, le prime tre curano tre aspetti che usualmente caratterizzano un sistema logico-formale:
- sintassi del linguaggio simbolico (non si tratta in verità di un linguaggio solo, ma di uno schema di linguaggio);
- semantica del linguaggio;
- armamentario deduttivo, che dota il linguaggio di un 'calcolo'.
La quarta presentazione propone alcuni esempi di teoria assiomatica basati su linguaggi predicativi del prim'ordine.
La quinta presentazione svolge alcuni esercizi riguardanti la logica del prim'ordine.
Dell'apparato deduttivo non parliamo ancora, nelle lezioni di questa settimana.
-
- tautologie: riguardano la logica minima (contenuta in qualsiasi logica booleana---e, come verificheremo, la logica predicativa dotata del suo calcolo è booleana);
- formule direttamente riconoscibili come valide ai sensi del calcolo predicativo del primo ordine;
- formule riconoscibili come valide nel quadro degli assiomi propri di una teoria.
-
(27/04/21 h.9--11; 28/04/21 h.11-13) Calcolo predicativo e teorema di deduzione. Espansioni di Henkin, Skolemizzazione, Universi di Herbrand.
Queste lezioni si basano principalmente sulla presentazione del *calcolo* predicativo del 1.o ordine caricata in questa pagina Moodle assieme al materiale della settimana scorsa.
-
(4/05/21 h.9--11; 5/05/21 h.11--13) Espansioni di Henkin, Universi di Herbrand, Teorema di completezza per il calcolo predicativo del 1.o ordine (senza uguaglianza). La nozione di enumerabilità ricorsiva.
Restiamo ancoràti alla presentazione del *calcolo* predicativo del 1.o ordine caricata in questa pagina Moodle assieme al materiale di due settimane fa.
-
...che porta alla dimostrazione che vi sono insiemi elencabili non decidibili
-
-
Per stabilire che ogni insieme ricorsivamente enumerabile ammette una specifica diofantea esponenziale, ci rifacciamo alla dimostrazione di Matiyasevich--Jones che migliora il risultato originale di Davis--Putnam--Robinson dotando la rappresentazione diofantea esponenziale della proprietà di single-foldness.
-
Trovando, nel 1970, una specifica diofantea polinomiale di una relazione a crescita esponenziale, Yuri Matiyasevich stabiliva (grazie a un risultato di Julia Robinson di una ventina d'anni prima) che la stessa esponenziazione ammetteva una definizione esistenziale diofantea.
Pertanto, grazie al teorema DPR che abbiamo visto la settimana scorsa, otteniamo che qualsiasi insieme enumerabile ricorsivamente è diofanteo polinomiale. Questo risultato, che rafforza DPR, viene chiamato teorema DPRM.
Il risultato di Matiyasevich sfruttava come relazione a crescita esponenziale una relazione legata alla progressione di Fibonacci; però, subito, molti autori sostituirono a tale relazione un'altra legata alle soluzioni nei naturali di un'equazione di Pell della forma X^2=(a^2-1) Y^2+1 ove a è un intero >1. Questa presentazione alternativa fu seguita da molti autori sia statunitensi che sovietici e da ultimo fu impiegata da Julia Robinson e Yuri Matiyasevich in un articolo del 1975, cui si rifà la presentazione riportata qui sotto.
-
(25/05/2021 h.9--10:15) Il teorema di Matiyasevich (completamento della presentazione della settimana scorsa); gödelizzazione del calcolo proposizionale
Per quanto riguarda il completamento della presentazione sul 10.o problema di Matiyasevich, ci si rifà al materiale della settimana scorsa. Nuova la dispensa sulla gödelizzazione (ossia: aritmetizzazione) del calcolo proposizionale.