# CSE473 Homework # 2 : Reasoning

Due Date: Friday, October 27

1. For each of the following assignments to KB and a, state whether KB Þa is valid.  Use truth tables to back your answers.

a)      KB =   (AÚB®C)ÙA,

a= C

b)     KB=     (A®B)

a= B

c)      KB=    (A®B) Ù (B®C)

a= (A®C)

SOLUTION:  Most people used truth tables to show that KB is true, a is also true.

a)

 A B C (a) AÚB AÚB®C (AÚB®C)ÙA T T T T T T T T F T F F T F T T T T T F F T F F F T T T T F F T F T F F F F T F T F F F F F T F

Whenever KB is true, so is a (in this case, C).  Therefore, KB Þa.

b)

 A B A®B T T T T F F F T T F F T

KB does not entail a, since B is not true every time that a is ( see row 4 ).

c)

 A B C A®B B®C (A®B) Ù (B®C) A®C T T T T T T T T T F T F F F T F T F T F T T F F F T F F F T T T T T T F T F T F F T F F T T T T T F F F T T T T

A®C is true whenever (A®B) Ù (B®C) is true, so KB Þa.

1. Consider the following collection of statements:

The team wins or I am sad.  If the team wins, then I go to a movie.  If I am sad, then my dog barks.  My dog is quiet.

a)      Convert these statements into propositional logic using the following definitions:

W:        The team wins.

M:        I go to a movie.

B:         My dog barks.

SOLUTION:

There are several correct answers to this question.  Some of you used a truth table to show that the initial statements entail that “I got to a movie.”

It was also acceptable to use a proof.

 W S M B WÚS W®M S®B (WÚS)Ù(W®M)Ù (S®B)Ù(ØB) T T T F T T F F T T F F T F F F T F T F T T T T T F F F T F T F F T T F T T F F F T F F T T F F F F T F F T T F F F F F F T T F

The table shows that M is true whenever the conjunction of the definitions is true (column 8).

A more compact solution would use a proof:

1. WÚS                 Premise

2. W®M               Premise

3. S®B                 Premise

4. ØB                     Premise

5. ØS                     3,4,MP (generalized, since S®B is equivalent to ØS Ú B).  This is sometimes called “Modus Tollens”

6.  W                     1,5, Unit Resolution

7. M                       2,6, MP

QED                  1,2,3,4,7, Constructive Proof.

Some of you also negated the conclusion “I go to a movie” and then used resolution to reach a contradiction, which was also a good answer.

1. R&N, Problem 6.12

SOLUTION:

Clark = Manager, Jones = Engineer, Smith = Programmer.

Following R&N suggestion, we should prove this by showing a statement like CM Ù JE Ù SP.  We can prove this indirectly by

negating it and reaching a contradiction.  With this particular problem, you could have also used a constructive proof.

Your answer could have taken the form of a proof or a refutation graph.

Constructive Proof:

1.  ØJP                                           Premise (since Jones owes the programmer money)

2. ØSM                                          Premise (since the manager’s spouse… smith is not married)

3. ØJM                                          Premise (since Jones owes… manager’s spouse prohibits borrowing…)

4. ØSM Ù ØJM ® CM                 Premise (since there are only three job assignments).

5. ØSM Ù ØJM                             2,3, and introduction

6. CM                                            4, 5, MP

7. ØJP Ù ØJM                               1,3, and introduction

8. ØJP Ù ØJM ® JE                     Premise (in principle, we can make up these sorts of premises if we need to, since there are only three job assignments)

9. JE                                              7,8, MP

10. ØSM Ù ØSE ® SP                 Premise, again, we can make up as many of these as we need to

11. JE ® ØSE                               Premise

12. ØSE                                         9, 11,  MP

13.  ØSMÙØSE                             2, 12, and introduction

14. SP                                            10, 13, MP

15. CM  Ù JE Ù SP                       6,9,14, and introduction

QED                                        1,2,3,4,8,10,11,15, CP

I was a bit of a stickler in the area of citing specific inference rules like modus ponens and unit resolution (disjunctive syllogism, etc…).  Many of you had the

right argument going, but you need to cite those inference procedures when you’re using them to prove your answer.

I also accepted a variant approach that some of you used in which you took every possible combination and then disproved the assumptions.

1. Transform the following statement into First Order Predicate Logic, and then use resolution to prove the statement “some dog likes people.”

“Every dog either likes people or hates cats.  Rover is a dog.  Rover loves cats.”

SOLUTION:

Let D(x) mean that x is a dog, L(x) mean that x likes people, and H(x) mean that x hates cats.

"x(D(x) ® L(x) Ú H(x)) Ù D(Rover) Ù ØH(Rover) ® \$x( D(x) Ù L(x))

The question asks for resolution, so the best answer took the form of a refutation graph:

 "x(D(x) ® L(x) Ú H(x))

 D(Rover)

 ØH(Rover)

 Ø\$x(D(x)ÙL(x)

{x/Rover}

 D(Rover) ® L(Rover) Ú H(Rover)

Modus Ponens

 . L(Rover) Ú H(Rover)

Unit Resolution

 . L(Rover)

 D(Rover)

And Intro.

 D(Rover) Ù L(Rover)

Existential Introduction

 \$x(D(x)ÙL(x) I also accepted indirect proofs that mirrored this graph construction:

1. "x(D(x) ® L(x) Ú H(x))                              Premise

2. D(Rover)                                                      Premise

3. ØH(Rover)                                                   Premise

4. Ø\$x(D(x)ÙL(x)                                            Premise for IP

5.  D(Rover) ® L(Rover) Ú H(Rover)             1, Universal Elimination

6.  L(Rover) Ú H(Rover)                                  2,5, MP

7.  L(Rover)                                                     3,6,Unit Resolution

8.  D(Rover) Ù L(Rover)                                  2,7, and introduction

9.  \$x (D(x) Ù L(x))                                         8, Existential introduction

10.\$x (D(x) Ù L(x)) Ù Ø(\$x(D(x)ÙL(x))          4,9, And introduction

QED                                                           1,2,3,4,10, IP

I also accepted constructive proofs of the form:

1. "x(D(x) ® L(x) Ú H(x))                  Premise

2. D(Rover)                                          Premise

3. ØH(Rover)                                       Premise

4. D(Rover) ® L(Rover) Ú H(Rover)  1, Universal Elimination

5. L(Rover) Ú H(Rover)                       2,4, MP

6. L(Rover)                                          3,5,Unit Resolution

7. D(Rover) Ù L(Rover)                       2,6, and introduction

8. \$x (D(x) Ù L(x))                              7, Existential introduction

QED                                                1,2,3,8, CP

** Existential introduction is not discussed in the book, so I did not take off points if you went from

7 to 8 with a statement like “Rover is a dog that likes people, so we know that some dog likes people.”

1. What’s wrong with the following argument?

1.      Men are widely distributed all over the Earth.

2.      Socrates is a man.

3.      Therefore, Socrates is widely distributed all over the Earth.

SOLUTION:

First of all, statement (1) is obviously universally quantified.  Statement (2) pertains only to Socrates, so

we’d have to use universal elimination to be able to derive anything like statement (3).  The problem is

also in the way that the arguing person is formulating the first statement.  We might imagine a formulation

like:

"y\$x ( PlaceOnEarth(y)  ® Man(x) Ù On( y, x) )

Remove implication:

"y\$x (ØPlaceOnEarth(y) Ú Man(x) Ù On( y, x) )

Remove existential quantifiers:

"y (ØPlaceOnEarth(y) Ú Man(f(y)) Ù On( y, f(y)) )

The conclusion that is being made would be:

"y( PlaceOnEarth(y)  ® Man(Socrates) Ù On( y, Socrates) )

Where On( y, x ) means “x is can be found on place y”  This would express something close to what the first

statement says – For any place on earth, one can find some man there (and therefore, men are widely distributed

throughout the Earth).

We know that x depends on y, since the existential quantifier lies within the scope of the universally quantified y.

Therefore, it would be error to use statement 2 and modus ponens to infer that Socrates is widely distributed all over

the earth.

1. Use Skolemization, if necessary, to transform the following formulas into a clausal form.

a)      (AÙB) ÚCÚD.

b)     \$y"x(p(x,y) ®q(x)).

c)      "x"y(p(x,y) Ú\$z(q(x,y,z)).

SOLUTION:

a)      (AÚCÚD) Ù (BÚCÚD)

b)      "x(Øp(x,c) Ú (q(x))

c)      "x"y ( p(x,y) Ú q(x,y, f(x,y)))

1. R&N, Problem 9.7

Several people were confused as to how to answer this question, which I admit is vaguely worded.  I ended up accepting most answers that were on track.

SOLUTION:

a)      Normally, we negate the sentence and then use resolution to seek a contradiction.  If it’s found, we can infer that the sentence is valid

b)      We can use the same process (resolution to find contradiction) without negating the sentence first.  If we find contradiction, we

know that the sentence is unsatisfiable.

8.   R&N, Problem 9.8

SOLUTION:

a) You have the following predicates: HeadOf(h,x), Horse(x), Animal(x) Write the logical formula corresponding to the statement: "The head of a horse is the head of an animal" and "Horses are animals".

To simply the formula below I use the follow predicates:

H(x,y) = x is the head of y

A(x) = x is an animal

S(x) = x is a horse

The premise and conclusion are:

(note: Forall is Universal quantifier and Exists is Existential quantifier)

(Forall(x)) (S(x) ==> A(x))

(Forall(x)) {[(Exists(y)) (S(y) ^ H(x,y))] ==> [(Exists(z)) (A(z) ^ H(x,z))]}

This says forall head x, if x is the head of some horse, x is the head of some animal, which is the correct translation. Here are a few common translations that don't work:
(Forall(x)) (Forall(y)) {[(S(y) ^ H(x,y))] ==> [(Exists(z)) (A(z) ^ H(x,z))]}

This says forall all head x, if X is the head of all horses y, etc. which is incorrect.
(Forall(x)) (Forall(y)) {[(S(y) ^ H(x,y))] ==> [(A(y) ^ H(x,y))]}

Besides the mistake above, this sentence also assumes the horse and the animal are the same entity. But that's not implied in the sentence.

b) Convert the statement into CNF.

Premise: ~S(x) V A(x) ------------ (I)
Conclusion:

First remove quantifiers; B and C are Skolem constants: (S(B) ^ H(x,B)) ==> (A(C) ^ H(x,C))

Next munch the formula:
~(S(B) ^ H(x,B)) V (A(C) ^ H(x,C))
~(S(B) ^ H(x,B)) V (A(C) ^ H(x,C))
(~S(B) V ~H(x,B)) V (A(C) ^ H(x,C))
(~S(B) V ~H(x,B) V A(C)) ^ ((~S(B) V ~H(x,B) V H(x,C))

c)

d)      Prove that "The head of a horse is the head of an animal" follows from "Horses are animals" using resolution and the statements you have in part A.

Negate and convert to CNF:

~ (Forall(x)) (Exists(y)) (Exists(z)) {((S(y) ^ H(x,y)) ==> (A(z) ^ H(x,z))}
(Exists(x)) (Forall(y)) (Forall(z)) ~ {((S(y) ^ H(x,y)) ==> (A(z) ^ H(x,z))}

Next, Skolemize the quantified variables. Let B be Skolem constants for x:
~ ((S(y) ^ H(B,y)) ==> (A(z) ^ H(B,z)))
Then we run the conversion procedure to get the CNF:
S(y) ^ H(B,y) ^ (~A(z) V ~H(B,z)) ------- (II)

Now we try to derive a contradiction from (I) and (II):
First we break (II) into its conjuncts by and-elimination into (III), (IV) and (V):

`S(y) -------- (III)`
`H(B, y) ------- (IV)`
`(~A(z) V ~H(B,z)) ------- (V)`
` `
`A(x) ---------- (VI)         by (III) and (I)   [ Note that x and y unifies ]`
`~H(B,z) ------- (VII)      by (VI) and (V) [ here z and y unifies ]`
`empty clause by (IV) and (VII) [ again z and y unifies ]`