Logical equivalence

Logical equivalence is the relation between formulas that have the same truth value under every interpretation and assignment. Equivalent formulas can replace one another without changing truth.

Propositional logic: A formal system for reasoning with propositions and logical connectives. Its formulas are equivalent when their truth values match under every valuation.
Logical consequence: A relation in which a conclusion is true whenever all its premises are true. Two formulas are equivalent exactly when each is a logical consequence of the other.
Logical equivalence versus material equivalence: A distinction between equivalence across all interpretations and an equivalence connective evaluated in one interpretation. A material biconditional may be true in one case without the formulas being logically equivalent.
Boolean satisfiability problem: The computational problem of deciding whether a propositional formula has a satisfying assignment. Equivalence checking can be reduced to testing whether a formula for their disagreement is unsatisfiable.
Model theory: The mathematical study of formal languages through the structures that satisfy their sentences. It supplies the interpretations over which semantic equivalence is defined.
Truth table: A table listing a formula’s truth value for each possible assignment of truth values to its variables. Comparing two columns checks equivalence across all propositional valuations.
Biconditional: A connective that is true when its two component propositions have the same truth value. The biconditional of two formulas is valid exactly when they are logically equivalent.
Logical equivalence versus logical consequence: A distinction between mutual entailment and one-way entailment between formulas. Equivalence requires consequence in both directions; consequence alone is weaker.
Equivalence checking: The task of deciding whether two expressions or systems have the same behavior under a specified semantics. Logical equivalence is the semantic relation that propositional equivalence-checking procedures test.
Equivalence relation: A relation that is reflexive, symmetric, and transitive. Logical equivalence has these properties and partitions formulas into classes with identical truth behavior.

Linked from 16 pages