Problem 1 (4 points):

Read Chapter 8 of the textbook. Drawing from the text and outside material (articles or websites) describe in your own words the differences between the following formal languages: high-level programming languages, first-order logic, temporal logic, probability theory, and fuzzy logic.

Note that I did not ask for definitions of these terms, but descriptions of the differences between them. The differences between FOL, temporal logic, probability theory, and fuzzy logic are easy to see given a description of each. Everyone that caught on to the fact that I was asking for the differences did a fairly good job of explaining the differences between them. Very good answers also related high-level programming languages with the rest in terms of procedural (programming languages) versus descriptive, the separation of knowledge from the methods used to manipulate it, and the ability (probability, fuzzy logic) versus inability (programming languages) to deal with partial information.

Problem 2 (6 points): [due to a problem with Part D one could earn up to 7 out of 6 points on this problem]

Part A:

1. ∀x (Dog(x) ∨ Cat(x)) → FourLegs(x)
2. ∀x∀y (Employee(x) ∧ President(y)) → ¬ GE(pay(x),pay(y)) where GE(a,b) is a >= b and pay(c) returns c's earnings.
3. ∃x∀y (Box(x) ∧ Book(y) ∧ Empty(x)) → ¬ Inside(y,x) where Inside(y,x) states that y is inside x
4. ∀x Lunch(x) → ¬ Free(x)

Part B:

1. Domain: the integers, R(x,y) is defined as x * y = 0
2. Domain: people, R(x,y) is defined as `x is a child of y'

Part C: Proving that Shakey will eventually crash.

Translating into first-order logic:

1. “All robots have sensors.” becomes: ∀x ∃y Robot(x) ∧ Sensor(y) → Has(x,y)
2. “No sensors are perfect.” becomes: ∀y Sensor(y) → ¬ Perfect(y)
3. “Robots without perfect sensors will crash.” becomes: ∀x ∀y Robot(x) ∧ Sensor(y) ∧ ¬ Perfect(y) ∧ Has(x,y) → WillCrash(x)
4. “Shakey is a robot.” becomes: Robot(Shakey)

Converting into CNF (prior to removing quantifiers):

1. ∀x ∃y ¬ Robot(x) ∨ ¬ Sensor(y) ∨ Has(x,y)
2. ∀y ¬ Sensor(y) ∨ ¬ Perfect(y)
3. ∀x ∀y ¬ Robot(x) ∨ ¬ Sensor(y) ∨ Perfect(y) ∨ ¬ Has(x,y) ∨ WillCrash(x)
4. Robot(Shakey)

Completing the CNF conversion for 1 requires a process called skolemization which creates a new function f(x) that gives the correct assignment for y given a specific value of x. Let f(Shakey) return a constant object G. By 1 we can assume that such an object exists and that it is a sensor, i.e. Sensor(G) is true.

After removing the quantifiers we have the following facts in CVF form:

1. ¬ Robot(x) ∨ ¬ Sensor(f(x)) ∨ Has(x,f(x))
2. ¬ Sensor(y) ∨ ¬ Perfect(y)
3. ¬ Robot(x) ∨ ¬ Sensor(y) ∨ Perfect(y) ∨ ¬ Has(x,y) ∨ WillCrash(x)
4. Robot(Shakey)
5. Sensor(G)

To prove that Shakey crashes, i.e. WillCrash(Shakey), assert ¬ WillCrash(Shakey)

6. ¬ WillCrash(Shakey)

Proof by contradiction using resolution:

Note that at this point fact 6, our contradiction, has not been used and WillCrash(Shakey) has been proven. If we were not proving by contradiction, we would be done now. The contradiction proof requires one more step:

Part D: This question was flawed. You could not prove that there is a bird that does not fly using the facts that I gave you. As a result everyone got one point for this problem. Those that attempted the proof (did some of the actual resolution proof, beyond conversion into CNF) got 2 points.