
Risorsa bibliografica obbligatoria 

Risorsa bibliografica facoltativa 

Anno Accademico

2017/2018

Scuola

Scuola di Ingegneria Industriale e dell'Informazione 
Insegnamento

080931  ALGEBRA AND MATHEMATICAL LOGIC

Docente 
Mauri Luca

Cfu 
5.00

Tipo insegnamento

Monodisciplinare

Corso di Studi 
Codice Piano di Studio preventivamente approvato 
Da (compreso) 
A (escluso) 
Insegnamento 
Ing Ind  Inf (Mag.)(ord. 270)  MI (481) COMPUTER SCIENCE AND ENGINEERING  INGEGNERIA INFORMATICA  *  A  ZZZZ  080931  ALGEBRA AND MATHEMATICAL LOGIC 
Programma dettagliato e risultati di apprendimento attesi 
This is an introductory course in logic, focusing on the basic techniques and theorems of first order logic and on some of their applications. It is also meant to provide sound foundations for the use of formal languages both in mathematics and computer science and to lay the ground for more advanced courses in logic. Along the way, algebraic concepts will be introduce as instrumental to the development of Tarski's semantics of first order logic and in order to provide interesting models of theories. Lab sessions will be used to present a theorem prover and to discuss its use in the automation of proofs. By the end of the course the student should be able to formalize simple reasonings from mathematics and natural language into the language of first order logic and to check their correctness by logical means, both manually and with the help of software.There is no logic prerequisite for this course. Nevertheless, knowledge of linear algebra from geometry courses and of elementary set theory from analysis courses is strongly recommended as it will be needed when working with examples of algebraic structures.
Topics
 Propositional logic. The language of propositional logic: variables, connectives, formulas. Semantics: evaluations, truth tables, models, satisfiability. Semantic equivalence. Normal forms. Syntax: deductive systems, axioms, theorems. The Hilbert deductive system for PL. Soundness and completeness. Resolution for PL.
 Relations and functions. Relations, operations with relations, representation by graphs and incidence matrices, closure operators. Equivalence relations and quotient sets. Order relations, posets, lattices. Functions, invertibility of functions, isomorphism theorems and factorizations. Cardinalities: definition, characterization of infinite sets, Cantor's theorem. Operations.
 First order logic. First order languages: variables, function and predicate symbols, terms, atomic formulas, formulas. Free and bound variables. Semantics: interpretations, models, satisfiability, validity. Prenex form. Skolemization. Resolutionfor first order logic: substitution, unification. Soundness and completeness. The Hilbert system for first order logic. First order theories: theories, theories with equality, algebraic theories, models.
 Algebraic structures. Internal operations, neutral elements, associativity, commutativity. Algebraic structures: semigroups, monoids, groups, abelian groups, rings, fields, skew fields. Morphisms of structures. Substructures. Congruence relations on a structure and quotients. Modular arithmetic. Morphisms of structures and their factorization. Normal subgrups and ideals. Boolean algebras.

Note Sulla Modalità di valutazione 
Students will have to take a written exam to earn a pass grade; the exam may comprise both exercises and theoretical questions. There will also be an opportunity, for students regularly attending the course, to write classworks for each section of the course which, when fully completed as indicated by the lecturer, will contribute significantly toward the final grade.

A. Cherubini. Lecture notes https://beep.metid.polimi.it Note:Available from the course page on the Beep platform
Exercises beep.metid.polimi.it Note:Available from the course page on the Beep platform
M. Fitting, First order logic and automated theorem proving
S. Hedman, A first course in logic
E. Mendelson, Introduction to mathematical logic
M. Machover, Set theory, logic and their limitations
K. Rosen, Discrete mathematics and its applications
M. BenAri, Mathematical logic for computer science
D. van Dalen, Logic and structure

Tipo Forma Didattica

Ore didattiche 
lezione

32.0

esercitazione

16.0

laboratorio informatico

4.0

laboratorio sperimentale

0.0

progetto

0.0

laboratorio di progetto

0.0

Informazioni in lingua inglese a supporto dell'internazionalizzazione 
Insegnamento erogato in lingua
Inglese

Disponibilità di materiale didattico/slides in lingua inglese

Disponibilità di libri di testo/bibliografia in lingua inglese

Possibilità di sostenere l'esame in lingua inglese

Disponibilità di supporto didattico in lingua inglese

