What Does Propositional Logic Entailment Mean?

Propositional entailment describes when a conclusion is forced by one or more premises. The question is not whether the conclusion is usually true, or whether it follows from the wording informally. It asks whether every possible truth assignment that satisfies the premises also satisfies the conclusion.

The central notation is

$$\Gamma \models \varphi$$

where $\Gamma$ is a set of premises and $\varphi$ is the proposed conclusion. Read this as “$\Gamma$ entails $\varphi$.”

Formal definition

Let $v$ be a valuation: an assignment of either true or false to each propositional variable. Then

$$\Gamma \models \varphi$$

if and only if, for every valuation $v$,

$$\left(\text{$v$ makes every formula in $\Gamma$ true}\right) \implies \left(\text{$v$ makes $\varphi$ true}\right).$$

If the premises are $P$ and $Q$, for example, then $\{P,Q\} \models P \land Q$. Any valuation satisfying both premises must satisfy their conjunction.

Entailment is a semantic relationship: it depends on the truth values assigned to formulas. It is different from a proof symbol such as $\vdash$, which describes derivability using a particular formal proof system. For a sound and complete standard propositional proof system, $\Gamma \models \varphi$ and $\Gamma \vdash \varphi$ agree, but the two symbols express different ideas.

The countermodel test

The fastest way to understand a proposed entailment is to look for a countermodel. A countermodel is a valuation that:

1. makes every premise true, and
2. makes the conclusion false.

If such a valuation exists, then

$$\Gamma \not\models \varphi.$$

If no such valuation exists, then the entailment holds.

For example, does $P \lor Q$ entail $P$? No. Set $P$ to false and $Q$ to true. The premise $P \lor Q$ is true, but the conclusion $P$ is false. This single assignment disproves the entailment:

$$P \lor Q \not\models P.$$

Notice that proving non-entailment generally requires only one counterexample. Proving entailment requires ruling out every possible counterexample.

Equivalent satisfiability test

There is a useful equivalent condition:

$$\Gamma \models \varphi \quad\Longleftrightarrow\quad \Gamma \cup \{\neg\varphi\}\text{ is unsatisfiable}.$$

In formula notation, for a finite set of premises, let $\gamma$ be their conjunction. Then

$$\Gamma \models \varphi \quad\Longleftrightarrow\quad \gamma \land \neg\varphi \text{ is unsatisfiable}.$$

Why does this work? A valuation witnessing failure of entailment would make all premises true and $\varphi$ false. Making $\varphi$ false is exactly the same as making $\neg\varphi$ true. Therefore, a satisfying assignment for $\gamma \land \neg\varphi$ is precisely a countermodel to the entailment.

Worked example: transitivity of implication

Test whether

$$\{P \to Q,\ Q \to R\} \models P \to R.$$

Combine the premises and negate the conclusion:

$$(P \to Q) \land (Q \to R) \land \neg(P \to R).$$

Use the equivalences $A \to B \equiv \neg A \lor B$ and $\neg(P \to R) \equiv P \land \neg R$:

$$(\neg P \lor Q) \land (\neg Q \lor R) \land P \land \neg R.$$

Since $P$ is true, the first clause forces $Q$ to be true. Since $Q$ is true, the second clause forces $R$ to be true. But the last clause requires $R$ to be false. The conjunction cannot be satisfied.

Thus there is no countermodel, and

$$\{P \to Q,\ Q \to R\} \models P \to R.$$

The same example with a truth table

A truth table can verify the result directly. The relevant columns are:

$P$	$Q$	$R$	$P \to Q$	$Q \to R$	$P \to R$
F	F	F	T	T	T
F	F	T	T	T	T
F	T	F	T	F	T
F	T	T	T	T	T
T	F	F	F	T	F
T	F	T	F	T	T
T	T	F	T	F	F
T	T	T	T	T	T

Look only at rows where both premises are true. Those are the first, second, fourth, and eighth rows. In each of them, $P \to R$ is also true. Therefore the entailment holds.

Entailment versus implication

A common source of confusion is treating $\models$ and $\to$ as interchangeable.

The expression

$$P \to Q$$

is a formula that is true or false under a particular valuation. By contrast,

$$P \models Q$$

is a claim about all valuations. It says that every valuation making $P$ true also makes $Q$ true.

For formulas $\alpha$ and $\beta$, the following are equivalent:

$$\alpha \models \beta \quad\Longleftrightarrow\quad \models (\alpha \to \beta)$$

The symbol on the right means that $(\alpha \to \beta)$ is a tautology. With multiple premises, combine them first:

$$\{\alpha_1,\ldots,\alpha_n\} \models \beta \quad\Longleftrightarrow\quad \models \left((\alpha_1 \land \cdots \land \alpha_n) \to \beta\right).$$

Practical methods

For a finite propositional problem, you can test entailment in several equivalent ways:

• Truth table: enumerate every valuation and inspect rows where all premises are true.
• Countermodel search: try to make the premises true and the conclusion false.
• Logical equivalences: simplify $\gamma \land \neg\varphi$ until its consistency is clear.
• Resolution or SAT solving: encode the premises plus the negated conclusion and check whether the result is unsatisfiable.
• Formal deduction: derive the conclusion using inference rules such as modus ponens.

Truth tables are straightforward, but with $n$ distinct variables they have $2^n$ rows. For larger formulas, a satisfiability procedure or a structured proof is usually more practical.

Common mistakes

Checking only some premise-true rows

One missed valuation can invalidate a claimed entailment. Every valuation satisfying all premises must be considered.

Confusing entailment with likely truth

A premise set may make a conclusion plausible without forcing it. Entailment has no probability component: one countermodel is decisive.

Reversing an implication

From $P \to Q$, you may not infer $Q \to P$. For instance, “being a square implies being a rectangle” does not mean every rectangle is a square.

Using an inconsistent premise set

If the premises cannot all be true simultaneously, then they entail every formula in classical logic. There is no valuation satisfying the premises, so there can be no countermodel. This is sometimes called the principle of explosion, and it is why checking premise consistency can matter.

Treating variables as statements about the real world

In propositional logic, $P$, $Q$, and $R$ are atomic propositions. Their meaning does not affect the truth-table test; only their assigned truth values matter.