Logics and discrete mathematics (2010/2011)

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

Lesson timetable

Learning outcomes

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

Syllabus

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.

Assessment methods and criteria

Periodic assignments. Midterm and final written exams.