Logical Equivalence

Precise definition

Propositions $P$ and $Q$ are logically equivalent, written $P\equiv Q$, when they have the same truth value under every assignment of their atomic variables. Equivalently, $P\leftrightarrow Q$ is a tautology. Equivalence permits replacement inside a larger expression without changing its truth function.

Notation and mathematical language

Key laws include $\neg(P\land Q)\equiv\neg P\lor\neg Q$, $\neg(P\lor Q)\equiv\neg P\land\neg Q$, $P\to Q\equiv\neg P\lor Q$, and $P\to Q\equiv\neg Q\to\neg P$. Equality-like notation $\equiv$ here concerns truth tables, not identical wording.

Conceptual picture

Equivalent formulas are different descriptions of the same region of a truth table. De Morgan's laws switch the connective because negating a requirement that both hold means at least one fails; negating a claim that either holds means both fail.

Fully worked example

Interpretation and application

Logic simplification reduces conditions in circuits, database filters, and programs. Equivalent code conditions should still be tested for side effects or undefined values, because logical equivalence assumes propositions already possess truth values and does not model evaluation order or exceptions.

Common mistakes