Entailment

“Going back to being a head coach entails a full-time commitment to that job.”
—Bill Cowher

Now that we know to determine whether WFFs are true or false in a given model, we can ask how WFFs are related to each other, in terms of which models make them true.

Example

Every model that makes $(P\land Q)$ true also makes $(Q\land P)$ true, and vice-versa.
Every model that makes $(P\land Q)$ true also makes $P$ true.
Not every model that makes $P$ true also makes $(P\land Q)$ true.
Every model where WFFs $P$ and $(P\to Q)$ are both true also makes $Q$ true.

Part (4) above follows by inspection of the truth table for implication; the only way that $(P\to Q)$ can be true in a model where $P$ is true is if that model also makes $Q$ true.

The Entailment Relation

Definition

We say that assumptions ${\cal A}_1,\ldots,{\cal A}_n$ entail a conclusion ${\cal B}$ if in every situation (model) where the assumptions are all true, the conclusion is true as well. In this case we write

{\cal A}_1,\ldots,{\cal A}_n \ \vDash \ {\cal B}

Equivalently, ${\cal A}_1,\ldots,{\cal A}_n \ \vDash \ {\cal B}$ if there is no possible scenario where our assumptions ${\cal A}_1,\ldots,{\cal A}_n$ are true but the conclusion ${\cal B}$ is false.

If ${\cal A}_1,\ldots,{\cal A}_n$ does not entail ${\cal B}$ then we write

{\cal A}_1,\ldots,{\cal A}_n \ \not\vDash \ {\cal B}

Example

We can rewrite the four observations above as:

$(P\land Q)\vDash (Q\land P)$ and $(Q\land P)\vDash (P\land Q)$ .
$(P\land Q)\vDash P$
$P\not\vDash (P\land Q)$ .
$P,\ (P\to Q)\vDash Q$ .

Definition

As a special case ( $n=0$ ), we say that ${\cal B}$ is valid or is a tautology if it is true in every possible model, and write

\vDash {\cal B}

In the entailment ${\cal A}_1,\ldots,{\cal A}_n\vDash {\cal B}$ , we can think of ${\cal A}_1,\ldots,{\cal A}_n$ as constraining which models we care about ${\cal B}$ being true in. The base case of having $n=0$ is that there is no constraint at all, and we need ${\cal B}$ to be true in all models.

Checking for Entailment

Entailment defines when a conclusion WFF follows from assumption WFFs, but says nothing about “step-by-step reasoning” or “proof.”

If we want to check whether

(P\to Q),\ \ \lnot Q\ \vDash\ \lnot P

then we must (for now, at least) check every relevant model, and confirm that every (relevant) model that makes the two assumptions true also makes the conclusion true.

Example

In order to verify that $(P\to Q),\ \ \lnot Q\ \vDash\ \lnot P$ , we can build a truth table. In a truth table, each row represents a different model, each column represents a WFF, and each cell represents whether the model makes the WFF true or false.

For this example, since there are two propositional variables involved ( $P$ and $Q$ ), we need four rows, corresponding to the four relevant models:

$P$	$Q$	$P\to Q$	$\lnot Q$	$\lnot P$
T	T	T	F	F
T	F	F	T	F
F	T	T	F	T
F	F	T	T	T

By inspection of the truth table, we see that the entailment holds: in every model where the assumptions $(P\to Q)$ and $\lnot Q$ are simultanously true (there’s only one such model), the conclusion $P$ is true.

Example

Now suppose we want to check whether $(P\to Q), \lnot P\ \vDash \ \lnot Q$ . Again, there are four possible models and we can build a truth table:

$P$	$Q$	$P\to Q$	$\lnot P$	$\lnot Q$
T	T	T	F	F
T	F	F	F	T
F	T	T	T	F
F	F	T	T	T

By inspection of the truth table we can see that the entailment fails; in the third model (where $P$ is false and $Q$ is true), both assumptions are true, but the conclusion is false. We conclude that

(P\to Q),\ \ \lnot P\ \not\vDash\ \lnot Q.

Example

Now suppose we want to know whether $\ \vDash (P\to (Q\to P))$ . (Recall that this means that $(P\to (Q\to P))$ is valid, i.e., true in every model.)

Again, there are four possible models and we can build a truth table. Previously we had columns for each assumption and conclusion, but just to make the calculations easier to do by hand, we can add a column for the intermediate formula $(Q\to P)$ .

$P$	$Q$	$(Q\to P)$	$(P\to(Q\to P))$
T	T	T	T
T	F	T	T
F	T	F	T
F	F	T	T

By inspection of the truth table we can see that the conclusion is true in every model. Thus the entailment holds and $(P\to(Q\to P))$ is valid.

Example

Finally, suppose we want to know whether $\bot \vDash P$ .

This time there are only two models (not because of the $\bot$ , but because this entailment doesn’t involve $Q$ , so we only care whether $P$ is true or false). We build the truth table. (We didn’t have to repeat the conclusion $P$ in the third column, but it’s harmless and my personal preference is to put the conclusion in the final column.)

$P$	$\bot$	$P$
T	F	T
F	F	F

The entailment holds, because in all models where the assumption $\bot$ is true (all zero of them), the conclusion $P$ is true.

Another way to think about this: the entailment holds because there are no counterexamples, i.e., no model where the assumption $\bot$ is true and the conclusion $P$ is false.

Logical Equivalence

WFFs ${\cal A}$ and ${\cal B}$ are logically equivalent if ${\cal A} \vDash {\cal B}$ and ${\cal B} \vDash {\cal A}$ . In this case, we write

{\cal A} \equiv {\cal B}.

An easier way to say this is that ${\cal A} \equiv {\cal B}$ whenever ${\cal A}$ and ${\cal B}$ have the same truth value in every model (i.e., no matter value we give their propositional variables, either ${\cal A}$ and ${\cal B}$ are both true, or they’re both false).

The following equivalences are important, and should be memorized.

${\cal A} \ \ \equiv \ \ \lnot\lnot {\cal A}$
${\cal A}\to {\cal B} \ \ \equiv \ \ \lnot {\cal A}\ \lor\ {\cal B}$
${\cal A}\to {\cal B} \ \ \equiv \ \ (\lnot {\cal B}\ \to\ \lnot {\cal A})$ (contrapositive)
$\lnot ({\cal A}\land {\cal B}) \ \ \equiv \ \ (\lnot {\cal A} \ \lor\ \lnot {\cal B})$ (DeMorgan’s Law)
$\lnot ({\cal A}\lor {\cal B}) \ \ \equiv \ \ (\lnot {\cal A} \ \land\ \lnot {\cal B})$ (DeMorgan’s Law)
$\lnot ({\cal A}\to {\cal B}) \ \ \equiv \ \ ({\cal A} \ \land\ \lnot {\cal B})$
$\lnot {\cal A} \ \ \equiv \ \ ({\cal A} \to \bot)$

Because equivalence preserves truth value, we can apply these equations inside other formulas without changing the truth value:

\lnot(P\to\lnot Q) \ \ \equiv \ \ (P\land \lnot\lnot Q) \ \ \equiv \ \ (P\land Q).