CSE2309/3309 CSC2091/3091
Artificial Intelligence  Assignment 3
(Propositional Logic and First Order Predicate Calculus)
Solutions from Richard Nichols and Lam Phuong Lam
Question 1
F: The French team will win at least one gold medal.
G: The German team will win at least one gold medal.
D: The Danish team will win at least one gold medal.
P: The French team is plagued with injuries.
S: The star German runner is disqualified.
R: It rains during most of the competition.

At least one (of the three teams) will win a gold medal.

At most one of them will win a gold medal.
( F G D ) (F G D ) (F G D ) (F G D ) or
( F G D ) (F G D ) (F G D ) (F G D )

Exactly one of them will win a gold medal.
( F G D ) (F G D ) (F G D )

Provided it doesn't rain during most of the competition and their star runner isn't disqualified, the Germans will win a gold medal if either of the other teams does.
( R S ( F D ) ) G

The Germans will win a gold medal only if it doesn't rain during most of the competition and their star runner is not disqualified.
( R S ) G (AN: Note "only if" is opposite direction to "if")
Question 2

(Smoke Fire) (Smoke Fire)
Convert to clausal form:
: (Smoke Fire) (Smoke Fire)
= (Smoke Fire) (Smoke Fire)
= (Smoke Fire) Smoke Fire
Now construct truth table:
Smoke

Fire

Fire

Smoke Fire

(Smoke Fire) Smoke Fire

T

T

F

F

T

T

F

T

T

T

F

T

F

F

F

F

F

T

F

T

From the result column it can be seen that this expression is neither valid nor unsatisfiable.

Smoke Fire Fire
Already in clausal form: Smoke Fire Fire
Now construct truth table:
Smoke

Fire

Fire

Smoke Fire Fire

T

T

F

T

T

F

T

T

F

T

F

T

F

F

T

T

From the result column it can be seen that this expression is always true, therefore  valid.

[(Smoke Heat) Fire] [(Smoke Fire) (Heat Fire)]
Convert to clausal form:
: [(Smoke Heat) Fire] [(Smoke Fire) (Heat Fire)]
= [(Smoke Heat) Fire] [(Smoke Fire) (Heat Fire)]
= (Smoke Heat Fire) (Smoke Fire Heat Fire)
= (Smoke Heat Fire) (Smoke Fire Heat)
= Smoke Heat Fire
Now construct truth table:
Heat

Smoke

Fire

Smoke

Heat

Smoke Heat
Fire

T

T

T

F

F

T

T

T

F

F

F

F

T

F

T

T

F

T

T

F

F

T

F

T

F

T

T

F

T

T

F

T

F

F

T

T

F

F

T

T

T

T

F

F

F

T

T

T

From the result column it can be seen that this expression is neither valid nor unsatisfiable.

{[Smoke Fire] [(Smoke Heat) Fire]}
Convert to clausal form:
: {[Smoke Fire] [(Smoke Heat) Fire]}
= {[Smoke Fire] [(Smoke Heat) Fire]}
= {[Smoke Fire] [(Smoke Heat) Fire]}
= [Smoke Fire] [Smoke Heat Fire]
= [Smoke Fire] [Smoke Heat Fire]
= (Smoke Fire) Smoke Heat Fire
Now construct truth table:
Heat

Smoke

Fire

Smoke

Fire

Smoke Fire

(Smoke Fire) Smoke Heat Fire

T

T

T

F

F

T

F

T

T

F

F

T

F

F

T

F

T

T

F

T

F

T

F

F

T

T

T

F

F

T

T

F

F

T

F

F

T

F

F

T

F

F

F

F

T

T

F

T

F

F

F

F

T

T

T

F

From the result column it can be seen that this expression is always false, therefore unsatisfiable.
Question 3
If the rain continues, then the river rises. If rain continues and the river rises, then the bridge will wash out. If continuation of rain will wash the bridge out, then a single road is not sufficient for the town. Either a single road is sufficient for the town or the traffic engineers have made a mistake. Prove the traffic engineers have made a mistake.
Symbols:
C

 Rain continues.

R

 River rises.

B

 Bridge washes out.

S

 Single road is not enough.

E

 Engineers have made a mistake.

Axioms:
1.

C R

Or

C R

2.

(R C) B

Or

R C B

3.

(C B) S

Or
So:
3.1
3.2

(C B) S =
(C B) S =
(S C) (S B)

4.

S E

Or

S E

R
Used Modus Ponens.
Result: The engineers made a mistake.
Quad Erat Demonstrandum  It is proven!
Used resolution because B and B can't both be true.
Used resolution because C and C can't both be true.
Eliminated one C.
Used resolution because R and R can't both be true.
equired to Prove: E
Question 4
If Mr. Smith is the brakeman's nextdoor neighbor, then Mr. Smith lives halfway between Detroit and Chicago. If Mr. Smith lives halfway between Detroit and Chicago, then he does not live in Chicago. Mr. Smith is the brakeman's nextdoor neighbor. If Mr. Robinson lives in Detroit, then he does not live in Chicago. Mr. Robinson lives in Detroit. Mr. Smith lives in Chicago or else either Mr. Robinson or Mr. Jones lives in Chicago. If Mr. Jones lives in Chicago, then the brakeman is Jones. Prove the brakeman is Jones.
Symbols:
SN

 Mr Smith is Brakeman's next door neighbour.

SH

 Mr Smith lives halfway between Detroit and Chicago.

SC

 Mr Smith lives in Chicago.

RD

 Mr Robinson lives in Detroit.

RC

 Mr Robinson lives in Chicago.

JC

 Mr Jones lives in Chicago.

JB

 Mr Jones is the brakeman.

A xioms:
Required to Prove: JB
Result: Mr Robinson or Mr Jones live in Chicago.
Result: Mr Smith doesn't live in Chicago.
Result: Mr Smith lives halfway between Detroit and Chicago.
Result: Mr Jones is the Brakeman.
Quad Erat Demonstrandum  It is proven!
Result: Therefore Mr Jones lives in Chicago.
Result: Mr Robinson doesn't live in Chicago.
Question 5
Show by a resolution refutation that the following formulas is a tautology:
(P Q) [(R v P) (R v Q)]
First must expand into clausal form:
N ow negate the whole expression, ready to perform resolution:
N
ow take each term and perform resolution:
nil
The negation of the statement we're trying to prove has evaluated to nil , therefore the inverse (the original statement) must be a tautology. Quad Erat Demonstrandum.
Question 6
Represent the following English sentences using predicate calculus:

Every chicken hatched from an egg.
x y ( ( chicken(x) egg(y) ) hatchedFrom(x,y) )
or simply: x y ( hatchedFrom(x,y) )

Someone profited from the Great Depression.
x ( person(x) profitedFrom(x,GreatDepression) )
or simply: x ( profitedFrom(x,GreatDepression) )

Some language is spoken by everyone in this room.
y x ( ( language(y) person(x) inThisRoom(x) ) spoke(x,y) )
or simply: y x ( inThisRoom(x) spoke(x,y) )

One of the coats in the closet belongs to Sarah.
x ( coat(x) inCloset(x) belongsTo(Sarah) )

All people are created equal.
X Y ([person(x) person(y) xy] createdEqual(x,y) )

Everybody loves somebody sometime.
x y t ( ( person(x) person(y) time(t) ) loves(x,y,t) )

An apple a day keeps the doctor away.
d ( (day(d) a (apple(a) eat(a,d) )) t visitDoctor(x,t) )
Question 7
Prove the validity of the following wff using the method of resolution refutation:
X Y [P(f(X)) Q(f(B))] [P(f(A)) P(Y) Q(Y)]
Convert the WFF to a clause:

Eliminate "" and "".
X Y [P(f(X)) Q(f(B))] [P(f(A)) P(Y) Q(Y)]

Move "" in as far as possible.
X Y [P(f(X)) Q(f(B))] [P(f(A)) P(Y) Q(Y)]
X Y [P(f(X)) Q(f(B))] [P(f(A)) P(Y) Q(Y)]
X Y P(f(X)) Q(f(B)) [P(f(A)) P(Y) Q(Y)]

Eliminate "".
Let X equal a constant "x" and Y equal a constant "f(x)".
P(f(x)) Q(f(B)) [P(f(A)) P(f(x)) Q(f(x))]

Eliminate "".  No need.

Put into Clausal form.  No need.
The final statement in clausal form: P(f(x)) Q(f(B)) [P(f(A)) P(y) Q(y)].
Now negate the clause for resolution:
{P(f(x)) Q(f(B)) [P(f(A)) P(f(x)) Q(f(x))]} =
{P(f(x)) Q(f(B)) [P(f(A)) P(f(x)) Q(f(x))]} =
{P(f(x1)) Q(f(B)) [P(f(A)) P(f(x2)) Q(f(x2))]}
Resolution:
P(f(x1))
Q(f(B))
P(f(A)) P(f(x2)) Q(f(x2))
{x2/B}
P(f(A)) P(f(B))
{x1/B}
P(f(A))
The negation of the statement we're trying to prove has evaluated to nil , therefore the inverse (the original statement) must be valid.
Quad Erat Demonstrandum.
{x1/A}
nil
Question 8
Prove using resolution refutation that Fido will die, given the axioms:

Fido is a dog.

All dogs are animals.

All animals will die.
Axioms:

dog(Fido).

X dog(X) animal(X).

X animal(X) dies(X).
Required to prove: dies(Fido)
So negate the goal and try to make a contradiction. Therefore add " dies(Fido)" to the list of axioms and begin resolution:
Final (clausal) list of axioms:

dog(Fido).

dog(X1) animal(X1).

animal(X2) dies(X2).

dies(Fido).
Resolution:
dog(Fido)
dog(X1) animal(X1)
animal(X1) dies(X1)
dies(Fido)
{X2/X1}
dog(X1) dies(X1)
{X1/Fido}
dog(Fido)
nil
The negation of the statement we're trying to prove has evaluated to nil , therefore the inverse (the original statement) must be true. Quad Erat Demonstrandum.
Question 9
Anyone passing his or her CSE1303 exam and winning the lottery is happy. But anyone who studies or is lucky can pass all his or her exams. Mary did not study but she is lucky. Anyone who is lucky wins the lottery. Is Mary happy? Use resolution refutation to prove your answer.
Represent the axioms in predicate calculus:

X ([pass(X, CSE1303) win(X, lotto)] happy(X))

X Y ([studies(X) lucky(X)] pass(X, Y))

studies(Mary)

lucky(Mary)

X (lucky(X) win(X, lotto))
Convert axioms to clauses:
1.

Eliminate
Convert to CNF
Eliminate

X [pass(X, CSE1303) win(X, lotto)] happy(X)
X pass(X, CSE1303) win(X, lotto) happy(X)
pass(X, CSE1303) win(X, lotto) happy(X)

2.

Eliminate
Convert to CNF
Eliminate
and split.

X Y ([studies(X) lucky(X)] pass(X, Y))
X Y ([studies(X) lucky(X)] pass(X, Y))
X Y ([studies(X) pass(X, Y)] [lucky(X) pass(X, Y)])
2.1. studies(X) pass(X, Y)
2.2. lucky(X) pass(X, Y)

3.

Nothing to do.

studies(Mary)

4.

Nothing to do.

lucky(Mary)

5.

Eliminate
Eliminate

X (lucky(X) win(X, lotto))
lucky(X) win(X, lotto)

And we wish to prove: happy(Mary)
So negate the goal and try to make a contradiction. Therefore add "happy(Mary)" to the list of axioms.
Final list of axioms: (with variables renamed)

pass(X1, CSE1303) win(X1, lotto) happy(X1)

studies(X2) pass(X2, Y1)

lucky(X3) pass(X3, Y2)

studies(Mary)

lucky(Mary)

lucky(X4) win(X4, lotto)

happy(Mary)
pass(X1, CSE1303)
win(X1, lotto) happy(X1)
studies(X2)
pass(X2, Y1)
lucky(X3)
pass(X3, Y2)
studies(Mary)
lucky(Mary)
lucky(X4) win(X4, lotto)
happy(Mary)
{X1/Mary}
{X4/Mary}
{X3/Mary}
pass(Mary, CSE1303)
win(Mary, lotto)
win(Mary, lotto)
pass(Mary, Y2)
{Y2/CSE1303}
win(Mary, lotto)
nil
The negation of the statement we're trying to prove has evaluated to nil , therefore the inverse (the original statement) must be true. Quad Erat Demonstrandum.
Question 10
All people who are not poor and are smart are happy. Those people who read are not stupid. John can read and is wealthy. Happy people have exciting lives. Can anyone be found with an exciting life? Use resolution refutation to prove your answer.
Represent the axioms in predicate calculus:

X ([poor(X) stupid(X)] happy(X))

X (reads(X) stupid(X))

reads(John)

poor(John)

X (happy(X) exciting(life, X))
Convert axioms to clauses:
1.

Eliminate
Convert to CNF
Eliminate

X ( [poor(X) stupid(X)] happy(X))
X (poor(X) stupid(X) happy(X))
poor(X) stupid(X) happy(X)

2.

Eliminate
Eliminate

X (reads(X) stupid(X))
reads(X) stupid(X)

3.

Nothing to do.

reads(John)

4.

Nothing to do.

poor(John)

5.

Eliminate
Eliminate

X (happy(X) exciting(life, X))
happy(X) exciting(life, X)

And we wish to prove: X exciting(life, X)
So negate the goal and try to make a contradiction. Therefore add "exciting(life, X)" to the list of axioms.
Final list of axioms: (renamed variables)

poor(X1) stupid(X1) happy(X1)

reads(X2) stupid(X2)

reads(John)

poor(John)

happy(X3) exciting(life, X3)

exciting(life, X4)
poor(X1) stupid(X1) happy(X1)
reads(X2) stupid(X2)
reads(John)
poor(John)
happy(X3) exciting(life, X3)
exciting(life, X4)
{X2/John}
{X1/John}
{X4/X3}
stupid(John)
happy(X3)
{X3/John}
poor(John) happy(John)
happy(John)
nil
The negation of the statement we're trying to prove has evaluated to nil , therefore the inverse (the original statement) must be true. Quad Erat Demonstrandum.
Page
