ITALIANO

Il corso si propone di introdurre lo studente alle nozioni fondamentali della Logica Matematica, come linguaggio formale del calcolo proposizionale e del calcolo dei predicati e i relativi sistemi formali per deduzioni. Verranno studiate strutture a primo ordine e nozioni di base di computabilità

- P. Cintioli e C. Toffalori, Logica Matematica, McGraw-Hill
- Mordechai Ben-Ari, Mathematical Logic for Computer Scientists, Springer
-D. van Dalen, Logic and Structures, Springer

Lo studente dovrà essere in grado di applicare le tecniche apprese nello studio di problemi elementari quali: formalizzazione di enunciati matematici in un linguaggio del primo ordine, dimostrazioni formali di enunciati, confronto tra strutture al primo ordine, uso della definibilità in strutture algebriche.
Lo studente dovrà mostrare anche di essere in grado di riconoscere quando una data funzione è effettivamente calcolabile

Algebra 1

Lezioni frontali. Saranno inoltre assegnati esercizi che lo studente dovrà risolvere e verranno discussi in aula.

Prova scritta e orale

Calcolo proposizionale: linguaggio, connettivi e formule. Valutazioni, formule soddisfacibili, tautologie, contraddizioni. Formule logicamente equivalenti. Insieme di formule soddisfacibile, conseguenza logica. Forme normali congiuntive e disgiuntive. Insieme adeguato di connettivi.
Tableaux semantici: completezza e validità. Teorema di compattezza con applicazione alla teoria dei grafi. Deduzione naturale, regole deduttive. Completezza e validità. Insiemi di formule inconsistenti.
Calcolo dei predicati: linguaggio, termini e formule. Strutture al primo ordine. Soddisfacibilità. Teorema di coincidenza. Soddisfacibilità di una formula in una struttura, formule vere in una struttura e formule logicamente valide. Conseguenza logica. Formule logicamente equivalenti. Strutture elementarmente equivalenti, strutture isomorfe. Omomorfismi, monomorfismi e isomorfismi tra strutture. Insiemi definibili in una struttura. Isomorfismi e insiemi definibili.
Sottostruttura elementare. Test di Tarski-Vaught (senza dimostrazione) e applicazione alle strutture ordinate dei razionali e dei reali. Tableaux semantici per il calcolo dei predicati. Deduzione naturale. Teorema di completezza (senza dimostrazione). Teorema di compattezza ed alcune applicazioni.
Computabilità: funzioni parziali ricorsive, tesi di Church. Macchine di Turing, tesi di Turing. Insiemi ricorsivi, insiemi ricorsivamente enumerabili. Problema della fermata. Alcuni problemi non decidibili

Italian

Fundamental notions of mathematical logic, as formal languages for propositional calculus and predicate calculus, and their formal deductive systems. First order structures. Introduction to computability.

- P. Cintioli e C. Toffalori, Logica Matematica, McGraw-Hill
- Mordechai Ben-Ari, Mathematical Logic for Computer Scientists, Springer
-D. van Dalen, Logic and Structures, Springer

Students will be able to apply the basic techniques of mathematical logic, such as formalize notions in propositional calculus language and in the predicate calculus language, construct formal proofs in the natural deduction system. They will be able to use the notion of definable set in order to analyze first order structures. Students will be able to recognize computable functions and distinguish computable sets from computable enumerable sets.

Basic notions of a first course in algebra

Lectures will be delivered in class. Students will be given homework exercises whose solutions which will be discussed in class.

Written and oral exam

Syntax of propositional calculus: Language, connectives, and formulas. Truth functions and truth table. Tautologies and contradictions. Adequate sets of connectives.Logically equivalent formulas. Semantic consequence. Disjunctive normal form and conjunctive normal form. Semantic tableaux for propositional logic: soundness and completeness.Compactness theorem and application to graph theory. Natural deduction for propositional logic, deductive rules. Soundness and completeness. Syntax of predicate calculus: language, terms and formulas. First order structures. Satisfiability in a structure. Truth, and semantic consequence. Elementary equivalent structures. Omomorphisms and isomorphisms of first order structures. Definable sets. Elementary substructures. Semantic tableaux for predicate calculus: soundness and completeness. Natural deduction for predicate calculus. Compactness theorem and non standard models of the reals and of the natural numbers. Computability: primitive computable functions, Ackermann function, partial recursive functions. Church thesis. Turing machines and Turing thesis. Computable sets and recursively computable sets (c.e.). Algebra of recursive sets. Relations between computable sets and c.e. sets. Halting problem.