The complete course — every concept, every formula, every proof technique — condensed into one galaxy-class reference.
A proposition is a declarative sentence that is either true (T) or false (F), but not both. Questions, commands, and opinions are NOT propositions.
Proposition: "2 + 3 = 5" → T
Proposition: "The moon is made of cheese" → F
NOT a proposition: "What time is it?" / "Close the door."
| Name | Symbol | Read As | True When |
|---|---|---|---|
| Negation | ¬p | "not p" | p is false |
| Conjunction | p ∧ q | "p and q" | both true |
| Disjunction | p ∨ q | "p or q" | at least one true |
| Exclusive Or | p ⊕ q | "p xor q" | exactly one true |
| Conditional | p → q | "if p then q" | ¬p or q (false only when p=T, q=F) |
| Biconditional | p ↔ q | "p if and only if q" | both same truth value |
| p | q | p → q |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | T |
| F | F | T |
p → q is only false when the hypothesis (p) is true and the conclusion (q) is false. A false hypothesis makes the whole conditional vacuously true.
Given the conditional p → q:
| Name | Form | Equivalent To |
|---|---|---|
| Converse | q → p | NOT equivalent to p → q |
| Inverse | ¬p → ¬q | equivalent to converse |
| Contrapositive | ¬q → ¬p | equivalent to p → q |
The contrapositive is always logically equivalent to the original. The converse and inverse are equivalent to each other but NOT to the original.
"p only if q" means p → q (NOT q → p!).
Think of it as: p can be true ONLY IF q is also true. If q is false, p must be false.
"You pass only if you study" = "If you pass, then you studied" = pass → studied
Tautology: Always true for all truth value assignments. Example: p ∨ ¬p
Contradiction: Always false for all truth value assignments. Example: p ∧ ¬p
Contingency: Neither — sometimes true, sometimes false. Example: p ∨ q
Build the full truth table. If the final column is ALL T → tautology. ALL F → contradiction. Mix → contingency.
Two propositions are logically equivalent (p ≡ q) if they have the same truth table.
| Law | Equivalence |
|---|---|
| Identity | p ∧ T ≡ p / p ∨ F ≡ p |
| Domination | p ∨ T ≡ T / p ∧ F ≡ F |
| Idempotent | p ∨ p ≡ p / p ∧ p ≡ p |
| Double Negation | ¬(¬p) ≡ p |
| Commutative | p ∨ q ≡ q ∨ p / p ∧ q ≡ q ∧ p |
| Associative | (p ∨ q) ∨ r ≡ p ∨ (q ∨ r) |
| Distributive | p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r) |
| p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r) | |
| De Morgan's | ¬(p ∧ q) ≡ ¬p ∨ ¬q |
| ¬(p ∨ q) ≡ ¬p ∧ ¬q | |
| Absorption | p ∨ (p ∧ q) ≡ p / p ∧ (p ∨ q) ≡ p |
| Negation | p ∨ ¬p ≡ T / p ∧ ¬p ≡ F |
Students confuse p → q with q → p (converse). The conditional is NOT symmetric! Use ¬p ∨ q as your go-to rewrite.
A predicate is a statement with variables that becomes a proposition when you plug in values.
P(x) = "x > 5"
P(3) = "3 > 5" = F
P(7) = "7 > 5" = T
The domain (universe of discourse) is the set of all possible values the variable can take.
| Symbol | Name | Meaning | True When |
|---|---|---|---|
| ∀x P(x) | Universal | "for all x, P(x)" | P(x) is true for EVERY x in domain |
| ∃x P(x) | Existential | "there exists x such that P(x)" | P(x) is true for AT LEAST ONE x |
To negate: flip the quantifier (∀ ↔ ∃) and negate the predicate. Repeat for nested quantifiers from left to right.
∀x ∃y (x + y = 0): "every number has an additive inverse" → TRUE
∃y ∀x (x + y = 0): "there is one number that is the additive inverse of every number" → FALSE
| English | Logic |
|---|---|
| "All dogs bark" | ∀x (Dog(x) → Barks(x)) |
| "Some dogs bark" | ∃x (Dog(x) ∧ Barks(x)) |
| "No dogs bark" | ¬∃x (Dog(x) ∧ Barks(x)) ≡ ∀x (Dog(x) → ¬Barks(x)) |
Universal (∀) pairs with → (conditional).
Existential (∃) pairs with ∧ (conjunction).
Mixing these up is one of the most common errors!
| Rule | Form | In Words |
|---|---|---|
| Modus Ponens | p → q, p ∴ q | If p then q; p is true; therefore q |
| Modus Tollens | p → q, ¬q ∴ ¬p | If p then q; q is false; therefore ¬p |
| Hypothetical Syllogism | p → q, q → r ∴ p → r | Chain two conditionals |
| Disjunctive Syllogism | p ∨ q, ¬p ∴ q | One of two; not the first; therefore the second |
| Addition | p ∴ p ∨ q | p is true so p OR anything is true |
| Simplification | p ∧ q ∴ p | Both true means each is true |
| Conjunction | p, q ∴ p ∧ q | Both true so the AND is true |
| Resolution | p ∨ q, ¬p ∨ r ∴ q ∨ r | Resolve away complementary literals |
| Rule | Form |
|---|---|
| Universal Instantiation | ∀x P(x) ∴ P(c) for any c |
| Universal Generalization | P(c) for arbitrary c ∴ ∀x P(x) |
| Existential Instantiation | ∃x P(x) ∴ P(c) for some specific c |
| Existential Generalization | P(c) ∴ ∃x P(x) |
For universal generalization, c must be truly arbitrary — no special assumptions about c! For existential instantiation, c is a specific (but unknown) element — you can't assume anything else about it.
| Fallacy | Invalid Form | Why Wrong |
|---|---|---|
| Affirming the Consequent | p → q, q ∴ p | q could be true for other reasons |
| Denying the Antecedent | p → q, ¬p ∴ ¬q | q might still be true without p |
Assume p is true. Use definitions, axioms, and known theorems to arrive at q.
Prove: If n is even, then n² is even.
Proof: Assume n is even, so n = 2k for some integer k.
Then n² = (2k)² = 4k² = 2(2k²).
Since 2k² is an integer, n² = 2(integer), so n² is even. ∎
Instead of p → q, prove the equivalent contrapositive. Assume ¬q and show ¬p.
Prove: If n² is odd, then n is odd.
Contrapositive: If n is even, then n² is even. (Same as above!) ∎
Assume the statement is FALSE (assume ¬S). Derive a contradiction (something impossible like p ∧ ¬p). Conclude S must be true.
Prove: √2 is irrational.
Proof: Assume √2 is rational, so √2 = a/b in lowest terms (gcd(a,b) = 1).
Then 2 = a²/b², so a² = 2b², meaning a² is even → a is even → a = 2k.
Then 4k² = 2b² → b² = 2k² → b is even.
Contradiction: both a and b are even, but we said gcd(a,b) = 1. ∎
Break into cases that cover all possibilities. Prove the result for each case.
Constructive: find/build a specific example.
Non-constructive: prove one must exist without finding it.
Find ONE specific x where P(x) is false. That's it — done.
Rational: a/b where a, b are integers and b ≠ 0.
Irrational: cannot be expressed as a/b (e.g., √2, π, e).
Key facts: rational + rational = rational. irrational + rational = irrational. The product of a nonzero rational and an irrational is irrational. But irrational + irrational can be rational (e.g., √2 + (−√2) = 0).
A set is an unordered collection of distinct objects (elements).
x ∈ A means x is in set A.
x ∉ A means x is not in A.
|A| = cardinality (number of elements in A).
A ⊆ B (A is a subset of B): every element of A is in B.
A ⊂ B (proper subset): A ⊆ B and A ≠ B.
Key facts: ∅ ⊆ A for any set A. A ⊆ A for any set A.
P(A) = the set of ALL subsets of A, including ∅ and A itself.
A = {1, 2}
P(A) = {∅, {1}, {2}, {1,2}}
|P(A)| = 2² = 4
| Operation | Symbol | Definition |
|---|---|---|
| Union | A ∪ B | {x | x ∈ A or x ∈ B} |
| Intersection | A ∩ B | {x | x ∈ A and x ∈ B} |
| Difference | A − B | {x | x ∈ A and x ∉ B} |
| Complement | A̅ or Aᶜ | {x ∈ U | x ∉ A} (U = universal set) |
| Symmetric Diff | A ⊕ B | (A − B) ∪ (B − A) |
∅ ∈ {∅} is TRUE (∅ is an element of the set containing ∅).
∅ ⊆ {∅} is TRUE (∅ is a subset of everything).
{∅} ≠ ∅ — one has one element, the other has zero.
A function f: A → B assigns to each element in A (domain) exactly one element in B (codomain).
Range (image) = {f(a) | a ∈ A} ⊆ B — the actual outputs used.
| Property | Definition | Intuition |
|---|---|---|
| Injective (one-to-one) | f(a) = f(b) → a = b | No two inputs share an output |
| Surjective (onto) | ∀b ∈ B, ∃a ∈ A: f(a) = b | Every element in codomain is hit |
| Bijective (one-to-one AND onto) | Injective + Surjective | Perfect pairing; invertible |
f⁻¹ exists only if f is bijective. Then f⁻¹(f(x)) = x and f(f⁻¹(y)) = y.
A sequence is an ordered list of elements: a₁, a₂, a₃, ... Each aₙ is a term.
f(x) is O(g(x)) if there exist constants C > 0 and k such that |f(x)| ≤ C|g(x)| for all x > k.
Think: f grows no faster than g.
f(x) is Ω(g(x)) if there exist constants C > 0 and k such that |f(x)| ≥ C|g(x)| for all x > k.
Think: f grows at least as fast as g.
f(x) is Θ(g(x)) if f(x) is both O(g(x)) and Ω(g(x)).
Think: f grows at the same rate as g.
log_a(n) = log_b(n) / log_b(a), so any two log bases differ by a constant factor. Since Big-O ignores constants, all logarithmic bases are the same in Big-O.
a | b ("a divides b") means b = a·k for some integer k. Equivalently, b/a is an integer.
a ≡ b (mod m) means m | (a − b), i.e., a and b have the same remainder when divided by m.
17 ≡ 5 (mod 6) because 17 − 5 = 12 and 6 | 12.
Or: 17 mod 6 = 5 and 5 mod 6 = 5. Same remainder!
Repeatedly divide by 2 and collect remainders (read bottom to top).
42 ÷ 2 = 21 r 0
21 ÷ 2 = 10 r 1
10 ÷ 2 = 5 r 0
5 ÷ 2 = 2 r 1
2 ÷ 2 = 1 r 0
1 ÷ 2 = 0 r 1
Read up: 42₁₀ = 101010₂
For n-bit numbers, the leftmost bit is the sign (0 = positive, 1 = negative).
An integer p > 1 is prime if its only positive divisors are 1 and p. Otherwise it's composite. Note: 1 is neither prime nor composite.
Every integer > 1 can be written as a product of primes in exactly one way (up to ordering).
360 = 2³ · 3² · 5
To check if n is prime, test divisibility by all primes up to √n. If none divide n, it's prime.
Repeatedly apply: gcd(a, b) = gcd(b, a mod b) until remainder = 0.
gcd(252, 105) = gcd(105, 252 mod 105) = gcd(105, 42)
gcd(105, 42) = gcd(42, 105 mod 42) = gcd(42, 21)
gcd(42, 21) = gcd(21, 42 mod 21) = gcd(21, 0)
gcd = 21
To prove P(n) is true for all integers n ≥ b:
Show P(b) is true (usually b = 0 or b = 1).
Assume P(k) is true for some arbitrary k ≥ b (inductive hypothesis). Then prove P(k+1) is true.
Think dominoes: base case knocks over the first. Inductive step says "if any domino falls, the next one falls too." Together → all dominoes fall.
Base case (n=1): LHS = 1. RHS = 1(2)/2 = 1. ✓
Inductive step: Assume 1 + 2 + ... + k = k(k+1)/2 (inductive hypothesis).
Show: 1 + 2 + ... + k + (k+1) = (k+1)(k+2)/2.
LHS = [1 + 2 + ... + k] + (k+1)
= k(k+1)/2 + (k+1) ← used IH here!
= k(k+1)/2 + 2(k+1)/2
= (k+1)(k+2)/2 = RHS ✓ ∎
Same as regular induction, but the inductive hypothesis assumes P(b), P(b+1), ..., P(k) are ALL true (not just P(k)). Then prove P(k+1).
Use strong induction when P(k+1) depends on multiple previous cases (not just P(k)).
Some structures (strings, trees, formulas) are defined recursively with base elements and rules for building bigger structures from smaller ones.
Base step: Prove the property for the base elements.
Recursive step: Assume the property holds for the smaller sub-structures, then prove it holds for the structure built from them.
Recursive definition:
Base: A single node is a binary tree.
Recursive: If T₁ and T₂ are binary trees, then connecting them to a new root gives a binary tree.
Prove: A binary tree with n internal nodes has n+1 leaves.
Base: 0 internal nodes → 1 leaf (just the root). 0 + 1 = 1. ✓
Recursive step: Assume true for T₁ (k₁ internal, k₁+1 leaves) and T₂ (k₂ internal, k₂+1 leaves).
Combined tree: (k₁ + k₂ + 1) internal nodes and (k₁+1) + (k₂+1) = k₁ + k₂ + 2 = (k₁+k₂+1) + 1 leaves. ✓ ∎
An equation defining aₙ in terms of previous terms. Plus initial conditions.
aₙ = 2aₙ₋₁ + 1, with a₀ = 0
a₁ = 2(0)+1 = 1, a₂ = 2(1)+1 = 3, a₃ = 2(3)+1 = 7, ...
Step 1: Write the characteristic equation: r² − c₁r − c₂ = 0
Step 2: Find the roots r₁, r₂.
Step 3: General solution depends on the roots:
Step 4: Use initial conditions to solve for A and B.
fₙ = fₙ₋₁ + fₙ₋₂, f₀ = 0, f₁ = 1
Characteristic eq: r² − r − 1 = 0
Roots: r = (1 ± √5)/2 → φ = (1+√5)/2 and ψ = (1−√5)/2
Solution: fₙ = (φⁿ − ψⁿ)/√5
If the characteristic equation has complex roots a ± bi, convert to polar form r·e^(iθ) and the solution involves rⁿcos(nθ) and rⁿsin(nθ) terms.
Complex numbers a + bi where i² = −1. A complex expression produces a real number when imaginary parts cancel. This happens with conjugate pairs (a+bi)(a−bi) = a² + b².
If task 1 can be done m ways and task 2 can be done n ways, both tasks together can be done m × n ways.
If task 1 can be done m ways OR task 2 can be done n ways (mutually exclusive), the total is m + n ways.
Permutation: "arrange", "order", "rank", "sequence", "password", "lineup"
Combination: "choose", "select", "committee", "group", "team", "hand"
(x+y)³ = C(3,0)x³ + C(3,1)x²y + C(3,2)xy² + C(3,3)y³
= x³ + 3x²y + 3xy² + y³
Count operations (comparisons, additions, multiplications) by analyzing loops:
When counting elements in a union, you have to correct for over-counting the overlaps.
Add singles, subtract pairs, add triples, subtract quadruples, ... Alternating signs!
In a class of 40: 25 take math, 20 take CS, 10 take both.
How many take math OR CS?
|M ∪ C| = 25 + 20 − 10 = 35
A relation R from set A to set B is a subset of A × B. If (a, b) ∈ R, we write aRb. A relation on a set A means R ⊆ A × A.
| Property | Definition | Matrix Check |
|---|---|---|
| Reflexive | ∀a ∈ A: aRa | All 1s on diagonal |
| Irreflexive | ∀a ∈ A: ¬(aRa) | All 0s on diagonal |
| Symmetric | aRb → bRa | Matrix equals its transpose |
| Antisymmetric | aRb ∧ bRa → a = b | If M[i][j]=1 and i≠j, then M[j][i]=0 |
| Transitive | aRb ∧ bRc → aRc | M² has no 1 where M has 0 |
Equivalence relation: reflexive + symmetric + transitive (partitions a set into classes)
Partial order: reflexive + antisymmetric + transitive (like ≤ on numbers)
= on ℤ: reflexive ✓, symmetric ✓, transitive ✓ → equivalence relation
≤ on ℤ: reflexive ✓, antisymmetric ✓, transitive ✓ → partial order
< on ℤ: irreflexive, antisymmetric, transitive (strict partial order)
If R is from A to B and S is from B to C, then S ∘ R is from A to C where:
(a, c) ∈ S ∘ R if there exists b ∈ B such that (a, b) ∈ R and (b, c) ∈ S.
In matrix terms: multiply the relation matrices (using Boolean AND for multiplication and OR for addition).
A relation R is transitive if and only if Rⁿ ⊆ R for all n ≥ 1.
M[i][j] = 1 if (aᵢ, aⱼ) ∈ R, else 0.
Nodes = elements, arrow from a to b if aRb. Self-loops for reflexive pairs.
| Proving... | Try This Method |
|---|---|
| p → q | Direct proof, contrapositive, or contradiction |
| p ↔ q | Prove p→q AND q→p separately |
| ∀n ≥ b, P(n) | Mathematical induction |
| ∃x P(x) | Find a specific example (constructive) |
| ¬∀x P(x) | Find one counterexample |
| Something is irrational | Proof by contradiction |
| A ⊆ B | Let x ∈ A, show x ∈ B |
| A = B | Show A ⊆ B AND B ⊆ A |
| f is injective | Assume f(a)=f(b), show a=b |
| f is surjective | Let y ∈ codomain, find x where f(x)=y |