## Description

Problem Set 3: Logic

EECS 492

Notation

There are many variations on logical notation. For the sanity of our graders, please adhere to the standards in

the following table. If it is feasible in your word processor, you should use the “preferred“ notation, but in

some cases it may be necessary to resort to the “acceptable” version.

meaning preferred acceptable

logical “not“ ¬x ~x

logical “and“ x ∧ y xˆy

logical “or“ x ∨ y x v y

logical implication x ⇒ y x =y

logical bi-implication x ⇔ y x <=y

existential quantifier ∃x Exists(x), E(x)

universal quantifier ∀x Forall(x), A(x)

1 Logic Concepts and Manipulation (20 points)

1.1 Validity and Satisfiability

Use model checking via truth tables to determine whether the following logical statements are valid, satisfiable,

or unsatisfiable. In your solution file, include both the truth tables and the statements’ validity/satisfiability.

a. (P ⇒ Q) ∧ (P ∧ ¬Q)

b. (P ⇒ Q) ∨ (Q ∨ ¬P)

c. (Q ⇒ (P ∨ R)) ∧ ¬[(P ∨ R) ∨ ¬Q]

1

1.2 Conjunctive Normal Form

Convert each of the following first-order logic statements into conjunctive normal form. Show every step of

your conversions and proceed carefully, lest early mistakes propagate through later steps!

a. ∀y, z P(y) ⇔ Q(z)

b. ¬∀x ¬[P(x) ∨ Q(x)] ⇒ R(x)

c. ∀x ∀y ∃z [P(x, z) ⇒ Q(y, z)]

2 Translation (25 points)

2.1 Propositional Logic

Translate the following English sentences into propositional logic statements. You may use the following

propositions about planets: BiggerThanEarth, GasPlanet, HasWater, HasRings, SupportsLife, and Terrestrial.

a. Planets that support life have water and are terrestrial.

b. Terrestrial planets are not bigger than Earth.

c. Gas planets with rings are bigger than Earth.

d. Gas planets have rings but other planets do not.

e. Planets are either terrestrial or gaseous (but not both).

2.2 Definitions

Consider the following English language sentences:

1. Rob fed Spot before Jim fed Rover.

2. Every dog chases a cat or a dog (or both).

3. There are at least two different cats.

4. Rob likes dogs that are bigger than any cat.

5. Jim fed some cat before Rover was fed.

2

a. Define any constants, predicates, and functions that you will use to best represent the five sentences in

First-Order Logic. Some examples are Likes(x,y) and Fed(x,y,z) (with feeder x, one being fed y, and

time of feeding z).

b. Translate each of the 5 sentences into First-Order Logic using your symbols from part (a).

3 Inference (25 points)

3.1 Unification

For each of the following pairs of legal first-order logic literals, find the most-general unifier. If none exists,

explain why not. You should assume that all variables are universally quantified. Note that your task is to

execute the unification algorithm, not to interpret the semantics of the logical statements.

a. Hates(J im, x) and Hates(y, Bob

b. Hates(J im, x) and Loves(y, z)

c. Sees(Owner(x), x, Home(M ittens)) and Sees(Owner(y), SpotHome(y))

d. Older(Father(x), x) and Older(Father(y), Spot)

e. Loves(Friend(Spot), x) and Loves(y, y)

3.2 Resolution-Refutation

The following information about University of Michigan classes can be represented in conjunctive

normal form.

1. Classes with thicker books are harder.

S1 = ¬T hickerBook(x, y) ∨ HarderClass(x, y)

2. Hardness of classes is transitive.

S2 = ¬HarderClass(u, v) ∨ ¬HarderClass(v, w) ∨ HarderClass(u, w)

3. Programming classes have thicker books than some other classes.

S3 = ¬P rogrammingClass(z) ∨ T hickerBook(z, SomeOtherClass(z))

4. EECS 492 has a thicker book than EECS 376.

S4 = T hickerBook(EECS492, EECS376)

5. EECS 376 is a harder class than ENGR 101.

S5 = HarderClass(EECS376, ENGR101)

6. ENGR 101 is a programming class.

S6 = P rogrammingClass(ENGR101)

7. ECON 101 is not a programming class.

S7 = ¬P rogrammingClass(ECON101)

a. Use resolution-refutation (p.345) with an answer literal to find some class that EECS 492 is harder than.

In other words, find a c such that HarderClass(EECS492, c) is entailed. Show all steps in your work,

including which sentences get resolved and how variables are bound at each step.

b. Continue this resolution-refutation process to find the other two values of c for which HarderClass(EECS492, c)

is entailed. Show all steps in your work.

3

4 Prolog (30 points)

For this task you will need access to the Prolog programming language. If your system does not have Prolog

installed, you can download SWI Prolog at www.swi-prolog.org. If you’re having trouble getting

started, a good Prolog tutorial can be found at www.learnprolognow.org.

Consider the following First-Order Logic expressions

1. ∀x University(x) ∧ W ealthy(x) ∧ GoodAt(x, Engr) ⇒ GoodAt(x, CS)

2.∀x University(x) ∧ focusOn(x, Engr) ⇒ GoodAt(x, Engr)

3. ∀x University(x) ∧ focusOn(x, F ootball) ⇒ GoodAt(x, F ootball)

4. ∀x University(x) ∧ GoodAt(x, F ootball) ∧ focusOn(x, Engr) ⇒ W ealthy(x)

5. ∀x ∀y University(x)∧Beat(x, y, F ootball)∧University(y)∧GoodAt(y, F ootball) ⇒ GoodAt(x, F ootball)

6. ∃x University(x) ∧ Beat(x, M ichigan, F ootball)

7. University(M ichigan) ∧ University(MIT) ∧ University(OSU) ∧ University(Alabama)

8. focusOn(Alabama, F ootball) ∧ focusOn(MIT, Engr) ∧ focusOn(OSU, F ootball)

∧ focusOn(M ichigan, F ootball)

9. beat(M ichigan, OSU, F ootball)

a. Create a file where you convert the preceding expressions as exactly as possible into Prolog syntax.

You can create one or more functions as necessary. Include this file (or a paste of it) with your assignment

submission.

b. Use Prolog to answer the queries: Who is good at football? and Who is good at Engr? Extract all answers.

Include the output of Prolog with your assignment submission (cut and paste is fine).

c. Now say we want to correct or change a statement in our knowledge base using assert and retract. Retract

the statement focusOn(M ichigan, F ootball) add the statement focusOn(M ichigan, Engr) to your KB

using assert and retract. Now extract all of the answers of asking rerunning the commands from (b). What

new answers did you get and (briefly) why? What answers from part b did you no longer get and (briefly)

why? Provide your prolog statements as well.

d. What happens when you invert the order of premises for expression 5? Change (a copy of) your file from

part (a), load it into a new instance of Prolog and run the same queries as in part b. Explain how (if at all) this

changes what Prolog tells you, and why. Include the output of Prolog with your assignment submission (you

dont need to include the slightly modified Prolog code).

4