Discrete Mathematics: cram pack

Formula sheets, the key method steps for every topic and 8 practice problems, with full solutions at the back.

New problems Back to the course

In the print window, choose “Save as PDF” to keep a copy on your device.

1Formulas and methods

Propositional logic & proofs

Rows of a truth table: 2ⁿ
Implication: p → q ≡ ¬p ∨ q ≡ ¬q → ¬p
Negated implication: ¬(p → q) ≡ p ∧ ¬q
Biconditional: p ↔ q ≡ (p → q) ∧ (q → p)
De Morgan: ¬(p ∧ q) ≡ ¬p ∨ ¬q, ¬(p ∨ q) ≡ ¬p ∧ ¬q
Distributive laws: p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r), p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)
Negated quantifiers: ¬∀x P(x) ≡ ∃x ¬P(x), ¬∃x P(x) ≡ ∀x ¬P(x)
Modus ponens, modus tollens: p → q, p ⊢ q; p → q, ¬q ⊢ ¬p

Method

Count the different variables: the truth table has 2ⁿ rows, starting with all of them 1.
Give every subformula its own column and fill the columns from the inside out.
Apply the rule of each connective: → is 0 only for 1 → 0, ↔ is 1 when both sides agree.
For equivalences, compare the final columns row by row; for an argument, look only at the rows in which every premise is 1.
To negate a quantified statement, move ¬ inwards, swap ∀ and ∃, and negate the inner formula.

Sets, relations & functions

Two sets: |A ∪ B| = |A| + |B| − |A ∩ B|
Three sets: |A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|
Difference and complement: A − B = A ∩ B′, |A′| = |U| − |A|
Power set and product: |𝒫(A)| = 2^|A|, |A × B| = |A|·|B|
Subsets of size k: C(n, k) = n!/(k!(n − k)!)
Functions A → B: nᵐ; injective n!/(n − m)!; surjective Σ (−1)ᵏ C(n, k)(n − k)ᵐ
Relations on n elements: 2^n²; reflexive 2^{n² − n}; symmetric 2^n(n+1)/2
Composition: (g ∘ f)(x) = g(f(x))

Method

Draw a Venn diagram and decide region by region what belongs to the set expression.
For counting problems, fill in the regions from the centre outwards: all sets, then pairs, then single sets, then the outside.
Use inclusion–exclusion as a check: |A ∪ B| = |A| + |B| − |A ∩ B|.
For a relation, test each property on every pair and give one counterexample when it fails.
For a function, count the arrows arriving at each element of B: at most one means injective, at least one surjective.

Graph theory

Handshake lemma: Σ deg(v) = 2|E|
Complete graphs: |E(K_n)| = n(n − 1)/2, |E(K_m,n)| = m·n
Regular graph: |E| = n·k/2
Tree and forest: |E| = n − 1, |E| = n − c
Leaves of a tree: L = 2 + Σ (deg(v) − 2) over deg(v) ≥ 3
Euler: circuit: all degrees even; path: exactly 2 odd degrees
Hamilton circuits in K_n: (n − 1)!/2
Dijkstra update: d(v) = min(d(v), d(u) + w(u, v))
Walks of length L: (Mᴸ)_ij

Method

Write down the degree of every vertex; the degrees add up to twice the number of edges.
For Euler questions, check that the graph is connected and count the vertices with odd degree.
For trees, use n − 1 edges and the handshake lemma.
For Dijkstra, keep a table of tentative distances and settle the smallest unsettled vertex each round.
For a minimum spanning tree, sort the edges by weight and skip every edge that closes a cycle (Kruskal), or grow one tree from a start vertex (Prim).

Number theory & modular arithmetic

Division with remainder: a = q·n + r, 0 ≤ r < n
Euclid: gcd(a, b) = gcd(b, a mod b)
Least common multiple: lcm(a, b) = a·b/gcd(a, b)
Inverse: a·a⁻¹ ≡ 1 (mod n), gcd(a, n) = 1
Linear congruence: a·x ≡ b → x ≡ a⁻¹·b (mod n)
Euler’s totient: φ(n) = n·∏(1 − 1/p), φ(pᵏ) = pᵏ − pᵏ⁻¹
Fermat: aᵖ⁻¹ ≡ 1 (mod p)
RSA: n = pq, φ = (p − 1)(q − 1), d = e⁻¹ mod φ, c = mᵉ mod n, m = cᵈ mod n

Method

Reduce every number modulo n first; remainders lie between 0 and n − 1.
For a gcd, divide repeatedly with Euclid’s algorithm; the last nonzero remainder is the gcd.
For an inverse, run the extended algorithm and keep the coefficient of a; add n if it is negative.
Solve a·x ≡ b by multiplying with a⁻¹; combine two congruences by writing x = r₁ + m₁k.
For powers, write the exponent in binary and square repeatedly; in RSA, d = e⁻¹ mod φ(n) with φ(n) = (p − 1)(q − 1).

2Practice problems

1.Propositional logic & proofsMedium

Which formula is logically equivalent to (q ∨ r) → p? Click it.

(q ∨ r) → p

1q ∨ (r → p)
2(q → p) ∨ (r → p)
3(q → p) ∧ (r → p)
4(q ∧ r) → p

2.Propositional logic & proofsHard

Which statement is equivalent to ¬∃x A(x), with the negation moved all the way inside? Click it.

¬∃x A(x)

1∀x A(x)
2∃x ¬A(x)
3∃x A(x)
4∀x ¬A(x)

3.Sets, relations & functionsMedium

Exactly one region of the Venn diagram is the set (A − C) − (C′ ∩ B). Click its number.

(A − C) − (C′ ∩ B)

1region 1
2region 2
3region 3
4region 4
5region 5
6region 6
7region 7
8region 8

4.Sets, relations & functionsHard

The arrow diagram shows a function f: A → B with A = {1, 2, 3, 4} and B = {a, b, c, d}. Click the description that fits f.

f = {(1, a), (2, a), (3, c), (4, b)}

1injective, not surjective
2surjective, not injective
3bijective
4neither

5.Graph theoryMedium

How many different Hamilton circuits H does the complete graph K₇ have? Circuits that differ only in the starting vertex or the direction count as the same.

K₇

H =

6.Graph theoryHard

How many closed walks of length 2 start and end at B? A walk may repeat vertices and edges. Call the number N.

M = adjacency matrixL = 2

N =

7.Number theory & modular arithmeticMedium

Find the inverse of 4 modulo 59: the number x with 0 < x < 59 and 4·x ≡ 1 (mod 59).

a = 4n = 59

4⁻¹ mod 59 =

8.Number theory & modular arithmeticHard

59 is prime. Use Fermat’s little theorem to find 26⁷⁶⁷⁵⁰ mod 59.

p = 59k = 76750

26⁷⁶⁷⁵⁰ mod 59 =

3Solutions

1.Propositional logic & proofs

Answer: (q → p) ∧ (r → p)

Logical equivalence: two formulas are equivalent (≡) when they have the same value in every row of the truth table. A tautology is 1 in every row, a contradiction is 0 in every row, and a contingency is neither. Useful laws: De Morgan, ¬(a ∧ b) ≡ ¬a ∨ ¬b and ¬(a ∨ b) ≡ ¬a ∧ ¬b; a → b ≡ ¬a ∨ b ≡ ¬b → ¬a (contrapositive); ¬(a → b) ≡ a ∧ ¬b; and the distributive laws, a ∨ (b ∧ c) ≡ (a ∨ b) ∧ (a ∨ c).

The law

(a ∨ b) → c needs c whenever either a or b holds: (a → c) ∧ (b → c).

(q ∨ r) → p ≡ (q → p) ∧ (r → p)

Check with the truth table

p = 1, q = 1, r = 1: 1 | 1 1 1 1

p = 1, q = 1, r = 0: 1 | 1 1 1 1

p = 1, q = 0, r = 1: 1 | 1 1 1 1

p = 1, q = 0, r = 0: 1 | 1 1 1 1

p = 0, q = 1, r = 1: 0 | 1 0 0 0

p = 0, q = 1, r = 0: 0 | 1 1 0 1

p = 0, q = 0, r = 1: 0 | 0 1 0 1

p = 0, q = 0, r = 0: 1 | 1 1 1 1

Answer

(q → p) ∧ (r → p)

The columns after the bar are the options in the order shown.

2.Propositional logic & proofs

Answer: ∀x ¬A(x)

Quantifiers and arguments: ¬∀x P(x) ≡ ∃x ¬P(x) and ¬∃x P(x) ≡ ∀x ¬P(x). Move a negation inwards, swap every quantifier it passes, and negate the inner formula with the propositional laws, such as ¬(a → b) ≡ a ∧ ¬b. An argument is valid when the conclusion is 1 in every row in which all premises are 1. A single row with true premises and a false conclusion is a counterexample and shows the argument is invalid.

Move the negation inwards

¬∃x A(x) ≡ ∀x ¬A(x)

Answer

∀x ¬A(x)

The other options either keep a quantifier unchanged, change the order of the quantifiers, or negate the inner formula wrongly.

3.Sets, relations & functions

Answer: region 2

Sets and Venn diagrams: A ∪ B holds the elements in A or B (or both), A ∩ B the elements in both, A − B the elements of A that are not in B, and the complement A′ everything in U that is not in A. In a Venn diagram every set expression is a union of regions, so count it region by region. Inclusion–exclusion: |A ∪ B| = |A| + |B| − |A ∩ B|, and |A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|.

Inside or outside each set

A ∩ B′ ∩ C′

The region

region 2

Answer

region 2

4.Sets, relations & functions

Answer: neither

Functions and counting: a function f: A → B gives every element of A exactly one image in B. f is injective (one-to-one) when different elements have different images, surjective (onto) when every element of B is an image, and bijective when both hold. With |A| = m and |B| = n there are nᵐ functions, n!/(n − m)! injective ones (m ≤ n), and by inclusion–exclusion Σ (−1)ᵏ·C(n, k)·(n − k)ᵐ surjective ones. |𝒫(A)| = 2ᵐ and |A × B| = m·n.

Injective?

f(1) = f(2) = a → not injective

Surjective?

d receives no arrow → not surjective

Answer

neither

Answer

neither

5.Graph theory

Answer: H = 360

Euler, Hamilton and trees: a connected graph has an Euler circuit (every edge once, back to the start) when every vertex has even degree, and an Euler path that is not a circuit when exactly two vertices have odd degree; the path then runs from one odd vertex to the other. A Hamilton circuit visits every vertex once; K_n has (n − 1)!/2 of them. A tree on n vertices has n − 1 edges, and a connected graph with m edges keeps a spanning tree after removing m − n + 1 edges.

Count

H = (7 − 1)!/2 = 720/2 = 360

Answer

H = 360

6.Graph theory

Answer: N = 4

Degrees: the degree of a vertex is the number of edges that meet it. Every edge has two ends, so the degrees add up to twice the number of edges: Σ deg(v) = 2|E| (the handshake lemma). The number of vertices with odd degree is therefore even. K_n has n(n − 1)/2 edges, a k-regular graph on n vertices has nk/2, and a tree on n vertices has n − 1 edges.

Adjacency matrix

A: 0 1 0 0 0 0

B: 1 0 1 1 1 0

C: 0 1 0 0 1 0

D: 0 1 0 0 0 1

E: 0 1 1 0 0 1

F: 0 0 0 1 1 0

Common neighbours

(M²)_BB = 1·1 + 0·0 + 1·1 + 1·1 + 1·1 + 0·0 = 4

Answer

N = 4

7.Number theory & modular arithmetic

Answer: 4⁻¹ mod 59 = 15

Inverses and congruences: a has an inverse modulo n exactly when gcd(a, n) = 1. The extended Euclidean algorithm writes 1 = s·n + t·a, and then a⁻¹ ≡ t (mod n). A congruence a·x ≡ b (mod n) with gcd(a, n) = 1 has the solution x ≡ a⁻¹·b. Two congruences x ≡ r₁ (mod m₁) and x ≡ r₂ (mod m₂) with coprime moduli have one solution modulo m₁·m₂ (Chinese remainder theorem). Euler’s φ(n) counts the numbers from 1 to n that are coprime to n: φ(n) = n·∏(1 − 1/p).

Extended Euclidean algorithm

Each remainder r is written as r ≡ t·4 (mod 59).

r = 59, t = 0

r = 4, q = 14, t = 1

r = 3, q = 1, t = −14

r = 1, q = 3, t = 15

Inverse

1 ≡ 15·4 (mod 59)

x = 15

check: 4·15 = 60 = 1·59 + 1

Answer

4⁻¹ mod 59 = 15

8.Number theory & modular arithmetic

Answer: 26⁷⁶⁷⁵⁰ mod 59 = 17

Modular powers and RSA: compute aᵏ mod n by repeated squaring: write k in binary, square, reduce after every step and multiply the powers whose bit is 1. Fermat: aᵖ⁻¹ ≡ 1 (mod p) for a prime p not dividing a, so the exponent can be reduced modulo p − 1. RSA: choose primes p and q, n = p·q and φ(n) = (p − 1)(q − 1); the public exponent e is coprime to φ(n), and the private exponent is d = e⁻¹ mod φ(n). Encrypt with c = mᵉ mod n and decrypt with m = cᵈ mod n.

Reduce the exponent

76750 mod 58 = 16

26⁷⁶⁷⁵⁰ ≡ 26¹⁶ (mod 59)

Small power

26¹⁶ mod 59 = 17

Answer

26⁷⁶⁷⁵⁰ mod 59 = 17

ExamProblems · examproblems.com/courses/discrete-mathematics