1ARTIFICIAL INTELLIGENCE (CS331/CS531)
ASSIGNMENT 2
SOLUTION
(There can be many different answers to each question, the solutions shows only one of the correct answer)
1. Translate the following English sentences into firstorder logic formulas. Invent a suitable vocabulary

Some students take ADB
X((student(X) ^ takes_ADB(X))

Every student who takes ADB passes it
X((student(X)^takes_ADB(Xpasses(X))

No good student flunks an exam
¬X((good_student(X) ^ flunks_exam(X))

Brothers are siblings (express the fact that “sibling” is a symmetric relation)
XY(brother(X,Y)^bother(Y,X) siblings(X,Y))

Harry and Potter are friends
friends(harry,potter) ^ friends(potter , harry)

One’s mother is one’s female parent
XY( mother_of(X,Y) ↔ female(X) ^ parent(X,Y))

A cousin is a child of a parent’s sibling
XY(cousin (X,Y) →
N M( parent_of (M,Y) ^ sibling (N,M) ^ parent_of (N,X) ^
¬ (N=M)))

Every person has only one mother
XY Z (mother_of (X,Z) ^ mother_of(Y,Z) → X = Y)

If it isn’t cloudy tomorrow, Harry will go to the zoo and will not take his umbrella with him.
¬ cloudy (tomorrow) → go (harry , zoo) ^ ¬ takes (harry, umbrella)

Some birds are crows but no birds are squirrels
X ( (bird(X) ^ crow (X) ) ^ ¬ Z ( birds(Z) ^ squirrel (Z))

If one or more lives are lost then all lives are lost
X (life (X) ^ lost (X) → Y (life (Y) → lost (Y))
Famous Quotations:

You can fool some people all of the time, and all of the people some of the time, but you cannot fool all of the people all of the time.
X ( people (X) ^ time (T) → can_fool (X)) ^
Y P ( time (Y) ^ people (P) → can_fool (P)) ^
( people (M) ^ time (N) → ¬ can_fool(M))

All for one, and one for all!
Y X isFor(X,Y) ) ^ YX isFor(X,Y))

If you're not for us, you're against us.
Y X ¬ isFor(X,Y) → Y X isAgainst(X,Y)

The enemy of your enemy is your friend.
ZY X (enemy(X,Y) ^ enemy(Y,Z) → friend(X,Z) )
2. Translate the following formulas into natural English, according to their intuitive intended meaning:

"X(male(X) V female(X))
Everyone is either a male or a female

"X ((father(X) → male(X)) ^ (mother(X) → female(X)))
Every father is a male and every mother is a female

¬$X(father(X) ^ mother(X))
No one can be both a father and a mother
3. Argue why $X "Y F(X, Y) is not logically equivalent to "Y $X F(X, Y). Comment on the formula F(X, Y) = mother(X, Y).
$X "Y F(X, Y) means that there exists a particular X for ALL Y. That is, there is some one who is the mother of everyone.
On the other hand, "Y $X F(X, Y) means that for ALL Y there exists some X. That is, everyone has a mother.
4. Hanging Basket Problem
We have a basket hanger with three hooks (a top, middle, and bottom hook). We have a green, blue, and yellow basket, and we can hang one on each hook. Each of the baskets can contain one kind of fruit: apples, peaches, and lemons. The following should hold true:

The top basket holds lemons.

The blue basket is hanging somewhere
below the basket containing the peaches.

The yellow basket is hanging somewhere
above the green basket.
Specify the representation of the states, operators, goal, start state and cost function.
States: There is possibility to hang the basket in 3! ways on the various hooks. Also the fruits can be present in 3! ways in the different baskets. Therefore, total number of possible states 3! X 3! = 6 X 6 = 36
Operators: Hanging a basket on a particular hook, moving up / down a basket, putting / taking out fruit
Goal:
Placing Basket Fruit
Top Yellow Lemons
Middle Green Peaches
Bottom Blue Apples
Start State: Any of the 36 states
OR
Baskets empty And Not hung
Cost Function: Number of actions to achieve the goal state
5. Missionaries and Cannibals 
There are three missionaries and three cannibals on the left bank of a river.

They wish to cross over to the right bank using a boat that can only carry two at a time.

The number of cannibals on either bank must never exceed the number of missionaries on the same bank, otherwise the missionaries will become the cannibals' dinner!

Specify the representation of the states, operators, goal, start state and cost function.

Plan a sequence of crossings that will take everyone safely across.
States: A state could be
(CannibalLeft, MissionaryLeft, BoatPos, CannibalRight, MissionaryRight)
(2, 2, RIGHT, 1, 1)
ie. 2 cannibals and 2 missionaries on the left bank of the river, the boat is on the right side, together with 1 cannibal and 1 missionary
Operators: A cannibal or missionary can either move to the left or the right of the river. A legal move is one which involves moving up to two people to the opposite bank (such that cannibals don't outnumber missionaries on either bank).
Goal: 3 missionaries, 3 cannibals on the right side of the river.
Start: 3 missioniaries, 3 cannibals on the left side of the river.
Cost function: Depending on the state representation, the procedure with which the cost function is evaluated may vary. Can be 1 unit for each movement until goal state.
6. A new operator, , or exclusiveor, may be defined by the following truth table:

P

Q

P Q

T

T

F

T

F

T

F

T

T

F

F

F

Create a propositional calculus expression using only ^, V and ¬ that is equivalent to
P Q. Prove their equivalence using truth tables.
P

Q

P Q

¬P

¬Q

P ^ ¬Q

¬P ^ Q

(P ^ ¬Q) V (¬P ^ Q)

T

T

F

F

F

F

F

F

T

F

T

F

T

T

F

T

F

T

T

T

F

F

T

T

F

F

F

T

T

F

F

F

(P Q) = ((P ^ ¬Q) V (¬P ^ Q))
7. Prove that implication is transitive in the propositional calculus, that is, that
((P→Q) ^ (Q → R)) → (P → R)
P

Q

R

P→Q

Q→R

((P→Q) ^ (Q → R))

P→Q

((P→Q) ^ (Q → R)) → (P → R)

T

T

T

T

T

T

T

T

T

T

F

T

F

F

F

T

T

F

T

F

T

F

T

T

T

F

F

F

T

F

F

T

F

T

T

T

T

T

T

T

F

T

F

T

F

F

T

T

F

F

T

T

T

T

T

T

F

F

F

T

T

T

T

T

Since there is no counter example (i.e. no case in which ((P→Q) ^ (Q → R)) → (P → R) is false) which shows that implication is transitive.
8. Attempt to unify the following pairs of expressions. Either show their most general unifiers or explain why they will not unify.
{ a / X , Y / Z }
Can’t be unified

ancestor(X,Y) and ancestor(bill, father(bill))
{ bill / X , father(bill) / Y }

ancestor(X,father(X)) and ancestor(david,george)
Can’t be unified
9. a) Compose the substitution sets {a/X, Y/Z} and {X/W, b/Y}
S1 = {a/X , Y/Z}
S2 = {X/W, b/Y}
S1.S2
1) Apply S2 to S1
S_{12 }= {b/Z}
Add elements of S1 = {b/Z, a/X}
2) Add S2 to S1
S_{12 }= {b/Z , a/X, X/W , b/Y}
3) S_{12 }= {b/Z , a/W , b/Y}
S2.S1
1) Apply S1 to S2
S_{21 }= {a/W}
Add elements of S2 = {a/W, b/Y}
2) Add S1 to S2
S_{21 }= {a/W , b/Y, a/X , Y/Z}
3) S_{21 }= {a/W , b/Y, a/X , Y/Z}
b) Prove that composition of substitution sets is associative
Associative Property: x.(y.z) = (x.y).z
S1 = a/b S3 = c/a S4 = d/c
S1 X S2 = c/b (S1 X S2) X S3 = c/b X d/e = d/b
S2 X S3 = d/a (S2 X S3) X S1 = d/a X a/b = d/b
Therefore, composition is associative
c) Construct an example to show that composition is not commutative
From 9a) we can see that S_{12} ≠ S_{21 }therefore, composition is not commutative
10. Write a set of logical predicates that will perform simple automobile diagnostics (e.g. if the engine wont turn over and the lights wont come on, then the battery is bad). Don’t try to be too elaborate, but cover the cases of bad battery, out of gas, bad spark plugs and bad starter motor.
¬ present (engine_power) ^ ¬ present (light) → bad (battery)
¬ present (engine_power) ^ ¬ present (sparks) → bad (sparks_plugs)
.
.
.
(other similar predicates)
11. I married a widow (lets call her W) who has a grownup daughter (call her D). My father (F), who visited us quite often, fell in love with my step daughter and married her. Hence, my father became my soninlaw and my stepdaughter became my mother. Some months later, my wife gave birth to a son (S1), who became the brotherinlaw of my father, as well as my uncle. The wife of my father, that is, my step daughter, also had a son (S2).
Using predicate calculus create a series of expressions that represent the situation in the above story. Add expressions defining basic family relations such as the definition of fatherinlaw and use modus ponens on this system to prove the conclusion that “I am my own grand daughter”.

father (X,Y) ^ father (Y,Z) → grandfather (X,Z)

father (X,Y) ^ married (Y,Z) → fatherinlaw (X,Z)

father (X,Y) ^ mother (Y,Z) → grandfather (X,Z)

father (X,Y) ^ father (X,Z) → brother (Y,Z)

brother (X,Y) ^ grandfather (Z,Y) → grandfather (Z,X)

married (I,W)

married (F,D)

father (I,S1)

father (I,D)

father (F,S2)

father (F,I)

mother (D,S2)

grandfather(I,S2)
USING 3:
9 ^ 12 → grandfather (I, S2) (RESULT 1)
USING 4:
10 ^ 11 → brother (S2,I) (RESULT 2)
USING 5: brother (X,Y) ^ grandfather (Z,Y) → grandfather (Z,X)
Result2 ^ Result1
brother (I , S2) ^ grandfather (I, S2) → grandfather (I, I)
THEREFORE, I AM MY OWN GRANDFATHER
Note: Each question can have various answers, the solution has only shown one of them!
