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. 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]




Victor has been murdered and Alice, Barney, and Caddy are the only suspects. As the chief detective on the case, you bring them in for questioning. Each one tells the truth except for the culprit, who may be lying. Here is what they told you:




Alice says that she is innocent. She says that Barney and Victor were friends, and Caddy and Victor were not friends.




Barney says that he is innocent, plus that he and Victor were not friends. Caddy says that she is innocent, and that Barney and Victor 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. Now you want to find the suspect.




(1 point) Write a set of FOL sentences representing the information learned when interviewing the three suspects.



(1 point) Write a set of FOL sentences representing the general knowledge assumptions you’ve made.



(2 point) Convert all of your sentences in (1) and (2) to CNF.



(1 point) State the goal to be solved as an FOL sentence.



(1 point) Caddy later tells you that she was a friend of Victor. Write an FOL sentence that represents this new piece of information.



(2 point) Is the knowledge base containing all of the sentences satisfiable? If so, give an interpretation that makes it true. If not, prove unsatisfiability using resolution.



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),




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 (1) and (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).