CS 331 – Introduction to Artificial Intelligence
Assignment 2 Solution
1. A new operator ⊕, or exclusive-or, may be defined by the following truth table:
P
T
T
F
F

P⊕Q
F
T
T
F

Q
T
F
T
F

Create a propositional calculus expression using only ^, v, and ~ that is equivalent to P ⊕ Q. Prove their equivalence using truth tables.
One possible correct answer is:
P ⊕ Q ≡ (P v Q) ^ ~(P ^ Q)
Proof using truth tables:
P
T
T
F
F

Q
T
F
T
F

(P v Q)
T
T
T
F

(P ^ Q)
T
F
F
F

~(P ^ Q)
F
T
T
T

(P v Q) ^ ~(P ^ Q)
F
T
T
F

P⊕Q
F
T
T
F

2. The logical operator “
” is read “if and only if.” P
Q is defined as being equivalent to (P Q) ^ (Q P). Based on this definition, show that P
Q is logically equivalent to (P v Q) (P ^ Q) using truth tables.
Truth Table for (P
P
T
T
F
F

Q) ^ (Q
Q
T
F
T
F

Truth Table for (P v Q)
P
T
T
F
F

Q
T
F
T
F

P)

P -> Q
T
F
T
T

Q -> P
T
T
F
T

(P

Q) ^ (Q

P^Q
T
F
F
F

(P v Q)

P)

T
F
F
T

(P ^ Q)
PvQ
T
T
T
F

(P ^ Q)
T
F
F
T

Hence shown that both expressions are logically equivalent.

3. Assuming this is a game in which animals attack each other, try to represent the following situation completely using first-order logic:

You have to represent the following facts:
a. The location (air/ground) of the animals
b. The abilities of the animals (e.g. flying)
c. The relative speed of the animals (slow/fast)
d. Line-of-sight status (animal A is visible to animal B)
Answers can be moderately different from the following suggested answer: is_at_location(turtle, ground) is_at_location(eagle, air) has_ability(turtle, hide_in_shell) has_ability(eagle, fly) has_speed(turtle, slow) has_speed(eagle, fast) can_see(eagle, turtle)
~can_see(turtle, eagle)
4. Answers are as follows:
a. P ^ P ≡ P
b. P ^ T ≡ P
c. P ^ F ≡ F
d. P v T ≡ T
e. P ^ ~P ≡ F
f. P v ~P ≡ T
g. P
P≡T

5. Draw a complete truth table for the following propositional logic statement:
(P ^ Q) v (P Q)
Truth table for expression (P ^ Q) v (P Q):
(P ^ Q) v (P
P
Q
P ^ Q P -> Q
T
T
F
F

T
F
T
F

T
F
F
F

T
F
T
T

Q)

T
F
T
T

6. Answers are as follows (names of predicates can be slightly different):
a. “All politicians are corrupt”
∀X politician(X) corrupt(X) b. “All Pakistani politicians are corrupt”
∀X [ politician(X) ^ pakistani(X) ] corrupt(X) c. “If a student has a GPA above 3.6, then he/she is a dean’s lister”
∀X [ student(X) ^ >(gpa(X), 3.6) ] deans_lister(X)
7. Represent the following using first order logic (using your own vocabulary):
a. Only one student failed History
∃X [ student(X) ^ failed (X, history) ] ^
[∀Y, student(Y) ^ failed(Y, history)
(X=Y) ]
The following answer will also gain partial credit:
∃X ∀Y [student(X) ^ failed(X, history)] ^
[student(Y) ^ ~failed(Y, history)]
(where X ≠ Y)
b. Only one student failed both History and Biology
∃X [student(X) ^ failed(X, history) ^ failed(X, biology)] ^
{ [ ∀Y student(Y) ^ failed(Y, history) ^ failed(Y, biology)]
The following answer will also gain partial credit:
∃X [student(X) ^ failed(X, history) ^ failed(X, biology)] ^
{ ∀Y student(Y) ^ ~[failed(Y, history) ^ failed(Y, biology)] }
(where X ≠ Y)
c. There is a woman who likes all men who are not vegetarians.
∃X ∀Y [ woman(X) ^ man(Y) ^ ~veg(Y) ] likes(X, Y)
d. No person likes a professor unless the professor is smart
∀X ∀Y professor(Y) ^ ~smart(Y) ~likes(X, Y)

(X = Y) }

e. Given that all dinosaurs are extinct, show that Denver, who is a dinosaur, is also extinct
1. ∀X dinosaur(X) extinct(X) 2. dinosaur(denver)
Using Modus Ponens on 1 and 2, we get: dinosaur(denver) extinct(denver)
8. Represent the sentence “All Germans speak the same languages” in first-order logic. Use the speaks(X, L) predicate, which means person X speaks language L.
∀X ∀Y ∀L german(X) ^ speaks(X, L) ^ german(Y)

speaks(Y, L)

9. Suppose you are investigating a death scene. Unfortunately, due to police restrictions, you cannot go to the death scene and look at the dead body, but you can talk to a person who has been to the scene. You have to use propositional logic and first-order logic to find out the cause of death.
The possible ways a death can take place are:
a. Death from a stray bullet
b. Murder by knife
c. Murder by gun
d. Murder by being strangled
e. Murder by baseball bat
f. Suicide by rope
g. Suicide by knife
h. Suicide by gun
i. Suicide by jumping off the roof
Due to the limited memory of the person you are interrogating, he can only answer the following questions:
a. Were there any bullet wounds?
b. Were there any cuts on the body?
c. Were there any marks on the neck?
d. Were there any head injuries?
e. Was the subject holding the weapon used, or have it nearby?
f. Was the subject inside the house?
Note that you will only get Boolean (Yes/No) responses to these questions
Assuming that a killer always takes his weapon with him when he leaves, prove by propositional logic, the following three murder cases:
a. Andy was murdered by a gun
b. Bush was strangled to death
c. Catherine jumped off a roof

Rule Base:
1. injuries(bullet) death(stray) v murder(gun) v suicide(gun)
2. ~injuries(bullet)
~death(stray) ^ ~murder(gun) ^ ~suicide(gun)
3. injures(cuts) murder(knife) v suicide(knife)
4. ~injuries(cuts)
~murder(knife) v ~suicide(knife)
5. injuries(marks_neck) murder(strangled) v suicide(rope)
6. ~injuries(marks_neck)
~murder(strangled) ^ ~suicide(rope)
7. injuries(head) murder(baseball_bat) v suicide(roof)
8. ~injuries(head)
~murder(baseball_bat) ^ ~suicide(roof)
9. inside(house)
~death(stray) ^ ~suicide(jump)
10. ~inside(house)
~murder(X) ^ ~suicide(Y) [Y ≠ jump]
11. holding(weapon) suicide(X) ^ ~murder(Y) [X ≠ jump]
12. ~holding(weapon)
~suicide(X) [X ≠ jump]
The answer consists of the following information:
For each step: Question Asked, Answer Received, Rule(s) Used, and the Status of the
Knowledge Base (KB)
a) Andy was murdered by a gun
Q1: Were there any bullet wounds?
A:
Yes
Rule #1: injuries(bullet) death(stray) v murder(gun) v suicide(gun)
Knowledge Base:

injuries(bullet) death(stray) v murder(gun) v suicide(gun)

Q2: Was the subject holding the weapon used, or have it nearby?
A: No
Rule #12: ~holding(weapon)
~suicide(X) [X ≠ jump] suicide(gun) contradicts ~suicide(X)… removed from KB
Knowledge Base:

injuries(bullet) death(stray) v murder(gun)
~holding(weapon)
~suicide(X) [X ≠ jump]

Q3: Was the subject inside the house?
A: Yes
Rule #9: inside(house)
~death(stray) ^ ~suicide(jump)
~death(stray) contradicts death(stray)… removed from KB
~suicide(jump) is True, therefore we can now say unconditional ~suicide(X)
Knowledge Base:

injuries(bullet) murder(gun) ~holding(weapon)
~suicide(X)
inside(house)
~death(stray)

murder(gun) is proved to be True.

b) Bush was strangled to death
Q1: Were there any marks on the neck?
A: Yes
Rule #5: injuries(marks_neck) murder(strangled) v suicide(rope)
Knowledge Base:

injuries(marks_neck) murder(strangled) v suicide(rope)

Q2: Was the victim holding the weapon, or have it nearby?
A: No
Rule #12: ~holding(weapon)
~suicide(X) [X ≠ jump] suicide(rope) contradicts ~suicide(X)… and is removed from the KB
Knowledge Base:

injuries(marks_neck) murder(strangled) ~holding(weapon)
~suicide(X) [X ≠ jump]

murder(strangled) is proven to be True

c) Catherine jumped off a roof
Q1: Were there any head injuries?
A: Yes
Rule #7: injuries(head) murder(baseball_bat) v suicide(roof)
Knowledge Base:

injuries(head) murder(baseball_bat) v suicide(roof)

Q2: Was the subject inside the house?
A: No
Rule #10: ~inside(house)
~murder(X) ^ ~suicide(Y)
Knowledge Base:

injuries(head) suicide(roof) ~inside(house)
~murder(X)
~suicide(Y) [Y ≠ jump]

suicide(roof) is proven to be True.

[Y ≠ jump]