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 (r ∨ q) → p? Click it.

(r ∨ q) → p

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

2.Propositional logic & proofsHard

The argument with premises a → c; ¬a and conclusion ¬c is invalid. Click the row of the truth table that is a counterexample.

a → c¬a∴ ¬c

1a = 1, c = 1
2a = 1, c = 0
3a = 0, c = 1
4a = 0, c = 0

3.Sets, relations & functionsMedium

A survey of 41 people finds that 32 own a laptop (L), 9 own a tablet (T) and 5 own both. How many are in L but not in T?

|U| = 41|L| = 32|T| = 9|L ∩ T| = 5

|L − T| =

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, e}. Click the description that fits f.

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

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

5.Graph theoryMedium

Does the connected graph have an Euler circuit, an Euler path that is not a circuit, or neither? Click your answer.

|V| = 5|E| = 6

1Euler circuit
2Euler path, no circuit
3neither

6.Graph theoryHard

How many walks of length 2 go from D to F? 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 53 modulo 67: the number x with 0 < x < 67 and 53·x ≡ 1 (mod 67).

a = 53n = 67

53⁻¹ mod 67 =

8.Number theory & modular arithmeticHard

How many solutions N does 22x ≡ 6 (mod 34) have in {0, 1, …, 33}?

22x ≡ 6 (mod 34)

N =

3Solutions

1.Propositional logic & proofs

Answer: (r → p) ∧ (q → 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).

(r ∨ q) → p ≡ (r → p) ∧ (q → 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 | 0 0 0 1

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

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

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

Answer

(r → p) ∧ (q → p)

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

2.Propositional logic & proofs

Answer: a = 0, c = 1

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.

Premises and conclusion row by row

a = 1, c = 1: 1 0 | 0

a = 1, c = 0: 0 0 | 1

a = 0, c = 1: 1 1 | 0

a = 0, c = 0: 1 1 | 1

Counterexample

a = 0, c = 1

Answer

a = 0, c = 1

An argument with this form looks like a valid rule, but one row is enough to show that it is not.

3.Sets, relations & functions

Answer: |L − T| = 27

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|.

Regions

L ∩ T: 5

L − T: 32 − 5 = 27

T − L: 9 − 5 = 4

(L ∪ T)′: 41 − (27 + 4 + 5) = 5

Answer

|L − T| = 27

Answer

|L − T| = 27

4.Sets, relations & functions

Answer: injective, not surjective

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?

every element of B is hit at most once → injective

Surjective?

c receives no arrow → not surjective

Answer

injective, not surjective

Answer

injective, not surjective

5.Graph theory

Answer: Euler circuit

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.

Degrees

deg(A) = 2, deg(B) = 4, deg(C) = 2, deg(D) = 2, deg(E) = 2

Odd vertices

Euler circuit

Answer

Euler circuit

6.Graph theory

Answer: N = 1

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 1 0 0 0

B: 1 0 1 1 0 0

C: 1 1 0 0 1 0

D: 0 1 0 0 1 1

E: 0 0 1 1 0 1

F: 0 0 0 1 1 0

Common neighbours

(M²)_DF = 0·0 + 1·0 + 0·0 + 0·1 + 1·1 + 1·0 = 1

Answer

N = 1

7.Number theory & modular arithmetic

Answer: 53⁻¹ mod 67 = 43

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·53 (mod 67).

r = 67, t = 0

r = 53, q = 1, t = 1

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

r = 11, q = 1, t = 4

r = 3, q = 3, t = −5

r = 2, q = 1, t = 19

r = 1, q = 2, t = −24

Inverse

1 ≡ −24·53 (mod 67)

x = 43

check: 53·43 = 2279 = 34·67 + 1

Answer

53⁻¹ mod 67 = 43

8.Number theory & modular arithmetic

Answer: N = 2

Divide by the gcd

gcd(22, 34) = 2

11x ≡ 3 (mod 17)

Solve the reduced congruence

11⁻¹ ≡ 14 (mod 17) → x ≡ 8 (mod 17)

Solutions modulo 34

x ∈ {8, 25}

N = 2

Answer

N = 2

ExamProblems · examproblems.com/courses/discrete-mathematics