B006803 - DISCRETE MATHEMATICS AND MATHEMATICAL LOGICS

Italian

Elements of set theory. Functions, relations, mathematical induction. Elements of combinatorics. Partially ordered sets, lattices and Boolean algebras. Elements of number theory. Modular arithmetic and applications to cryptography. Elements of graph theory. Formulas-semantics. The “normal form theorem”. Solving method. Predicate logic.

Teachers’ notes available on the course webpage. (UniFi e-Learning platform)

Knowledge acquired: The course aims to increase the student’s understanding of mathematical ideas and encourage an attitude for abstract thought. Moreover we want to emphasize the importance of a correct mathematical notation in scientific arguments. The student will improve his mathematical knowledge developing his skills in mathematical language.Competence acquired: At the end of the course the student will acquire basic abilities in discrete mathematics and logic, as specified in the course programme. Moreover, he will acquire experience and know-how in order to solve combinatoric, arithmetical and logic problems.Skills acquired (at the end of the course): At the end of the course the students will be able to: appropriately state in a suitable language the acquired notions; solve numerical problems either directly or setting up algorithms to be implemented on computing machines; develop simple proofs in a direct approach, or by way of contradiction and/or by induction; manipulate logical expressions.

Courses to be used as requirements (required and/or recommended)Courses required: NoneCourses recommended: None

CFU: 9Total hours of the course (including the time spent in attending lectures, seminars, private study, examinations, etc...): 234Hours reserved to private study and other individual formative activities: 150Contact hours for: Lectures (hours): 80Contact hours for: Laboratory (hours): 0Contact hours for: Laboratory-field/practice (hours): 0Seminars (hours): 0Stages: 0Hours reserved to intermediate examinations: 4

Frequency of lectures, practice and lab: RecommendedTeaching Tools: UniFi e-Learning: http://e-l.unifi.itOffice Hours: Prof. Marco BarlottiTuesdays, from 4:00 to 6:00 p.m.;Tuesdays, from 3:30 to 5:30 p.m.;Via delle Pandette, 9 - 50127 Firenze Tel. (+39)0554374669;Fax (+39)0554374913 E-mail: marco.barlotti@dmd.unifi.it

Written and Oral

Set theory. Applications. Cardinality. Basic combinatorics: combinations and dispositions, with and without repetition.Permutations: decomposition as a product of disjoint cycles and as a product of transpositions.Elements of Number Theory: mathematical induction, recursive functions, greatest common divisor, Euclidean algorithm. b-adic representations. Diofantine equations and modular arithmetic. Applications to cryptography. Equivalence and order relations. Lattices. Boolean algebras.Elements of graph theory. Propositional logic: formulas, evaluations, tautologies. Resolution method: decomposition theorem, Davis-Putnam rules, soundness and completeness theorem. Predicate logic. Prenex form theorem, Skolem’s theorem, Herbrand universe, Herbrand’s theorem.