patternModerate
How is implication same as entailment
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.
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.
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.