Consider the problem of deciding whether a propositional logic sentence is true in a given model. a)
Question:
Consider the problem of deciding whether a propositional logic sentence is true in a given model.
a). 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.)
b). 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.
c). Show that the truth value (if any) of a sentence in a partial model cannot be determined efficiently in general.
d). Modify your PL-TRUE? 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.
e). Investigate whether the modified algorithm makes TT-ENTAILS? more efficient.
Artificial Intelligence A Modern Approach
ISBN: 978-0137903955
2nd Edition
Authors: Stuart J. Russell and Peter Norvig