Last Update: 24 February 2009
Note: or material is highlighted |
If the logical form is: | Then a strategy is: |
---|---|
p | Indirect Proof: Assume/suppose/make believe that ¬p & then try to derive a contradiction; i.e., try to find r such that (r ∧ ¬r) |
PRED(c), where PRED(c) =def DEF(c) | Try to prove DEF(c)
In general, wherever possible in a proof, |
¬P(x), where P(x) is a compound proposition |
Try to prove
Q(x), where Q(x) ≡ ¬P(x), but the "¬" has been moved to the right by DeMorgan |
(p → q), where p is a contradiction | "Vacuous" proof: (p → q) must be true! |
(p → q), where q is a tautology | "Trivial" proof: (p → q) must be true! |
(p → q) | Direct Proof: Assume p & then try to show q
Hint: |
(p → q) | Indirect Proofs:
Proof by Contraposition: Try to show (¬q → ¬p) (by using one of the other strategies for "→")
Proof by Contradiction: |
(p_{1} ∨ p_{2}) → q
To make this simpler to understand, |
Proof by Cases: Try to show each of the following: (p_{1} → q) and (p_{2} → q) (by using any of the above strategies for "→") |
(p ↔ q) | Try to show both (p → q) and (q → p) (by using any of the above strategies for "→") |
(p_{1} ↔ p_{2} ↔ p_{3})
To make this simpler to understand, |
Try to show all of the following: (p_{1} → p_{2}) and (p_{2} → p_{3}) and (p_{3} → p_{1}) (by using any of the above strategies for "→") |
∀x[P(x) → Q(x)] | Try to show [P(c) → Q(c)], for arbitrary c (by using one of the strategies for "→"; then apply UG) |
∃xP(x) | Constructive Proof: Find c such that P(c)
Non-constructive Proof by Contradiction: |
¬∀xP(x) | Find a counterexample; i.e., try to show ∃x¬P(x) |