Logics and discrete mathematics (2011/2012)

Course code
4S000018
Name of lecturer
Andrea Masini
Coordinator
Andrea Masini
Number of ECTS credits allocated
6
Academic sector
INF/01 - INFORMATICS
Language of instruction
Italian
Period
II semestre dal Mar 1, 2012 al Jun 15, 2012.

Lesson timetable

II semestre
Day Time Type Place Note
Tuesday 10:30 AM - 1:30 PM lesson Lecture Hall Gino Tessari  
Wednesday 11:30 AM - 1:30 PM lesson Lecture Hall Gino Tessari  

Learning outcomes

The main objective of this course is the introduction of the fundamental notions of symbolic logic (syntax, semantics, deductive systems) and of discrete mathematics (sets, functions, graphs, trees, structures).

Syllabus

Part 1 (3CFU) Discrete Mathematics

Sets: applications and functions, relations, equivalences, partitions, relation orders, cardinality, finite, denumerable and not denumerable sets, (Cantor's theorem), ordering of the cardinals;
Lattices: the concepts of inf and sup, complete lattices and Boolean lattices, lattices seen as an example of algebraic structures.
Graphs and trees, paths, Eulerian circuits, planar graphs and trees.

Part 2 (3CFU) Logic

Propositional language: propositions and connectives, truth tables, valuations;
Structures: notable examples, monoids, semigroups, natural numbers, graphs;
The language of the first order: Tarski semantics, logical consequence;
Natural Deduction.
Fundamental theorems of natural deduction: soundness (with proof) and completeness (only statement);
First order formalizations of properties.
Algebraic Structures: Sets equipped with an operation (examples: semigroups, monoids, monoids of words, groups, permutations), sets equipped with multiple operations (examples: rings, Boolean algebras). Homomorphisms and isomorphisms of structures.

Reference books
Author Title Publisher Year ISBN Note
Alberto Facchini Algebra e Matematica Discreta (Edizione 1) Edizioni Decibel/Zanichelli 2000 978-8808-09739-2 Studiare: cap 1 (saltando paragrafo 5 e 6) cap 2 (saltando paragrafo 11 ed appendice 14.1)
Andrea Asperti, Agata Ciabattoni Logica a Informatica McGraw-Hill 2007 Srtudiare: Cap 1 (saltando 1.3.6 e 1.3.7) Cap 4 (saltando 4.3.4, 4.3.5 e 4.3.6)
Dirk van Dalen Logic and Structure (Edizione 4) Springer-Verlag 2004 3540208798

Assessment methods and criteria

Written exam

Teaching aids

Documents