Discrete Mathematics and Logic - Winter 2009

Teaching period: 21.9. - 18.9.2009
Lecture: Monday 14:30-16:00, Dept. of Mathematics
Examination period: 4.1. - 12.2.2010


  1. Propositional formulas, tautological equivalence in propositional logic. CNF and DNF. Boolean calculus.
  2. Semantic consequence.
  3. Predicate logic, interpretation.
  4. Semantic consequent and tautological equivalence in predicate logic.
  5. Mathematical induction.
  6. Binary relations, equivalnce relation, partial ordering.
  7. Integers. Eukleid Algorithm, Fermat Theorem.
  8. Relation mod n on integers and its properties.
  9. Classes mod n and operations with them. Applications.
  10. Chinese Remainder Theorem, RSA cryptosystem.
  11. Semigroups. monoids, groups.
  12. Difference equations with constant coefficients.


  • M. Demlová: Mathematical logic. Kernberg Publishing, s.r.o., 2008.
  • L. Childs: A concrete Introduction to Higher Algebra. Springer-Verlag, Berlin, 1979.
  • J. Velebil: Matematics 5(d), available at web pages .

Structure of the exam:

The exam consists of a written part and an oral part. The written part contains four problems. For each problem you get up to 20 points, making the total 80 points for the written part. Oral exam is a theoretical question for up to 20 points. This part is not obligatory, it allows you to add points to those you had got for the written exam.


Sum Grade
50-59 E (sufficient)
60-69 D (satisfactory)
70-79 C (good)
80-89 B (very good)
90-100 A (excellent)