Sintassi e Semantica della logica del primo ordine. Completezza e decidibilità di teorie. Eliminazione dei quantificatori. Teoria dei modelli finiti. Esprimibilità e non-esprimibilità di queries su database relazionali. Giochi di Ehrenfeucht-Fraissé. Completezza della logica del primo ordine. Teorema di Compattezza. Assiomatizzabilità e non assiomatizzabilità. Ultrafiltri e ultraprodotti. Teoremi di Incompletezza di Godel. Logica modale e logica della dimostrabilità. Modelli di Kripke. Cut-elimination. Gerarchia Aritmetica e gradi di insolubilità algoritmica. Teorema di Post. Analisi del contenuto algoritmico di teoremi di combinatoria. Complessità descrittiva: Teorema di Fagin.

Non vi è un manuale di riferimento. Il docente fornisce dispense dettagliate di tutti gli argomenti affrontati.

Sintassi e Semantica della logica del primo ordine. Completezza e decidibilità di teorie. Eliminazione dei quantificatori. Teoria dei modelli finiti. Esprimibilità e non-esprimibilità di queries su database relazionali. Giochi di Ehrenfeucht-Fraissé. Completezza della logica del primo ordine. Teorema di Compattezza. Assiomatizzabilità e non assiomatizzabilità. Ultrafiltri e ultraprodotti. Teoremi di Incompletezza di Godel. Logica modale e logica della dimostrabilità. Modelli di Kripke. Cut-elimination. Gerarchia Aritmetica e gradi di insolubilità algoritmica. Teorema di Post. Analisi del contenuto algoritmico di teoremi di combinatoria. Complessità descrittiva: Teorema di Fagin.

Non vi è un manuale di riferimento. Il docente fornisce dispense dettagliate di tutti gli argomenti affrontati.