Countermodel (Propositional Logic)

Definition

Countermodel (Propositional Logic)

A countermodel to an entailment claim $F_1,\dots ,F_n\models G$ is a model of the premises that refutes the conclusion — an interpretation $v$ with

$$v(F_1)=v(\top )\wedge \cdots \wedge v(F_n)=v(\top ),v(G)=v(\perp ).$$

A countermodel exists exactly when the entailment fails: $F_1,\dots ,F_n/\models G$.

Relation to Unsatisfiability

By the entailment–unsatisfiability duality, the entailment fails exactly when $F_1\wedge \cdots \wedge F_n\wedge \neg G$ is satisfiable — a countermodel is a model of that conjunction.

Examples

A countermodel exists

Given

$$P\vee Q\models P,$$

is there an interpretation $v$ with the premise true and $P$ false —

$$v(P\vee Q)=v(\top ),v(P)=v(\perp )?$$

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

$$P\vee Q,\neg P,$$

which is satisfiable: take $v(P)=v(\perp )$ and $v(Q)=v(\top )$. Then $Q$ makes $P\vee Q$ true and $P$ false makes $\neg P$ true, so $v$ is such a model. Hence a countermodel exists: the entailment fails, $P\vee Q/\models P$.