Logical Entailment

We say that a sentence φ logically entails a sentence ψ (written φ ⊨ ψ) if and only if every truth assignment that satisfies φ also satisfies ψ. More generally, we say that a set of sentences Δ logically entails a sentence ψ (written Δ ⊨ ψ) if and only if every truth assignment that satisfies all of the sentences in Δ also satisfies ψ.

For example, the sentence p logically entails the sentence (p ∨ q). Since a disjunction is true whenever one of its disjuncts is true, then (p ∨ q) must be true whenever p is true. On the other hand, the sentence p does not logically entail (p ∧ q). A conjunction is true if and only if both of its conjuncts are true, and q may be false. Of course, any set of sentences containing both p and q does logically entail (p ∧ q).

Note that the relationship of logical entailment is a purely logical one. Even if the premises of a problem do not logically entail the conclusion, this does not mean that the conclusion is necessarily false, even if the premises are true. It just means that it is possible that the conclusion is false.

Once again, consider the case of (p ∧ q). Although p does not logically entail this sentence, it is possible that both p and q are true and, therefore, (p ∧ q) is true. However, the logical entailment does not hold because it is also possible that q is false and, therefore, (p ∧ q) is false.

Note also that logical entailment is not the same as logical equivalence. The sentence p logically entails (p ∨ q), but (p ∨ q) does not logically entail p. Logical entailment is not analogous to arithmetic equality; it is closer to arithmetic inequality.

As with logical equivalence, we can use truth tables to determine whether or not a set of premises logically entails a possible conclusion by checking the truth table for the proposition constants in the language. (1) We form a truth table for the proposition constants and add a column for the premises and a column for the conclusion. (2) We then evaluate the premises. (3) We evaluate the conclusion. (4) Finally, we compare the results. If every row that satisfies the premises also satisfies the conclusion, then the premises logically entail the conclusion.

As an example, let's use this method to show that p logically entails (p ∨ q). We set up our truth table and add a column for our premise and a column for our conclusion. In this case the premise is just p and so evaluation is straightforward; we just copy the column. The conclusion is true if and only if p is true or q is true. Finally, we notice that every row that satisfies the premise also satisfies the conclusion.

Now, let's do the same for the premise p and the conclusion (p ∧ q). We set up our table as before and evaluate our premise. In this case, there is only one row that satisfies our conclusion. Finally, we notice that the assignment in the second row satisfies our premise but does not satisfy our conclusion; so logical entailment does not hold.

Now, let's look at the problem of determining whether the set of propositions {p, q} logically entails (p ∧ q). Here we set up our table as before, but this time we have two premises to satisfy. Only one truth assignment satisfies both premises, and this truth assignment also satisfies the conclusion; hence in this case logical entailment does hold.

As a final example, let's return to the love life of the fickle Mary. Here is the problem from the course introduction. We know (p ⇒ q), i.e. if Mary loves Pat, then Mary loves Quincy. We know (m ⇒ p ∨ q), i.e. if it is Monday, then Mary loves Pat or Quincy. Let's confirm that, if it is Monday, then Mary loves Quincy. We set up our table and evaluate our premises and our conclusion. Both premises are satisfied by the truth assignments on rows 1, 3, 5, 7, and 8; and we notice that those truth assignments make the conclusion true. Hence, the logical entailment holds.