ITALIANO

Il corso si propone di introdurre lo studente alle nozioni fondamentali della Logica Matematica, come linguaggi formali e i relativi sistemi deduttivi. 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, essere padrone delle nozioni di base di computabilità

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

The course is an introduction to the fundamental notions of mathematical logic, as formal languages and their deductive systems. First order structures and basic notions in computability will be presented.

- 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 formalizing notions in first order logic, construct formal proofs in the natural deduction system, analyzing first order structures, and master the basic notions in computability.

Basic notions of a first course in algebra

Lectures will be delivered in class. Students will be assigned exercises to solve and the solutions 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.