Implication and Equivalence
Learning Objectives
From Combining to Reasoning
In the previous lesson we learned to combine propositions using negation, conjunction, and disjunction. These connectives express what is the case: “\(P\) and \(Q\),” “\(P\) or \(Q\),” “not \(P\).”
Mathematics, however, is not merely a catalogue of facts. It is a discipline of reasoning — of drawing conclusions from hypotheses. The sentence “if a number is divisible by 4, then it is divisible by 2” does not simply combine two propositions; it asserts a relationship of dependency between them. This is the domain of implication.
When such a dependency runs in both directions — “a number is even if and only if it is divisible by 2” — we have an equivalence. Together, implication and equivalence complete the set of classical propositional connectives.
Implication (\(\to\))
The implication (or material conditional) of propositions \(P\) and \(Q\), written \(P \to Q\) (read “if \(P\) then \(Q\),” or “\(P\) implies \(Q\)”), is the proposition that is false if and only if the hypothesis \(P\) is true and the conclusion \(Q\) is false.
Formally:
\[P \to Q \;=\; \begin{cases} F & \text{if } P = T \text{ and } Q = F \\ T & \text{otherwise} \end{cases}\]
In the expression \(P \to Q\):
\(P\) is called the hypothesis (or antecedent, or premise)
\(Q\) is called the conclusion (or consequent)
Truth Table
\[\begin{array}{|c|c|c|} \hline P & Q & P \to Q \\ \hline T & T & T \\ T & F & F \\ F & T & T \\ F & F & T \\ \hline \end{array}\]
Implication — Examples
Let \(P\): “\(6\) is divisible by 4” (\(F\)) and \(Q\): “\(6\) is divisible by 2” (\(T\)). Then \(P \to Q\): “If \(6\) is divisible by 4, then \(6\) is divisible by 2” → \(T\). — The hypothesis is false, so the implication is true regardless of the conclusion.
Let \(P\): “\(8\) is divisible by 4” (\(T\)) and \(Q\): “\(8\) is divisible by 2” (\(T\)). Then \(P \to Q\) → \(T\). — True hypothesis, true conclusion: the implication holds.
Let \(P\): “\(4 > 1\)” (\(T\)) and \(Q\): “\(4\) is odd” (\(F\)). Then \(P \to Q\): “If \(4 > 1\), then \(4\) is odd” → \(F\). — This is the only case in which an implication is false: a true hypothesis leading to a false conclusion.
Vacuous Truth and the Material Conditional
The third and fourth rows of the truth table — where \(P\) is false and the implication is true regardless of \(Q\) — trouble many students. When the hypothesis is false, the implication is said to be vacuously true.
Consider: “If \(1 = 2\), then the Moon is made of cheese.” In everyday language, this seems absurd. In logic, it is true. The implication \(P \to Q\) makes a promise: whenever \(P\) holds, \(Q\) will also hold. When \(P\) does not hold, the promise is never tested — and an untested promise is not broken.
This convention is not arbitrary. It ensures that implication behaves consistently with the other connectives. In particular, the material conditional satisfies a fundamental relationship:
\[P \to Q \;\;\text{ has the same truth values as }\;\; \neg P \lor Q\]
This can be verified by comparing the truth tables column by column. When \(P = F\), we have \(\neg P = T\), so \(\neg P \lor Q = T\) regardless of \(Q\) — matching exactly the vacuous-truth rows.
Related Conditionals
Given an implication \(P \to Q\), three related conditionals arise naturally:
The converse: \(Q \to P\)
The inverse: \(\neg P \to \neg Q\)
The contrapositive: \(\neg Q \to \neg P\)
By inspecting their truth tables, one can verify that the contrapositive has the same truth values as the original implication, while the converse and inverse do not. We will prove this systematically in the next lesson, when we formally define logical equivalence. For now, note a useful consequence: to prove “if \(P\) then \(Q\),” one may equivalently prove “if not \(Q\) then not \(P\).”
Necessary Conditions and Sufficient Conditions
The implication \(P \to Q\) admits two complementary readings:
\(P\) is a sufficient condition for \(Q\): the truth of \(P\) is enough to guarantee the truth of \(Q\).
\(Q\) is a necessary condition for \(P\): \(Q\) must be true whenever \(P\) is true. Equivalently, the falsity of \(Q\) is enough to guarantee the falsity of \(P\).
These are two descriptions of the same logical relationship, read from different ends.
Formally, to say “\(Q\) is necessary for \(P\)” is precisely to assert \(P \to Q\). To say “\(P\) is sufficient for \(Q\)” is also to assert \(P \to Q\).
Necessary and Sufficient — Examples
“If \(n\) is divisible by 6, then \(n\) is divisible by 3.” — Divisibility by 6 is sufficient for divisibility by 3 (every multiple of 6 is a multiple of 3). Divisibility by 3 is necessary for divisibility by 6 (a number that is not divisible by 3 cannot be divisible by 6). But divisibility by 3 is not sufficient for divisibility by 6: \(9\) is divisible by 3 but not by 6.
“If a quadrilateral is a square, then it has four right angles.” — Being a square is sufficient for having four right angles. Having four right angles is necessary for being a square — but not sufficient, since a rectangle also has four right angles.
Equivalence (\(\leftrightarrow\))
The equivalence (or biconditional) of propositions \(P\) and \(Q\), written \(P \leftrightarrow Q\) (read “\(P\) if and only if \(Q\)”), is the proposition that is true if and only if \(P\) and \(Q\) have the same truth value.
Formally:
\[P \leftrightarrow Q \;=\; \begin{cases} T & \text{if } P = Q \\ F & \text{if } P \neq Q \end{cases}\]
Truth Table
\[\begin{array}{|c|c|c|} \hline P & Q & P \leftrightarrow Q \\ \hline T & T & T \\ T & F & F \\ F & T & F \\ F & F & T \\ \hline \end{array}\]
Equivalence — Examples
Let \(P\): “\(n\) is even” and \(Q\): “\(n\) is divisible by 2.” Then \(P \leftrightarrow Q\) is true — these two properties hold for exactly the same integers.
Let \(P\): “\(4 > 0\)” (\(T\)) and \(Q\): “\(3 + 2 = 5\)” (\(T\)). Then \(P \leftrightarrow Q\) → \(T\). Both are true, so they share the same truth value.
Let \(P\): “\(2 > 3\)” (\(F\)) and \(Q\): “\(7 = 5\)” (\(F\)). Then \(P \leftrightarrow Q\) → \(T\). Both are false — same truth value.
Let \(P\): “\(5 > 1\)” (\(T\)) and \(Q\): “\(5\) is even” (\(F\)). Then \(P \leftrightarrow Q\) → \(F\). Different truth values.
Equivalence as Mutual Implication
The biconditional can be decomposed into two implications:
\[P \leftrightarrow Q \;\;\text{ has the same truth values as }\;\; (P \to Q) \land (Q \to P)\]
This can be verified by comparing truth tables. The phrase “if and only if” (often abbreviated iff) captures this duality: \(P \leftrightarrow Q\) means that \(P\) implies \(Q\) and \(Q\) implies \(P\).
In the language of conditions, \(P \leftrightarrow Q\) asserts that \(P\) is both necessary and sufficient for \(Q\) (and vice versa).
The Five Classical Connectives
With implication and equivalence, we have now introduced all five classical propositional connectives:
\[\neg \qquad \land \qquad \lor \qquad \to \qquad \leftrightarrow\]
Every compound proposition in classical propositional logic can be built from atomic propositions and these five operations. (In fact, as we will see in later lessons, a smaller subset suffices — but that is a question of logical economy, not of expressiveness.)
Exercise 1
Determine the truth value of each implication or equivalence.
Exercise 2
For each statement, determine what kind of condition the hypothesis is for the conclusion.
Exercise 3
Determine the truth value. Evaluate step by step, working from the innermost sub-expressions outward.
Critical Examination
A student reads the implication “If \(1 = 2\), then \(1 = 2\)” and accepts it as true (both sides share the same truth value: both false, so row 4 of the truth table gives \(T\)).
Then the student reads “If \(1 = 2\), then the Moon is made of cheese” and protests: “This should be false — the hypothesis has nothing to do with the conclusion.”
Is the student right to object?
Analysis
The objection rests on an intuition about relevance: that an implication should express a meaningful connection between hypothesis and conclusion. This is a perfectly reasonable expectation in everyday reasoning, and there are indeed formal logics — called relevance logics — that build this requirement into the definition of implication.
Classical logic, however, deliberately does not. The material conditional \(P \to Q\) is defined purely in terms of truth values: it is false only when \(P\) is true and \(Q\) is false. The subject matter, meaning, or causal connection between \(P\) and \(Q\) plays no role. Both “If \(1 = 2\), then \(1 = 2\)” and “If \(1 = 2\), then the Moon is made of cheese” are true for exactly the same reason: the hypothesis is false, so the promise “whenever \(P\) holds, \(Q\) will hold” is never tested.
This is a design choice, not a defect. The material conditional is simple, compositional, and sufficient for all of classical mathematics. The price of this simplicity is that some true implications feel unintuitive. The alternative — requiring “relevance” — introduces significant technical complexity and is not part of standard mathematical practice.
In this course, we work within classical logic. The material conditional is our implication.
Summary
Implication (\(P \to Q\)) is false only when the hypothesis is true and the conclusion is false. When the hypothesis is false, the implication is vacuously true.
In \(P \to Q\): \(P\) is a sufficient condition for \(Q\), and \(Q\) is a necessary condition for \(P\).
The contrapositive (\(\neg Q \to \neg P\)) has the same truth values as the original implication; the converse (\(Q \to P\)) and inverse (\(\neg P \to \neg Q\)) generally do not.
Equivalence (\(P \leftrightarrow Q\)) is true when \(P\) and \(Q\) have the same truth value. It can be read as mutual implication: \((P \to Q) \land (Q \to P)\).
\(P \leftrightarrow Q\) means \(P\) is necessary and sufficient for \(Q\).
The five classical connectives — \(\neg, \land, \lor, \to, \leftrightarrow\) — are now all defined.