Course Details

1. Discuss the core principles of mathematical logic and its applicability to computer science.
2. Use symbolic logic and truth tables to prove equivalence of statements by determining the validity of arguments and formulate statements into symbolic form using logical connectives and quantifiers.
3. Identify and correctly employ different methods of proofs including direct proofs, proofs by contradiction and mathematical induction.
4. Develop ability of dealing with abstract notions and reasoning through the introduction and manipulation of basic ideas from the theory of sets, functions and relations.
5. Apply Boolean combination of sets and operations on such expressions, examine various characterisations of functions and relations, analyse their properties and ways of combining them; and compare matrix and graphical methods for their representation.
6. Describe main counting techniques including the Inclusion-Exclusion and Pigeonhole principle and employ them to solve problems of combinatorial nature.
7. Discuss basic concepts of Elementary Graph Theory, decide whether a graph is Eulerian or not and employ Kruskall’s algorithm for finding minimal spanning trees in related problem situations.

Mathematical logic: Propositional Algebra; Logical Operators; Basic logic Equivalences; Predicates; Quantifiers.

Proof Methods: Direct Proofs; Mathematical Induction; Contradiction and Contraposition.

Sets: Basic Definitions; Set operations; Venn diagrams; Set Identities

Relations and Functions: Relations; Equivalence Relations; Equivalence Classes; Definition and Properties of Functions; Inverse Functions; Composition of Functions.

Combinatorics: Basic counting principles; Permutations and Combinations.

Graph Theory: Terminology, Graph Representation and Isomorphism; Connectivity; Traversability; Eulerian graphs; Kruskall’s algorithm for finding Minimal Spanning Trees. 

• K.K. Rosen. Discrete Mathematics and Its Applications, 7th Edition, McGraw-Hill, 2012

• S. S. Epp, Discrete Mathematics with Applications, 4th Edition, Thomson Brooks/Col, 2011.

For the delivery of the class material, power point presentations are primarily used, along with the whiteboard. The lecture notes, consisting of slides presented in class, and additional material, are made available to the students through the course website and are complementary of the course textbooks. The theoretical part of each lecture is accompanied with detailed solved examples on which emphasis is given in the class. The solutions to these exercises, as well as specimen solutions for all tests and assignments, are discussed with students.