Elements of set theory. Mathematical induction. Relations. Maps. Permutations. Posets, lattices. The Euclidean algorithm. Modular arithmetic and applications to cryptography. Cardinality. Elements of combinatorics: the pigeonhole principle, Hall’s marriage theorem, arrangements, combinations.
Graph theory: bipartite graphs, planar graphs, Eulerian graphs, Hamiltonian graphs. Colourings. Propositional logic: formulas, confutations. First order logic: prenex normal form, Skolem form.
Marco Barlotti - Appunti di Algebra.
Marco Barlotti - Appunti di Teoria dei Grafi.
Marco Barlotti - Appunti di Logica.
These textbooks are freely downloadable from:
https://e-l.unifi.it/course/view.php?id=5066
Learning Objectives
The course aims to increase the student’s understanding of mathematical ideas and to encourage an attitude for abstract thought. Moreover we want to emphasize the importance of a correct mathematical notation in scientific arguments.
At the end of the course the student should have acquired the following basic knowledges:
(1) familiarity with the language of set theory;
(2) knowledge of the arithmetical properties of the set of naturals, specifically the ability to carry out sums, products and euclidean divisions and to verify the relations called "less or equal" and "divides";
(3) familiarity with the arithmetic of residues modulo any positive integer and knowledge of certain diophantine equations;
(4) knowledge of the fundamental problems of elementary combinatorics and of some related solving techniques (principle of addition, principle of multiplication, pigeonhole principle, marriage theorem);
(5) knowledge of the most elementary notions of graph theory (planarity, connession) and of some classifications (such as the definition of Eulerian graphs and of Hamiltonian graphs);
(6) knowledge of the basic principles of propositional logic and of first order logic;
(7) familiarity with refutation techniques and in particular with the Davis-Putnam resolution algorithm.
At the end of the course, moreover, the student should have acquired the following basic abilities:
(1) to state correctly, with an adequate language, the notions he learned;
(2) to develop simple proofs (by induction, by contradiction, or by applying certain mathematical principles);
(3) to calculate the gratest common divisor of two natural number by applying Euclid's algorithm;
(4) to calculate the least common multiple of two natural numbers;
(5) to solve linear diophantine equations in two unknowns;
(6) to apply Euler's theorem to the study and to the solution of certain exponential equations;
(7) to express a natural number in different bases;
(8) to apply some divisibility criterions in different bases;
(9) to evaluate the cardinality of a finite set via the principle of addition and/or the principle of multiplication, whichever applies;
(10) to verify the non-planarity of a finite graph by applying the relevant necessary conditions;
(11) to verify whether a given finite graph is Eulerian;
(12) to verify, in certain particular instances, whether a given finite graph is Hamiltonian;
(13) to describe the dual graph of a given finite plane graph;
(14) to convert a formula of propositional logic to a logically equivalent one which is in conjunctive normal form;
(15) to decide whether a formula of propositional logic is satisfiable;
(16) to convert a formula of first order logic to a logically equivalent one which is in prenex normal form;
(17) to convert a formula of first order logic to another one which is in Skolem form and is satisfiable if and only if the former one is satisfiable;
(18) to decide, in some particular cases, whether a formula of first order logic is satisfiable;
(19) to solve simple logical problems by translating them to appropriate logic formulas.
Prerequisites
None.
Teaching Methods
The course consists in lectures and training sessions, both given by the same teacher.
In the lectures the theory is presented, with a stress on the most important ideas; proofs requiring special subtleties are often avoided, and the interested students are invited to look them up in the notes freely downloadable from the relevant e-learning webpage.
In the training sessions it is shown how the general techniques are applied in specific numerical instances. An appropriate amount of exercises, together with their complete solution, are offered in the previously cited webpage.
During both the lectures and the training sessions comments and questions from the attending students are encouraged.
Further information
The course assigns 9 CFUs and is expected to consist of about 70 hours of lectures and 20 hours of training sessions.
Two optional written tests will be held, one in february and the other in may, and any student passing them will be able to take the oral exam (only once!) bypassing the preliminary written test.
Attendance of lectures is suggested, but hopefully the textbooks available for free download through the dedicated e-learning webpage are sufficient for an adequate preparation.
Prof. Marco Barlotti is contactable in room 2.13 on the second floor of the building in via delle Pandette 9 in Firenze, usually on wednesdays from 3:00 to 5:00 PM: please send in advance an email to <marco.barlotti@unifi.it>. Through email it is also possible to arrange a different place and/or a different time for the meeting.
Type of Assessment
The examination through which the student attains the credits for this course consists in:
(1) a written test where 5 to 7 exercises are proposed to ascertain the student's ability to apply simple algorithms;
and
(2) an oral exam where questions are posed and the student's answers are evaluated in order to verify his knowledge of
(2.1) the fundamental notions taught during the course (definitions)
(2.2) the interrelations among such notions (theorems)
and
(2.3) specific techniques used to prove such interrelations.
Passing the written text is a necessary and sufficient condition to take the oral exam.
The student passing the two written tests which are proposed in february and may (the so-called "in itinere" tests) can directly take the oral exam (only once!) any time in the same academic year he has taken those two written tests.
Course program
Elements of set theory: defining a set via its elements, as a subset via a property of its elements, as the union of sets, as the set of all subsets of a given set. Ordered pairs, ordered tuples, cartesian product.
Induction. Proofs by induction.
Relations in a set. The inverse relation. Restriction to a subset. Functions. Domain. Image, inverse image. Injectivity and surjectivity. The inverse function. Composition of functions. Recursive definition of successions. Fibonacci numbers.
Operations in a set. Associativity and commutativity. Distributivity. Groups. Rings. Rings of matrices.
Permutation. The symmetric group. The group Sym(n). Cycles.
Posets. Intervals. Minimal and maximal elements in a poset. Sup and inf.
The Euclidean division. The greatest common divisor of two natural numbers. Euclid's algorithm. A class of diophantine equations. The least common multiple of two natural numbers.
Irreducible numbers. Prime numbers. The "fundamental theorem of arithmetic". Fermat numbers. Mersenne numbers. Perfect numbers.
Lattices. Complemented lattices. Distributivity.
Equivalence relations. Equivalence classes. The quotient set. Modular arithemtic. Notation for natural numbers in different bases. Divisibility criterions.
Some equations in modular arithmetic. Divisors of zero and units in modular arithmetic. The theorem of Fermat-Euler and its application to some exponential equations. The RSA cryptosystem.
Cardinality. The pigeonhole principle. The marriage theorem.
Elements of combinatorics. The principle of addition and the principle of multiplication. Dispositions, permutations, combinations.
Graphs. Examples of graphs. Directed graphs, non-directed graphs. Isomorphism of graphs. Bipartite graphs. Subgraphs. Girth of a graph.
Walks, paths, circuits, cycles. Connession. A characterization of bipartite connected graphs.
The adjacency matrix of a graph. Trees and some characterizations. Girth and planarity. the theorem of Kuratowski.
Eulerian graphs and their characterization. Hamiltonian graphs: some sufficiente conditions and some necessary conditions for a graph to be Hamiltonian: Ore's theorem, Ginberg's theorem.
Coloration of maps. The dual graph of a plane graph. Coloration of the vertices of a graph.
Propositional logic. Truth tables. Logical equivalence. Conjunctive normal form. Refutations. The algorithm of Martin Davis and Hilary Putnam. The compactness theorem.
First order logic. Prenex normal form. Skolem form. The Herbrand universe.