True wisdom comes to each of us when we realize how little we understand about life, ourselves, and the world around us - Socrates

Discrete Structures

Teaching -> Discrete Structures

Duration: Approximately 30 lecture hours

Prerequisites: Basic knowledge in Mathematics

Course contents:
  1. Introduction, Statements (Propositions), Compound statements, Truth tables, Logical equivalence, Conditional statements, Valid and invalid arguments.
  2. Predicates, Quantified statements, Statements with multiple quantifiers, Negations of quantified statements, Arguments with quantified statements. 
  3. Direct proofs and counter examples, Elementary number theory, Proof by division into cases, Indirect proofs: contradiction and contraposition.
  4. Sequences, Mathematical induction, Strong mathematical induction, Well-ordering principle.
  5. Set theory: properties of sets, set proofs and disproofs; Boolean algebras, Russell's Paradox and the Halting Problem.
  6. Counting arguments: Sum  and product rule, Inclusion-exclusion principle.
  • 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%

  • 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.