First-year courses · Mathematics

Discrete mathematics: logic, proofs, counting, graphs

Discrete maths flashcards: propositional logic, quantifiers, sets, functions, proof methods, induction, counting, the pigeonhole principle and graph basics.

43 cards5 topicsAbout 15 minutes a roundTypical first-year discrete mathematics for computing and mathematics students

Print cards to cut out (PDF)Print a study list (PDF)

About this deck

This deck is for students in a first-year discrete mathematics course, which is often required for computer science, software engineering and mathematics programs. It covers propositional logic and truth tables, quantifiers and how to negate them, sets and functions, the main proof techniques (direct proof, contrapositive, contradiction and induction), a little number theory, counting with permutations and combinations, the pigeonhole principle, and the basic vocabulary of graphs and trees.

No calculus is needed. You should be comfortable with high school algebra, factorials and exponents, and willing to write full sentences in your answers: in this course the reasoning is the answer, not just the final number.

For logic and set cards, build a small truth table or Venn diagram before you flip. For proof cards, try writing the first and last lines of the proof yourself (what you assume and what you must reach), then fill in the middle. For counting cards, decide first whether order matters and whether repetition is allowed; that one question picks the formula. Mix the tags once each feels familiar.

Common mistakes: treating a conditional statement as equivalent to its converse; in induction, assuming the statement for n + 1 instead of proving it from the case n; and using combinations when the problem cares about order, or permutations when it does not.

Before you start: Grade 12 mathematics (for example Math 30-1 or Advanced Functions), including exponents, factorials and algebraic manipulation.

All 43 cards

Cover the definitions with a sheet of paper and test yourself, or use the study modes above.

Logic

Proposition: A declarative sentence that is either true or false, but not both.Example: '7 is prime' is one (true); 'Close the door' is not, because it has no truth value.
Negation: The statement 'not p', which is true exactly when p is false.Example: The opposite of 'x > 3' is 'x <= 3'.
Conjunction: The compound 'p and q', true only when both parts are true.Example: '2 is even and 3 is even' is false because the second part is false.
Conditional statement: 'If p then q' (p implies q). It is false only when p is true and q is false; with a false hypothesis it is vacuously true.Example: 'If 2 + 2 = 5 then the moon is cheese' is true, since the hypothesis is false.
Biconditional: 'p if and only if q', true when p and q have the same truth value.Example: 'n is even iff n^2 is even' is true for every integer n.
Contrapositive: From 'if p then q', the statement 'if not q then not p'. It is logically equivalent to the original.Example: 'If it rains the ground is wet' becomes 'if the ground is not wet it did not rain'.
Converse: From 'if p then q', the statement 'if q then p'. It is not equivalent to the original in general.Example: 'If n is divisible by 4 then n is even' is true; its reverse fails for n = 6.
Tautology: A compound statement that is true for every assignment of truth values to its variables.Example: 'p or not p' is true in both rows of its truth table.
De Morgan's laws: not (p and q) is equivalent to (not p) or (not q); not (p or q) is equivalent to (not p) and (not q).Example: 'Not (x > 0 and y > 0)' means 'x <= 0 or y <= 0'.
Universal and existential quantifiers: 'For all x' asserts a property of every element of the domain; 'there exists x' asserts it of at least one.Example: Over the integers, 'for all x, x^2 >= 0' is true; 'there exists x with x^2 = 2' is false.
Negating a quantified statement: Swap 'for all' with 'there exists' and negate the inner statement.Example: not (for all x, x > 0) becomes 'there exists x with x <= 0'.
Size of a truth table: A table listing every combination of truth values; with n variables it has 2^n rows.Example: Three variables p, q, r need 2^3 = 8 rows.

Sets and functions

Subset: A is contained in B when every element of A is also an element of B; the empty set is contained in every set.Example: {1, 2} is contained in {1, 2, 3}, but {1, 4} is not.
Power set: The set of all subsets of a set; if the set has n elements this collection has 2^n members.Example: For {a, b, c}: 2^3 = 8 subsets, from the empty set up to {a, b, c}.
Union and intersection: A union B holds elements in A or B (or both); A intersect B holds elements in both.Example: A = {1, 2, 3}, B = {3, 4}: union {1, 2, 3, 4}, intersection {3}.
Set difference: A - B is the set of elements in A that are not in B.Example: {1, 2, 3} - {3, 4} = {1, 2}.
Cartesian product: A x B is the set of all ordered pairs (a, b) with a in A and b in B; its size is |A| times |B|.Example: |A| = 3 and |B| = 4 give 3 x 4 = 12 ordered pairs.
Inclusion-exclusion for two sets: |A union B| = |A| + |B| - |A intersect B|, subtracting the overlap that was counted twice.Example: 30 students take math, 25 take physics, 10 take both: 30 + 25 - 10 = 45 take at least one.
Injective, surjective and bijective functions: One-to-one: distinct inputs give distinct outputs. Onto: every element of the codomain is hit. Bijective: both, so an inverse exists.Example: f(n) = 2n from integers to integers is one-to-one but not onto, since 3 is never an output.
Composition of functions: (g o f)(x) = g(f(x)): apply f first, then g; the order matters.Example: f(x) = x + 1, g(x) = 2x: g(f(3)) = 8 but f(g(3)) = 7.

Proofs and number theory

Direct proof: Assume the hypothesis and reason step by step, using definitions and known results, until the conclusion is reached.Example: If a = 2j and b = 2k then a + b = 2(j + k), so the sum of two even integers is even.
Proof by contrapositive: To prove 'if p then q', prove instead 'if not q then not p', which is equivalent and sometimes easier.Example: To show 'n^2 even implies n even', show 'n odd implies n^2 odd': (2k + 1)^2 = 2(2k^2 + 2k) + 1.
Proof by contradiction: Assume the statement is false and derive something impossible, so the assumption must be wrong.Example: Assume sqrt(2) = a/b in lowest terms; then a and b both turn out even, contradicting lowest terms.
Counterexample: A single specific case that satisfies the hypothesis but not the conclusion, which disproves a universal claim.Example: 'n^2 + n + 41 is always prime' fails at n = 40, giving 1681 = 41^2.
Mathematical induction: To prove P(n) for all n >= n0: show P(n0), then show that P(k) implies P(k + 1) for every k >= n0.Example: 1 + 2 + ... + n = n(n + 1)/2. Check n = 4: 1 + 2 + 3 + 4 = 10 = 4(5)/2.
Strong induction: A variant where the inductive step may assume the statement for all values from the base case up to k, not just k itself.Example: Used to show every integer n >= 2 is a product of primes: a composite n = ab with smaller a and b.
Congruence modulo n: a is congruent to b mod n when n divides a - b; equivalently a and b leave the same remainder on division by n.Example: 17 mod 5 = 2, and 17 is congruent to 2 (mod 5) because 5 divides 15.
Euclidean algorithm: Find gcd(a, b) by repeatedly replacing the pair (a, b) with (b, a mod b) until the remainder is 0; the last nonzero remainder is the gcd.Example: gcd(84, 36): 84 = 2(36) + 12, 36 = 3(12) + 0, so the gcd is 12.

Counting

Product rule: If a task is a sequence of steps with m ways for the first and n ways for the second, the task can be done in m n ways.Example: 3 shirts and 4 pairs of pants give 3 x 4 = 12 outfits.
Sum rule: If a choice can come from one of two disjoint groups of sizes m and n, there are m + n options.Example: Picking one rep from 12 first-years or 9 second-years: 12 + 9 = 21 choices.
Permutations: Ordered arrangements of r objects chosen from n distinct ones: P(n, r) = n!/(n - r)!.Example: President and vice-president from 5 people: P(5, 2) = 5 x 4 = 20.
Combinations: Unordered selections of r objects from n: C(n, r) = n!/(r!(n - r)!).Example: A 2-person committee from 5 people: C(5, 2) = 10. Five-card hands from 52 cards: C(52, 5) = 2,598,960.
Arrangements with repeated letters: The number of distinct orderings of n items where groups are identical is n! divided by the factorial of each group size.Example: MISSISSIPPI: 11!/(1! 4! 4! 2!) = 34,650 arrangements.
Pigeonhole principle: If more than k items go into k boxes, some box holds at least two; more generally some box holds at least the ceiling of N/k.Example: Among 13 people, at least two were born in the same month.
Binomial theorem: (x + y)^n expands to the sum over k of C(n, k) x^(n - k) y^k, so the coefficients are binomial coefficients.Example: The coefficient of x^2 in (1 + x)^5 is C(5, 2) = 10.

Graphs and trees

Graph: A set of vertices together with a set of edges, each edge joining a pair of vertices.Example: A road map with towns as vertices and roads as edges.
Handshake lemma: In any undirected graph the sum of all vertex degrees equals twice the number of edges, so the number of odd-degree vertices is even.Example: A graph with 5 edges has degrees summing to 10.
Connected graph: A graph in which some path joins every pair of vertices.Example: Two separate triangles drawn side by side form a graph that is not connected.
Tree: A connected graph with no cycles; with n vertices it always has exactly n - 1 edges.Example: A tree on 10 vertices has 9 edges, and adding any edge creates a cycle.
Euler circuit: A closed walk using every edge exactly once; a connected graph has one exactly when every vertex has even degree.Example: The Konigsberg bridge graph has four vertices of odd degree, so no such walk exists.
Hamilton cycle: A cycle that visits every vertex exactly once; no simple degree test decides whether one exists.Example: Any complete graph with at least 3 vertices has one.
Complete graph: The simple graph K_n in which every pair of the n vertices is joined by an edge; it has n(n - 1)/2 edges.Example: K_6 has 6 x 5/2 = 15 edges.
Bipartite graph: A graph whose vertices split into two groups so that every edge joins one group to the other; equivalently it has no odd cycle.Example: Students and courses, with an edge when a student takes a course.