Description
1. (5 points) What logic rule did the Cheshire Cat use in this argument, and
is it sound?
“To begin with,” said the Cat, “a dog’s not mad. You grant that?”
“I suppose so,” said Alice.
“Well, then,” the Cat went on, “you see a dog growls when it’s angry, and
wags its tail when it’s pleased. Now I growl when I’m pleased, and wag my
tail when I’m angry. Therefore I’m mad.”
2. (5 points) Translate the following Lewis Carroll sentences into a
Propositional Logic Knowledge Base and derive two statements from the
Knowledge Base:
All hummingbirds are richly colored.
No large birds live on honey.
Birds that do not live on honey are dull in color.
3. (5 points) Translate the following into First Order Logic and then convert
to Conjunctive Normal Form (CNF):
According to the Pidgeon: If little girls eat eggs, then they are a kind of
serpent. Alice (who is a little girl) eats eggs. Therefore, she is a kind of
serpent.
4. (10 points) Determine for the following pairs of sentences if they can be
unified and if they can, given the most general unifier, if not discuss why.
a. P(x) Q(Dog, x) R(Cat,Dog)
P(Cat) Q(y,z) R(z,y)
b. Queen(Hearts) ^ HasProblem(Hearts, y) Solve(y, Beheading) ^
HasHeadandBody(y)
Queen(x) ^ HasProblem(x, Cheshire) Solve(y, Beheading) ^
HasHeadandBody(y)
c. ((Son(x,x) Sister(Mary,Jack)) (Daughter(x,Mary)
Brother(Jack,Mary)
((Son(Jack,x) Sister(z,x)) (Daughter(z,f(x)) Brother(y,z)))
5. (15 points) Use resolution with refutation to show that the following three
queries can be inferred from the given knowledge base. At each resolution
step also indicate the corresponding identifier and binding list.
KB: S1: Uncle(John, Jack)
S2: Aunt( Mary, Amy)
S3: Female(Amy)
S4: Brother(Jack, Amy)
S5: Brother(Bill, Jack)
S6: Sister(x,y) Siblings(x,y)
S7: Brother(x,y) Siblings(x,y)
S8: Brother(x,y) Female(y) Sister(y,x)
S9: Siblings(x,y) Uncle(z,y) Uncle(z,x)
S10: Siblings(x,y) Siblings(y,x)
S11: Uncle(x,y) Aunt(z,y) Married(x,z)
S12: Uncle(x,y) Married(z,x) Aunt(z,y)
S13: Married(x,y) Married(y,x)
a. Married(John, Mary)
b. Aunt(Mary, Jack)
c. x(Siblings(Jack,x) Uncle(John,x))
6. (10 points)Translate the knowledge base from problem 4 into a formula list
for otter and use it to perform a proof by refutation for the queries from
problem 4, and the two below. A copy of the otter executable and
documentation can be found in the course directory.
If you want to run
otter on a non-Windows computer you can access the information you will
need at http://www-unix.mcs.anl.gov/AR/otter/.
If a sentence cannot be proven determine what needs to be added to the
knowledge base to make it provable, and would this invalidate the KB.
(Turn-in the otter files, and a copy of the screen output for each query)
d. Brother(Bill, Amy)
e. Uncle(John,Bill) ^ Siblings(Bill,Jack)
7. (25 points) For the following logic problem, a) encode the problem and have
Otter solve it, and b) represent the problem as a constraint satisfaction
problem and solve using the backward algorithm with forward checking.
Link, Zelda, and Ganondorf fought three different evil creatures, the
Octorock, an Iron Knuckle, and a Poe. They fought them with three different
weapons, a bow and arrows, magic, and a sword. Determine who fought
what creature and with what weapon.
1. Ganondorf did not fight the Octorock.
2. The Iron Knuckle was not fought against with magic.
3. Zelda fought the Octorock.
4. Link has a sword and did not fight the Poe.
5. Zelda fought with the bow and arrows.
8. (25 points) Use the Graphplan planning algorithm to solve the blocks world
planning problem shown in Figure 1 and the Rush Hour problems in Figures
2 and 3. The executable, fact, and operator files for the blocks domain are
in the course directory. You must modify the fact file to solve blocks world
planning problem shown in Figure 1.
And write your own fact file and
operator file for the two Rush Hour problems shown in Figures 2 and 3.
Assume there are no trucks only cars of length two. Define actions as a
movement of a car one square north, south, east, or west depending on
orientation.
During execution of Graphplan, respond to the prompts to
perform automatic time steps, and information, and for other hit ‘B’ for build
until goals. Note your operator file (for Rush Hour) should be the same for
both problems. The only part that should be different is the initial condition
in the fact file.
Turn in a copy of your domain files, and a printout of the solutions the
planner found. For the Rush Hour problems also include a report on the
search time required and a comparison on the ease of use between
Graphplan, and the search you implemented in Assignment 1. Which makes
the most sense for this domain? And why?
Problem coding recommendations: The ops file will be fairly short; the work
is in getting the fact file correct. For the facts create a car object for each
car, and location for each grid square. Your preconditions should label
whether vehicles can go horizontally or vertically, where the nose and tail
of the car are located on the board, which squares are free, and what
locations are horizontally and vertically adjacent to each other.
Figure 1: Blocks World Planning Problem.
….O1O1….
….A1……
X0X0A1…… <= EXIT
….B1B1….
…………
…………
Figure 2: Initial State Rush Hour Problem 1.
O1P1P1Q1Q1B1
O1….C1..B1
..X0X0C1…. <= EXIT
……D1….
……D1….
…………
Figure 3: Initial State Rush Hour Problem 2.
A
C
D
B
A
C
D
B
Start State Goal State
