Propositional Logic
| Connective | Symbol | Truth Condition |
|---|
| Conjunction (AND) | p ∧ q | True only when both true |
| Disjunction (OR) | p ∨ q | True when at least one true |
| Negation (NOT) | ¬p | Opposite truth value |
| Implication | p → q | False only when p true, q false |
| Biconditional | p ↔ q | True when p and q same value |
Quantifiers
| Quantifier | Symbol | Meaning |
|---|
| Universal | ∀x P(x) | "For all x, P(x) is true" |
| Existential | ∃x P(x) | "There exists an x where P(x) is true" |
| Negation | ¬∀x P(x) ≡ ∃x ¬P(x) | Universal negation becomes existential |
| Negation | ¬∃x P(x) ≡ ∀x ¬P(x) | Existential negation becomes universal |
Proof Techniques
| Technique | How It Works |
|---|
| Direct | Assume p, derive q through logical steps |
| Contrapositive | Prove ¬q → ¬p instead of p → q |
| Contradiction | Assume ¬(p → q) = p ∧ ¬q, derive contradiction |
| Induction | Base case P(1) + inductive step P(k) → P(k+1) |
| Exhaustion | Check all finite cases one by one |
Relations & Functions
| Property | Definition |
|---|
| Reflexive | ∀a ∈ A: aRa (every element relates to itself) |
| Symmetric | ∀a,b ∈ A: aRb → bRa |
| Transitive | ∀a,b,c ∈ A: aRb ∧ bRc → aRc |
| Equivalence | Reflexive + Symmetric + Transitive |
| Injective | f(a) = f(b) → a = b (one-to-one) |
| Surjective | ∀y ∈ B ∃x ∈ A: f(x) = y (onto) |
| Bijective | Injective + Surjective (one-to-one correspondence) |
Pro Tip: In discrete math, every proof is either direct, by contradiction, contrapositive, or induction. If you cannot classify your proof into one of these, you do not have a proof yet.