✦ScienexySCIENCE KNOWLEDGE LIBRARY
reference · SCI-MAT-012-015

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

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.

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