Entailment (Propositional Logic)

Definition

Entailment (Propositional Logic)

Let $F_1,\dots ,F_n$ and $G$ be propositional formulas. The premises $F_1,\dots ,F_n$ entail $G$, written

$$F_1,\dots ,F_n\models G,$$

if every interpretation $v$ that makes all premises $F_i$ true also makes $G$ true:

$$\forall \text{interpretation}v(v(F_1)=v(\top )\wedge \cdots \wedge v(F_n)=v(\top ))⟹v(G)=v(\top ).$$

Here $v(F)$ is the truth value $v$ assigns to $F$, and $v(\top )$ denotes the truth value true. For a single premise this reads $\phi \models \psi$: $\phi$ entails $\psi$.

Intuition

Entailment is a claim about all truth assignments. You are saying: no matter how the atoms are interpreted — no matter which atoms are true and which are false — whenever the premises come out true, the conclusion is forced. Checking entailment means checking every row of the truth table.

• Entailment ($\models$) lives outside the logic: it is a statement about formulas.
• Implication ($\to$) lives inside the logic: it is a connective that builds a new formula.

$$F\models G\text{ is a claim about formulas.}F\to G\text{ is a formula.}$$

Duality

Definition

Entailment–Unsatisfiability Duality (Propositional Logic)

The entailment–unsatisfiability duality is the equivalence between semantic entailment and the unsatisfiability of a counterexample set.

For a set $\Gamma$ of propositional formulas and a propositional formula $Q$,

$$\Gamma \models Q\text{if and only if}\Gamma \cup \{\neg Q\}\text{ is unsatisfiable}.$$

Thus, $\Gamma$ entails $Q$ exactly when there is no interpretation that satisfies all formulas in $\Gamma$ while falsifying $Q$.

Link to original

Reductions

Entailment can be rephrased as unsatisfiability of the premises together with the negated conclusion:

$$\begin{array}{rl}{F}_1,\dots ,F_n\models G& ⟺F_1\wedge \cdots \wedge F_n\wedge \neg G\text{ is unsatisfiable}\\ \models F& ⟺\neg F\text{ is unsatisfiable}\end{array}$$

Here unsatisfiable means the negation of satisfiable.

Examples

Modus ponens by truth table

To check $P\to Q,P\models Q$, inspect all four assignments:

$P$	$Q$	$P\to Q$	$P$	premises true?	$Q$
$\top$	$\top$	$\top$	$\top$	yes	$\top$
$\top$	$\perp$	$\perp$	$\top$	no	—
$\perp$	$\top$	$\top$	$\perp$	no	—
$\perp$	$\perp$	$\top$	$\perp$	no	—

Both premises are true only in the first row, and there $Q$ is true. Hence $P\to Q,P\models Q$.

Disjunctive syllogism

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

If $\neg A$ is true, then $C\to A$ forces $C$ false, and $C\vee M$ then forces $M$ true.

A non-entailment

$$P\to Q,\neg P/\models \neg Q.$$

Under $v(P)=v(\perp )$ and $v(Q)=v(\top )$, both premises are true but $\neg Q$ is false.