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.
