Entailment (Propositional Logic)

Definition

Entailment (Propositional Logic)

Let and be propositional formulas. The premises entail , written

if every interpretation that makes all premises true also makes true:

Here is the truth value assigns to , and denotes the truth value true. For a single premise this reads : entails .

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 () lives outside the logic: it is a statement about formulas.
• Implication () lives inside the logic: it is a connective that builds a new 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 of propositional formulas and a propositional formula ,

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

Link to original

Reductions

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

Here unsatisfiable means the negation of satisfiable.

Examples

Modus ponens by truth table

To check , inspect all four assignments:

				premises true?
				yes
				no	—
				no	—
				no	—

Both premises are true only in the first row, and there is true. Hence .

Disjunctive syllogism

If is true, then forces false, and then forces true.

A non-entailment

Under and , both premises are true but is false.