# Discrete Structures

Teaching -> Discrete Structures

**Duration:** Approximately 30 lecture hours

**Prerequisites:** Basic knowledge in Mathematics

**Course contents:**

- Introduction, Statements (Propositions), Compound statements, Truth tables, Logical equivalence, Conditional statements, Valid and invalid arguments.
- Predicates, Quantified statements, Statements with multiple quantifiers, Negations of quantified statements, Arguments with quantified statements.
- Direct proofs and counter examples, Elementary number theory, Proof by division into cases, Indirect proofs: contradiction and contraposition.
- Sequences, Mathematical induction, Strong mathematical induction, Well-ordering principle.
- Set theory: properties of sets, set proofs and disproofs; Boolean algebras, Russell’s Paradox and the Halting Problem.
- Counting arguments: Sum and product rule, Inclusion-exclusion principle.

**Objectives:**

To provide a solid foundation in areas of Discrete Mathematics that play an important role in Computer Science: logic (propositional and predicate), methods of mathematical proof and set theory.

**Method of assessments:**

Continuous assessments – 40%

Final examination – 60%

**Attendance:**

- Only those who satisfy the requirement of attendance (at least 80%) at lectures are allowed to sit the end of semester examination.
- Students who misbehave in the class will be asked to leave the class. If a student is asked to leave a lecture, this will count as an absence.

**Recommended reading:**

- Discrete Mathematics with Applications (Third edition), Susanna S. Epp, Brooks/Cole, 2004.
- Discrete and Combinatorial Mathematics – An Applied Introduction, Ralph P. Grimaldi, Pearson Addison Wesley, 2003.
- Discrete Mathematics (Third edition), Seymour Lipschuts and Marc Lipson, Schaum’s Outlines, 2007.