Discrete Mathematics

Cheatsheet Content

### Logic and Proofs - **Proposition:** A declarative sentence that is either true or false, but not both. - **Truth Table:** A table showing all possible truth values of a propositional form. - **Logical Equivalence:** Two propositional forms $P$ and $Q$ are logically equivalent, denoted $P \equiv Q$, if they have the same truth values for all possible assignments of truth values to their variables. #### Logical Equivalences - **Commutative Laws:** - $p \wedge q \equiv q \wedge p$ - $p \vee q \equiv q \vee p$ - **Associative Laws:** - $(p \wedge q) \wedge r \equiv p \wedge (q \wedge r)$ - $(p \vee q) \vee r \equiv p \vee (q \vee r)$ - **Distributive Laws:** - $p \wedge (q \vee r) \equiv (p \wedge q) \vee (p \wedge r)$ - $p \vee (q \wedge r) \equiv (p \vee q) \wedge (p \vee r)$ - **De Morgan's Laws:** - $\neg(p \wedge q) \equiv \neg p \vee \neg q$ - $\neg(p \vee q) \equiv \neg p \wedge \neg q$ - **Implication Equivalence:** $p \rightarrow q \equiv \neg p \vee q$ - **Contrapositive:** $p \rightarrow q \equiv \neg q \rightarrow \neg p$ #### Rules of Inference - **Modus Ponens:** $p \rightarrow q$ $p$ $\therefore q$ - **Modus Tollens:** $p \rightarrow q$ $\neg q$ $\therefore \neg p$ - **Hypothetical Syllogism:** $p \rightarrow q$ $q \rightarrow r$ $\therefore p \rightarrow r$ - **Disjunctive Syllogism:** $p \vee q$ $\neg p$ $\therefore q$ #### Proof Techniques - **Direct Proof:** To prove $P \rightarrow Q$, assume $P$ is true and show that $Q$ must also be true. - **Example:** Prove that if $n$ is an even integer, then $n^2$ is an even integer. - **Proof:** Assume $n$ is an even integer. By definition, $n = 2k$ for some integer $k$. - Then $n^2 = (2k)^2 = 4k^2 = 2(2k^2)$. - Since $2k^2$ is an integer, $n^2$ is an even integer. Q.E.D. - **Proof by Contraposition:** To prove $P \rightarrow Q$, prove its contrapositive $\neg Q \rightarrow \neg P$. - **Example:** Prove that if $n^2$ is even, then $n$ is even. - **Proof:** We prove the contrapositive: if $n$ is odd, then $n^2$ is odd. - Assume $n$ is an odd integer. By definition, $n = 2k + 1$ for some integer $k$. - Then $n^2 = (2k + 1)^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1$. - Since $2k^2 + 2k$ is an integer, $n^2$ is an odd integer. Q.E.D. - **Proof by Contradiction:** To prove $P$, assume $\neg P$ is true and derive a contradiction. - **Example:** Prove that $\sqrt{2}$ is irrational. - **Proof:** Assume, for the sake of contradiction, that $\sqrt{2}$ is rational. - Then $\sqrt{2} = \frac{a}{b}$ for some integers $a, b$ with $b \neq 0$ and $\frac{a}{b}$ is in simplest form (i.e., $a$ and $b$ have no common factors other than 1). - Squaring both sides gives $2 = \frac{a^2}{b^2}$, so $2b^2 = a^2$. - This implies $a^2$ is even. By the previous example (proof by contraposition), if $a^2$ is even, then $a$ is even. - So, $a = 2k$ for some integer $k$. - Substituting this into $2b^2 = a^2$: $2b^2 = (2k)^2 = 4k^2$. - Dividing by 2 gives $b^2 = 2k^2$. - This implies $b^2$ is even, and thus $b$ is even. - Since both $a$ and $b$ are even, they both have a common factor of 2. This contradicts our assumption that $\frac{a}{b}$ is in simplest form. - Therefore, our initial assumption that $\sqrt{2}$ is rational must be false. Hence, $\sqrt{2}$ is irrational. Q.E.D. - **Proof by Induction:** To prove a statement $P(n)$ for all integers $n \ge a$: 1. **Basis Step:** Show $P(a)$ is true. 2. **Inductive Step:** Assume $P(k)$ is true for an arbitrary integer $k \ge a$ (Inductive Hypothesis), and show that $P(k+1)$ is true. - **Example:** Prove that $1 + 2 + \dots + n = \frac{n(n+1)}{2}$ for all integers $n \ge 1$. - **Proof:** 1. **Basis Step:** For $n=1$, $1 = \frac{1(1+1)}{2} = \frac{1 \cdot 2}{2} = 1$. The statement holds for $n=1$. 2. **Inductive Step:** Assume $P(k)$ is true for an arbitrary integer $k \ge 1$. That is, assume $1 + 2 + \dots + k = \frac{k(k+1)}{2}$. - We want to show $P(k+1)$ is true: $1 + 2 + \dots + k + (k+1) = \frac{(k+1)((k+1)+1)}{2} = \frac{(k+1)(k+2)}{2}$. - Starting with the left side of $P(k+1)$: $1 + 2 + \dots + k + (k+1) = (1 + 2 + \dots + k) + (k+1)$ By the Inductive Hypothesis, this equals $\frac{k(k+1)}{2} + (k+1)$. $= (k+1)\left(\frac{k}{2} + 1\right)$ $= (k+1)\left(\frac{k+2}{2}\right)$ $= \frac{(k+1)(k+2)}{2}$. - This is the right side of $P(k+1)$. Thus, $P(k+1)$ is true. - By the principle of mathematical induction, $1 + 2 + \dots + n = \frac{n(n+1)}{2}$ for all integers $n \ge 1$. Q.E.D. - **Strong Induction:** Similar to standard induction, but the inductive hypothesis assumes $P(i)$ is true for all integers $i$ from $a$ to $k$. ### Set Theory - **Set:** A collection of distinct objects. - **Element:** An object belonging to a set. Notation: $a \in A$. - **Subset:** $A \subseteq B$ if every element of $A$ is also an element of $B$. - **Proper Subset:** $A \subset B$ if $A \subseteq B$ and $A \neq B$. - **Empty Set:** $\emptyset = \{\}$, the set with no elements. - **Universal Set:** $U$, the set of all elements under consideration. - **Power Set:** $P(A)$, the set of all subsets of $A$. If $|A|=n$, then $|P(A)| = 2^n$. #### Set Operations - **Union:** $A \cup B = \{x \mid x \in A \text{ or } x \in B\}$ - **Intersection:** $A \cap B = \{x \mid x \in A \text{ and } x \in B\}$ - **Difference:** $A - B = \{x \mid x \in A \text{ and } x \notin B\}$ - **Complement:** $\bar{A} = U - A = \{x \mid x \notin A\}$ - **Cartesian Product:** $A \times B = \{(a, b) \mid a \in A \text{ and } b \in B\}$ #### Set Identities - **De Morgan's Laws for Sets:** - $\overline{A \cup B} = \bar{A} \cap \bar{B}$ - $\overline{A \cap B} = \bar{A} \cup \bar{B}$ - **Distributive Laws for Sets:** - $A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$ - $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$ #### Proofs of Set Identities - **Example:** Prove $\overline{A \cup B} = \bar{A} \cap \bar{B}$. - **Proof:** We need to show that for any $x$, $x \in \overline{A \cup B}$ if and only if $x \in \bar{A} \cap \bar{B}$. - **Part 1: Show $\overline{A \cup B} \subseteq \bar{A} \cap \bar{B}$** - Let $x \in \overline{A \cup B}$. - By definition of complement, $x \notin (A \cup B)$. - By definition of union, it is not the case that ($x \in A$ or $x \in B$). - By De Morgan's Law for logic, this means $x \notin A$ and $x \notin B$. - By definition of complement, $x \in \bar{A}$ and $x \in \bar{B}$. - By definition of intersection, $x \in \bar{A} \cap \bar{B}$. - Thus, $\overline{A \cup B} \subseteq \bar{A} \cap \bar{B}$. - **Part 2: Show $\bar{A} \cap \bar{B} \subseteq \overline{A \cup B}$** - Let $x \in \bar{A} \cap \bar{B}$. - By definition of intersection, $x \in \bar{A}$ and $x \in \bar{B}$. - By definition of complement, $x \notin A$ and $x \notin B$. - This means it is not the case that ($x \in A$ or $x \in B$). - By definition of union, $x \notin (A \cup B)$. - By definition of complement, $x \in \overline{A \cup B}$. - Thus, $\bar{A} \cap \bar{B} \subseteq \overline{A \cup B}$. - Since both inclusions hold, $\overline{A \cup B} = \bar{A} \cap \bar{B}$. Q.E.D. ### Functions - **Function:** A relation $f$ from set $A$ (domain) to set $B$ (codomain), denoted $f: A \rightarrow B$, such that every element in $A$ is mapped to exactly one element in $B$. - **Image:** For $x \in A$, $f(x)$ is the image of $x$. For a subset $S \subseteq A$, $f(S) = \{f(x) \mid x \in S\}$. - **Preimage:** For $y \in B$, the preimage of $y$ is $\{x \in A \mid f(x) = y\}$. - **Range:** The set of all images of elements in the domain, $f(A) = \{y \in B \mid \exists x \in A, f(x) = y\}$. #### Types of Functions - **Injective (One-to-one):** If $f(x_1) = f(x_2)$ implies $x_1 = x_2$ for all $x_1, x_2 \in A$. - **Proof Technique:** Assume $f(x_1) = f(x_2)$ and show $x_1 = x_2$. - **Surjective (Onto):** For every $y \in B$, there exists an $x \in A$ such that $f(x) = y$. - **Proof Technique:** Let $y \in B$ be arbitrary. Show there exists an $x \in A$ (often by constructing it) such that $f(x) = y$. - **Bijective (One-to-one correspondence):** A function that is both injective and surjective. - **Inverse Function:** If $f: A \rightarrow B$ is bijective, then there exists an inverse function $f^{-1}: B \rightarrow A$ such that $f^{-1}(y) = x$ if and only if $f(x) = y$. - **Theorem:** A function has an inverse if and only if it is bijective. - **Proof (Sketch):** - ($\Rightarrow$) Assume $f$ has an inverse $f^{-1}$. To show $f$ is injective: If $f(x_1) = f(x_2)$, then applying $f^{-1}$ to both sides gives $f^{-1}(f(x_1)) = f^{-1}(f(x_2))$, so $x_1 = x_2$. To show $f$ is surjective: For any $y \in B$, let $x = f^{-1}(y)$. Then $f(x) = f(f^{-1}(y)) = y$. - ($\Leftarrow$) Assume $f$ is bijective. Since $f$ is surjective, for every $y \in B$, there is at least one $x \in A$ such that $f(x)=y$. Since $f$ is injective, this $x$ is unique. Thus, we can define $f^{-1}(y) = x$ for each $y \in B$. - **Composition of Functions:** For $f: A \rightarrow B$ and $g: B \rightarrow C$, the composition $g \circ f: A \rightarrow C$ is defined by $(g \circ f)(x) = g(f(x))$. ### Relations - **Binary Relation:** A subset of the Cartesian product $A \times B$. If $A=B$, it's a relation on $A$. - **Notation:** $a R b$ means $(a, b) \in R$. #### Properties of Relations on a Set $A$ - **Reflexive:** For all $a \in A$, $a R a$. - **Example:** "is equal to" on integers. $a=a$. - **Symmetric:** For all $a, b \in A$, if $a R b$ then $b R a$. - **Example:** "is a sibling of" on people. If A is a sibling of B, then B is a sibling of A. - **Transitive:** For all $a, b, c \in A$, if $a R b$ and $b R c$ then $a R c$. - **Example:** "is less than" on integers. If $a ### Counting - **Pigeonhole Principle:** If $N$ items are placed into $k$ bins, then at least one bin must contain at least $\lceil N/k \rceil$ items. - **Proof:** Assume for contradiction that no bin contains at least $\lceil N/k \rceil$ items. This means every bin contains strictly fewer than $\lceil N/k \rceil$ items. - So, each bin contains at most $\lceil N/k \rceil - 1$ items. - The total number of items would then be at most $k \cdot (\lceil N/k \rceil - 1)$. - We know that $\lceil N/k \rceil - 1 ### Graph Theory - **Graph:** A pair $(V, E)$, where $V$ is a set of vertices and $E$ is a set of edges connecting pairs of vertices. - **Directed Graph (Digraph):** Edges have a direction. - **Undirected Graph:** Edges have no direction. - **Degree of a Vertex (Undirected):** The number of edges incident to it. - **In-degree/Out-degree (Directed):** Number of edges entering/leaving a vertex. #### Graph Types - **Complete Graph ($K_n$):** Every pair of distinct vertices is connected by a unique edge. - **Cycle Graph ($C_n$):** Vertices form a single cycle. - **Path Graph ($P_n$):** Vertices form a single path. - **Bipartite Graph:** Vertices can be divided into two disjoint sets $U$ and $W$ such that every edge connects a vertex in $U$ to one in $W$. #### Graph Properties - **Walk:** A sequence of vertices and edges. - **Path:** A walk with no repeated vertices. - **Cycle:** A path that starts and ends at the same vertex. - **Connected Graph:** For every pair of distinct vertices $u, v$, there is a path from $u$ to $v$. - **Tree:** A connected undirected graph with no simple circuits (cycles). - **Theorem:** An undirected graph is a tree if and only if there is a unique simple path between any two distinct vertices. - **Proof (Sketch):** - ($\Rightarrow$) Assume $G$ is a tree. Since $G$ is connected, there is at least one path between any two vertices. Assume there are two distinct simple paths between $u$ and $v$. Then combining these paths would form a cycle, which contradicts the definition of a tree. - ($\Leftarrow$) Assume there is a unique simple path between any two distinct vertices. This implies the graph is connected. If there were a cycle, then any two vertices on the cycle would have at least two distinct simple paths between them (one clockwise, one counter-clockwise), which contradicts our assumption. Thus, there are no cycles. - **Theorem:** A tree with $n$ vertices has $n-1$ edges. - **Proof (by induction on $n$, the number of vertices):** 1. **Basis Step:** For $n=1$, a tree has 1 vertex and 0 edges. $1-1=0$. The statement holds. For $n=2$, a tree has 2 vertices and 1 edge. $2-1=1$. The statement holds. 2. **Inductive Step:** Assume that any tree with $k$ vertices has $k-1$ edges for some $k \ge 1$. - Consider a tree $T$ with $k+1$ vertices. - A key property of trees is that any tree with at least two vertices has at least one leaf vertex (a vertex of degree 1). If a tree had no leaf vertices, every vertex would have degree at least 2, which implies it must contain a cycle (contradiction for a tree). - Let $v$ be a leaf vertex in $T$. Let $e$ be the unique edge incident to $v$. - Consider the graph $T' = T - v - e$ (remove vertex $v$ and edge $e$). - $T'$ is still connected (removing a leaf doesn't disconnect a tree) and has no cycles, so $T'$ is a tree. - $T'$ has $(k+1)-1 = k$ vertices. - By the inductive hypothesis, $T'$ has $k-1$ edges. - Since $T$ was formed by adding vertex $v$ and edge $e$ to $T'$, $T$ has $(k-1) + 1 = k$ edges. - This shows that a tree with $k+1$ vertices has $k$ edges. Thus, the statement holds for $k+1$. - By induction, a tree with $n$ vertices has $n-1$ edges for all $n \ge 1$. Q.E.D. - **Spanning Tree:** A subgraph that is a tree and includes all vertices of the original graph. #### Graph Traversals - **Depth-First Search (DFS):** Explores as far as possible along each branch before backtracking. - **Breadth-First Search (BFS):** Explores all neighbor nodes at the present depth before moving on to nodes at the next depth level. #### Euler and Hamilton Paths/Circuits - **Euler Path:** A path that visits every edge exactly once. - **Euler Circuit:** An Euler path that starts and ends at the same vertex. - **Theorem:** An undirected graph has an Euler circuit if and only if it is connected and every vertex has an even degree. - **Theorem:** An undirected graph has an Euler path (but not a circuit) if and only if it is connected and has exactly two vertices of odd degree. - **Hamilton Path:** A path that visits every vertex exactly once. - **Hamilton Circuit:** A Hamilton path that starts and ends at the same vertex. (No simple necessary and sufficient conditions are known). ### Recurrence Relations - **Definition:** An equation that defines a sequence recursively, where each term is defined as a function of preceding terms. - **Solving Linear Homogeneous Recurrence Relations with Constant Coefficients:** - Form: $a_n = c_1 a_{n-1} + c_2 a_{n-2} + \dots + c_k a_{n-k}$ - **Characteristic Equation:** $r^k - c_1 r^{k-1} - c_2 r^{k-2} - \dots - c_k = 0$ - **Case 1: Distinct Real Roots:** If $r_1, r_2, \dots, r_k$ are distinct real roots, the general solution is $a_n = \alpha_1 r_1^n + \alpha_2 r_2^n + \dots + \alpha_k r_k^n$. - **Case 2: Repeated Real Roots:** If a root $r$ has multiplicity $m$, then the terms $(\alpha_1 + \alpha_2 n + \dots + \alpha_m n^{m-1}) r^n$ are included in the general solution. - **Example: Fibonacci Sequence** - $F_n = F_{n-1} + F_{n-2}$ for $n \ge 2$, with $F_0=0, F_1=1$. - Characteristic equation: $r^2 - r - 1 = 0$. - Roots: $r = \frac{1 \pm \sqrt{1 - 4(1)(-1)}}{2} = \frac{1 \pm \sqrt{5}}{2}$. - Let $\phi = \frac{1 + \sqrt{5}}{2}$ and $\psi = \frac{1 - \sqrt{5}}{2}$. - General solution: $F_n = \alpha_1 \phi^n + \alpha_2 \psi^n$. - Using initial conditions: - For $n=0$: $F_0 = 0 = \alpha_1 + \alpha_2$. So $\alpha_2 = -\alpha_1$. - For $n=1$: $F_1 = 1 = \alpha_1 \phi + \alpha_2 \psi = \alpha_1 \phi - \alpha_1 \psi = \alpha_1 (\phi - \psi)$. - $\phi - \psi = \frac{1+\sqrt{5}}{2} - \frac{1-\sqrt{5}}{2} = \frac{2\sqrt{5}}{2} = \sqrt{5}$. - So $1 = \alpha_1 \sqrt{5}$, which means $\alpha_1 = \frac{1}{\sqrt{5}}$. - And $\alpha_2 = -\frac{1}{\sqrt{5}}$. - Therefore, **Binet's Formula:** $F_n = \frac{1}{\sqrt{5}} \left( \left(\frac{1+\sqrt{5}}{2}\right)^n - \left(\frac{1-\sqrt{5}}{2}\right)^n \right)$. ### Automata and Languages - **Alphabet ($\Sigma$):** A finite, non-empty set of symbols. - **String:** A finite sequence of symbols from an alphabet. - **Language:** A set of strings over an alphabet. - **Regular Expression:** A notation for describing regular languages. - **Finite Automaton (FA):** A mathematical model of computation. - **Deterministic Finite Automaton (DFA):** - $M = (Q, \Sigma, \delta, q_0, F)$ - $Q$: finite set of states - $\Sigma$: input alphabet - $\delta$: transition function $\delta: Q \times \Sigma \rightarrow Q$ - $q_0$: start state - $F$: set of final (accepting) states - **Nondeterministic Finite Automaton (NFA):** Similar to DFA, but $\delta: Q \times (\Sigma \cup \{\epsilon\}) \rightarrow P(Q)$ (power set of $Q$). - **Theorem:** For every NFA, there exists an equivalent DFA. - **Proof (Subset Construction):** - Given an NFA $N = (Q_N, \Sigma, \delta_N, q_{0N}, F_N)$, construct a DFA $D = (Q_D, \Sigma, \delta_D, q_{0D}, F_D)$. - $Q_D = P(Q_N)$ (the power set of $Q_N$). Each state in $D$ is a set of states from $N$. - $q_{0D} = \epsilon\text{-closure}(q_{0N})$. - For $S \in Q_D$ and $a \in \Sigma$, $\delta_D(S, a) = \epsilon\text{-closure}(\bigcup_{q \in S} \delta_N(q, a))$. - $F_D = \{S \in Q_D \mid S \cap F_N \neq \emptyset\}$. - This construction effectively simulates all possible paths of the NFA in parallel. If any path ends in an accepting state of the NFA, the corresponding state in the DFA (which is the set of all states reachable) will be an accepting state. - **Theorem:** A language is regular if and only if it is accepted by a DFA (or NFA). - **Proof (Kleene's Theorem, Sketch):** - Part 1: If $L$ is regular, then there exists an FA that accepts $L$. (Construction from regular expression to NFA, then NFA to DFA). - Part 2: If $L$ is accepted by an FA, then $L$ is regular. (Construction from FA to regular expression using Arden's Lemma or state elimination). - **Pumping Lemma for Regular Languages:** - If $L$ is a regular language, then there exists an integer $p \ge 1$ (the pumping length) such that for any string $s \in L$ with $|s| \ge p$, $s$ can be divided into three parts $s=xyz$ satisfying the conditions: 1. $|y| \ge 1$ 2. $|xy| \le p$ 3. For all $i \ge 0$, $xy^iz \in L$. - **Proof:** Let $M = (Q, \Sigma, \delta, q_0, F)$ be a DFA that accepts $L$. Let $p = |Q|$ be the number of states. - Consider a string $s \in L$ with $|s| \ge p$. - When $M$ processes $s$, it visits a sequence of $p+1$ states (including $q_0$) for the first $p+1$ symbols. - By the Pigeonhole Principle, since there are only $p$ distinct states, at least one state must be repeated in this sequence of $p+1$ states. - Let $q_j$ be the first state repeated, and let $q_k$ be its second occurrence ($j 1$, $xy^iz \in L$ (looping through $y$ multiple times at state $q_j$). Since $q_j$ is reached by $x$, and $y$ takes $M$ from $q_j$ to $q_j$, we can traverse $y$ any number of times and still end up at $q_j$. From $q_j$, $z$ takes $M$ to an accepting state. - The Pumping Lemma is often used to prove that a language is *not* regular by contradiction.