Logics and discrete mathematics
Scientific Disciplinary Sector (SSD)
INF/01 - INFORMATICS
II semestre dal Mar 1, 2011 al Jun 15, 2011.
Introduction to fundamental notions of symbolic logic (syntax, semantics, language and meta-language, deductive system, structures and representations) and of constitutive and enumerative principles of fundamentals discrete structures (sets, multisets, sequences, trees, graphs, structural induction and enumeration methods).
Sets and operations. Compositions, iterations, closures, and extensions of operations. Discreteness, incommensurability, continuity, and approximation. Measures and number notations. Mathematical induction. Trees, graphs, variables, and expressions. Patterns, tags and mark-up notations. Finite structures and hyper-structures. Structural induction. Allocations, combinations, and partitions. Factorials and binomials. Numbers of Stirling, Catalan, and Bell. Recurrent relations and enumerations of fundamental finite structures. Stirling approximation.
Propositions and propositional compactness. Predicate logic: quantifiers, syntax and semantics of first-order logic. Examples of first order theories. Deductive systems (introduction at least of one of the following systems: natural deduction, sequent calculus, tableaux). Theorems of soundness, compactness and Loewenheim-Skolem theorem. First order formalization within mathematical structures. Peano arithmetics. Statement of the incompleteness theorem.
Periodic assignments. Midterm and final written exams.