Discrete Mathematics Syllabus

State the Hypothetical Syllogism rule of inference.

From $p \to q$ and $q \to r$, conclude $p \to r$.

State the Disjunctive Syllogism rule of inference.

From $p \lor q$ and $\neg p$, conclude $q$.

Name and state the rules of inference for Addition and Simplification.

Addition: from $p$ conclude $p \lor q$. Simplification: from $p \land q$ conclude $p$.

Describe a direct proof of $p \to q$.

Assume $p$ is true, then use axioms, definitions, and prior theorems with valid inference to derive that $q$ must also be true.

Describe proof by contraposition and when it is useful.

To prove $p \to q$, instead prove the equivalent contrapositive $\neg q \to \neg p$ by a direct proof. It is useful when assuming $\neg q$ gives a more workable starting point than assuming $p$.

Describe proof by contradiction.

To prove a proposition $p$, assume $\neg p$ is true and derive a contradiction (something of the form $r \land \neg r$). This shows $\neg p$ is false, so $p$ is true.

What is a proof by cases (exhaustive proof)?

When the hypothesis splits into finitely many cases whose disjunction covers all possibilities, prove the conclusion separately in each case; if it holds in every case, it holds overall.

Using set-builder notation, define the union $A \cup B$ and intersection $A \cap B$.

$A \cup B = \{x \mid x \in A \lor x \in B\}$ and $A \cap B = \{x \mid x \in A \land x \in B\}$.

Define the set difference $A \setminus B$ and the complement $\overline{A}$.

$A \setminus B = \{x \mid x \in A \land x \notin B\}$; the complement $\overline{A} = \{x \in U \mid x \notin A\} = U \setminus A$, where $U$ is the universal set.

What is the power set of a set $A$, and how many elements does it have if $|A| = n$?

The power set $\mathcal{P}(A)$ is the set of all subsets of $A$. If $|A| = n$ then $|\mathcal{P}(A)| = 2^{n}$.

State De Morgan's laws for sets.

$\overline{A \cup B} = \overline{A} \cap \overline{B}$ and $\overline{A \cap B} = \overline{A} \cup \overline{B}$.

Define the Cartesian product $A \times B$ and give its cardinality.

$A \times B = \{(a,b) \mid a \in A \land b \in B\}$, the set of ordered pairs. If $|A| = m$ and $|B| = n$, then $|A \times B| = mn$.

State the inclusion–exclusion formula for $|A \cup B|$.

$|A \cup B| = |A| + |B| - |A \cap B|$.

Define a function $f: A \to B$, including domain, codomain, and range.

A function assigns to each element of the domain $A$ exactly one element of the codomain $B$. The range is $\{f(a) \mid a \in A\} \subseteq B$, the set of actual output values.

Define an injective (one-to-one) function.

$f$ is injective if $f(a) = f(b)$ implies $a = b$; equivalently, distinct inputs map to distinct outputs.

Define a surjective (onto) function.

$f: A \to B$ is surjective if for every $b \in B$ there exists $a \in A$ with $f(a) = b$; that is, the range equals the codomain.

Define a bijection and state when a function is invertible.

A bijection is a function that is both injective and surjective. A function $f$ has an inverse $f^{-1}$ if and only if it is a bijection.

What is a geometric sequence, and what is the sum of the finite geometric series $\sum_{k=0}^{n} ar^{k}$?

A geometric sequence has the form $a, ar, ar^{2}, \dots$ with common ratio $r$. For $r \neq 1$: $$\sum_{k=0}^{n} ar^{k} = \frac{a(r^{n+1} - 1)}{r - 1}.$$

Give the closed form for $\sum_{k=1}^{n} k$ and $\sum_{k=1}^{n} k^{2}$.

$\sum_{k=1}^{n} k = \dfrac{n(n+1)}{2}$ and $\sum_{k=1}^{n} k^{2} = \dfrac{n(n+1)(2n+1)}{6}$.

What does it mean for a set to be countably infinite?

A set is countably infinite if there exists a bijection between it and the set of positive integers $\mathbb{Z}^{+}$; its cardinality is denoted $\aleph_{0}$. Examples include $\mathbb{Z}$ and $\mathbb{Q}$.

Is the set of real numbers $\mathbb{R}$ countable or uncountable, and how is this shown?

$\mathbb{R}$ is uncountable. This is proved by Cantor's diagonalization argument, which shows no bijection with $\mathbb{Z}^{+}$ can exist.

What does it mean for two sets $A$ and $B$ to have the same cardinality?

$A$ and $B$ have the same cardinality, written $|A| = |B|$, if there exists a bijection $f: A \to B$.

State the Schröder–Bernstein theorem.

If there exist injections $f: A \to B$ and $g: B \to A$, then $|A| = |B|$ (a bijection between $A$ and $B$ exists).

What is an algorithm, and what are its key required properties?

An algorithm is a finite sequence of precise steps for solving a problem. Key properties: input, output, definiteness (each step precisely defined), correctness, finiteness (it terminates), effectiveness, and generality.

Give the formal definition of "$f(x)$ is $O(g(x))$" (Big-O notation).

$f(x)$ is $O(g(x))$ if there exist constants $C > 0$ and $k$ such that $|f(x)| \leq C\,|g(x)|$ for all $x > k$. It gives an asymptotic upper bound.

Contrast Big-O, Big-Omega, and Big-Theta.

$O(g)$ is an asymptotic upper bound; $\Omega(g)$ is an asymptotic lower bound; $\Theta(g)$ is a tight bound, meaning $f$ is both $O(g)$ and $\Omega(g)$.

Order these complexity classes from slowest-growing to fastest-growing: $O(n)$, $O(2^{n})$, $O(\log n)$, $O(n^{2})$, $O(n \log n)$, $O(1)$, $O(n!)$.

$O(1) < O(\log n) < O(n) < O(n \log n) < O(n^{2}) < O(2^{n}) < O(n!)$.

What is the worst-case time complexity of linear search and of binary search on a list of $n$ elements?

Linear search: $O(n)$. Binary search (on a sorted list): $O(\log n)$.

What is a recurrence relation, and what two parts define a sequence recursively?

A recurrence relation expresses each term $a_{n}$ using previous terms. A recursive definition needs a base case (initial conditions) and a recursive step. Example: the Fibonacci numbers $F_{n} = F_{n-1} + F_{n-2}$ with $F_{0}=0,\ F_{1}=1$.

For divide-and-conquer recurrences $T(n) = aT(n/b) + f(n)$, what is the solution of $T(n) = 2T(n/2) + O(n)$ (merge sort)?

By the Master Theorem, compare $f(n)$ with $n^{\log_{b} a}$. Here $\log_{2} 2 = 1$ and $f(n) = \Theta(n)$ matches $n^{1}$, giving $T(n) = \Theta(n \log n)$.