Entailment

logic

Definition

Entailment

A formula $\varphi$ entails a formula $\psi$ if every interpretation that makes $\varphi$ true also makes $\psi$ true.

Formally,

$$\varphi \models \psi$$

More generally, for formulas $F_1,\dots ,F_n$ and a formula $G$:

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

means that whenever all $F_i$ are true, $G$ is true as well.

Entailment is the semantic counterpart of implication at the level of formulas.

Duality

Definition

Entailment–Unsatisfiability Duality

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

For a set of formulas $\Gamma$ and a 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

Monotonicity

Definition

Monotonicity of Entailment

Monotonicity of entailment is the property that adding antecedents does not remove existing consequents.

If a consequent $C$ follows from a set of antecedents $\Gamma$, then it also follows from any larger set of antecedents:

$$\Gamma ⊢C\Rightarrow \Gamma ,A⊢C$$

for any additional antecedent $A$.

In other words, valid arguments remain valid when extra assumptions are added. ¹

Footnotes

1. https://en.wikipedia.org/wiki/Monotonicity_of_entailment ↩

Link to original

Mutual Entailment

Definition

Mutual Entailment

Two formulas mutually entail each other (are equivalent) if they have the same truth value under every interpretation.

$$A\equiv B:⟺A\models B\wedge B\models A$$

Hence, there is no interpretation that makes one of them true and the other false, so we cannot distinguish them semantically. Semantic equivalence is an equivalence relation on formulas.

Link to original

Examples

Example

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

The premises are true and the conclusion is true.

Example

$$P⟹Q,P\models Q$$

If $P$ and $P⟹Q$ are true, then $Q$ is true.

Example

$$P⟹Q,\neg P/\models \neg Q$$

The premises do not force $\neg Q$.