# ICY0001 Logic and Discrete Mathematics

This course is designed to introduce students to the techniques, algorithms, and reasoning processes involved in the study of discrete mathematical structures. Students will be introduced to set theory, deductive and inductive reasoning, elementary counting techniques, ordering, functional and equivalence relations, graphs, and trees. The aim is to give them knowledge and skills that would enable to use the basic methods of discrete mathematics in subsequent courses, in the design and analysis of algorithms, computability theory, software engineering, and computer systems.

Form for anonymous feedback Say something

# Exam arrangement details and registration

Choose only one date. Please also register at ÕIS (corresponding date), otherwise registration is not valid.

# Topics to be covered

• Elementary set theory (basic definitions and set operations, the power set and Cartesian products);
• Basic connectives in propositional logic and their properties with emphasis on some of the methods of proving mathematical results;
• Quantifiers in predicate logic and in infinitely large domain sets;
• Mathematical induction;
• Binary relations and, in particular, the equivalence relation; partial order relations;
• Basic counting techniques, combinations, permutations;
• Binomial coefficients, Pascal’s triangle;
• Graphs, vertices, edges, paths, cycles;
• Eulerian and Hamiltonian graphs, travelling-salesman problem;
• Basic definitions and properties of trees;
• Planar graphs, graph colouring.

# Schedule and lecture slides 2018

The grading allocation is designed as follows:

• Homeworks -- are not graded, but solving homework problems helps passing quizzes, tests and exam;
• Quizzes -- 20%
• Midterm + final test -- 40%
• Final exam (oral) -- 40%

The final ranking for the course will turn out by summarising the student’s individual results of quizzes, tests and exam (maximum sum of points is 100) and the final grade will be as follows:

• `0` - less than 51 points
• `1` - 51--60 points
• `2` - 61--70 points
• `3` - 71--80 points
• `4` - 81--90 points
• `5` - 91 and more points

# Study material

## Primary material:

• S.Lipschutz and M.Lipson. Schaum's Outline of Discrete Mathematics, McGraw Hill 2007, Revised 3rd edition

• K. H. Rosen. Discrete Mathematics and Its Applications, WCB/McGraw Hill, 7th edition