Discrete Math – Complete Formula Sheet

1. Logic - Propositions & Connectives

Logical Operators

$\neg p$: Negation (NOT)

$p \land q$: Conjunction (AND)

$p \lor q$: Disjunction (OR)

$p \implies q$: Implication (IF-THEN)

$p \iff q$: Biconditional (IF AND ONLY IF)

Truth Tables Essentials

$\neg T = F$, $\neg F = T$

$T \land T = T$, else $F$

$F \lor F = F$, else $T$

$p \implies q \equiv \neg p \lor q$

$p \iff q \equiv (p \implies q) \land (q \implies p)$

2. Logical Equivalences

De Morgan's Laws

$\neg(p \land q) \equiv \neg p \lor \neg q$

$\neg(p \lor q) \equiv \neg p \land \neg q$

Distributive Laws

$p \land (q \lor r) \equiv (p \land q) \lor (p \land r)$

$p \lor (q \land r) \equiv (p \lor q) \land (p \lor r)$

Other Key Laws

Commutative: $p \land q \equiv q \land p$

Associative: $(p \land q) \land r \equiv p \land (q \land r)$

Idempotent: $p \land p \equiv p$

Double Negation: $\neg \neg p \equiv p$

Absorption: $p \lor (p \land q) \equiv p$

3. Predicates & Quantifiers

Universal Quantifier

$\forall x \, P(x)$: For all $x$, $P(x)$ is true

Domain must be non-empty for truth

Existential Quantifier

$\exists x \, P(x)$: There exists $x$ such that $P(x)$ is true

At least one element must satisfy $P(x)$

De Morgan's for Quantifiers

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

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

Multiple Quantifiers

Order matters: $\forall x \exists y$ vs $\exists y \forall x$

4. Methods of Proof

Direct Proof

Assume hypothesis true, derive conclusion

Used for: $P \implies Q$

Proof by Contraposition

Prove $\neg Q \implies \neg P$ instead

Equivalent to $P \implies Q$

Proof by Contradiction

Assume $P$ is false, derive contradiction

Proof by Cases

Partition domain, prove each case

Mathematical Induction

Base case + Inductive step

5. Sets - Notation & Operations

Set Notation

Roster: $A = \{1, 2, 3\}$

Set-builder: $A = \{x | P(x)\}$

$x \in A$: $x$ is member of $A$

$\emptyset$: Empty set

$\mathcal{P}(A)$: Power set (all subsets)

Basic Operations

$A \cup B = \{x | x \in A \text{ or } x \in B\}$

$A \cap B = \{x | x \in A \text{ and } x \in B\}$

$A \setminus B = \{x | x \in A, x \notin B\}$

$\overline{A} = \{x | x \notin A\}$ (Complement)

6. Set Identities

Commutative & Associative

$A \cup B = B \cup A$

$(A \cup B) \cup C = A \cup (B \cup C)$

De Morgan's for Sets

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

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

Distributive Laws

$A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$

$A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$

Idempotent & Absorption

$A \cup A = A$, $A \cap A = A$

$A \cup \emptyset = A$, $A \cap \emptyset = \emptyset$

7. Functions - Types & Properties

Function Definition

$f: A \to B$ assigns each $a \in A$ to exactly one $b \in B$

Injective (One-to-One)

$f(a_1) = f(a_2) \implies a_1 = a_2$

Surjective (Onto)

$\forall b \in B, \exists a \in A: f(a) = b$

Bijective

Both injective AND surjective

Invertible: $f^{-1}$ exists

Composition

$(f \circ g)(x) = f(g(x))$

8. Sequences & Summations

Sequence Notation

$\{a_n\}$: Sequence indexed by $n$

Arithmetic: $a_n = a_1 + (n-1)d$

Geometric: $a_n = a_1 \cdot r^{n-1}$

Summation Formulas

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

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

$\sum_{i=1}^n r^i = \frac{r(r^n-1)}{r-1}$ ($r \ne 1$)

Summation Rules

$\sum (a_i + b_i) = \sum a_i + \sum b_i$

$\sum c \cdot a_i = c \sum a_i$

9. Mathematical Induction

Weak Induction

Base Case: Verify $P(1)$ is true

Inductive Step: Assume $P(k)$, prove $P(k+1)$

Then $P(n)$ is true for all $n \ge 1$

Strong Induction

Base Cases: Verify $P(1), ..., P(k)$

Inductive Step: Assume $P(1) \land ... \land P(k)$, prove $P(k+1)$

Well-Ordering Principle

Every non-empty set of positive integers has a minimum element

Induction works for recursive/recursive-like claims about positive integers

10. Recursion & Recurrence

Recurrence Relation

$a_n = f(a_{n-1}, a_{n-2}, ...)$

Linear Homogeneous (2nd order)

$a_n = c_1 a_{n-1} + c_2 a_{n-2}$

Characteristic equation: $r^2 - c_1 r - c_2 = 0$

If distinct roots $r_1, r_2$: $a_n = A r_1^n + B r_2^n$

Fibonacci Example

$F_n = F_{n-1} + F_{n-2}$, $F_1 = 1, F_2 = 1$

Solving Techniques

Characteristic equation method

Iteration method

Generating functions

11. Counting Principles

Product Rule

If task A: $m$ ways, task B: $n$ ways $\Rightarrow$ both: $m \times n$ ways

Sum Rule

If tasks are mutually exclusive: $m + n$ ways total

Inclusion-Exclusion (2 sets)

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

Inclusion-Exclusion (3 sets)

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

Pigeonhole Principle

$k+1$ objects in $k$ pigeonholes $\Rightarrow$ one has $\ge 2$ objects

12. Permutations & Combinations

Permutations (Order Matters)

$P(n, k) = \frac{n!}{(n-k)!}$ (Choose $k$ from $n$)

All permutations: $P(n,n) = n!$

Combinations (Order Doesn't Matter)

$C(n, k) = \binom{n}{k} = \frac{n!}{k!(n-k)!}$

Identity: $\binom{n}{k} = \binom{n}{n-k}$

Permutations with Repetition

$n^k$ ways to fill $k$ positions from $n$ choices

Combinations with Repetition

$\binom{n+k-1}{k}$ ways to choose $k$ from $n$ types

13. Binomial Theorem

Binomial Expansion

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

Binomial Coefficient

$\binom{n}{k}$ = number of $k$-element subsets of $n$ elements

$\binom{n}{0} = 1$, $\binom{n}{n} = 1$

Pascal's Triangle

$\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$

Useful Identities

$\sum_{k=0}^n \binom{n}{k} = 2^n$

$\sum_{k=0}^n (-1)^k \binom{n}{k} = 0$

$\sum_{k=0}^n k \binom{n}{k} = n \cdot 2^{n-1}$

14. Advanced Counting Principle

Pigeonhole Principle

If $n$ objects in $k$ boxes ($n > k$), some box has $\ge \lceil n/k \rceil$ objects

General Inclusion-Exclusion

$|\bigcup_{i=1}^n A_i| = \sum |A_i| - \sum |A_i \cap A_j| + \sum |A_i \cap A_j \cap A_k| - ...$

Derangements

$D_n = n! \sum_{i=0}^n \frac{(-1)^i}{i!} \approx \frac{n!}{e}$

Number of permutations with no fixed points

Surjections

Surjections from $n$ to $k$ elements: $k! \cdot S(n,k)$

$S(n,k)$ = Stirling number of 2nd kind

15. Relations - Properties

Relation Definition

$R \subseteq A \times B$ (or $A \times A$ for binary)

$(a, b) \in R$ means $a \, R \, b$

Properties

Reflexive: $\forall a: a \, R \, a$

Symmetric: $a \, R \, b \implies b \, R \, a$

Transitive: $a \, R \, b \land b \, R \, c \implies a \, R \, c$

Antisymmetric: $a \, R \, b \land b \, R \, a \implies a = b$

Equivalence Relation

Reflexive + Symmetric + Transitive

Partitions set into equivalence classes

16. Partial Orders & Graphs

Partial Order

Reflexive + Antisymmetric + Transitive

Notation: $(A, \le)$ or $(A, \preceq)$

Total Order

Partial order where all pairs are comparable

Hasse Diagram

Visual representation of partial order

Draw edge $a \to b$ if $a < b$ with no intermediate

Graph Terminology

Vertex (node), Edge (link)

Degree: # of edges at vertex

Path: sequence of edges

17. Graph Types & Properties

Basic Definitions

Simple graph: No loops or parallel edges

Multigraph: Allows parallel edges

Directed graph: Edges have direction

Special Graph Types

Complete $K_n$: Edge between every pair

Bipartite: Vertices split into 2 sets, edges only between

Complete bipartite $K_{m,n}$

Regular: All vertices same degree

Graph Properties

Handshaking Lemma: $\sum_v \deg(v) = 2|E|$

Even number of odd-degree vertices

18. Connectivity & Special Paths

Connectivity

Connected: Path exists between any 2 vertices

Connected component: Maximal connected subgraph

Special Paths & Cycles

Path: Sequence of edges, no vertex repeated

Cycle: Path starting & ending at same vertex

Euler path: Uses every edge exactly once

Hamiltonian path: Visits every vertex exactly once

Euler Path Condition

Connected graph has Euler path iff 0 or 2 odd-degree vertices

Distance & Diameter

Distance $d(u,v)$ = shortest path length

19. Trees - Structure & Traversal

Tree Definition

Connected acyclic graph

If $|V| = n$, then $|E| = n - 1$

Tree Properties

Exactly one path between any 2 vertices

Removing any edge disconnects it

Leaf: Degree-1 vertex

Rooted Trees

Root, parent, children, ancestor, descendant

Height, depth of vertices

Traversal Orders

Preorder: Root, left, right

Inorder: Left, root, right

Postorder: Left, right, root

Level-order: By depth level

20. Boolean Algebra

Boolean Operations

$0$ (False) and $1$ (True)

AND: $x \cdot y$ (meets $\cap$)

OR: $x + y$ (joins $\cup$)

NOT: $\bar{x}$ (complement)

Boolean Laws

Idempotent: $x \cdot x = x$, $x + x = x$

Domination: $x \cdot 0 = 0$, $x + 1 = 1$

Absorption: $x + (x \cdot y) = x$

De Morgan: $\overline{x \cdot y} = \bar{x} + \bar{y}$

Normal Forms

DNF: Disjunctive Normal Form (OR of ANDs)

CNF: Conjunctive Normal Form (AND of ORs)

DISCRETE MATH Comprehensive Formula Sheet