Docente/i:   

Denominazione del corso: Istituzioni di logica
Codice del corso: 064143
Corso di laurea: Ingegneria Informatica
Settore scientifico disciplinare: M-FIL/02
Crediti formativi: CFU 5
Sito web del corso: n.d.

Obiettivi formativi specifici

Programma del corso

Le lezioni vengono tenute presso il Collegio Ghislieri. Si veda anche il sito: www.ghislieri.it

Prima parte (30 ore)

• Logica proposizionale. La forma logica del discorso dichiarativo: le operazioni di connessione. Sintassi enunciativa e semantica classica delle valutazioni. Il calcolo delle sequenze di Gentzen. Un algoritmo non-deterministico di ricerca per le derivazioni e sua terminazione.
• Logica elementare: prima parte. La forma logica del discorso dichiarativo: le operazioni di quantificazione. Sintassi dei linguaggi elementari e semantica di Tarski. Il calcolo di Gentzen per i linguaggi elementari. Qualche altro calcolo logico (tavole di Beth, deduzione naturale, sistemi alla Hilbert).
• Complementi: la logica predicativa monadica (applicazione alla logica tradizionale: la teoria del sillogismo).

Seconda parte (30 ore)

• La Logica predicativa: seconda parte. Costruzione dell’albero canonico e completezza delle regole di Gentzen. Compattezza, completezza forte e corollari. Sui rapporti fra logica proposizionale e logica predicativa: il teorema di Herbrand. Cenni alle applicazioni.
• Indecidibilità e dell’incompletezza: una introduzione informale L’analisi del concetto di algoritmo. Un modello formale: le macchine di Turing. L’indecidibiltà della logica elementare (Church). I sistemi assiomatici e i loro limiti deduttivi ed espressivi (teoremi di Goedel e di Tarski).
• Complementi: cenni di logica proposizionale modale (logica modale e incompletezza, logica modale e conoscenza)

Prerequisiti

Tipologia delle attività formative

Lezioni (ore/anno in aula): 60
Esercitazioni (ore/anno in aula): 0
Laboratori (ore/anno in aula): 0
Progetti (ore/anno in aula): 0

Materiale didattico consigliato

I riferimenti bibliografici verranno forniti a lezione.

Modalità di verifica dell'apprendimento