Implications
Definitions
Implication, Hypothesis, Conclusion
Definition
| T | T | T |
| T | F | F |
| F | T | T |
| F | F | T |
If
Remark
Vacuous Truth
Definition
When the hypothesis can never be fulfilled, so the statement is true
Example
Converse and Contrapositive
Converse
Definition
The converse of
Contrapositive
Definition
The contrapositive of
Theorem
I.e the contrapositive is logically equivalent to the original implication.
| T | T | F | F | T | T | T | T |
| T | F | F | T | F | F | T | T |
| F | T | T | F | T | T | F | F |
| F | F | T | T | T | T | T | T |
Negation of an Implication
(1) See De Morgan's law
Definition
Proof
Proof Method - Proving Implications
Proof
- To prove the implication
, assume that the hypothesis is true, and use this assumption to show is true. The hypothesis is what you start with, and the conclusion is where you must end up - To prove the universally quantified implication
, let be an arbitrary element of , assume that the hypothesis is true, and use this assumption to show that the conclusion is true.
Tip
Implications are "distributive"
Example
Let
Let
Proof Method - Contrapositive
Proof
- For proving an
, replace it with its contrapositive . Then prove this contrapositive, usually via direct proof. - To prove the universally quantified implication
, prove instead
With an implication of the form
Proof Method - Elimination
Proof
1: We assume