Countermodel (Propositional Logic)

Definition

Countermodel (Propositional Logic)

A countermodel to an entailment claim is a model of the premises that refutes the conclusion — an interpretation with

A countermodel exists exactly when the entailment fails: .

Relation to Unsatisfiability

By the entailment–unsatisfiability duality, the entailment fails exactly when is satisfiable — a countermodel is a model of that conjunction.

Examples

A countermodel exists

Given

is there an interpretation with the premise true and false —

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

which is satisfiable: take and . Then makes true and false makes true, so is such a model. Hence a countermodel exists: the entailment fails, .