$30
Artificial Intelligence CPSC 470/570
PS 3: Logic and Inference
• Late assignments are not accepted without a Dean’s excuse.
• Collaboration policy: Remains the same as in PS2.
• Submission: You must upload your submission electronically to Gradescope
before the cutoff deadline posted above. One way to do this is to print this
assignment, write out your answers with pen or pencil in the spaces
provided, and then upload images of each page of your assignment.
• Students taking CPSC570: Problem #4 is designed to be completed only by
students in CPSC570. Students taking CPSC 470 do not need to do problem 4.
Problem 1 (3 points)
State each of the following in First-Order Predicate Calculus (FOPC), using only the list
of provided predicates and functions. You may invent any variable or constant names
that you desire. If there is a single, unambiguous way to represent the statement,
then just provide the FOPC representation. If there is any ambiguity in the
sentence, the interpretation, or the representation, you should write 1-3 English
sentences that describe the ambiguity and provide at least 2 FOPC sentences that
are both accurate representations of the English statement.
Allowed Predicates: Likes(x,y), Bird(x), Ostrich(x), Penguin(x), Flies(x),
NeedsToLove(x,y). Likes(x,y) means “x likes y” and NeedsToLove(x,y) means “x needs to
love y”. The remaining have their obvious interpretations.
1.1 Everybody doesn’t like something but nobody doesn’t like Sara Lee.
1.2 All birds except Ostriches and Penguins fly.
1.3 Everybody needs somebody to love
Problem 2 (3 points)
Using propositional logic, it is possible to prove theorems by simply enumerating all
possible truth values of all variables and checking that the theorem holds. Demonstrate
that each of the following is a valid theorem by filling in the provided truth table with
“T” for true and “F” for false.
2.1 (p Þ ¬p) Þ ¬p
p
a:
¬p
b:
(pÞ¬p) b Þ a
2.2 ((p Ù q) Ù r) Þ (p Ù (q Ù r))
p q r
a:
p Ù q
b:
a Ù r
c:
q Ù r
d:
p Ù c b Þ d
2.3 (p Ù (q Ú r)) Þ ((p Ù q) Ú (p Ù r))
p q r
a:
q Ú r
b:
p Ù a
c:
p Ù q
d:
p Ù r
e:
c Ú d b Þ e
Problem 3 (6 points)
You are given the following facts:
1. Everyone who entered this country and who was not a diplomat was searched
by a customs official.
2. William was a terrorist.
3. William entered this country.
4. William was searched by terrorists only.
5. No terrorist was a diplomat.
Show using first-order logic that:
Goal: There is a person who is both a terrorist and a customs official.
Your solutions should have the same format as slide 14 from the lecture on Inference (#9).
Hints:
• Start by translating the goal into FOPC and enter it into the line marked “goal”.
• Line numbers 1-5 should be the FOPC statements that are equivalent to the
English sentences 1-5 above.
• Use only the following predicates: Entered(x) meaning “x entered this country”,
Diplomat(x), CustomsOfficial(x), Terrorist(x), and Searched(x,y) meaning that “x
searched y”.
• You may introduce any constants or variables that you need.
• The Reasoning column should contain references to an inference rule and the
statements that you used to derive the new sentence. For example, “Existential
elimination on 7” or “Modus ponens on 9 and 3” or “And-introduction on 1, 3,
and 5” or “de Morgan’s rules on 7”.
• Your last line in the table should be the same FOPC statement as your goal.
• You may or may not need all of the lines in the table.
# FOPC
Sentence Reasoning
--- GOAL ---
1
given
2
given
3
given
4
given
5
given
Problem 4 (6 points) : GRADUATE STUDENTS ONLY
Consider the following (fictional) tale:
Dorsey has been murdered. Angluin, Bhattacharjee, and Cai are suspects. Only one is
guilty and the other two are innocent. The innocent ones told the truth to the police,
but the guilty one may have lied.
Angluin said that Bhattacharjee and Dorsey were friends and that Cai did not like
Dorsey. Bhattacharjee said that he was not in town at the time of the murder, and
moreover, he did not know Dorsey. Cai said that Angluin and Bhattacharjee were both
with Dorsey just before Dorsey was murdered.
Your job is to prove that Bhattacharjee is the murderer (i.e., murderer(B) ).
You should do this via a proof by contradiction. You should assume ¬ murderer(B) and show
that this leads to a something of the form P ˄ ¬P, which is a contradiction since P cannot not
be both true and false. (Your last line of the table should be something of the form P ˄ ¬P ).
You should use the following predicates: innocent(x), friends(x,y), murderer(x), likes(x,y),
inTown(x), knows(x,y), with(x,y).
# FOPC Sentence Reasoning
¬ murderer(B) assumption
1