Matematica | Università di Parma

LOGICA MATEMATICA
cod. 00662

Docente

Settore scientifico disciplinare

Logica matematica (MAT/01)

Field

A scelta dello studente

Tipologia attività formativa

A scelta dello studente

56 ore
di attività frontali

6 crediti

sede: PARMA

insegnamento
in - - -

Obiettivi formativi

Nozioni di base di logica del primo ordine

Prerequisiti

Nozioni di bse di algebra e di programmazione

Contenuti dell'insegnamento

Corso isitituzionale di Logica Matematica.

Calcolo proposizionale, logica del primo ordine, ricorsivita' e calcolabilita', teoremi di incompletezza.

Programma esteso

1) Calcolo proposizionale:
Formule proposizionali, valutazioni Booleane; teorema di compattezza, forme
normali, formule come funzioni Booleane.

2)Logica del Primo Ordine:
Strutture, termini, formule, modelli; omomorfismi; espansioni del linguaggio,
sostituzione; esempi di teorie; insiemi definibili.

3) Deduzione e completezza:
Regole di deduzione; teorema di completezza (lemma di Lindembaum, costanti di
Henkin); teoremi di compattezza e di Lowenheim-Skolem; esempi di teorie complete; classi elementari

4) Ricorsione
Funzioni e insiemi ricorsivi; codifiche di tuple; insiemi ricorsivamente enumerabili; teorema di Post; quantificatori limitati; insiemi aritmetici

5) Computabilità
Macchine di Turing (cenni);
macchine a registri di memoria; tesi di Church per MRM; MRM universale;

6) Decidibilità
Codifiche di formule, chiusura deduttiva di una teoria, teorie decidibili; esempi di teorie decidibili

7) Indecidibilità
Teorema di Tarski sulla non-definibilità della verità aritmetica; teoria Q di Robinson; rappresentabilità in Q; primo teorema di Godel;
assiomi di Peano al primo ordine; secondo teorema di Godel.

Bibliografia

Note del corso

Note del corso di A. Berarducci

Toffalori-Cintioli "Logica Matematica" McGraw-Hill (2000)

Metodi didattici

Lezioni frontali

Modalità verifica apprendimento

Esame orale

LOGICA MATEMATICA cod. 00662