COS1501
Theoretical Computer Science I

COS1501 Study Guide

0. Introduction
0.1. What is Discrete Mathematics?
0.2. The purpose of the module
0.3. Outcomes of the module
0.4. Syllabus
0.5. How to study this module
0.6. Acknowledgements
1. The development of numbers systems: Z+, Z≥ and Z
1.1. Introduction to the study unit
1.2. Positive integers: Z+
1.2.1. Commutative property
1.2.2. Associative property
1.2.3. Distributive property
1.2.4. Multiplicative identity
1.3. Non-negative integers: Z≥
1.3.1. The existence of an additive identity
1.3.2. Multiplication by zero
1.4. Integers: Z
1.5. The additive inverse, absolute values and prime numbers
1.6. The nine laws for Z≥
1.7. In summary of the study unit
2. Rational and real numbers: Q and R
2.1. Introduction to this study unit
2.2. The rational numbers: Q
2.3. The 11th law of Q
2.4. The real numbers: R
2.5. In summary of the study unit
3. Sets
3.1. Introduction to this study unit
3.2. Why do set theory?
3.3. How do we talk about sets?
3.4. How to build new sets from old ones
3.5. In summary of the study unit
4. Proofs involving sets
4.1. Venn diagrams
4.2. Proofs
4.3. Working with (X ∩ Y)' and (X ∪ Y)
4.4. The Inclusion-exclusion principle
4.5. Proofs on specific sets
4.6. In summary of the study unit
5. Relations
5.1. Ordered pairs
5.2. Relations
5.3. Properties of relations
5.4. In summary of the study unit
6. Special kinds of relation
6.1. Order relations
6.2. Some comments on proof strategies
6.3. Equivalence relations
6.4. n-ary relations
6.5. Functions
6.6. In summary of the study unit
7. More about functions
7.1. Surjective functions
7.2. Injective functions
7.3. The composition of relations / functions
7.4. Bijective functions and inverses
7.5. In summary of the study unit
8. Operations
8.1. Binary operations
8.2. The properties of binary operations
8.3. Operations on vectors
8.4. Operations on matrices
8.5. In summary of the study unit
9. Logic: Truth tables
9.1. Statements and connectives
9.2. Relationships between statements
9.3. In summary of the study unit
10. Logic: quantifiers, predicates, and proof strategies
10.1. Quantifiers and predicates
10.2. Proof strategies
10.2.1. Direct proof
10.2.2. Proof by contradiction (reductio ad absurdum)
10.2.3. Proof by contrapositive
10.2.4. Proofs involving quantifiers
10.2.5. Vacuous proof
10.3. In summary of the study unit