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.

Conditions and key results

An equivalence proof must cover all assignments or use previously established equivalence laws at every rewrite. Similar truth values in selected examples are insufficient. The converse $Q\to P$ is not equivalent to $P\to Q$ in general, whereas the contrapositive is.

A reliable strategy

1. Identify the main connective and decide whether a truth table or sequence of laws is shorter.
2. If using a table, include every $2^n$ assignment and compute intermediate columns.
3. If rewriting, name a valid equivalence law at each step and preserve parentheses.
4. Check the final claim on assignments most likely to distinguish the formulas.

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

Verification and reasonableness

• Build a complete truth table for the original and final forms and compare their last columns.
• Test the assignment that would falsify an implication: premise true, conclusion false.
• Reverse each algebraic-style rewrite; genuine equivalence laws work in both directions.

Practice

1. Rewrite $\neg(P\land Q)$ without a negated conjunction.
2. Rewrite $P\to Q$ using only $\neg$ and $\lor$.
3. Are $P\to Q$ and $Q\to P$ equivalent?

Further deduction

Absorption gives $P\lor(P\land Q)\equiv P$: if $P$ is true the whole disjunction is true, and if $P$ is false both $P$ and $P\land Q$ are false. Its dual is $P\land(P\lor Q)\equiv P$. These laws can simplify a condition without distributing every term. By contrast, logical implication $P\models Q$ is one-directional: every model of $P$ is a model of $Q$, but equivalence requires implication in both directions.

Normal forms provide standardized targets: conjunctive normal form is an AND of OR-clauses, while disjunctive normal form is an OR of AND-terms. Truth-table rows can construct either form, though algebraic simplification often yields a much shorter equivalent statement.

Related topics

• Truth Tables
• Logic and Statements
• Methods of Proof