Subject 'Elements of Discrete Mathematics'

Year:   2019/2020    

To give basic knowledge of mathematics needed in computer science and to develop the ability of structured thinking and abstraction.

After passing this course the student can

• express statements using propositional formulas, establish properties (e.g. satisfiability, validity) of and relations (e.g. equivalence, consequence) between these formulas with the help of the truth table, convert formulas into equivalent formulas in suitable form, and relate the results to the original statements;
• construct proofs of simple statements originating from different areas of mathematics and explain the steps and principles of proof (e.g. direct proof, proof by contraposition, proof by example, mathematical induction) used in these;
• explain and illustrate the notions of set, function and relation, and perform operations with these, describing each action using the standard terminology of the corresponding area;
• compute the number of permutations and combinations without or with repetitions, reduce finding of the solution of a counting problem to applying the addition principle or the multiplication principle (also in the form of a recurrent eqution), compute the exact numerical solution of the problem, if required;
• explain, illustrate with examples, and associate with each other the basic notions of graph theory, use graphs and trees to model situations, and draw conclusions about the situation using basic properties of graphs and trees.

An introductory course on discrete mathematics, consists of five topics: propositional calculus, proofs, sets, combinatorics, and graphs.