Proof Flashcards
NOT P
¬ P
P AND Q
P ∧ Q
P OR Q
P ∨ Q
If P then Q
P ⟹ Q
P if and only if Q
P ⟺ Q
NOT (P AND Q)
¬ P ∨ ¬Q
(NOT P) OR (NOT Q)
NOT (P OR Q)
¬ P ∧ ¬Q
(NOT P) AND (NOT Q)
NOT (If P then Q)
P ∧ (¬Q)
P AND (NOT Q)
NOT (For all x ∈ S, P(x))
There exists x ∈ S, (¬P(x))
NOT (There exists x ∈ S, P(x))
For all x ∈ S, (¬P(x))
Direct proof steps
- Write down assumptions and known facts
- Create a logical chain of argument
- Deduce the statement to be proven
Proof by cases
split the proposition into a finite number of cases and verify the proposition in each case
Proof by contradiction steps
- Assume the negation of the statement (¬P) is true
- Use logical deductions to show it leads to a contradiction and conclude that the original statement (P) is true
Proof by induction steps
- Base Case - show true for the initial value (usually 0 or 1)
- Inductive Hypothesis - assume the statement is true for n = k (some number k)
- Inductive Step - show if the statement is true for n = k then it must be true for n = k + 1
- Conclusion - conclude the statement holds for all n (since base case and inductive step work)
Proof by construction
- Create an object or example that satisfies the given statement
- Show that the object or example meets the required conditions
- Conclude that the statement is true by virtue of the constructed object or example
When is a direct proof most useful
When proving “if (claim A is true), then (claim B is true)”
When is proof by cases most useful
For claims involving modular arithmetic, even v.s. odd, “is a multiple of” or absolute value
When is proof by construction most useful
When the claim asks you to “show that something exists”
When is proof by induction most useful
When previous results seem to build upon each other to yield a later result
