Definition 1.27.
Let \(P\) and \(Q\) be statements. We say that \(P\) implies \(Q\) if the statement \(P \to Q\) is a tautology.
Section 1.2 Relations Between Statements
Up until now we have constructed statements; now we want to discuss relations between them. Relations between statements are not formal statements in themselves, but are “meta-statements” that we make about statements. The two types of such relations we will study, namely, implication and equivalence, are the meta-statement analogs of conditionals and biconditionals.
Subsection Implications
“Implication is thus the very texture of our web of belief, and logic is the theory that traces it.”―Willard Van Orman Quine
Convention 1.28.
We abbreviate the English expression “\(P\) implies \(Q\)” with the notation “\(P ⇒ Q\text{.}\)”
The intuitive idea of logical implication is that statement \(P\) implies statement \(Q\) if necessarily \(Q\) is true whenever \(P\) is true. In other words, it can never be the case that \(P\) is true and \(Q\) is false. Necessity is the key here, because one statement implying another should not simply be a matter of coincidentally appropriate truth values.
Remark 1.29.
It is important to note the difference between the notations “\(P ⇒ Q\)” and “\(P \to Q\text{.}\)” The notation “\(P \to Q\)” is a statement; it is a compound statement built up out of the statements \(P\) and \(Q\text{.}\) The notation “\(P ⇒ Q\)” is a meta-statement, which is simply a shorthand way of writing the English expression “\(P\) implies \(Q\text{,}\)” and it means that \(P \to Q\) is not just true in some particular instances, but is a tautology.
It might appear at first glance as if we are not introducing anything new here, given that we are defining implication in terms of conditional statements, but there is a significant new idea in the present discussion, which is that we single out those situations where \(P \to Q\) is not just a statement (which is always the case), but where \(P \to Q\) is a tautology.
In particular, the following implications will be used extensively.
Example 1.30. Important Implications.
Let \(P, Q, R\) and \(S\) be statements.
-
Modus Ponens.\(\displaystyle (P \to Q) \wedge P ⇒ Q\)
-
Modus Tollens.\(\displaystyle (P \to Q) \wedge ¬Q ⇒ ¬P\)
-
Simplification.\(\displaystyle P \wedge Q ⇒ P\)
-
Simplification.\(\displaystyle P \wedge Q ⇒ Q\)
-
Addition.\(\displaystyle P ⇒ P \vee Q\)
-
Addition.\(\displaystyle Q ⇒ P \vee Q\)
-
Modus Tollendo Ponens.\(\displaystyle (P \vee Q) \wedge ¬P ⇒ Q\)
-
Modus Tollendo Ponens.\(\displaystyle (P \vee Q) \wedge ¬Q ⇒ P\)
-
Biconditional-Conditional.\(\displaystyle P ↔ Q ⇒ P \to Q\)
-
Biconditional-Conditional.\(\displaystyle P ↔ Q ⇒ Q \to P\)
-
Conditional-Biconditional.\(\displaystyle (P \to Q) \wedge (Q \to P) ⇒ P ↔ Q\)
-
Hypothetical Syllogism.\(\displaystyle (P \to Q) \wedge (Q \to R) ⇒ P \to R\)
-
Constructive Dilemma.\(\displaystyle (P \to Q) \wedge (R \to S) \wedge (P \vee R) ⇒ Q \vee S\)
The implications stated in Example 1.30 were chosen because they are symbolic statements of various rules of valid argumentation.
Subsection Equivalent Statements
“Too much may be the equivalent of none at all.”―Lee Loevinger
Logical implication is not always reversible.
Example 1.31.
Written in symbols, we saw that \(¬(P \to Q) ⇒ P ∨ Q\text{.}\) On the other hand, the same truth tables used to establish this implication also show that \(P ∨ Q\) does not imply \(¬(P \to Q)\text{.}\) For example, when P and Q are both true, then \(P ∨ Q\) is true, but \(¬(P \to Q)\) is false. Alternatively, it can be seen by a truth table that \((P ∨ Q) \to [¬(P \to Q)]\) is not a tautology.
Some logical implications, however, are reversible. Such implications are very convenient, and they convey the idea of logical equivalence, to which we now turn.
Definition 1.32.
Let \(P\) and \(Q\) be statements. We say that \(P\) and \(Q\) are equivalent if the statement \(P ↔ Q\) is a tautology. We abbreviate the English expression “\(P\) and \(Q\) are equivalent” with the notation “\(P ⇔ Q\text{.}\)”
The intuitive idea of equivalence of statements is that to claim that statements \(P\) and \(Q\) are equivalent means that necessarily \(P\) is true if and only if \(Q\) is true. Necessity is once again the key here.
Such equivalences will allow us to find alternative forms of the statements of some theorems, and these alternative forms are sometimes easier to prove than the originals.
Remark 1.33.
Certainly, two different English sentences can convey equivalent statements, for example “if it rains I will stay home” and “I will stay home if it rains.” These two statements are both English variants of \(P \to Q\text{,}\) where \(P = \)“it rains,” and \(Q = \)“I will stay home.” The difference between these two statements is an issue only of the flexibility of the English language; symbolically, these two statements are identical, not just equivalent.
Warning 1.34.
It is important to note the difference between the notations “\(P ⇔ Q\)” and “\(P ↔ Q\text{.}\)” The latter is a statement, whereas the former is a meta-statement, which is simply a shorthand way of writing the English expression “\(P\) is equivalent to \(Q\text{.}\)”
Example 1.35. Double Negation.
\(¬(¬P) ⇔ P\text{.}\)
Remark 1.36.
Example 1.35 might appear innocuous, but this equivalence plays a very important role in standard mathematical proofs. In informal terms, the equivalence of \(¬(¬P)\) and \(P\) means that “two negatives cancel each other out.”
Example 1.37. Important Equivalent Statements.
Let \(P\text{,}\) \(Q\) and \(R\) be statements.
-
Commutative Law.\(P ∨ Q ⇔ Q ∨ P\text{.}\)
-
Commutative Law.\(P \wedge Q ⇔ Q \wedge P\text{.}\)
-
Associative Law.\((P ∨ Q) ∨ R ⇔ P ∨ (Q ∨ R)\text{.}\)
-
Associative Law.\((P \wedge Q) \wedge R ⇔ P \wedge (Q \wedge R)\text{.}\)
-
Distributive Law.\(P \wedge (Q ∨ R) ⇔ (P \wedge Q) ∨ (P \wedge R\text{.}\)
-
Distributive Law.\(P ∨ (Q \wedge R) ⇔ (P ∨ Q) \wedge (P ∨ R)\text{.}\)
- \(P \to Q ⇔ ¬P ∨ Q\text{.}\)
-
Contrapositive.\(P \to Q ⇔ ¬Q \to ¬P\text{.}\)
- \(P ↔ Q ⇔ Q ↔ P\text{.}\)
- \(P ↔ Q ⇔ (P \to Q) \wedge (Q \to P)\text{.}\)
-
De Morgan’s Law.\(¬(P \wedge Q) ⇔ ¬P ∨ ¬Q\text{.}\)
-
De Morgan’s Law.\(¬(P ∨ Q) ⇔ ¬P \wedge ¬Q\text{.}\)
- \(¬(P \to Q) ⇔ P \wedge ¬Q\text{.}\)
- \(¬(P ↔ Q) ⇔ (P \wedge ¬Q) ∨ (¬P \wedge Q)\text{.}\)
Subsection Contrapositive, Converse, Inverse
“Logic is the hygiene the mathematician practices to keep his ideas healthy and strong.”―Hermann Weyl
Definition 1.38.
Given a conditional statement of the form \(P \to Q\text{,}\) we call \(¬Q \to ¬P\) the contrapositive of the original statement.
Definition 1.38 gives a reformulation of the biconditional in terms of conditionals.
Example 1.39.
For example, the contrapositive of “if I eat too much I will feel sick” is “if I do not feel sick I did not eat too much.”
We also give names to two other variants of statements of the form \(P \to Q\text{.}\)
Definition 1.40.
For a statement \(P \to Q\text{,}\) we call \(Q \to P\) the converse of the original statement.
Definition 1.41.
For a statement \(P \to Q\text{,}\) we call \(¬P \to ¬Q\) the inverse of the original statement.
Example 1.42.
Continuing the example of the previous paragraph, the converse of “if I eat too much I will feel sick” is “if I feel sick then I ate too much”; the inverse of the original statement is “if I did not eat too much then I will not feel sick.”
Warning 1.43.
It is important to recognize that neither the converse nor the inverse is equivalent to the original statement, as the reader can verify by constructing the appropriate truth tables.
Remark 1.44.
Although the converse and inverse of a statement are not equivalent to the original statement, we note that, however, that the converse and the inverse are equivalent to each another, as can be seen by applying Fact 1.3.2 (9) to the statement \(Q \to P\text{.}\)
Exploration 1.45.
Let \(P, Q, A\) and \(B\) be statements. Show that the following are true.
- \(P ⇔ P \vee (P \wedge Q)\text{.}\)
- \(P ⇔ P \wedge (P \vee Q)\text{.}\)
- \(P ↔ Q ⇔ (P \to Q) \wedge (¬P \to ¬Q)\text{.}\)
- \(P \to (A \wedge B) ⇔ (P \to A) \wedge (P \to B)\text{.}\)
- \(P \to (A \vee B) ⇔ (P \wedge ¬A) \to B\text{.}\)
- \((A \vee B) \to Q ⇔ (A \to Q) \wedge (B \to Q)\text{.}\)
- \((A \wedge B) \to Q ⇔ (A \to Q) \vee (B \to Q)\text{.}\)
- \((A \wedge B) \to Q ⇔ A \to (B \to Q)\text{.}\)
