Exercise 7.3 [truth-value-exercise]
Consider the problem of deciding whether a propositional logic sentence is true in a given model.
-
Write a recursive algorithm PL-True?$ (s, m )$ that returns ${true}$ if and only if the sentence $s$ is true in the model $m$ (where $m$ assigns a truth value for every symbol in $s$). The algorithm should run in time linear in the size of the sentence. (Alternatively, use a version of this function from the online code repository.)
-
Give three examples of sentences that can be determined to be true or false in a partial model that does not specify a truth value for some of the symbols.
-
Show that the truth value (if any) of a sentence in a partial model cannot be determined efficiently in general.
-
Modify your algorithm so that it can sometimes judge truth from partial models, while retaining its recursive structure and linear run time. Give three examples of sentences whose truth in a partial model is not detected by your algorithm.
-
Investigate whether the modified algorithm makes $TT-Entails?$ more efficient.