Definitions, claims, and proof checks by unit
Each unit names the actual skills, demonstrates one complete case, and identifies the mistake most likely to change the result.
Logic
You can build truth tables, negate a statement correctly, and check whether an argument is valid. You can also translate an English sentence into symbols.
Claims to justify
- Build the full truth table for an if-then statement.
- Negate 'all cats are grey' as 'some cat is not grey'.
- Apply modus ponens and spot the converse mistake.
Worked example: When is 'if p then q' false?
- Check all four rows of the truth table
- Only the row with p true and q false fails
- It is false only when p is true and q is false
Unsupported step: Reading 'if p then q' as 'if q then p': from 'if it rains, the ground is wet' concluding 'the ground is wet, so it rained', which any sprinkler disproves.
Proof methods
You can prove a claim directly, by contradiction, by contrapositive, or by induction. You can also knock a claim down with a single counterexample.
Claims to justify
- Prove odd plus odd is even by writing both numbers in 2k + 1 form.
- Run an induction proof with a base case and an inductive step.
- Disprove 'every prime is odd' by naming the number 2.
Worked example: Prove that the sum of two odd numbers is even
- Let a = 2m + 1 and b = 2n + 1
- a + b = 2m + 2n + 2 = 2(m + n + 1)
- It is 2 times a whole number, so it is even
Unsupported step: Stopping after examples: 3 + 5 = 8 and 7 + 9 = 16 show the pattern but prove nothing about the infinitely many pairs you did not test.
Sets and relations
You can work with unions, intersections and complements, and test a relation for being reflexive, symmetric or transitive. You can also check whether a relation is a function.
Claims to justify
- Compute the size of a union with inclusion-exclusion.
- Test whether 'is a sibling of' is transitive.
- Build the equivalence classes of a relation.
Worked example: Set A has 20 members, set B has 15, and 6 are in both. How big is the union?
- Size of union = 20 + 15 - 6
- 35 - 6
- 29
Unsupported step: Adding the two sizes and stopping: reporting 35, which counts each of the 6 shared members twice.
Counting
You can count arrangements and selections without listing them, using products, permutations and combinations. You can also use the pigeonhole idea to prove something must repeat.
Claims to justify
- Decide whether order matters before choosing permutations or combinations.
- Compute the number of 3-person teams from a group of 10.
- Use the pigeonhole principle to show two of 13 people share a birth month.
Worked example: How many 3-person teams can be picked from 10 people?
- Order does not matter, so use combinations
- (10 x 9 x 8)/(3 x 2 x 1) = 720/6
- 120
Unsupported step: Using permutations by mistake: reporting 10 x 9 x 8 = 720, which counts the same three people once for each of their 6 orders.
Recurrence relations
You can define a sequence in terms of its earlier terms and then find a closed formula. You can also count the steps an algorithm takes this way.
Claims to justify
- Solve a(n) = 2a(n-1) with a(0) = 3.
- Use the characteristic root method on a two-term recurrence.
- Write the Towers of Hanoi move count as T(n) = 2T(n-1) + 1.
Worked example: Solve a(n) = 2a(n-1) with a(0) = 3
- a(1) = 6, a(2) = 12, a(3) = 24
- Each step doubles the one before
- a(n) = 3 times 2 to the power n
Unsupported step: Writing a(n) = 2 to the power n and losing the starting value: that formula gives a(0) = 1 when the sequence actually starts at 3.
Graph theory
You can model connections as dots and lines, then find paths, trees and colourings. You can also decide whether a walk using every edge exists.
Claims to justify
- Use vertex degrees to test for an Euler circuit.
- Run Dijkstra's algorithm on a small weighted graph.
- Find a minimum spanning tree with Kruskal's algorithm.
Worked example: A graph has vertex degrees 2, 2, 3, 3. Is there an Euler circuit?
- An Euler circuit needs every degree to be even
- Two vertices have odd degree
- No circuit, but an Euler path exists between those two odd vertices
Unsupported step: Counting edges instead of degrees: the total number of edges tells you nothing here, since the test is on each vertex's own degree.
Number theory
You can work with divisibility, greatest common divisors, primes and clock arithmetic. You can also solve the simple congruences that coding schemes rely on.
Claims to justify
- Run the Euclidean algorithm to find a greatest common divisor.
- Reduce a large power in modular arithmetic by finding its cycle.
- Find the inverse of 3 modulo 7.
Worked example: Find the greatest common divisor of 252 and 105
- 252 = 2(105) + 42
- 105 = 2(42) + 21, then 42 = 2(21) + 0
- 21
Unsupported step: Stopping at the first remainder: reporting 42 as the answer, even though 42 does not divide 105 evenly.
Read, attempt, challenge, and revise an argument
Short cycles create evidence that the idea is becoming usable rather than merely familiar.
Define
Write the definitions and assumptions that the claim can use.
Attempt
Build the argument without consulting a model proof.
Challenge
Search for a missing direction, edge case, or unsupported implication.
Revise
Repair the earliest logical gap and present the dependency clearly.
Trace the dependency of each claim
Definitions and earlier results supply the reasons used later, so repair the first unsupported step.
LogicWeeks 1-2 · You can build truth tables, negate a statement correctly, and check whether an argument is valid. You can also translate an English sentence into symbols.Proof methodsWeeks 3-4 · You can prove a claim directly, by contradiction, by contrapositive, or by induction. You can also knock a claim down with a single counterexample.Sets and relationsWeeks 5-6 · You can work with unions, intersections and complements, and test a relation for being reflexive, symmetric or transitive. You can also check whether a relation is a function.CountingWeeks 7-8 · You can count arrangements and selections without listing them, using products, permutations and combinations. You can also use the pigeonhole idea to prove something must repeat.Recurrence relationsWeeks 9-10 · You can define a sequence in terms of its earlier terms and then find a closed formula. You can also count the steps an algorithm takes this way.Graph theoryWeeks 11-12 · You can model connections as dots and lines, then find paths, trees and colourings. You can also decide whether a walk using every edge exists.Number theoryWeeks 13-14 · You can work with divisibility, greatest common divisors, primes and clock arithmetic. You can also solve the simple congruences that coding schemes rely on.
Questions about studying Discrete Mathematics
Where should I begin in this course?
Start with the earliest unit whose definitions or notation you cannot explain from memory. Later units often depend on that foundation even when the current assignment looks different.
When should I move to the next unit?
Move on after you can choose the method on a changed problem, complete it without copying a model, and check the answer independently.
How should I use the practice workspace?
Begin without a hint, record the first uncertain decision, repair only that connection, and then answer a fresh question to test whether the repair transferred.