Logical Equivalences

Why This Matters

Logical equivalences are the tools you'll use to transform complex statements into simpler ones, construct valid proofs, and verify arguments. When you're asked to prove two expressions are equivalent or simplify a compound proposition, you're really being tested on your ability to recognize which equivalence applies and how to chain multiple equivalences together.

These equivalences fall into distinct families: some govern how negation interacts with connectives, others describe structural properties like order and grouping, and still others handle special cases involving truth values. Knowing what type of transformation each equivalence performs matters more than raw memorization. If you can categorize an equivalence by its function, you'll navigate proofs and simplifications much more smoothly.

---

Structural Properties: Order and Grouping

These equivalences tell you that the arrangement of propositions doesn't affect truth value.

Commutativity

• Order doesn't matter for $\land$ and $\lor$: $P \land Q \equiv Q \land P$ and $P \lor Q \equiv Q \lor P$
• This applies only to conjunction and disjunction. Implication is not commutative: $P \to Q \not\equiv Q \to P$. (Consider: "if it rains, the ground is wet" does not mean "if the ground is wet, it rained.")
• Use commutativity to rearrange operands before applying other equivalences like distribution or absorption.

Associativity

• Grouping doesn't matter for repeated $\land$ or $\lor$: $(P \land Q) \land R \equiv P \land (Q \land R)$, and likewise for $\lor$
• This lets you drop parentheses when chaining the same connective, writing simply $P \land Q \land R$.
• You'll rely on this during multi-step simplifications where you need to regroup terms before applying distributivity.

Idempotence

• Repeating a proposition has no effect: $P \land P \equiv P$ and $P \lor P \equiv P$
• This eliminates redundancy when the same variable appears multiple times. It often shows up after applying other rules that produce duplicate terms.

---

Negation Interactions: De Morgan's and Double Negation

These equivalences govern how negation distributes through or cancels within compound statements.

Double Negation

• Two negations cancel: $\lnot(\lnot P) \equiv P$
• This is a cleanup rule. You'll frequently use it after applying De Morgan's or other negation rules to tidy up the result.
• It works in both directions: you can add double negations strategically to set up other transformations.

De Morgan's Laws

• Negation flips the connective and distributes inward:
  • $\lnot(P \land Q) \equiv \lnot P \lor \lnot Q$
  • $\lnot(P \lor Q) \equiv \lnot P \land \lnot Q$
• These are probably the most frequently tested equivalences. Expect to apply them in nearly every simplification problem.
• The pattern: negating a conjunction produces a disjunction of negations, and negating a disjunction produces a conjunction of negations. The connective always flips.

---

Distribution and Absorption: Restructuring Expressions

These equivalences let you expand or collapse expressions by distributing one connective over another or absorbing redundant terms.

Distributivity

• $\land$ distributes over $\lor$, and $\lor$ distributes over $\land$:
  • $P \land (Q \lor R) \equiv (P \land Q) \lor (P \land R)$
  • $P \lor (Q \land R) \equiv (P \lor Q) \land (P \lor R)$
• This works in both directions. Left-to-right expands; right-to-left factors out a common term.
• Distributivity is the key tool for converting between conjunctive normal form (CNF) and disjunctive normal form (DNF), which require systematic expansion.

Note that the second form ($\lor$ distributing over $\land$) has no direct analogue in ordinary arithmetic, so it can feel unintuitive at first. Verify it with a truth table if you're unsure.

Absorption Laws

• A proposition "absorbs" a compound containing itself:
  • $P \land (P \lor Q) \equiv P$
  • $P \lor (P \land Q) \equiv P$
• These are powerful simplifiers that eliminate entire subexpressions when a variable appears at multiple levels.
• Absorption is often the final step after distribution reveals redundant structure.

---

Special Truth Values: Identity, Domination, and Negation Laws

These equivalences describe how propositions interact with the constants True ($\top$) and False ($\bot$), plus the fundamental relationship between a proposition and its negation.

Identity Laws

• True is the identity for $\land$; False is the identity for $\lor$:
  • $P \land \top \equiv P$
  • $P \lor \bot \equiv P$
• Think of these like multiplying by 1 or adding 0 in arithmetic. The constant doesn't change the proposition.
• You'll typically use these to simplify after other operations introduce truth constants.

Domination Laws

• False dominates $\land$; True dominates $\lor$:
  • $P \land \bot \equiv \bot$
  • $P \lor \top \equiv \top$
• The entire expression collapses regardless of what $P$ is. Check for these early in simplification to avoid unnecessary work on subexpressions that won't survive.

Negation Laws (Excluded Middle and Contradiction)

• A proposition and its negation together yield constants:
  • $P \lor \lnot P \equiv \top$ (law of excluded middle)
  • $P \land \lnot P \equiv \bot$ (law of contradiction)
• These establish that in classical logic, every proposition is either true or false, and no proposition is both.
• Combine these with identity and domination laws to simplify expressions containing both $P$ and $\lnot P$.

---

Conditional Transformations: Implication, Contraposition, and More

These equivalences handle the conditional ($\to$) and biconditional ($\leftrightarrow$), converting them into forms using only $\lnot$, $\land$, and $\lor$ when needed.

Implication (Material Conditional)

• Implication reduces to disjunction: $P \to Q \equiv \lnot P \lor Q$
• This is your go-to move for eliminating $\to$ when you need to work with only the basic connectives $\lnot$, $\land$, $\lor$.
• It also clarifies why an implication is false only when the antecedent is true and the consequent is false: $\lnot P \lor Q$ is false only when $\lnot P$ is false (so $P$ is true) and $Q$ is false.

Contraposition

• An implication equals its contrapositive: $P \to Q \equiv \lnot Q \to \lnot P$
• Proving the contrapositive is often easier than a direct proof, making this one of the most useful proof techniques.
• Be careful to distinguish the contrapositive ($\lnot Q \to \lnot P$, equivalent to the original) from the converse ($Q \to P$, not equivalent) and the inverse ($\lnot P \to \lnot Q$, also not equivalent). Only the contrapositive is logically equivalent to the original.

Biconditional

• Biconditional means "both directions": $P \leftrightarrow Q \equiv (P \to Q) \land (Q \to P)$
• It's true when both sides have the same truth value: both true or both false.
• An alternative useful form: $P \leftrightarrow Q \equiv (P \land Q) \lor (\lnot P \land \lnot Q)$. This version is handy when you want to eliminate $\to$ entirely.

Exportation

• A conjunction in the antecedent can be "exported" into a nested conditional: $(P \land Q) \to R \equiv P \to (Q \to R)$
• This lets you assume premises one at a time, which is useful in proof construction. Instead of assuming $P \land Q$ all at once, you assume $P$, then assume $Q$, then derive $R$.

---

Tautologies and Contradictions: The Logical Extremes

These aren't equivalences in the usual sense but rather classifications of statements that are always true or always false.

Tautology and Contradiction

• A tautology is true under every possible assignment of truth values. Classic example: $P \lor \lnot P$.
• A contradiction is false under every possible assignment. Classic example: $P \land \lnot P$.
• A common simplification goal is to reduce an expression to $\top$ or $\bot$. If you reach $\top$, the original expression is always true; if you reach $\bot$, it's always false.

---

Quick Reference Table

---

Self-Check Questions

1. Which two equivalences would you use in sequence to simplify $\lnot(P \land \lnot Q)$ into a form with no negations of compound statements?

2. Explain why $P \to Q$ is not equivalent to $Q \to P$, but is equivalent to $\lnot Q \to \lnot P$. What distinguishes contraposition from the converse?

3. Given the expression $P \lor (P \land Q)$, which equivalence simplifies it to $P$? How does this differ from applying idempotence?

4. Compare distributivity and De Morgan's Laws: both transform expressions with mixed $\land$ and $\lor$. When would you reach for each one?

5. If you simplify an expression and obtain $P \land \lnot P$ as a subexpression, what can you immediately conclude about the entire conjunction containing it? Which equivalences justify this conclusion?