## Description

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.