Entailment

Definition

Entailment

Entailment ($\models$) is the relation between premises and conclusion that holds when every interpretation making all premises true also makes the conclusion true. Its precise meaning depends on the order of the underlying logic: propositional entailment and first-order entailment differ in what counts as an interpretation.

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

Link to original

First-order logic

Definition

Entailment (First-Order Logic)

Let $F_1,\dots ,F_n,G$ be formulas. Then $F_1,\dots ,F_n$ entail $G$, written

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

if for every structure $\mathcal{M}$ and every variable assignment $\sigma$:

$$\mathcal{M},\sigma \models F_i\text{ for all }i⟹\mathcal{M},\sigma \models G$$

Link to original