Model (Propositional Logic)

Definition

Model (Propositional Logic)

An interpretation $I$ is called model of a formula $F$ iff $F$ is true under $I$, i.e.,

$$I(F)=I(\top ).$$

The set of all models of a formula $F$ is denoted as

$$\mathrm{Mod}(F)=\{I\mid I(F)=I(\top )\}.$$

Equivalence

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$.

Link to original

Examples

Attempting a countermodel

Given

$$C\vee M,C\to A,\neg A\models M,$$

is there an interpretation $v$ with the premises true and $M$ false —

$$I(C\vee M)=I(C\to A)=I(\neg A)=I(\top ),I(M)=I(\perp )?$$

By the entailment–unsatisfiability duality, such a $I$ is a model of

$$C\vee M,C\to A,\neg A,\neg M,$$

which forces $I(M)=I(\perp )$ and $I(A)=I(\perp )$. By equivalent replacement the set reduces to the contradiction

$$C,\neg C,$$

so no such $v$ exists: the entailment is valid and the countermodel construction fails.