Logical Equivalences

Why This Matters

Logical equivalences are the backbone of formal reasoning—they're 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 being tested on your ability to recognize which equivalence applies and how to chain multiple equivalences together. These aren't just abstract rules; they're the grammar of logical manipulation.

Think of equivalences as falling 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. Don't just memorize formulas—know what type of transformation each equivalence performs and when to reach for it. If you can categorize an equivalence by its function, you'll navigate proofs and simplifications with confidence.

---

Structural Properties: Order and Grouping

These equivalences tell you that the arrangement of propositions doesn't affect truth value—only the connectives and the propositions themselves matter.

Commutativity

• Order doesn't matter for $\land$ and $\lor$—you can freely swap operands: $P \land Q \equiv Q \land P$ and $P \lor Q \equiv Q \lor P$
• Applies only to conjunction and disjunction—implication is not commutative ($P \to Q \not\equiv Q \to P$)
• Use it to rearrange expressions before applying other equivalences like distribution or absorption

Associativity

• Grouping doesn't matter for repeated $\land$ or $\lor$—parentheses can shift freely: $(P \land Q) \land R \equiv P \land (Q \land R)$
• Lets you drop parentheses when chaining the same connective, writing simply $P \land Q \land R$
• Critical for multi-step simplifications where you need to regroup before applying distributivity

Idempotence

• Repeating a proposition has no effect—$P \land P \equiv P$ and $P \lor P \equiv P$
• Eliminates redundancy when the same variable appears multiple times in an expression
• Often appears after applying absorption or when simplifying expressions with repeated terms

---

Negation Interactions: De Morgan's and Double Negation

These equivalences govern how negation distributes through or cancels within compound statements—essential for pushing negations inward or outward.

Double Negation

• Two negations cancel—$\lnot(\lnot P) \equiv P$, returning you to the original proposition
• Foundation for many proof steps—you'll use this to "clean up" after applying other negation rules
• 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—$\lnot(P \land Q) \equiv \lnot P \lor \lnot Q$ and $\lnot(P \lor Q) \equiv \lnot P \land \lnot Q$
• The most frequently tested equivalence—expect to apply these in nearly every simplification problem
• Remember the pattern: negating a conjunction gives a disjunction (and vice versa), with each component negated

---

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 vice versa—$P \land (Q \lor R) \equiv (P \land Q) \lor (P \land R)$ and $P \lor (Q \land R) \equiv (P \lor Q) \land (P \lor R)$
• Works in both directions—use left-to-right to expand, right-to-left to factor out common terms
• Key for converting between CNF and DNF—conjunctive and disjunctive normal forms require systematic distribution

Absorption Laws

• A proposition "absorbs" a disjunction or conjunction containing itself—$P \land (P \lor Q) \equiv P$ and $P \lor (P \land Q) \equiv P$
• Powerful simplification tool—eliminates entire subexpressions when a variable appears at multiple levels
• 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$ and $P \lor \bot \equiv P$
• "Neutral elements" that don't change the proposition—like multiplying by 1 or adding 0 in arithmetic
• Use these to simplify after other operations introduce truth constants

Domination Laws

• False dominates $\land$; True dominates $\lor$—$P \land \bot \equiv \bot$ and $P \lor \top \equiv \top$
• Entire expressions collapse when a dominating value appears—no matter what $P$ is
• Check for these early in simplification to avoid unnecessary work on irrelevant subexpressions

Negation Laws (Excluded Middle and Contradiction)

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

---

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$
• Essential for eliminating $\to$ when you need to work with only basic connectives
• Explains why implications are false only when the antecedent is true and consequent is false

Contraposition

• An implication equals its contrapositive—$P \to Q \equiv \lnot Q \to \lnot P$
• Powerful proof technique—proving the contrapositive is often easier than direct proof
• Distinct from converse and inverse—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)$
• True when both sides match—either both true or both false; equivalence of truth values
• Can also be written as $(P \land Q) \lor (\lnot P \land \lnot Q)$—useful for certain simplifications

Exportation

• Nested implication equals conjunction in antecedent—$(P \land Q) \to R \equiv P \to (Q \to R)$
• Lets you "export" a conjunct from the antecedent into a nested conditional structure
• Useful in proof construction when you want to assume premises one at a time

---

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—benchmarks for evaluating expressions.

Tautology and Contradiction

• A tautology is true under all interpretations—classic example: $P \lor \lnot P$ (law of excluded middle)
• A contradiction is false under all interpretations—classic example: $P \land \lnot P$
• Simplification goal: reduce expressions to $\top$ (tautology) or $\bot$ (contradiction) when possible to determine validity

---

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?