Review of Propositional Logic, Part 3

Entailment

Now we get to the logic part of propositional logic.

Entailment

We say that

• B is a logical consequence of A₁, …, Aₙ, or

• A₁, …, Aₙ logically imply B, or

• A₁, …, Aₙ entail B,

written A ⊨ B, if every truth assignment on A₁, …, Aₙ and B that satisfies A₁, …, Aₙ also satisfies B. This captures the notion of a logically valid argument:

\(\begin{gather*} A_1, \ldots, A_n \models B \quad\mbox{means that} \\ \mbox{conclusion }B\mbox{ must be true } \\ \mbox{if the premises }A_1,\ldots,A_n\mbox{ are true}, \end{gather*}\)

based solely on the structural form of the propositional formulas, and not on any intended meaning of the propositional symbols. For notational convenience we’ve assumed a finite set of premises here, but the same definition works for an infinite set of premises.

Truth tables and entailment

We can check whether or not the entailment relation holds by filling out a truth table. Here is an example:

Checking this truth table we see that b is T whenever a ⋀ (a → b) is T.

The need to be explicit

Remember that any internal structure or intended semantics of the propositional symbols is irrelevant to the entailment relation:

Checking the table we see that x < 3 does not entail x < 5; we’ve used “x < 3” and “x < 5” as propositional symbols with the intention for them to have certain meanings, but they don’t acquire those meanings automatically — we would need to add additional premises that express the desired meanings. For example, we could add the following additional premises that express the ordering of the integers:

\(\begin{eqnarray*} \Gamma &= \{ & \mathtt{x < 1} \rightarrow \mathtt{x < 2}, \\ &&\mathtt{x < 2} \rightarrow \mathtt{x < 3}, \\ &&\mathtt{x < 3} \rightarrow \mathtt{x < 4}, \\ &&\mathtt{x < 4} \rightarrow \mathtt{x < 5} \;\}\\ \end{eqnarray*}\)

It is then, in fact, true that

\(\Gamma, \mathtt{x < 3} \models \mathtt{x < 5} \)

We’ll see more such examples in later posts.

Finitely many premises

Do we ever need an infinite number of premises? No, according to the compactness theorem for propositional logic:

\(\begin{gather*} \Gamma \models A \\ \mbox{ if and only if } \\ G \models A \mbox{ for some finite subset }G\mbox{ of }\Gamma \end{gather*}\)

But if we have only finitely many premises A₁, …, Aₙ, we might as well AND them together into one single premise A₁ ⋀ … ⋀ Aₙ. The entailment relation then becomes a binary relation between propositional formulas. This binary relation has the following properties:

• A is a tautology if and only if T ⊨ A.
  We abbreviate this as ⊨ A.

• A is a contradiction if and only if, for any B whatsoever, A ⊨ B.
  This is why contradictions are so pernicious: you can prove anything at all if you use a contradiction as a premise.

• A is a contradiction if and only if ⊨ ¬A.
  That is, A is a contradiction if and only if ¬A is a tautology.

• A ⊨ B if and only if ⊨ A → B.
  That is, A entails B if and only if A → B is a tautology.

Equivalence

We can now also say a bit more precisely what we mean when we say that two propositional formulas A and B are equivalent, which we write A ≡ B:

\(A \equiv B \mbox{ means }\models A \leftrightarrow B.\)

Equivalence has the following property:

\(A \equiv B \mbox{ if and only if both }A \models B\mbox{ and }B \models A.\)

This concludes our review of propositional logic.