Skip to main content

Propositions, Implication, and Equivalence

What This Concept Is​

A proposition is a statement that has a single, well-defined truth value: true or false. "$2 + 2 = 4$" is a proposition. "$x + 1 > 0$" is not a proposition by itself, because its truth value depends on the unbound variable $x$ -- it is a predicate waiting to become a proposition once $x$ is assigned a value from a chosen domain.

Logical connectives -- negation ($\lnot$), conjunction ($\land$), disjunction ($\lor$), implication ($\rightarrow$), and biconditional ($\leftrightarrow$) -- combine propositions into larger compound statements. Classical logic is truth-functional: the truth value of a compound is determined entirely by the truth values of its parts. That compositional property is what makes propositional logic a calculus instead of a debate.

The two connectives that dominate proof work are implication and biconditional:

  • $P \rightarrow Q$ ("if $P$ then $Q$") says: whenever $P$ holds, $Q$ must also hold. By the classical convention, it is vacuously true whenever $P$ is false -- this is why "if pigs fly, then $1 = 2$" is technically a true implication.
  • $P \leftrightarrow Q$ ("$P$ if and only if $Q$") is shorthand for $(P \rightarrow Q) \land (Q \rightarrow P)$. It is two obligations bundled into one symbol.

Two propositions are logically equivalent, written $P \equiv Q$, when they have the same truth value under every truth assignment. Equivalence is the relation that lets you substitute one form for another inside any proof without changing validity -- which is why moves such as contrapositive reasoning and De Morgan's laws are safe. Equivalence is also how you define "the same theorem written two different ways."

A convenient mental model: think of each propositional variable as a switch and each connective as a gate. A proof is not about the switches; it is about which configurations of switches the theorem rules in or out.

The shapes you will see most often in this module, written symbolically:

ShapeEnglishProof obligation
$P \rightarrow Q$"if $P$ then $Q$"one direction
$P \leftrightarrow Q$"$P$ iff $Q$"two directions
$\forall x \in D,\ P(x)$"every $x$ in $D$ satisfies $P$"prove for arbitrary $x$
$\exists x \in D,\ P(x)$"some $x$ in $D$ satisfies $P$"exhibit a witness
$\forall x \in D,\ P(x) \rightarrow Q(x)$"every $x$ that is $P$ is also $Q$"assume $P(x)$ for arbitrary $x$, derive $Q(x)$

The last row is by far the most common theorem shape you will meet; recognise it on sight.

Why It Matters Here​

Almost every proof in this module begins by reading the logical shape of the statement correctly. If you misread an implication as an equivalence, you quietly take on twice the proof burden -- or worse, you finish the one direction and declare victory. If you treat an equivalence as a single implication, you hand in half a proof. Most beginner failures at mathematical writing are not algebraic mistakes; they are logical mis-readings of the goal.

The propositional backbone also extends beyond this module. Cluster 2 proof strategies (direct, contrapositive, contradiction) are chosen based on the connective structure of the theorem. Cluster 3's set-equality proofs are two implications glued together. Cluster 4's relation properties (reflexive, symmetric, transitive, antisymmetric) are each universally quantified implications on pairs. Cluster 5's induction step is itself an implication $P(n) \rightarrow P(n+1)$.

Later semesters keep cashing in this same vocabulary. Loop invariants in Semester 2 are written as implications ("if the invariant held at the top of iteration $k$, it still holds at iteration $k+1$"). Preconditions and postconditions in Semester 4/5 are propositions tied by implication arrows. Service contracts in Semester 7 are equivalences between caller assumptions and callee guarantees. If the propositional backbone is shaky here, every later claim inherits the wobble.

Concrete Examples​

Example 1 -- reading an implication correctly.

Consider "If $n$ is divisible by 4, then $n$ is even." The hypothesis is "$n$ is divisible by 4"; the conclusion is "$n$ is even." A valid proof only needs to establish the conclusion under that assumption:

Assume $n$ is divisible by 4. Then $n = 4k$ for some integer $k$, so $n = 2(2k)$, which is even. $\blacksquare$

The converse -- "if $n$ is even, then $n$ is divisible by 4" -- is a different theorem, and it is false (take $n = 2$; it is even but not divisible by 4). A reader who silently promotes the "if" to "iff" has invented an obligation the original theorem did not carry.

Example 2 -- proving an equivalence requires both halves.

Claim: $n$ is odd $\ \leftrightarrow\ n^2$ is odd.

  • Forward ($\rightarrow$). Assume $n = 2k + 1$. Then $$n^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1,$$ which is odd by definition.
  • Backward ($\leftarrow$). Assume $n^2$ is odd. The cleanest argument is contrapositive: if $n$ were even, $n = 2k$, then $n^2 = 4k^2$ is even, contradicting the assumption. So $n$ must be odd.

Both directions must be written and labelled. A single paragraph covering only one direction does not prove the biconditional, no matter how carefully it is phrased.

Example 3 -- equivalence as a substitution license.

The identity $P \rightarrow Q \equiv \lnot P \lor Q$ justifies rewriting "if not authenticated, then reject" as "authenticated or reject" in a boolean expression during a code refactor. Without the equivalence law, the rewrite is a guess. With it, the rewrite is a theorem. This matters: static analysis tools, optimizers, and type checkers apply equivalences like this thousands of times per compile without re-deriving them.

The tiny logical algebra that students skim in week one is the same algebra every SAT solver, SMT solver, and symbolic execution engine relies on. Treat the laws as tools you will reuse, not as decoration.

Common Confusion / Misconceptions​

  1. "If" silently promoted to "if and only if." A student proves $P \rightarrow Q$ and then starts using the converse as free. Counter-argument: the converse is its own theorem; famous implications such as "differentiable $\rightarrow$ continuous" fail in the reverse direction. Discipline move: after proving $P \rightarrow Q$, ask explicitly whether the converse is also being claimed, and, if so, prove it separately.
  2. Implication confused with causation. "$P \rightarrow Q$" is a purely truth-functional relationship; it does not claim $P$ causes $Q$. "If the moon is made of cheese, then $2+2=4$" is a true implication with zero causal content. In code terms, implication is a constraint, not a dataflow edge.
  3. Vacuous truth feels like a trick. When $P$ is false, $P \rightarrow Q$ is true regardless of $Q$. This is a design choice that keeps the logic compositional: it is what lets "for all $x$ in the empty set, $P(x)$" be vacuously true, which in turn makes set-theoretic identities clean at their edge cases. See Paradoxes of material implication for the philosophical discussion.
  4. "Logically equivalent" confused with "synonymous." Equivalence is a precise truth-table relation, not a claim about meaning or connotation. "$P \land Q$" and "$Q \land P$" are equivalent; "$P \rightarrow Q$" and "$Q \rightarrow P$" are not, even though the English sounds close.

How To Use It​

When a theorem lands on your desk, classify its surface form before writing anything:

  1. Identify the outermost connective. Is the theorem a conditional, a biconditional, a universal claim, a conjunction of claims, or an existence claim?
  2. Name the hypothesis and conclusion for every implication in sight. Say them out loud.
  3. If it is a biconditional, split into two labelled directions before algebra starts.
  4. If it is a universal implication ($\forall x,\ P(x) \rightarrow Q(x)$), your opening line is almost always "Let $x$ be arbitrary and assume $P(x)$."
  5. If the claim might be false, pause before proof-writing and consider hunting for a counterexample first. Spending ten minutes looking for a witness is cheaper than a failed proof.
  6. Write the proof plan in one sentence ("Prove both directions; the reverse direction goes by contrapositive") before committing to symbols.
  7. After the proof, re-read the original statement and verify your proof closes exactly that obligation -- not a cousin of it.

Transfer / Where This Shows Up Later​

  • Semester 2 (algorithms). Every termination argument reads "if the loop has not exited, then the rank function strictly decreases" -- an implication whose contrapositive gives you the halting conclusion. Correctness proofs of sorting, search, and graph algorithms are bundles of universally quantified implications.
  • Semester 5 (concurrency). A lock invariant is a propositional claim of the form "if holder == me, then no other thread is inside the critical section." Violations are exhibited as a truth assignment that satisfies the hypothesis and falsifies the conclusion -- i.e., a counterexample in the propositional sense.
  • Semester 6 (distributed systems). Quorum correctness theorems ("if a majority of replicas ACK, then the value is durable") are implications. The converse (durability $\rightarrow$ majority ACK) is usually false in the presence of replication lag, so sloppy readers propagate a subtle bug.
  • Semester 7 (architecture / DDD). An ADR of the form "we choose X iff Y holds" is literally a biconditional; writing one direction pretends to justify the decision both ways. Risk-driven review asks readers to audit both halves.

Check Yourself​

  1. What is the difference between $P \rightarrow Q$ and $Q \rightarrow P$? Give a real-world pair where one is true and the other is false.
  2. To prove $P \leftrightarrow Q$, how many directions do you need to establish, and why can't a single cleverly worded argument replace both?
  3. Why is $P \rightarrow Q$ considered true when $P$ is false? What would break in, say, the statement "for all $x \in \emptyset$, $P(x)$" if we abandoned vacuous truth?
  4. Are $\lnot P \lor Q$ and $P \rightarrow Q$ logically equivalent? Justify with a truth table and say where this identity is useful in practice.
  5. What is the contrapositive of "if $n$ is prime and $n > 2$, then $n$ is odd"?
  6. Can two theorems with the same English hypothesis have different logical forms? Construct an example using the words "unique" vs "at least one."

Mini Drill or Application​

For each statement, rewrite it in theorem-shape language using $\forall$, $\exists$, $\rightarrow$, $\leftrightarrow$, then label the outermost connective:

  1. "A number is odd exactly when it is not even."
  2. "Every injective function from a finite set to itself is surjective."
  3. "Two sets are equal when each is a subset of the other."
  4. "Among any three consecutive integers, at least one is divisible by 3."
  5. "A binary relation is a function iff every input has exactly one related output."

For each rewrite:

  • state whether the proof obligation is a single implication, a biconditional, or a universal implication;
  • state the hypothesis and conclusion explicitly;
  • if the claim might be false, propose one candidate counterexample to try first.

Read This Only If Stuck​