An interactive reference covering logic, proofs, sets, functions, number theory, induction, combinatorics, and graph theory — every formula, concept, and technique you need.
| Name | Form | Equivalent To | Key Fact |
|---|---|---|---|
| Implication | p → q | ¬p ∨ q | Original statement |
| Converse | q → p | — | NOT equivalent to original |
| Inverse | ¬p → ¬q | — | NOT equivalent; equivalent to converse |
| Contrapositive | ¬q → ¬p | p → q | LOGICALLY EQUIVALENT to original ✓ |
Select a compound proposition to generate its truth table:
| Rule | Given | Conclude | Form |
|---|---|---|---|
| Modus Ponens | p → q, p | q | [(p→q) ∧ p] → q |
| Modus Tollens | p → q, ¬q | ¬p | [(p→q) ∧ ¬q] → ¬p |
| Hypothetical Syllogism | p → q, q → r | p → r | Chain rule |
| Disjunctive Syllogism | p ∨ q, ¬p | q | If not this, then that |
| Addition | p | p ∨ q | Can always add disjunct |
| Simplification | p ∧ q | p | Extract from conjunction |
| Conjunction | p, q | p ∧ q | Combine two truths |
| Universal Instantiation | ∀x P(x) | P(c) | Any specific c in domain |
| Universal Generalization | P(c) for arbitrary c | ∀x P(x) | Must hold for ALL values |
| Existential Instantiation | ∃x P(x) | P(c) for some c | Name the witness |
Assume p is true, then use logical steps to conclude q is true.
Example: Prove that if n is odd, then n² is odd.
Since p→q ≡ ¬q→¬p, proving the contrapositive is logically equivalent. Use when the conclusion involves a negative property.
Example: Prove that if n² is odd, then n is odd.
Assume the statement is FALSE. Show this leads to a contradiction (like 1=0 or x is both odd and even). Therefore the statement must be TRUE.
Classic example: Prove √2 is irrational.
Divide the domain into EXHAUSTIVE cases, then prove the statement holds in EVERY case.
Example: Prove n² + n is even for all integers n.
| Operation | Symbol | Formal Definition | Meaning |
|---|---|---|---|
| Union | A ∪ B | {x | x∈A ∨ x∈B} | Everything in A OR B |
| Intersection | A ∩ B | {x | x∈A ∧ x∈B} | Only what's in BOTH |
| Difference | A − B | {x | x∈A ∧ x∉B} | A without B's elements |
| Complement | Ā or A' | {x | x∉A} | Everything NOT in A |
| Cartesian Product | A × B | {(a,b) | a∈A, b∈B} | All ordered pairs |
| Power Set | P(A) or 2^A | Set of all subsets of A | |P(A)| = 2^|A| |
| Type | Count (|A|=m, |B|=n) | Condition |
|---|---|---|
| Any function | n^m | No restrictions |
| Injective functions | P(n,m) = n!/(n-m)! | Requires n ≥ m |
| Bijective functions | n! (if m = n) | Requires m = n |
| Class | Name | Example | n=10 | n=100 |
|---|---|---|---|---|
| O(1) | Constant | Array index access | 1 | 1 |
| O(log n) | Logarithmic | Binary search | ~3 | ~7 |
| O(n) | Linear | Linear scan | 10 | 100 |
| O(n log n) | Linearithmic | Merge sort | ~33 | ~664 |
| O(n²) | Quadratic | Bubble sort | 100 | 10,000 |
| O(n³) | Cubic | Matrix multiply (naive) | 1,000 | 1,000,000 |
| O(2^n) | Exponential | Brute-force TSP | 1,024 | 1.27×10³⁰ |
| O(n!) | Factorial | All permutations | 3,628,800 | 9.3×10¹⁵⁷ |
| Type | Order Matters? | Formula | Example |
|---|---|---|---|
| Permutation P(n,r) | ✓ YES | n! / (n-r)! | Arrange 3 from 5: P(5,3)=60 |
| Combination C(n,r) | ✗ NO | n! / (r!(n-r)!) | Choose 3 from 5: C(5,3)=10 |
| Perm w/ Repetition | ✓ YES | n^r | 4-digit PIN: 10⁴=10,000 |
| Combo w/ Repetition | ✗ NO | C(n+r-1, r) | Choose 2 flavors from 5 (repeats ok): C(6,2)=15 |
| Circular Permutation | ✓ YES | (n-1)! | Seat 5 at round table: 4!=24 |
| Multinomial | ✓ YES | n! / (n₁!n₂!···nₖ!) | Arrangements of MISSISSIPPI |
| Property | Definition | Formal | Example on {1,2,3} |
|---|---|---|---|
| Reflexive | Every element relates to itself | ∀x: (x,x) ∈ R | {(1,1),(2,2),(3,3),...} |
| Symmetric | If aRb then bRa | ∀x,y: (x,y)∈R → (y,x)∈R | If (1,2)∈R then (2,1)∈R |
| Antisymmetric | If aRb and bRa, then a=b | (x,y)∈R ∧ (y,x)∈R → x=y | ≤ is antisymmetric |
| Transitive | If aRb and bRc then aRc | (x,y)∈R ∧ (y,z)∈R → (x,z)∈R | If (1,2),(2,3)∈R then (1,3)∈R |