Logic and Knowledge Representation

Homework Assignment 3600.335/435 Artificial Intelligence
Logic and Knowledge RepresentationLately we have been focusing on methods for representing knowledge such that anintelligent agent can follow rules and make inferences. In this assignment, you willbe using propositional logic, first order logic, and knowledge representation to solvewritten questions. Please be sure to show all relevant work.Translate the following English sentences into propositional logic1. A and B are both true.2. If A is true, then B must be true as well.3. If a student studies for a test, they will do well on it. We can also tell that if astudent did well on a test, then they must have studied for it.4. If a student is completely dry and it is raining outside, it is because they have anumbrella or a hoodie and it is not raining heavily.5. If a student doesn’t hand in the homework late or incomplete, this doesn’t necessarilyimply that they will not lose points.Simplify and translate the following propositional logic sentenceinto English6. A _ (A ^ B) () :(A ^ B ^ C)Is the following sentence valid?7. A _ BIs the following sentence satisfiable?8. A =) B1Is the following sentence unsatisfiable?9. (A ^ (B _ C)) ^ ((A ^ B) _ (A ^ C))Translate the following english sentences into first order logic10. Some students pass English but not Math.11. Every student is registered in a class and enrolled at a university.12. If someone is an aunt or uncle, then someone must be their niece or nephew.13. The old that is strong does not wither.Translate the following first order logic sentence into English14. :(8x; Gold(x) =) Glitter(x))15. Given the Wumpus World game discussed in class, please encode all KB rulesfor finding the wumpus in first order logic given two known spaces that have astench present. Hint: I am not explicitly saying the relationship between thesetwo spaces, so think about different cases that are possible within the game’slogic.16. Suppose you are given the following axioms:1. 0 ? 32. 7 ? 93. 8x; x ? x4. 8x; x ? x + 05. 8x; x + 0 ? x6. 8x; y; x + y ? y + x7. 8w; x; y; z;w ? y ^ x ? z =) w + x ? y + z8. 8x; y; z; x ? y ^ y ? z =) x ? zA. Give a backward-chaining proof of the sentence 7 ? 3 + 9. (Be sure, ofcourse, to use only the axioms given here, not anything else you may know aboutarithmetic.) Show only the steps that lead to success, not the irrelevant steps.B. Give a forward-chaining proof of the sentence 7 ? 3+9. Again, show onlythe steps that lead to success.2For the next several questions, use the following two sentences infirst order logic.Assume that x and y range over the set of natural numbers, and that ? has theconventional mathematical definition.(A) 9y8x(x ? y)(B) 8x9y(x ? y)17. Translate (A) and (B) into English18. Is (A) true?19. Is (B) true?20. Does (A) entail (B)?21. Does (B) entail (A)?22. Grad Students Only: Using resolution, try to prove that (A) follows from (B). Youshould either complete the proof (if possible), or continue until the proof breaksdown and you cannot continue (if impossible). Show the unifying substitution ineach step. If the proof fails, explain where, how, and why it fails.23. Define the ExhaustiveDecomposition, Disjoint, and Partition properties of categoriesusing first order logic.24. Define an ontology in first order logic for tic-tac-toe. The ontology should containsituations, actions, squares, players, marks (X, O, or blank), and the notionof winning, losing, or drawing a game. Also define the notion of a forced win(or draw): a position from which a player can force a win (or draw) with theright sequence of actions. Write axioms for the domain. (Note: The axioms thatenumerate the different squares and that characterize the winning positions arerather long. You need not write these out in full, but indicate clearly what theylook like.)25. Grad Students Only: Develop a representational system for reasoning aboutwindows in a window-based computer interface. In particular, your representationshould be able to describe:-The state of a window: minimized, displayed, or nonexistent-Which window (if any) is the active window-The position of every window at a given time-The order (front to back) of overlapping windows-The actions of creating, destroying, resizing, and moving windows; changingthe state of a window; and bringing a window the front. Treat these actions asatomic; that is, do not deal with the issue of relating them to mouse actions. Giveaxioms describing the effects of actions on fluents. You may use either event or3situational calculus.Assume an ontology containing situations, actions, integers (for x and y coordinates)and windows. Define a language over this ontology; that is, a list ofconstants, function symbols, and predicates with an English description of each.If you need to add more categories to the ontology (e.g. pixels), you may do so,but be sure to specify these in your write-up. You may (and should) use symbolsdefined in class or the textbook, but be sure to list these explicitly.26. A popular children’s riddle is "Brothers and sisters have I none, but that man’sfather is my father’s son." Using the rules of a family domain (objects are people,predicates are Parent, Sibling, Brother, etc) to show who that man is. You mayapply any of the inference methods described in class. Why do you think thisriddle is difficult to grasp?27. Given the following clauses in first order logic, prove by resolution that :istype(Tuna;Mammal);that is, prove that a Tuna is not a Mammal.istype(Tuna; Fish):equal(Mammal; Fish)istype(p; Type(p)):istype(p; k) _ equal(Type(p); k):equal(x; y) _ :equal(y; z) _ equal(x; z):equal(x; y) _ equal(y; x)