Logical equivalence expresses that two formulas have identical semantic behavior. In propositional logic, two formulas are equivalent when their truth tables contain the same final truth value for every possible assignment of their variables. The relation is represented by φ ≡ ψ or by the semantic statement ⊨ (φ ↔ ψ). Important equivalence laws include double negation, De Morgan's laws, commutativity, associativity, distributivity, and implication elimination. These laws allow complicated expressions to be simplified without changing their logical meaning. Logical equivalence is useful in mathematical proofs, circuit design, programming, and formal verification.
Logical Equivalence
Two logical formulas are logically equivalent when they have the same truth value under every possible interpretation.
φ ≡ ψ
¬(p ∧ q) ≡ (¬p ∨ ¬q)
¬(p ∨ q) ≡ (¬p ∧ ¬q)
p → q ≡ ¬p ∨ q
¬¬p ≡ p
Explanation
Variables
φ, ψ: logical formulas
p, q: propositions
≡: logical equivalence
↔: biconditional
¬: negation
∧: conjunction
∨: disjunction
Example or application
The expressions p → q and ¬p ∨ q are logically equivalent because they have the same truth value for all four possible assignments of p and q.
Definition
Two logical formulas are logically equivalent if they are true under exactly the same interpretations.
Purpose
To identify different symbolic expressions that represent the same logical meaning and enable valid transformations of formulas.
Importance
Logical equivalence makes it possible to simplify formulas, prove identities, optimize digital circuits, and transform program conditions without changing their behavior.
Learning Objectives
Define logical equivalence.
Test equivalence using truth tables.
Apply De Morgan's laws.
Recognize implication elimination.
Simplify logical expressions without changing their meaning.
Key Concepts
Logical equivalence
Biconditional
Truth-table comparison
De Morgan's laws
Double negation
Logical simplification
Working Principle
Two formulas are compared across all possible interpretations. If their truth values match in every case, they are logically equivalent and can replace one another in suitable logical contexts.
Process
Identify the two formulas to compare.
List all possible truth assignments.
Evaluate each formula under every assignment.
Compare their final truth values.
Declare them equivalent if every result matches.
Applications
Simplifying mathematical proofs
Optimizing Boolean expressions
Digital circuit design
Program condition simplification
Formal verification
Automated theorem proving
Worked Example
Verify p → q ≡ ¬p ∨ q. If p = T and q = T, both expressions are true. If p = T and q = F, both are false. If p = F and q = T, both are true. If p = F and q = F, both are true. Since the results match in all four cases, the formulas are logically equivalent.
Common Misconceptions
Two formulas are not equivalent merely because they are both true in one example.
Logical equivalence is stronger than having the same truth value under a single interpretation.
Equivalent formulas may have very different symbolic structures.
Replacing a formula with an equivalent one must preserve the intended interpretation.
Practice Questions
Define logical equivalence.
How can a truth table establish equivalence?
State both of De Morgan's laws.
Show that p → q is equivalent to ¬p ∨ q.
Simplify ¬¬(p ∧ q).
Key Takeaway
Logical equivalence allows one formula to be replaced by another without changing its truth under any interpretation.
Prerequisites
Truth Values and Logical Interpretation
Logical Expressions and Formulas
Logical Validity and Logical Truth
Reference
Discrete Mathematics and Its Applications — Kenneth H. Rosen
A Mathematical Introduction to Logic — Herbert B. Enderton
Related Topics
Logical Validity and Logical Truth
Satisfiability and Unsatisfiability
Logical Expressions and Formulas
Logical Consistency and Inconsistency
Sources and verification
Sources are shown as provided in the project data. Not every source has yet been independently verified. Please report errors or missing citations.
- Source verification pending; check an authoritative textbook, university, standards body, or peer-reviewed source.
Suggest a correction or source · More in Mathematical Logic & Set Theory