Discrete Structures (CSE2301)

Topic-wise Revision Notes and Practice

Workbook
Complete notes, worked examples, and practice problems with full solutions

How to use this workbook: study each unit’s definitions and laws first, then work through the
examples with paper and pen. Attempt every practice problem yourself before reading its
solution. Whenever a truth table appears, reproduce it yourself line by line — writing the
complete table is what earns full marks.

Unit 1. Set Theory and Set Identities

1.1 Core definitions
 A set is an unordered collection of distinct objects (elements). x ∈ A means x is an element
of A.
 A ⊆ B (subset): every element of A is also in B. A = B exactly when A ⊆ B and B ⊆ A —
this is how set equalities are proved.
 Union A ∪ B = {x : x ∈ A or x ∈ B}; Intersection A ∩ B = {x : x ∈ A and x ∈ B};
Difference A − B = {x : x ∈ A and x ∉ B}; Complement A′ = {x ∈ U : x ∉ A}.
 Power set P(A): the set of all subsets of A; if |A| = n then |P(A)| = 2ⁿ.
 Cartesian product A × B = {(a, b) : a ∈ A, b ∈ B}; |A × B| = |A|·|B|.

1.2 The standard set identities (learn to state and prove them)
 Commutative: A ∪ B = B ∪ A; A ∩ B = B ∩ A
 Associative: (A ∪ B) ∪ C = A ∪ (B ∪ C); (A ∩ B) ∩ C = A ∩ (B ∩ C)
 Distributive: A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C); A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)
 De Morgan: (A ∪ B)′ = A′ ∩ B′; (A ∩ B)′ = A′ ∪ B′
 Absorption: A ∪ (A ∩ B) = A; A ∩ (A ∪ B) = A
 Identity/Domination: A ∪ ∅ = A, A ∩ U = A, A ∪ U = U, A ∩ ∅ = ∅

Proof techniques. There are two standard proof techniques: (i) the element (double-inclusion)
argument — show each side is a subset of the other; (ii) the membership table — 1 means "x
belongs", 0 means "x does not belong", one row per case. Practise both.

1.3 Worked example — element-argument proof of a De Morgan law

Claim: (A ∪ B)′ = A′ ∩ B′.

(⊆) Let x ∈ (A ∪ B)′. Then x ∉ A ∪ B, so x is in neither A nor B; hence x ∈ A′ and x ∈ B′, i.e.
x ∈ A′ ∩ B′.

(⊇) Let x ∈ A′ ∩ B′. Then x ∉ A and x ∉ B, so x cannot belong to A ∪ B; hence x ∈ (A ∪ B)′.

Both inclusions hold, so the two sets are equal. ∎

1.4 Worked example — proof of the distributive law by membership table

Claim: A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C).

A B C B∩C A∪(B∩C A∪B A∪C (A∪B)∩(

) A∪C)
1 1 1 1 1 1 1 1
1 1 0 0 1 1 1 1
1 0 1 0 1 1 1 1
1 0 0 0 1 1 1 1
0 1 1 1 1 1 1 1
0 1 0 0 0 1 0 0
0 0 1 0 0 0 1 0
0 0 0 0 0 0 0 0
Columns 5 and 8 are identical in all eight rows, so the two sets are equal. ∎

1.5 Practice problems

Practice 1. Prove the absorption law A ∩ (A ∪ B) = A by the element argument.

so x ∈ A ∩ (A ∪ B). Hence equality. ∎

Solution. (⊆) If x ∈ A ∩ (A ∪ B) then in particular x ∈ A. (⊇) If x ∈ A then x ∈ A ∪ B as well,

Practice 2. Prove A − (B ∪ C) = (A − B) ∩ (A − C) using a membership table.

Solution. Full table over all eight cases:

A B C B∪C A−(B∪C) A−B A−C (A−B)∩(

A−C)
1 1 1 1 0 0 0 0
1 1 0 1 0 0 1 0
1 0 1 1 0 1 0 0
1 0 0 0 1 1 1 1
0 1 1 1 0 0 0 0
0 1 0 1 0 0 0 0
0 0 1 1 0 0 0 0
0 0 0 0 0 0 0 0
Columns 5 and 8 agree in every row, proving the identity. ∎

Practice 3. For A = {1, 2, 3}, B = {2, 3, 4}, C = {3, 5} inside U = {1, …, 6}, verify A ∩ (B ∪ C)
= (A ∩ B) ∪ (A ∩ C).

RHS = {2,3} ∪ {3} = {2, 3}. LHS = RHS ✓ (a verification on an example; the general proof
Solution. B ∪ C = {2, 3, 4, 5}; LHS = A ∩ {2,3,4,5} = {2, 3}. A ∩ B = {2, 3}; A ∩ C = {3};

uses either technique above).

Unit 2. Propositional and Predicate Logic
2.1 Core definitions
 Proposition: a declarative sentence that is either true or false. Connectives: ¬ (not), ∧ (and),
∨ (or), → (implies), ↔ (iff).
 Tautology: a compound proposition true under every truth assignment (e.g. p ∨ ¬p).
 Contradiction: false under every truth assignment (e.g. p ∧ ¬p). A contingency is neither.
 Logical equivalence: P ≡ Q when P and Q have identical truth values in every case
(equivalently, P ↔ Q is a tautology). Standard proof: a truth table whose final columns
coincide row by row.
 Well-formed formula (WFF): a string built by the formation rules — every variable is a
WFF; if α, β are WFFs so are ¬α, (α ∧ β), (α ∨ β), (α → β), (α ↔ β); nothing else is.
Example: ((p ∧ q) → r) is a WFF; (p ∧∨ q) is not.
 Satisfiable: at least one truth assignment makes the formula true; otherwise unsatisfiable.
Every contradiction is unsatisfiable.
 Predicate logic: predicates P(x) with quantifiers ∀x (for all), ∃x (there exists). Example: over
ℝ, ∀x (x² ≥ 0) is true; over ℤ, ∃x (x + 1 = 0) is true.
 Quantifier negation: ¬∀x P(x) ≡ ∃x ¬P(x); ¬∃x P(x) ≡ ∀x ¬P(x).

2.2 The key equivalences (memorise)

 De Morgan: ¬(p ∧ q) ≡ ¬p ∨ ¬q; ¬(p ∨ q) ≡ ¬p ∧ ¬q
 Implication law: p → q ≡ ¬p ∨ q; contrapositive: p → q ≡ ¬q → ¬p
 Double negation: ¬¬p ≡ p; Distributive: p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r) and dually
 Biconditional: p ↔ q ≡ (p → q) ∧ (q → p)

2.3 Worked example — De Morgan’s first law by truth table

Claim: ¬(p ∧ q) ≡ ¬p ∨ ¬q.

p q p∧q ¬(p∧q) ¬p ¬q ¬p∨¬q

T T T F F F F
T F F T F T T
F T F T T F T
F F F T T T T
The columns for ¬(p∧q) and ¬p∨¬q are identical, hence the formulas are logically equivalent. ∎

2.4 Worked example — De Morgan’s second law by truth table

Claim: ¬(p ∨ q) ≡ ¬p ∧ ¬q.

p q p∨q ¬(p∨q) ¬p ¬q ¬p∧¬q

T T T F F F F
T F T F F T F
F T T F T F F
F F F T T T T
The columns for ¬(p∨q) and ¬p∧¬q agree in all four rows — logically equivalent. ∎
2.5 Worked example — the implication law by truth table
Claim: (p → q) ≡ (¬p ∨ q).

p q p→q ¬p ¬p∨q
T T T F T
T F F F F
F T T T T
F F T T T
Columns 3 and 5 are identical — equivalent. ∎

2.6 Practice problems

Practice 1. Prove that q → p ≡ ¬p → ¬q by truth table.

Solution.

p q q→p ¬p ¬q ¬p→¬q
T T T F F T
T F T F T T
F T F T F F
F F T T T T
Columns q→p and ¬p→¬q match in every row — equivalent. ∎

Practice 2. Show that (p ∧ (p → q)) → q is a tautology (modus ponens in formula form).

Solution.

p q p→q p∧(p→q) (p∧(p→q))→q

T T T T T
T F F F T
F T T F T
F F T F T
The final column is T in every row — a tautology. ∎

Practice 3. Classify (p ∨ q) ∧ (¬p ∧ ¬q) as tautology, contradiction or contingency.

Solution.

p q p∨q ¬p∧¬q (p∨q)∧(¬p∧¬q)

T T T F F
T F T F F
F T T F F
F F F T F
False in every row — a contradiction (hence also unsatisfiable). ∎
Practice 4. Classify p → (p ∨ q) and p → ¬q.

Solution. p → (p ∨ q): if p is T then p∨q is T; if p is F the implication is vacuously T — every

row T, a tautology. p → ¬q: T when p = F, but F when p = T and q = T — a contingency. (Draw
the 4-row tables in your answer, as in the examples above.)

Practice 5. Write the negation of "∀x ∈ ℤ, if x is even then x² is even" in words and symbols.

Solution. ¬∀x (E(x) → E(x²)) ≡ ∃x (E(x) ∧ ¬E(x²)): "there exists an even integer whose square is
odd." (The original statement is true; its negation is false.)

Practice 6. Is (p ∨ q) ∧ ¬p satisfiable? Justify.

Solution. Yes. Take p = F, q = T: then p ∨ q = T and ¬p = T, so the whole formula is T.

Exhibiting one satisfying assignment is a complete justification.

Unit 3. Functions: Injective, Surjective, Bijective

3.1 Core definitions
 A function f : A → B assigns to every element of A exactly one element of B. A is the
domain, B the codomain.
 Injective (one-to-one): f(a₁) = f(a₂) implies a₁ = a₂ — different inputs never share an output.
 Surjective (onto): for every b ∈ B there is a ∈ A with f(a) = b — the range equals the
codomain.
 Bijective: both injective and surjective; exactly the bijections have inverses f ⁻¹.
 Finite-set method: list all images. No repeated image ⇒ injective; every codomain element
appears ⇒ surjective. If |A| = |B|, either property implies the other.

3.2 Worked example

Let g : {1, 2, 3, 4} → {w, x, y, z} with g(1) = y, g(2) = w, g(3) = z, g(4) = x. Is g a bijection?

Images: y, w, z, x — all distinct, so g is injective. The image set {w, x, y, z} is the whole

1, g⁻¹(z) = 3. ∎
codomain, so g is surjective. Hence g is a bijection, with inverse g ⁻¹(w) = 2, g ⁻¹(x) = 4, g ⁻¹(y) =

3.3 Practice problems

Practice 1. h : {a, b, c, d} → {1, 2, 3, 4} has h(a)=2, h(b)=4, h(c)=2, h(d)=1. Is h injective?
Surjective? Bijective?

Solution. h(a) = h(c) = 2 with a ≠ c: not injective. The value 3 is never attained: not surjective.
Hence not a bijection — quote one repeated value and one missed value for a complete
justification.

Practice 2. Show f : ℝ → ℝ, f(x) = 3x − 5, is a bijection and find f⁻¹.

= y. Bijective with f⁻¹(y) = (y + 5)/3. ∎
Solution. Injective: 3x₁ − 5 = 3x₂ − 5 ⇒ x₁ = x₂. Surjective: given y, x = (y + 5)/3 satisfies f(x)

Practice 3. Is f : ℤ → ℤ, f(x) = x² injective? Surjective?

Solution. Neither: f(−2) = f(2) = 4 breaks injectivity; no integer squares to −1, so not onto.

Unit 4. Counting: Product Rule, Pigeonhole, Permutations,

Combinations, Inclusion–Exclusion
4.1 The basic rules
 Product (multiplication) rule: a two-step task with m ways then n ways can be done in m·n
ways.
 Sum rule: m ways OR n disjoint alternative ways gives m + n ways.
 Pigeonhole principle: n + 1 or more objects in n boxes force some box to hold at least two.
Generalised: N objects in k boxes force a box with at least ⌈N/k⌉ objects.
 Permutations P(n, r) = n!/(n−r)!; Combinations C(n, r) = n!/(r!(n−r)!).
 Permutations of a multiset: n!/(n₁!n₂!…nₖ!) for repeated types.
 Stars and bars: n indistinguishable balls into k distinguishable bins: C(n + k − 1, k − 1).
 Inclusion–exclusion: |A ∪ B| = |A| + |B| − |A ∩ B|; for three sets add singles, subtract pairs,
add the triple.

4.2 Worked examples

(a) Licence plates, 3 letters then 3 digits: 26³·10³ = 17,576,000 (product rule).

(b) Among any 13 people two share a birth month: 13 objects, 12 boxes, pigeonhole.

(c) Strings from MISSISSIPPI (M×1, I×4, S×4, P×2, 11 letters): 11!/(4!·4!·2!) = 34,650.

4.3 Practice problems

Practice 1. How many different strings can be formed by reordering the letters of
MATHEMATICS?

Solution. 11 letters with M×2, A×2, T×2 (H, E, I, C, S once each): 11!/(2!·2!·2!) = 39,916,800/8
= 4,989,600.

Practice 2. A dealer gives hands of 5 cards to each of four players from a 52-card deck. In how
many ways?

Solution. Sequential combinations: C(52,5)·C(47,5)·C(42,5)·C(37,5) = 52!/(5!·5!·5!·5!·32!) — a

multinomial coefficient; the remaining 32 cards stay with the dealer. Leaving the answer in this
exact form is standard.

Practice 3. In how many ways can 10 identical chocolates be distributed among 4 children?

Solution. Stars and bars: C(10 + 4 − 1, 4 − 1) = C(13, 3) = 286.

Practice 4. Same, but every child gets at least one.

Solution. Hand each child one first, distribute the remaining 6 freely: C(6 + 4 − 1, 3) = C(9, 3) =
84.

Practice 5. How many bit strings of length ten either start with 1 or end with 01?

Solution. Start with 1: 2⁹ = 512. End with 01: 2⁸ = 256. Both: 2⁷ = 128. Inclusion–exclusion: 512
+ 256 − 128 = 640.

Practice 6. In a class of 150 students, 80 study Mathematics, 60 Physics, 25 both. How many
study neither?

Solution. |M ∪ P| = 80 + 60 − 25 = 115; neither = 150 − 115 = 35.

Practice 7. Show that among any 5 integers two leave the same remainder mod 4.

Solution. Only 4 remainders exist (0–3); five integers force a repeat by pigeonhole. ∎

Unit 5. Recurrence Relations

5.1 Core definitions
 A recurrence relation defines aₙ from earlier terms; linear with constant coefficients: a ₙ =
c₁aₙ₋₁ + … + cₖaₙ₋ₖ + F(n).
 Homogeneous: F(n) = 0 — e.g. aₙ = 5aₙ₋₁ − 6aₙ₋₂.
 Non-homogeneous (inhomogeneous): F(n) ≠ 0 — e.g. aₙ = 3aₙ₋₁ + 2ⁿ or aₙ = aₙ₋₁ + n.
General solution = homogeneous solution + one particular solution.

5.2 Solution method (linear homogeneous, constant coefficients)

 Step 1 — characteristic equation: substitute aₙ = rⁿ; for order 2: r² − c₁r − c₂ = 0.
 Step 2 — roots: distinct roots give aₙ = α₁r₁ⁿ + α₂r₂ⁿ; a double root r gives (α + βn)rⁿ.
 Step 3 — fit the initial conditions by solving the small linear system for the constants.
 Step 4 — verify against the initial terms and one extra term computed from the recurrence.

5.3 Worked example (second order, distinct roots)

Solve aₙ = aₙ₋₁ + 6aₙ₋₂, a₀ = 3, a₁ = 4.

Characteristic equation r² − r − 6 = 0 = (r − 3)(r + 2): roots 3, −2. General solution a ₙ = α·3ⁿ +

β·(−2)ⁿ.

n = 0: α + β = 3; n = 1: 3α − 2β = 4. Substituting β = 3 − α: 3α − 6 + 2α = 4 ⇒ α = 2, β = 1.

Answer: aₙ = 2·3ⁿ + (−2)ⁿ. Check: a₂ = 18 + 4 = 22; recurrence: 4 + 18 = 22 ✓

5.4 Practice problems

Practice 1. Solve aₙ = 3aₙ₋₁ − 2aₙ₋₂ with a₀ = 2, a₁ = 5.
3, α = −1. Answer: aₙ = 3·2ⁿ − 1. Check a₂ = 11 = 3·5 − 2·2 ✓
Solution. r² − 3r + 2 = (r − 1)(r − 2): roots 1, 2, so aₙ = α + β·2ⁿ. α + β = 2 and α + 2β = 5 give β =

Practice 2. Solve aₙ = 6aₙ₋₁ − 11aₙ₋₂ + 6aₙ₋₃ with a₀ = 2, a₁ = 5, a₂ = 15.

Solution. Characteristic r³ − 6r² + 11r − 6 = 0; r = 1 works, and factoring gives (r − 1)(r − 2)(r −
3). General: aₙ = α + β·2ⁿ + γ·3ⁿ.

System: α + β + γ = 2; α + 2β + 3γ = 5; α + 4β + 9γ = 15. Successive differences: β + 2γ = 3 and

2β + 6γ = 10 ⇒ β + 3γ = 5 ⇒ γ = 2, β = −1, α = 1.

Answer: aₙ = 1 − 2ⁿ + 2·3ⁿ. Check a₂ = 1 − 4 + 18 = 15 ✓; a₃ formula 47 = 90 − 55 + 12 ✓

Practice 3. Solve aₙ = 6aₙ₋₁ − 9aₙ₋₂ with a₀ = 1, a₁ = 6 (repeated root).

Answer: aₙ = (1 + n)·3ⁿ. Check a₂ = 27 = 36 − 9 ✓

Solution. r² − 6r + 9 = (r − 3)²: double root 3, so aₙ = (α + βn)·3ⁿ. α = 1; (1 + β)·3 = 6 ⇒ β = 1.

Practice 4. Solve the non-homogeneous relation aₙ = 3aₙ₋₁ + 2ⁿ with a₀ = 1.

aₙ = α·3ⁿ − 2ⁿ⁺¹; a₀ = 1 gives α = 3. Answer: aₙ = 3ⁿ⁺¹ − 2ⁿ⁺¹. Check a₁ = 5 = 3 + 2 ✓

Solution. Homogeneous part: α·3ⁿ. Particular try A·2ⁿ: 2A = 3A + 2 ⇒ A = −2, so −2ⁿ⁺¹. General

Unit 6. Algebraic Structures: Groups, Subgroups, Cyclic Groups

6.1 Core definitions
 Group (G, ∗): closure, associativity, identity e, inverse a⁻¹ for every a. Abelian if also
commutative.
 Examples: (ℤ, +) identity 0; (ℚ − {0}, ×) identity 1; (ℤₙ, +ₙ).
 Order of a group: |G|. Order of an element a: least positive k with aᵏ = e.
 Subgroup: subset that is itself a group under the same operation (contains e, closed under
operation and inverses). Example: even integers in (ℤ, +).
 Cyclic group: G = ⟨a⟩ = {aᵏ}; a is a generator; every cyclic group is abelian.

6.2 Worked example — the fourth roots of unity

Show G = {1, i, −1, −i} under multiplication is a cyclic group; find all generators.

Group check: products of fourth roots of unity are fourth roots of unity (closure); associativity
from ℂ; identity 1; inverses 1↔1, −1↔−1, i↔−i. |G| = 4.

only {1} and {1, −1}. Generators: i and −i. ∎ ({1, −1} is a subgroup of order 2.)
Powers of i: i, −1, −i, 1 — all of G, so G = ⟨i⟩ is cyclic. Similarly −i generates. 1 and −1 generate

6.3 Practice problems

Practice 1. Show (ℤ₆, +₆) is cyclic and list all generators.
Solution. Axioms hold (identity 0, inverse of k is 6 − k). Multiples of 1: 1,2,3,4,5,0 — everything
⇒ 1 generates; similarly 5. Multiples of 2, 3, 4 give proper subsets. Generators: 1 and 5 (in
general k generates ℤₙ iff gcd(k, n) = 1).

Practice 2. Give a subgroup of (ℤ₆, +₆) of order 3 and verify it.

H. Subgroup of order 3. ∎
Solution. H = {0, 2, 4}: contains 0; closed (2+4 ≡ 0, 2+2 = 4, 4+4 ≡ 2); inverses −2 ≡ 4, −4 ≡ 2 ∈

Practice 3. Find the order of every element of {1, i, −1, −i}.

Solution. ord(1) = 1, ord(−1) = 2, ord(i) = ord(−i) = 4 — each divides |G| = 4 (Lagrange).

Unit 7. Graph Theory

7.1 Core definitions and types of graphs
 Graph G = (V, E); degree deg(v) = number of incident edges; handshaking theorem: Σ deg(v)
= 2|E|.
 Simple graph (no loops/parallel edges); multigraph; directed graph; weighted graph.
 Complete graph Kₙ: all pairs joined, n(n−1)/2 edges (K₄ has 6).
 Bipartite graph and complete bipartite Kₘ,ₙ (example K₂,₃).
 Regular graph: all degrees equal k. C₅ is 2-regular; K₄ is 3-regular.
 Other standard families: cycle Cₙ, wheel Wₙ, hypercube Qₙ.

7.2 Matrix representations

Definitions. Adjacency matrix A (n×n): A[i][j] = 1 if ij is an edge (0 otherwise); symmetric for
undirected graphs. Incidence matrix M (n×m, vertices × edges): M[v][e] = 1 when e touches v;
every column has exactly two 1s (a loop counts 2).

 Adjacency — advantages: O(1) edge queries; Aᵏ counts k-step walks. Disadvantages: n²

space even for sparse graphs; parallel edges need integer entries.
 Incidence — advantages: natural for multigraphs and edge-based arguments. Disadvantages:
n·m space; adjacency queries require scanning columns.

7.3 Euler circuits and paths

 Euler circuit: closed walk using every edge exactly once; Euler path: open version.
 Theorem: connected multigraph has an Euler circuit ⇔ all vertex degrees are even; an Euler
path (not circuit) ⇔ exactly two odd-degree vertices.

Example: C₅ (all degrees 2) is its own Euler circuit. The Königsberg bridges graph has four odd
vertices — neither circuit nor path; this problem started graph theory.

7.4 Planar graphs

 Planar: drawable without edge crossings; a drawing has faces.
 Euler’s formula (connected planar): v − e + f = 2.
 Bounds: simple connected planar with v ≥ 3 ⇒ e ≤ 3v − 6; if additionally
triangle-free/bipartite ⇒ e ≤ 2v − 4.
 Kuratowski: a graph is non-planar iff it contains a subdivision of K₅ or K₃,₃.

7.5 Worked example — planarity checks

Decide whether K₅ and K₂,₃ are planar.

K₅: v = 5, e = 10; planarity would need e ≤ 3v − 6 = 9, but 10 > 9 ⇒ non-planar. ∎

K₂,₃: v = 5, e = 6; it satisfies the bipartite bound e ≤ 2v − 4 = 6 and admits a crossing-free

drawing ⇒ planar.

7.6 Practice problems

Practice 1. Is K₆ planar?

Solution. v = 6, e = 15 > 3·6 − 6 = 12 ⇒ non-planar (it also contains K₅).

Practice 2. Show K₄ is planar and verify Euler’s formula on your drawing.

f = 4 (three inner faces + outer): 4 − 6 + 4 = 2 ✓

Solution. Triangle with the fourth vertex inside joined to all corners — no crossings. v = 4, e = 6,

Practice 3. Write the adjacency and incidence matrices of the cycle C₄ (vertices 1–2–3–4–1).

Solution. Adjacency rows 1..4: (0,1,0,1), (1,0,1,0), (0,1,0,1), (1,0,1,0). Incidence with e₁={1,2},
e₂={2,3}, e₃={3,4}, e₄={4,1}: rows (1,0,0,1), (1,1,0,0), (0,1,1,0), (0,0,1,1); each column has
exactly two 1s.

Practice 4. Degrees (2, 2, 4, 4, 2), connected — Euler circuit? Degrees (3, 3, 2, 2)?

Solution. All even + connected ⇒ Euler circuit exists. Exactly two odd vertices ⇒ Euler path
between them, no circuit.

Practice 5. For which m, n is Kₘ,ₙ regular?

Solution. Degrees are n on one side and m on the other; regular exactly when m = n.

One-page Formula Recap

 Sets: distributive A∪(B∩C) = (A∪B)∩(A∪C); De Morgan (A∪B)′ = A′∩B′; prove by
double inclusion or membership table.
 Logic: ¬(p∧q) ≡ ¬p∨¬q; ¬(p∨q) ≡ ¬p∧¬q; p→q ≡ ¬p∨q ≡ ¬q→¬p;
tautology/contradiction/satisfiable via full truth table.
 Functions: injective (no repeats), surjective (nothing missed), bijective (both ⇒ inverse
exists).
 Counting: P(n,r) = n!/(n−r)!; C(n,r) = n!/(r!(n−r)!); multiset n!/(n₁!…nₖ!); stars & bars
C(n+k−1, k−1); |A∪B| = |A|+|B|−|A∩B|; pigeonhole ⌈N/k⌉.
 Recurrences: characteristic equation → roots → αr₁ⁿ + βr₂ⁿ (or (α+βn)rⁿ) → fit initial
conditions → verify.
 Groups: 4 axioms; cyclic = ⟨a⟩; k generates ℤₙ iff gcd(k, n) = 1; element order divides group
order.
 Graphs: Σdeg = 2e; Kₙ has n(n−1)/2 edges; Euler circuit ⇔ connected + all even degrees;
planar ⇒ e ≤ 3v−6 (bipartite 2v−4); v − e + f = 2; K₅, K₃,₃ minimal non-planar.