CSE473 Homework # 2 : Reasoning
Due Date: Friday, October 27
- 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.
- 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.
S: I am sad.
M: I go to a movie.
B: My dog barks.
b) Do I go to a movie? Prove your answer.
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.
- 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.
- 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)
Contradiction
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.”
- 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.
- 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)))
- 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 ]