Homework 8 Solution

Question 1: Resolution [9 points]




Given the knowledge base




=) (q =) r)



use resolution to prove the query




(p ^ q) =) (q =) r):




Be sure to show what you convert to CNF (do not skip steps), and how you perform each resolution step.




Question 2: Translation from English to First Order Logic [13 points]




(7 points) Consider the following axioms:



Every child loves Santa.




Everyone who loves Santa loves any reindeer.




Rudolph is a reindeer, and Rudolph has a red nose.




Anything which has a red nose is weird or is a clown. No reindeer is a clown.




Scrooge does not love anything which is weird. (Conclusion) Scrooge is not a child.




Give the First Order Logic (FOL) sentences. You may define your FOL predicates and functions.




(6 points) Consider the following axioms:



Every Austinite who is not conservative loves some armadillo. Anyone who wears maroon-and-white shirts is an Aggie.

Every Aggie loves every dog.




Nobody who loves every dog loves any armadillo.




Clem is an Austinite, and Clem wears maroon-and-white shirts. There is a conservative Austinite.




Give the First Order Logic (FOL) sentences. You may define your FOL predicates and functions.




Question 3: First Order Logic [8 points]




You are a homicide detective and receive news of the murder of your teacher, Chuck. His students Abby (aka A), Ben (aka B), and Chris (aka C) are the only suspects. You bring them in for questioning. Here’s what they tell you:




Abby says that Ben and Chuck were friends, and Chris and Chuck were not friends. Ben says he and Chuck were not friends.

Chris says that Ben and Chuck were friends.




As an astute detective you make the following assumptions about the world:




Friends don’t murder each other.




There is no more than one murderer.




If a person isn’t a murderer, they don’t lie.




(2.5 points) Write a set of sentences in FOL representing the knowledge in the six English sentences above. Note: You may have more than one FOL sentence representing one English sentence, if necessary, and you may include the knowledge given in sentence 6 directly into your representation of sentences 1-3. Use the following predicates: M(x) means x is a murderer, and F(x) means x is a friend of Chuck. Represent 5 sentences using the equality predicate.



(4 points) Write all of your sentences from (a) in conjunctive normal form (CNF). Instead of using your repre-sentation of sentence (5) from (a), convert to CNF the equivalent sentence:



(:M(A) _ :M(B)) ^ (:M(A) _ :M(C)) ^ (:M(B) _ :M(C))




(1.5 points) Chris later tells you that he was a friend of Chuck. Write an FOL sentence that represents this new piece of information.



Question 4: Forward Chaining and backward Chaining [10 points]




(5 points) Use forward chaining to solve the following problem: Given:



A B C




A^B)D B^D)F F ) G




A^E)H




A ^ C ) E Is H true? Draw a tree to illustrate the search for a proof.




(5 points) Use backward chaining on the following KB to prove Q:



P ) Q E ) B R ) Q




M^N)Q A^B)P A ) M




C ) M D ) N D




A




Draw a tree to illustrate the search for a proof. Mark the nodes that are satisfied in this KB. What is the proof of Q? (Please show the steps)




Question 5: Clustering [20 points]




Consider the following information about distances in miles between pairs of 10 U.S. cities:




The coordinates (latitude, longitude) of these cities are:




BOS (42.4, 71.1),




NY (41.7, 74.0),




DC (38.9, 77.0),

CS 540










MIA (25.8, 80.2),




SLC (40.8, 111.9),




SEA (47.6, 122.3),




SF (37.8, 122.4),




LA (34.1, 118.2),




DEN (39.7, 105.0),




ATL (33.7, 84.3).




Please directly use the Euclidean distance when solving Question 5.1 and Question 5.2.




(10 points) Perform hierarchical clustering using single-linkage and the above data.



Show the resulting dendrogram.



What clusters of cities are created if you want 3 clusters?



(10 points) Show the results of one iteration of k-means clustering assuming k = 2 and the initial cluster centers are defined as c1 = (50, 90) and c2 = (30, 100)



Give the list of cities in the initial 2 clusters.



Give the coordinates of the new cluster centers.



Give the list of cities in the 2 clusters based on the new cluster centers computed in the (b).