mail unicampaniaunicampania webcerca

    Paola D'AQUINO

    Insegnamento di LOGICA MATEMATICA

    Corso di laurea magistrale in MATEMATICA

    SSD: MAT/01

    CFU: 8,00

    ORE PER UNITÀ DIDATTICA: 64,00

    Periodo di Erogazione: Secondo Semestre

    Italiano

    Lingua di insegnamento

    ITALIANO

    Contenuti

    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à

    Testi di riferimento

    - 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

    Obiettivi formativi

    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

    Prerequisiti

    Algebra 1

    Metodologie didattiche

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

    Metodi di valutazione

    Prova scritta e orale

    Programma del corso

    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

    English

    Teaching language

    Italian

    Contents

    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.

    Textbook and course materials

    - 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

    Course objectives

    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.

    Prerequisites

    Basic notions of a first course in algebra

    Teaching methods

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

    Evaluation methods

    Written and oral exam

    Course Syllabus

    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.

    facebook logoinstagram buttonyoutube logotype