Definition
Model Characterization of Equivalence (Propositional Logic)
Two propositional formulas
are equivalent if and only if they have the same models: where
is the set of models of over all interpretations .
Proof
Proof
Assume
for every interpretation . If is a model of , then and hence so
is a model of . Symmetrically, every model of is a model of . Therefore
Assume
and fix an interpretation . If , then is a model of , hence of ; if , then is a model of neither nor . In both cases so
and are equivalent.