Quick reference for logic operators, set operations, combinatorics formulas, and graph theory.
LogicSet TheoryGraph TheoryCombinatorics
Propositional Logic
| Operator | Symbol | True when… | Code |
|---|
| AND (conjunction) | ∧ | Both P and Q are true | && |
| OR (disjunction) | ∨ | At least one of P, Q is true | || |
| NOT (negation) | ¬ | P is false | ! |
| IMPLIES | → | P false, OR both P and Q true (false only when P=T, Q=F) | !p || q |
| IFF (biconditional) | ↔ | P and Q have the same truth value | p === q |
| XOR (exclusive or) | ⊕ | Exactly one of P, Q is true | p !== q |
Key Equivalences (De Morgan's)
¬(P ∧ Q) ≡ ¬P ∨ ¬Q // NOT (A AND B) = (NOT A) OR (NOT B)
¬(P ∨ Q) ≡ ¬P ∧ ¬Q // NOT (A OR B) = (NOT A) AND (NOT B)
// Contrapositive (always equivalent to original implication):
P → Q ≡ ¬Q → ¬P
// Tautology: always true (P ∨ ¬P)
// Contradiction: always false (P ∧ ¬P)
Set Theory
| Operation | Notation | Meaning |
|---|
| Union | A ∪ B | Elements in A or B (or both) |
| Intersection | A ∩ B | Elements in both A and B |
| Difference | A − B | Elements in A but not in B |
| Complement | Aᶜ | Elements NOT in A (within universe U) |
| Power Set | 𝒫(A) | All subsets of A; |𝒫(A)| = 2^|A| |
| Cartesian Product | A × B | All ordered pairs (a, b) where a∈A, b∈B |
// Inclusion-Exclusion (avoid double-counting)
|A ∪ B| = |A| + |B| − |A ∩ B|
|A ∪ B ∪ C| = |A| + |B| + |C| − |A∩B| − |A∩C| − |B∩C| + |A∩B∩C|
Combinatorics Formulas
| Formula | Name | When to use |
|---|
| n! | Factorial | Arrange n distinct items in a row |
| P(n,r) = n!/(n-r)! | Permutation | Ordered selection of r from n |
| C(n,r) = n!/r!(n-r)! | Combination | Unordered selection of r from n |
| n₁ × n₂ × … × nₖ | Multiplication rule | k independent choices |
| ⌈n/k⌉ | Pigeonhole Principle | n items in k boxes → ≥⌈n/k⌉ share a box |
Graph Theory Terms
| Term | Definition |
|---|
| Degree | Number of edges incident to a vertex; sum of all degrees = 2|E| |
| Path | Sequence of distinct vertices connected by edges |
| Cycle | Path that starts and ends at the same vertex |
| Connected | Every vertex is reachable from every other (undirected) |
| Tree | Connected acyclic undirected graph; n nodes → n-1 edges |
| Bipartite | Vertices split into two sets; edges only between sets (no odd cycles) |
| Planar | Can be drawn without crossing edges; Euler: V - E + F = 2 |
| DAG | Directed Acyclic Graph — used for scheduling, build deps, topological sort |
Proof Techniques
// Direct proof: assume P, derive Q step by step
// "If n is even, n² is even"
// Assume n = 2k → n² = 4k² = 2(2k²) → even ✓
// Proof by contradiction: assume ¬Q, derive contradiction
// "√2 is irrational": assume √2 = p/q (fully reduced)
// → 2 = p²/q² → p² = 2q² → p even → p = 2m
// → 4m² = 2q² → q² = 2m² → q even → contradiction (both even, not reduced)
// Proof by induction:
// Base case: show P(1) is true
// Inductive step: assume P(k), prove P(k+1)
// "Sum 1..n = n(n+1)/2":
// Base: n=1 → 1 = 1(2)/2 = 1 ✓
// Step: assume S(k) = k(k+1)/2
// S(k+1) = k(k+1)/2 + (k+1) = (k+1)(k+2)/2 ✓
Relation Properties
| Property | Condition | Example |
|---|
| Reflexive | (a, a) ∈ R for all a | a ≤ a (always true) |
| Symmetric | (a,b) ∈ R → (b,a) ∈ R | a is friend of b ↔ b is friend of a |
| Transitive | (a,b), (b,c) ∈ R → (a,c) ∈ R | a ≤ b and b ≤ c → a ≤ c |
| Equivalence | Reflexive + Symmetric + Transitive | Congruence mod n; same birthday |
Key Rules
- P → Q is only false when P is true and Q is false. (A broken promise: I said I would, and I didn't.)
- Contrapositive (¬Q → ¬P) is logically equivalent to P → Q — often easier to prove.
- Permutation = order matters; Combination = order doesn't matter. C(n,r) = P(n,r) / r!
- Tree: n vertices → exactly n-1 edges; connected and acyclic.
- Mathematical induction = the domino principle: prove the first falls, prove each one knocks over the next.