8
$\begingroup$

In propositional logic (Artificial intelligence to be specific) $\alpha$ entails $\beta$ iff $\alpha\Rightarrow\beta$ is a statement. However if I write the truth table for implies ($\Rightarrow$) if $\alpha$ is false implies that $\beta$ is a true sentence as shown in the table below in the fourth row.

\begin{array}{cc|c} \alpha & \beta & \alpha\Rightarrow \beta\\ \hline T & T & T\\ T & F & F\\ F & T & T\\ F & F & T \end{array}

Now this should be false according to the model checking approach, since there could be models in which $\alpha$ is false but $\beta$ is true given that $\alpha$ entails $\beta$. This is further supported by the book on artificial intelligence by Peter Norvig that states that $\alpha\vDash\beta$ iff M$(\alpha)\subseteq M(\beta)$, where $M(\alpha)$ is the set of all models where $\alpha$ is true.

$\endgroup$

2 Answers 2

12
$\begingroup$

Let $\varphi$ and $\psi$ be formulas of propositional logic. We write, as Norvig says, $\varphi\vDash \psi$ iff $M(\varphi)\subseteq M(\psi)$: that is, iff every truth assignment that makes $\varphi$ true also make $\psi$ true. This is the case iff $\vDash \varphi\Rightarrow\psi$, i.e., if the formula $\varphi\Rightarrow\psi$ is true in all truth assignments (is a tautology).

Entailment and implication operate at different levels. An implication is something that may be true or false, depending on which truth assignment you're considering at the moment, whereas an entailment is a statement about all truth assignments. In particular, the truth of the entailment $\varphi\vDash\psi$ depends only on truth assignments that make $\varphi$ true. If a particular truth assigment makes $\varphi$ false, then it cannot make the entailment false. Similarly, if an assignment makes $\varphi$ false, it cannot make the implication $\varphi\Rightarrow\psi$ false.

$\endgroup$
1
  • $\begingroup$ Sounds like we should do the category-theory thing where natural transformations are functors in a "higher" category. So, given an "N-"theory, then implication is an (N-1)-arrow while entailment is an N-arrow. $\endgroup$ Commented Mar 23 at 21:46
3
$\begingroup$

Very briefly, implication and entailment are not the same because they operate at different levels of logic. Implication applies to certain truth assignments. Entailment considers all possible truth assignments for some statement(s).

There is a helpful explanation of this on Philosophy Stack Exchange if you want to go more in-depth.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.