Proof Flashcards
1
Q
NOT P
A
¬ P
2
Q
P AND Q
A
P ∧ Q
3
Q
P OR Q
A
P ∨ Q
4
Q
If P then Q
A
P ⟹ Q
5
Q
P if and only if Q
A
P ⟺ Q
6
Q
NOT (P AND Q)
A
¬ P ∨ ¬Q
(NOT P) OR (NOT Q)
7
Q
NOT (P OR Q)
A
¬ P ∧ ¬Q
(NOT P) AND (NOT Q)
8
Q
NOT (If P then Q)
A
P ∧ (¬Q)
P AND (NOT Q)
9
Q
NOT (For all x ∈ S, P(x))
A
There exists x ∈ S, (¬P(x))
10
Q
NOT (There exists x ∈ S, P(x))
A
For all x ∈ S, (¬P(x))
11
Q
Direct proof steps
A
- Write down assumptions and known facts
- Create a logical chain of argument
- Deduce the statement to be proven
12
Q
Proof by cases
A
split the proposition into a finite number of cases and verify the proposition in each case
13
Q
Proof by contradiction steps
A
- 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
14
Q
Proof by induction steps
A
- 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)
15
Q
Proof by construction
A
- 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
