# 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 in (where in 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 runtime. 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.

a. Write a recursive algorithm PL-TRUE? (s m) that returns true if and only if the sentence s is true in the model in (where in 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 runtime. 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.

## Answer to relevant Questions

Prove each of the following assertions: a. α is valid if and only if True | = α. b. For any a, False | = α. c. α | = β if and only if the sentence (α → β) is valid. d. α ...(Adapted from Bar wise and Etchemendy (1993)) Given the following, can you prove that the unicorn is mythical? How about magical? Horned? If the unicorn is mythical, then it is immortal, hut if it is not mythical, then it is ...How long does it take to prove KB | = α using DPLL when α is a literal already contained in KB? Explain.What axiom is needed to infer the fact Female (Laura) given the facts Male (Jim) and Spouse (Jim, Laura)?Extend the vocabulary from Section 8.4 to define addition for n-bit binary numbers. Then encode the description of the four-bit adder in Figure and pose the queries needed to verify that it is in factcorrect.Post your question

0