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