Discrete Mathematics Review

This review pulls together everything from the Discrete Mathematics section. Use it to test yourself across all five areas before moving on.

Every symbol used in this section, in one place.

• A proposition has a definite truth value. Predicates with free variables do not.
• Connectives: $\neg p$ (not), $p \wedge q$ (and, true only when both are), $p \vee q$ (inclusive or, true when at least one is)
• A truth table with $n$ propositions needs $2^n$ rows
• Tautology: true in every row. Contradiction: false in every row.
• De Morgan’s laws: $\neg(p \wedge q) \equiv \neg p \vee \neg q$ and $\neg(p \vee q) \equiv \neg p \wedge \neg q$. Push the negation in, flip the connective.

• $p \rightarrow q$ is false only when $p$ is true and $q$ is false
• $p \rightarrow q \equiv \neg p \vee q$, so $\neg(p \rightarrow q) \equiv p \wedge \neg q$
• Contrapositive $\neg q \rightarrow \neg p$ is equivalent to the original
• Converse $q \rightarrow p$ and inverse $\neg p \rightarrow \neg q$ are not equivalent to it
• ”$p$ only if $q$” and ”$q$ is necessary for $p$” both mean $p \rightarrow q$
• $p \leftrightarrow q \equiv (p \rightarrow q) \wedge (q \rightarrow p)$, so proving it takes two proofs

• $\forall x \, P(x)$: hard to prove, disproved by one counterexample
• $\exists x \, P(x)$: proved by one example, hard to disprove
• $\neg \forall x \, P(x) \equiv \exists x \, \neg P(x)$ and $\neg \exists x \, P(x) \equiv \forall x \, \neg P(x)$
• Mixed quantifier order matters: $\forall x \exists y$ lets $y$ depend on $x$; $\exists y \forall x$ demands one fixed $y$

• Unordered, no duplicates. $\{1,2,2,3\} = \{1,2,3\}$
• $\in$ compares object to set; $\subseteq$ compares set to set
• $\emptyset \subseteq A$ always. $A = B$ iff $A \subseteq B$ and $B \subseteq A$
• $|\mathcal{P}(A)| = 2^{|A|}$, and $|A \times B| = |A| \cdot |B|$
• Operations: $A \cup B$, $A \cap B$, $A - B$, $\bar{A}$, $A \oplus B$
• Inclusion-exclusion: $|A \cup B| = |A| + |B| - |A \cap B|$, and for three sets add singles, subtract pairs, add the triple

• Direct: assume $p$, unfold definitions ($n = 2k$ for even, $n = 2k+1$ for odd, $b = ak$ for $a \mid b$), derive $q$
• Counterexample: one case where $p$ holds and $q$ fails disproves an implication
• Contrapositive: assume $\neg q$, derive $\neg p$. Best when the hypothesis is about a squared quantity
• Contradiction: assume $p \wedge \neg q$, derive an impossibility. Best for non-existence and irrationality claims
• Induction: base case plus inductive step. Both required. Strong induction assumes all cases up to $k$

• Multiplication principle (and, steps in sequence): multiply
• Addition principle (or, mutually exclusive alternatives): add
• With repetition: $n^k$. Without: $n(n-1)\cdots(n-k+1)$
• Complement rule for “at least one”: total minus none
• Permutations (order matters): $P(n,r) = \dfrac{n!}{(n-r)!}$
• Repeated items: $\dfrac{n!}{n_1! \, n_2! \cdots n_k!}$. Circular: $(n-1)!$
• Combinations (order does not matter): $\binom{n}{r} = \dfrac{n!}{r!(n-r)!}$
• Symmetry: $\binom{n}{r} = \binom{n}{n-r}$. Sum over all $r$: $2^n$
• Binomial theorem: coefficient of $x^{n-r}y^r$ in $(x+y)^n$ is $\binom{n}{r}$
• Pigeonhole: $n$ objects in $k$ boxes forces $\lceil n/k \rceil$ in some box. To guarantee $m$ in a box, take $k(m-1)+1$

• $G = (V,E)$. Handshake theorem: $\sum \deg(v) = 2|E|$, so the count of odd-degree vertices is even
• $K_n$ has $\binom{n}{2}$ edges, each vertex of degree $n-1$
• Bipartite iff no odd cycle
• Path: no repeated vertex. Trail: no repeated edge. Cycle: closed path
• Bridge iff the edge lies on no cycle
• Euler (every edge once): circuit iff all degrees even; path iff exactly two odd
• Hamilton (every vertex once): no simple test, NP-complete
• Tree: connected, acyclic, $|E| = |V| - 1$, unique path between every pair
• Balanced binary tree of $n$ vertices has height about $\log_2 n$
• MST: Kruskal sorts edges globally and skips cycles; Prim grows one tree outward

• Reflexive, symmetric, antisymmetric, transitive
• Equivalence relation = reflexive + symmetric + transitive, and it partitions the set
• Partial order = reflexive + antisymmetric + transitive, and it permits incomparable pairs
• Injective: nothing hit twice. Surjective: nothing missed. Bijective: both, and only these have inverses
• $a \equiv b \pmod n$ iff $n \mid (a-b)$. Congruence mod $n$ is an equivalence relation with $n$ classes
• Addition, subtraction, multiplication, and powers all respect congruence, so reduce early
• Division needs a modular inverse, which exists iff $\gcd(a,n) = 1$
• Fermat’s little theorem: for prime $p$ with $p \nmid a$, $a^{p-1} \equiv 1 \pmod p$

Example 1: Negate a compound statement.

Negate: “If the build passes and the tests are green, then we deploy.”

Let $p$ = build passes, $q$ = tests green, $r$ = we deploy. The statement is $(p \wedge q) \rightarrow r$.

$$\neg\big((p \wedge q) \rightarrow r\big) \equiv (p \wedge q) \wedge \neg r$$

“The build passes, the tests are green, and we do not deploy.”

Example 2: Quantifier negation.

Negate: $\forall x \exists y \, (x \cdot y = 1)$ over the real numbers.

$$\exists x \forall y \, (x \cdot y \neq 1)$$

The negation is true, witnessed by $x = 0$, since $0 \cdot y = 0$ for every $y$. So the original statement is false.

Example 3: Inclusion-exclusion.

Of 200 surveyed users, 120 use the mobile app, 90 use the desktop app, and 45 use both. How many use neither?

$$|M \cup D| = 120 + 90 - 45 = 165$$ $$200 - 165 = 35$$

Example 4: Contrapositive proof.

Claim. For integers $n$, if $n^2 - 6n + 5$ is even, then $n$ is odd.

Proof by contrapositive. Assume $n$ is even, so $n = 2k$.

$$n^2 - 6n + 5 = 4k^2 - 12k + 5 = 2(2k^2 - 6k + 2) + 1$$

That’s odd. So an even $n$ produces an odd value, and the contrapositive holds. ∎

Example 5: Induction.

Claim. $1 + 3 + 5 + \cdots + (2n-1) = n^2$ for all $n \geq 1$.

Base case: $n=1$. Left side is 1, right side is $1^2 = 1$. ✓

Inductive step: Assume $1 + 3 + \cdots + (2k-1) = k^2$. Then

$$1 + 3 + \cdots + (2k-1) + (2k+1) = k^2 + 2k + 1 = (k+1)^2$$

By induction the formula holds for all $n \geq 1$. ∎

Example 6: Mixed counting.

A team of 5 is chosen from 8 engineers and 6 designers, and must include at least 1 designer. How many teams?

Complement rule. Total teams:

$$\binom{14}{5} = 2002$$

Teams with no designer, all engineers:

$$\binom{8}{5} = 56$$ $$2002 - 56 = 1946$$

Example 7: Permutation with repeats.

How many distinct arrangements of the letters in ASSESSES?

8 letters: A (1), S (5), E (2).

$$\frac{8!}{1! \, 5! \, 2!} = \frac{40320}{240} = 168$$

Example 8: Pigeonhole.

How many cards must you draw from a standard 52-card deck to guarantee 3 of the same suit?

4 suits, want 3 in one. Worst case is 2 of each suit:

$$4(3-1) + 1 = 9$$

Example 9: Graph analysis.

A connected graph has degrees 3, 3, 4, 4, 2. Edges? Euler circuit? Euler path? Tree?

$$|E| = \frac{3+3+4+4+2}{2} = \frac{16}{2} = 8$$

Two odd degrees (the 3’s), so no Euler circuit but an Euler path exists between them. Not a tree, since a tree on 5 vertices would need 4 edges, not 8.

Example 10: Kruskal’s algorithm.

Vertices $P,Q,R,S$. Edges: $PQ=4$, $PR=1$, $PS=6$, $QR=2$, $QS=3$, $RS=5$.

Sorted: $PR(1)$, $QR(2)$, $QS(3)$, $PQ(4)$, $RS(5)$, $PS(6)$.

1. $PR(1)$ - add
2. $QR(2)$ - add
3. $QS(3)$ - add. Now 3 edges for 4 vertices, done.

$$\text{MST} = \{PR, QR, QS\}, \quad \text{weight} = 6$$

Example 11: Modular arithmetic.

Compute $5^{30} \bmod 13$.

13 is prime and $13 \nmid 5$, so Fermat gives $5^{12} \equiv 1 \pmod{13}$. Reduce the exponent mod 12:

$$30 = 2 \cdot 12 + 6 \quad \Longrightarrow \quad 5^{30} \equiv 5^6 \pmod{13}$$ $$5^2 = 25 \equiv 12 \equiv -1 \pmod{13}$$ $$5^6 = (5^2)^3 \equiv (-1)^3 = -1 \equiv 12 \pmod{13}$$

Example 12: Classify a relation.

Is “has the same number of characters as” on a set of strings an equivalence relation?

• Reflexive: every string has its own length. ✓
• Symmetric: length equality goes both ways. ✓
• Transitive: equal lengths chain. ✓

Yes, and its equivalence classes group strings by length.