Logics and discrete mathematics (2011/2012)

Course code
Name of lecturer
Andrea Masini
Andrea Masini
Number of ECTS credits allocated
Academic sector
Language of instruction
II semestre dal Mar 1, 2012 al Jun 15, 2012.

Lesson timetable

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).


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