Model Characterisation of Equivalence (Propositional Logic)

Definition

Model Characterization of Equivalence (Propositional Logic)

Two propositional formulas $P,Q$ are equivalent if and only if they have the same models:

$$P\equiv Q⟺\mathrm{Mod}(P)=\mathrm{Mod}(Q),$$

where $\mathrm{Mod}(F)=\{I\mid I(F)=I(\top )\}$ is the set of models of $F$ over all interpretations $I$.

Proof

Proof

$\Rightarrow$

Assume $I(P)=I(Q)$ for every interpretation $I$. If $I$ is a model of $P$, then $I(P)=I(\top )$ and hence

$$I(Q)=I(P)=I(\top ),$$

so $I$ is a model of $Q$. Symmetrically, every model of $Q$ is a model of $P$. Therefore

$$\mathrm{Mod}(P)=\mathrm{Mod}(Q).$$

$\Leftarrow$

Assume $\mathrm{Mod}(P)=\mathrm{Mod}(Q)$ and fix an interpretation $I$. If $I(P)=I(\top )$, then $I$ is a model of $P$, hence of $Q$; if $I(P)=I(\perp )$, then $I$ is a model of neither $P$ nor $Q$. In both cases

$$I(Q)=I(P),$$

so $P$ and $Q$ are equivalent.