CS 480 – WRITTEN ASSIGNMENT 3

CS 480 – WRITTEN ASSIGNMENT 3
There are five questions. Please submit your solutions through Blackboard.
1. Resolution. Perform resolution on the following pairs of sentences. Simplify them to the degree which
they can no longer be simplified. If two rules can be resolved in multiple different ways, show them
separately.
a.
R1: P  Q
R2: Q
b.
R1: P  Q  R
R2: Q  R
c.
R1: P  Q
R2: P  Q
d.
R1: P  Q
R2: P  Q
e.
R1: P  Q  R  S
R2: P  R  Z
2. Convert to CNF. Convert each of the following sentences into the Conjunctive Normal Form (CNF). If a
sentence is already in CNF, write so. Treat each sentence as an independent sentence; this is not a single
KB, and this is not a resolution problem.
a. A  B
b. A  (B  C)
c. (A  B)  C
d. (A  B)  (C  D)
e. (A  B)  (C  D)
3. Proof by contradiction and resolution - I. We are given the following KB, which is already in CNF form.
Does this KB entail R? Prove your answer using proof-by-contradiction and resolution. Any reasoning
other than proof-by-contradiction and resolution is NOT acceptable. Number the sentences and write
which other sentences you used to derive them. Remember to answer the question of whether KB
entails R.
R1: A  M
R2: B  L
R3: Q  R
R4: R  P  Q
R5: R  S
R6: P  L  M
R7: P  R
R8: A
R9: B
4. Proof by contradiction and resolution - II. We are given the following KB, which is already in CNF form.
Does this KB entail (E  G)? Prove your answer using proof-by-contradiction and resolution. Any
reasoning other than proof-by-contradiction and resolution is NOT acceptable. Number the sentences
and write which other sentences you used to derive them. Remember to answer the question of
whether KB entails (E  G).
R1: A  B
R2: A  C
R3: B  D  E
R4: C  D
R5: C  G
R6: A
5. Convert English sentences to FOL. Write each of the following English sentences using First Order Logic.
Use the following predicates and constants only.
Occupation(p, o): Predicate. Person p has occupation o. You can also read it as p is o.
Customer(p1, p2): Predicate. Person p1 is a customer of person p2.
Boss(p1, p2): Predicate. Person p1 is a boss of person p2.
Doctor, Surgeon, Lawyer, Actor: Constants denoting some occupations. This
list is not comprehensive. There are also other occupations not mentioned in this list.
Mary, John: Constants denoting some people. This list is not comprehensive. There are
also other people not mentioned in this list.
a. Mary is either a lawyer or an actor.
b. John is a lawyer, but he also holds another job.
c. All surgeons are doctors.
d. John does not have a lawyer (i.e., John is not a customer of any lawyer.)
e. Every surgeon has a lawyer.