HiveBrain v1.2.0
Get Started
← Back to all entries
patternModerate

How is implication same as entailment

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
sameimplicationentailmenthow

Problem

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.

Solution

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.

Context

StackExchange Computer Science Q#72360, answer score: 12

Revisions (0)

No revisions yet.