# Artificial intelligence (CS331/CS531) assignment 2 solution

 Date conversion 03.01.2017 Size 79.29 Kb.
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 first-order logic formulas. Invent a suitable vocabulary

1. Every student who takes ADB passes it

1. No good student flunks an exam

¬X((good_student(X) ^ flunks_exam(X))

1. Brothers are siblings (express the fact that “sibling” is a symmetric relation)

XY(brother(X,Y)^bother(Y,X) siblings(X,Y))

1. Harry and Potter are friends

friends(harry,potter) ^ friends(potter , harry)

1. One’s mother is one’s female parent

XY( mother_of(X,Y) ↔ female(X) ^ parent(X,Y))

1. A cousin is a child of a parent’s sibling

XY(cousin (X,Y)  →

N M( parent_of (M,Y) ^ sibling (N,M) ^ parent_of (N,X) ^

¬ (N=M)))

XY Z (mother_of (X,Z) ^ mother_of(Y,Z) → X = Y)

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

1. Some birds are crows but no birds are squirrels

X ( (bird(X) ^ crow (X) ) ^ ¬ Z ( birds(Z) ^ squirrel (Z))

1. If one or more lives are lost then all lives are lost

X (life (X) ^ lost (X) → Y (life (Y) → lost (Y))
Famous Quotations:

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

1. All for one, and one for all!

Y X isFor(X,Y) ) ^ YX isFor(X,Y))

1. If you're not for us, you're against us.

Y X ¬ isFor(X,Y) → Y X isAgainst(X,Y)

ZY X (enemy(X,Y) ^ enemy(Y,Z) → friend(X,Z) )

2. Translate the following formulas into natural English, according to their intuitive intended meaning:

1. "X(male(X) V female(X))

Everyone is either a male or a female

1. "X ((father(X) → male(X)) ^ (mother(X) → female(X)))

Every father is a male and every mother is a female

1. ¬\$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.

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

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:

Top Yellow Lemons

Middle Green Peaches

Bottom Blue Apples
Start State: Any of the 36 states

OR

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!

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

2. 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 exclusive-or, 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.

1. p(X,Y) and p(a,Z)

{ a / X , Y / Z }

1. p(X,X) and p(a,b)

Can’t be unified

1. ancestor(X,Y) and ancestor(bill, father(bill))

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

1. ancestor(X,father(X)) and ancestor(david,george)

1. q(X) and ¬q(a)

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

S12 = {b/Z}

Add elements of S1 = {b/Z, a/X}

S12 = {b/Z , a/X, X/W , b/Y}

3) S12 = {b/Z , a/W , b/Y}
S2.S1

1) Apply S1 to S2

S21 = {a/W}

Add elements of S2 = {a/W, b/Y}

S21 = {a/W , b/Y, a/X , Y/Z}

3) S21 = {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 S12 ≠ S21 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 grown-up 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 son-in-law and my step-daughter became my mother. Some months later, my wife gave birth to a son (S1), who became the brother-in-law 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 father-in-law and use modus ponens on this system to prove the conclusion that “I am my own grand daughter”.

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

2. father (X,Y) ^ married (Y,Z) → father-in-law (X,Z)

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

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

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

6. married (I,W)

7. married (F,D)

8. father (I,S1)

9. father (I,D)

10. father (F,S2)

11. father (F,I)

12. mother (D,S2)

13. 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!