Discrete Mathematics

1. Propositional and Predicate Logic

1.1 Propositional Logic

A proposition is a statement that is either true or false. Propositional logic deals with Propositions and their combinations using logical connectives.

Basic connectives:

Truth tables. The implication $p \implies q$ is false only when $p$ is true and $q$ is false.

Logical equivalence. Two propositions are logically equivalent ($\equiv$) if they have the Same truth value for all assignments.

Important equivalences:

• $\neg(p \land q) \equiv \neg p \lor \neg q$ (De Morgan)
• $\neg(p \lor q) \equiv \neg p \land \neg q$ (De Morgan)
• $p \implies q \equiv \neg p \lor q$
• $p \iff q \equiv (p \implies q) \land (q \implies p)$
• $\neg(p \implies q) \equiv p \land \neg q$

1.2 Predicate Logic

Predicates extend propositional logic with variables and quantifiers.

• Universal quantifier: $\forall x\, P(x)$ — ”$P(x)$ holds for all $x$.”
• Existential quantifier: $\exists x\, P(x)$ — “there exists $x$ such that $P(x)$ holds.”

Negation of quantifiers:

$\neg \forall x\, P(x) \equiv \exists x\, \neg P(x)$

$\neg \exists x\, P(x) \equiv \forall x\, \neg P(x)$

Nested quantifiers must be read carefully. The order matters:

$\forall x\, \exists y\, P(x, y) \not\equiv \exists y\, \forall x\, P(x, y)$

The first says “for every $x$ there is a (possibly different) $y$.” The second says “there exists a Single $y$ that works for all $x$.“

1.3 Validity and Satisfiability

A formula is valid (a tautology) if it is true under all interpretations. A formula is satisfiable if it is true under at least one interpretation.

Theorem 1.1. A formula is valid if and only if its negation is unsatisfiable.

1.4 Truth Table Construction Methods

For a propositional formula with $n$ distinct variables, the truth table has $2^n$ rows (one per Assignment). Two systematic methods ensure no assignment is missed.

Method 1: Binary counting. Treat the first variable as the most significant bit. Enumerate all Binary $n$-tuples from $(0, \ldots, 0)$ to $(1, \ldots, 1)$. The first variable changes most slowly (only every $2^{n-1}$ rows), while the last variable alternates every row.

Method 2: Recursive splitting. For $n$ variables, the table splits into two blocks of $2^{n-1}$ Rows: the top block has the first variable as $T$The bottom as $F$. Recurse on the remaining $n - 1$ variables within each block.

Worked Example. Construct the truth table for $(p \implies q) \land (q \implies r)$.

Worked Example. Verify that hypothetical syllogism $(p \implies q) \land (q \implies r) \implies (p \implies r)$ is a tautology.

1.5 Natural Deduction

Natural deduction is a proof system that mirrors ordinary mathematical reasoning. Each connective Has introduction rules (how to derive a formula with that connective) and elimination rules (how to use a formula with that connective).

Rules of inference:

Square brackets $[A]$ denote an assumption that is discharged after the rule is applied.

Worked Example. Prove: $p \to q \vdash \neg q \to \neg p$ (contraposition).

Worked Example. Prove: $p \lor q, \neg p \vdash q$ (disjunctive syllogism).

Worked Example. Prove: $p \land (q \lor r) \vdash (p \land q) \lor (p \land r)$ (distribution).

:::caution Common Pitfall In natural deduction, always track which assumptions are discharged. A common mistake is to use a Discharged assumption in a later step. Each discharged assumption is only valid within the scope Indicated by the rule that discharges it. :::

1.6 CNF and DNF

A literal is a propositional variable or its negation. A clause is a disjunction of literals. A term (or cube) is a conjunction of literals.

• Disjunctive Normal Form (DNF): a disjunction of terms, e.g. $(p \land \neg q) \lor (\neg p \land r)$.
• Conjunctive Normal Form (CNF): a conjunction of clauses, e.g. $(p \lor \neg q) \land (\neg p \lor r)$.

Theorem 1.2. Every propositional formula is equivalent to a formula in CNF and to a formula in DNF.

Conversion to CNF:

1. Eliminate $\iff$ and $\implies$: $A \implies B \equiv \neg A \lor B$And $A \iff B \equiv (\neg A \lor B) \land (A \lor \neg B)$.
2. Push $\neg$ inward using De Morgan”s laws and double negation ($\neg\neg A \equiv A$) until every $\neg$ applies to a single variable.
3. Distribute $\lor$ over $\land$: $A \lor (B \land C) \equiv (A \lor B) \land (A \lor C)$.

Conversion to DNF: Same steps 1—2; in step 3 distribute $\land$ over $\lor$ instead.

Worked Example. Convert $(p \land q) \lor (\neg p \land r)$ to CNF.

Worked Example. Convert $\neg(p \implies q) \lor r$ to CNF.

:::caution Common Pitfall Distributing $\lor$ over $\land$ can cause exponential blowup. A DNF formula with $n$ terms can Produce up to $2^n$ clauses when converted to CNF. This exponential growth underlies the hardness Of many satisfiability problems. :::

1.7 Resolution

The resolution rule is a single inference rule that is refutation-complete for propositional Logic.

Resolution rule. From clauses $(A \lor x)$ and $(B \lor \neg x)$Derive the resolvent $(A \lor B)$Where $A$ and $B$ are (possibly empty) sets of literals and $x$ is a propositional Variable.

Resolution refutation. To show that clauses $\{C_1, \ldots, C_k\}$ entail clause $C$:

1. Add $\neg C$ to the clause set.
2. Repeatedly apply the resolution rule to derive new clauses.
3. If the empty clause $\bot$ is derived, the entailment holds.

Theorem 1.3 (Refutation completeness). If a set of clauses is unsatisfiable, the empty clause Can be derived by resolution.

Worked Example. Show that $\{p \lor q,\; \neg p \lor r,\; \neg q \lor \neg r\}$ entails $\neg r$.

1.8 The SAT Problem

The Boolean satisfiability problem (SAT) asks: given a propositional formula $\phi$Is there a Truth assignment that makes $\phi$ true?

Definition. An instance of SAT is a propositional formula. The answer is YES if $\phi$ is Satisfiable, NO otherwise.

k-SAT. A restricted version where the formula is in CNF and every clause has exactly $k$ Literals.

• 1-SAT: solvable in linear time (each clause is a single literal).
• 2-SAT: solvable in $O(n + m)$ time using the implication graph and strongly connected components, where $n$ is the number of variables and $m$ the number of clauses.
• 3-SAT: NP-complete (Cook—Levin theorem, 1971). This was the first problem proven NP-complete.

Theorem 1.4 (Cook—Levin). SAT is NP-complete. Consequently, 3-SAT is also NP-complete.

SAT solvers (DPLL, CDCL) are widely deployed in hardware verification, software model checking, and AI planning. Modern solvers routinely handle instances with millions of variables.

:::caution Common Pitfall Do not confuse satisfiability with validity. A formula is satisfiable if it is true under some Assignment; it is valid (a tautology) if true under all assignments. Checking validity is Co-NP-complete, not NP-complete. :::

2. Sets, Relations, and Functions

2.1 Sets

Basic operations:

• Union: $A \cup B = \\{x : x \in A \mathrm{ or} x \in B\\}$
• Intersection: $A \cap B = \\{x : x \in A \mathrm{ and} x \in B\\}$
• Difference: $A \setminus B = \\{x : x \in A \mathrm{ and} x \notin B\\}$
• Complement: $A^c = U \setminus A$ (where $U$ is the universal set)

De Morgan’s Laws:

$(A \cup B)^c = A^c \cap B^c, \quad (A \cap B)^c = A^c \cup B^c$

Power set: $\mathcal{P}(A) = \\{B : B \subseteq A\\}$. If $|A| = n$Then $|\mathcal{P}(A)| = 2^n$.

2.2 Relations

A binary relation $R$ from set $A$ to set $B$ is a subset of $A \times B$.

A relation $R$ on $A$ is:

• Reflexive: $\forall a \in A$, $(a,a) \in R$.
• Symmetric: $(a,b) \in R \implies (b,a) \in R$.
• Antisymmetric: $(a,b) \in R$ and $(b,a) \in R \implies a = b$.
• Transitive: $(a,b) \in R$ and $(b,c) \in R \implies$(a,c) \in R$.

Equivalence relation: reflexive, symmetric, transitive. Partitions the set into equivalence classes.

Partial order: reflexive, antisymmetric, transitive. Written $(A, \preceq)$.

A Hasse diagram is a graphical representation of a finite poset $(A, \preceq)$: an element $a$ Is drawn below $b$ whenever $a \prec b$ (i.e., $a \preceq b$ and $a \neq b$), and an edge is drawn From $a$ to $b$ whenever $b$ covers $a$ (there is no $c$ with $a \prec c \prec b$).

Worked Example. Show that $R$ on $\mathbb{{'}Z{}'}$ defined by $a\,R\,b$ iff $a \equiv b \pmod{5}$ is An equivalence relation. Describe the equivalence classes.

Worked Example. Let $\preceq$ be divisibility on $A = \\{1, 2, 3, 4, 6, 12\\}$: $a \preceq b$ iff $a \mid b$. Verify this is a partial order and identify the cover relations.

2.3 Functions

A function $f : A \to B$ is a relation where each $a \in A$ appears exactly once as a first element.

• Injective (one-to-one): $f(a_1) = f(a_2) \implies a_1 = a_2$.
• Surjective (onto): for every $b \in B$There exists $a \in A$ with $f(a) = b$.
• Bijective: both injective and surjective.

Theorem 2.1. If $A$ and $B$ are finite sets, $f : A \to B$ is:

• Injective if and only if $|A| \leq |B|$.
• Surjective if and only if $|A| \geq |B|$.
• Bijective if and only if $|A| = |B|$.

Theorem 2.2 (Pigeonhole Principle). If $|A| \gt{} |B|$Then no function $f : A \to B$ is injective. Equivalently, placing $n$ items into $m$ boxes with $n \gt{} m$ forces at least one box to contain at least $\lceil n/m \rceil$ items.

Function composition. Given $f : A \to B$ and $g : B \to C$The composition $g \circ f : A \to C$ is defined by $(g \circ f)(a) = g(f(a))$ for all $a \in A$.

Theorem 2.3. If $f : A \to B$ and $g : B \to C$ are both injective, then $g \circ f$ is injective.

Proof. Suppose $(g \circ f)(a_1) = (g \circ f)(a_2)$. Then $g(f(a_1)) = g(f(a_2))$. Since $g$ is Injective, $f(a_1) = f(a_2)$. Since $f$ is injective, $a_1 = a_2$. Hence $g \circ f$ is injective. $\blacksquare$

Theorem 2.4. If $f : A \to B$ and $g : B \to C$ are both surjective, then $g \circ f$ is surjective.

Proof. Let $c \in C$. Since $g$ is surjective, $\exists\, b \in B$ with $g(b) = c$. Since $f$ is Surjective, $\exists\, a \in A$ with $f(a) = b$. Then $(g \circ f)(a) = g(f(a)) = g(b) = c$. Hence $g \circ f$ is surjective. $\blacksquare$

Corollary 2.5. The composition of two bijections is a bijection.

A function $f : A \to B$ is invertible if there exists $f^{-1} : B \to A$ such that f^{-1} \circ f = \mathrm{id{}_A and f \circ f^{-1} = \mathrm{id{}_B. A function is invertible If and only if it is bijective.

2.4 Countability

Definition. A set $S$ is countable if it is finite or countably infinite. A set is countably infinite if there exists a bijection $\mathbb{{'}N{}'} \to S$. A set that is not countable Is uncountable.

Theorem 2.6. $\mathbb{{'}Z{}'}$ is countably infinite.

Proof. The function $f : \mathbb{{'}N{}'} \to \mathbb{{'}Z{}'}$ defined by

$f(n) = \begin{cases} n/2 & \mathrm{if}\; n\; \mathrm{is}\; even \\ -(n+1)/2 & \mathrm{if}\; n\; \mathrm{is}\; odd \end{cases}$

Is a bijection, enumerating $0, -1, 1, -2, 2, -3, 3, \ldots$ $\blacksquare$

Theorem 2.7. $\mathbb{{'}Q{}'}$ is countably infinite.

Proof. Every positive rational can be written as $p/q$ with $p, q \in \mathbb{{'}N{}'}^+$. Arrange the Pairs $(p, q)$ in an infinite grid and traverse them diagonally:

$1/1,\; 1/2,\; 2/1,\; 3/1,\; 1/3,\; 1/4,\; 2/3,\; 3/2,\; 4/1, \ldots$

Skipping duplicates (where $p/q = p'/q'$ in reduced form) yields an enumeration of $\mathbb{{'}Q{}'}^+$. Extending with negatives and zero gives an enumeration of $\mathbb{{'}Q{}'}$. $\blacksquare$

Theorem 2.8 (Cantor, 1891). $\mathbb{{'}R{}'}$ is uncountable.

Proof (Diagonal argument). Suppose for contradiction that $\mathbb{{'}R{}'}$ is countable. Then the Interval $[0, 1)$ can be listed as $r_1, r_2, r_3, \ldots$ where each $r_i$ has a unique decimal Expansion $r_i = 0.d_{i1}d_{i2}d_{i3}\ldots$ with each $d_{ij} \in \\{0, 1, \ldots, 9\\}$ (choosing the expansion that does not end in all 9s to avoid dual representations).

Define $s = 0.s_1 s_2 s_3 \ldots$ by

$s_i = \begin{cases} 5 & \mathrm{if}\; d_{ii} \neq 5 \\ 6 & \mathrm{if}\; d_{ii} = 5 \end{cases}$

Then $s \in [0, 1)$ and $s$ differs from $r_i$ in the $i$-th decimal place for every $i$ So $s \notin \\{r_1, r_2, \ldots\\}$Contradicting the assumption that the list was complete. Therefore $\mathbb{{'}R{}'}$ is uncountable. $\blacksquare$

3. Proof Techniques

3.1 Direct Proof

To prove $P \implies Q$: assume $P$Derive $Q$ by a chain of logical deductions.

Example. Prove: if $n$ is odd, then $n^2$ is odd.

Proof. Let $n = 2k + 1$. Then $n^2 = (2k+1)^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1$Which is odd. $\blacksquare$

Worked Example. Prove: the sum of any two rational numbers is rational.

3.2 Proof by Contrapositive

To prove $P \implies Q$: prove $\neg Q \implies \neg P$ instead.

Example. Prove: if $n^2$ is even, then $n$ is even.

Proof. Contrapositive: if $n$ is odd, then $n^2$ is odd. This was proved above. $\blacksquare$

Worked Example. Prove: if $3n + 2$ is odd, then $n$ is odd.

3.3 Proof by Contradiction

To prove $P$: assume $\neg P$ and derive a contradiction.

Example (Euclid). There are infinitely many primes.

Proof. Suppose there are finitely many primes $p_1, p_2, \ldots, p_n$. Consider $N = p_1 p_2 \cdots p_n + 1$. $N$ is not divisible by any $p_i$ (it leaves remainder 1). So $N$ is either prime itself or has a prime Factor not in the list. Either way, the list was incomplete. Contradiction. $\blacksquare$

Worked Example. Prove: $\sqrt{2}$ is irrational.

3.4 Mathematical Induction

Principle of Mathematical Induction. To prove $P(n)$ for all $n \geq n_0$:

1. Base case: Prove $P(n_0)$.
2. Inductive step: Prove $P(k) \implies P(k+1)$ for all $k \geq n_0$.

Strong Induction. The inductive step assumes $P(n_0), P(n_0+1), \ldots, P(k)$ to prove $P(k+1)$.

Example. Prove: $\sum_{i=1}^{n} i = n(n+1)/2$ for all $n \geq 1$.

Proof. Base case: $n = 1$: $1 = 1 \cdot 2 / 2$. True.

Inductive step: Assume $\sum_{i=1}^{k} i = k(k+1)/2$. Then

$\sum_{i=1}^{k+1} i = \frac{k(k+1)}{2} + (k+1) = \frac{k(k+1) + 2(k+1)}{2} = \frac{(k+1)(k+2)}{2}$

$\blacksquare$

Worked Example. Prove by strong induction: every integer $n \geq 2$ can be factored into primes.

Worked Example. Prove: $\sum_{i=0}^{n} 2^i = 2^{n+1} - 1$ for all $n \geq 0$.

3.5 Structural Induction

For recursively defined structures (lists, trees, formulas), prove a property by induction on the Structure:

1. Base cases (empty list, leaf node, atomic formula).
2. Inductive cases (cons, node with children, compound formula).

3.6 The Well-Ordering Principle

Well-Ordering Principle (WOP). Every nonempty set of nonnegative integers has a least element.

Theorem 3.1. The Well-Ordering Principle is equivalent to the Principle of Mathematical Induction.

Proof (WOP implies induction). Let $P(n)$ be a property with $P(0)$ true and $P(k) \implies P(k+1)$. Suppose for contradiction that $P(n)$ fails for some $n \geq 0$. Let S = \\{n \geq 0 : P(n)\; \mathrm{is\; false{}\\}. By assumption $S \neq \emptyset$So by WOP, $S$ has a least Element $m$. Since $P(0)$ is true, $m \geq 1$. Then $P(m - 1)$ is true (by minimality of $m$), And $P(m - 1) \implies P(m)$ by the inductive hypothesis, so $P(m)$ is true, contradicting $m \in S$. Therefore $S = \emptyset$ and $P(n)$ holds for all $n \geq 0$.

Proof (induction implies WOP). Let $S \subseteq \mathbb{{'}N{}'}$ be nonempty. We prove by induction that If $S \cap \\{0, 1, \ldots, n\\} \neq \emptyset$Then $S$ has a least element. For $n = 0$, $S$ Contains $0$Which is the least element. Assume the claim for $n = k$. If $0 \in S \cap \\{0, \ldots, k+1\\}$ Then $0$ is the least element. Otherwise $S \cap \\{0, \ldots, k+1\\} = S \cap \\{1, \ldots, k+1\\}$And by The induction hypothesis applied to the shifted set, a least element exists. $\blacksquare$

Worked Example. Use the WOP to prove that every $n \geq 1$ can be written as a sum of distinct Powers of 2.

4. Combinatorics

4.1 Counting Principles

Rule of Sum. If task $A$ can be done in $m$ ways and task $B$ in $n$ ways, and they cannot both be Done, then $A$ or $B$ can be done in $m + n$ ways.

Rule of Product. If task $A$ can be done in $m$ ways and task $B$ in $n$ ways independently, then $A$ and $B$ together can be done in $mn$ ways.

4.2 Permutations and Combinations

Permutations: $P(n, r) = n! / (n-r)!$ — ordered arrangements of $r$ items from $n$.

Combinations: $\binom{n}{r} = \frac{n!}{r!(n-r)!}$ — unordered selections of $r$ items from $n$.

Theorem 4.1 (Binomial Theorem).

$(x + y)^n = \sum_{r=0}^{n} \binom{n}{r} x^{n-r} y^r$

Theorem 4.2 (Pascal’s Identity). $\binom{n}{r} = \binom{n-1}{r} + \binom{n-1}{r-1}$

Proof. Every $r$-subset of $\\{1, \ldots, n\\}$ either contains $n$ (giving $\binom{n-1}{r-1}$ ways To choose the remaining $r-1$) or does not contain $n$ (giving $\binom{n-1}{r}$ ways to choose all $r$ From $\\{1, \ldots, n-1\\}$). $\blacksquare$

4.3 Inclusion-Exclusion Principle

Theorem 4.3 (Inclusion-Exclusion). For finite sets $A_1, \ldots, A_n$:

$\left|\bigcup_{i=1}^{n} A_i\right| = \sum_i |A_i| - \sum_{i \lt j} |A_i \cap A_j| + \sum_{i \lt j \lt k} |A_i \cap A_j \cap A_k| - \cdots + (-1)^{n+1}|A_1 \cap \cdots \cap A_n|$

Proof (for two sets). Every element of $A_1 \cup A_2$ is in $A_1$ or $A_2$ or both. Counting $|A_1| + |A_2|$ counts elements in $A_1 \cap A_2$ twice, so we subtract $|A_1 \cap A_2|$ once: $|A_1 \cup A_2| = |A_1| + |A_2| - |A_1 \cap A_2|$.

For the general case, an element in exactly $t$ of the sets is counted $\binom{t}{1} - \binom{t}{2} + \binom{t}{3} - \cdots = 1 - (1-1)^t = 1$ time, which is correct. $\blacksquare$

Worked Example. How many integers from 1 to 1000 are not divisible by 2, 3, or 5?

Let $A_2$ = multiples of 2, $A_3$ = multiples of 3, $A_5$ = multiples of 5.

$|A_2| = 500$, $|A_3| = 333$, $|A_5| = 200$.

$|A_2 \cap A_3| = 166$, $|A_2 \cap A_5| = 100$, $|A_3 \cap A_5| = 66$.

$|A_2 \cap A_3 \cap A_5| = 33$.

$|A_2 \cup A_3 \cup A_5| = 500 + 333 + 200 - 166 - 100 - 66 + 33 = 734$.

Not divisible by 2, 3, or 5: $1000 - 734 = 266$. $\blacksquare$

Worked Example. How many integers from 1 to 500 are divisible by 3 or 7 but not by 5?