Solutions to Homework Set #6 - Michigan State University

Solutions to Homework Set #6

CSE 260, Spring 2007

Section 1.5

5. See textbook.

29. See textbook.

30. Use resolution to show the hypothesis "Allen is a bad boy or Hillary is a good girl" and "Allen is a good boy or David is happy" imply the conclusion "Hillary is a good girl or David is happy.". Let a be "Allen is a good boy"; let h be "Hillary is a good girl"; let d be "David is happy." Then our assumptions are ?a h and a d. Using resolution gives us h d, as desired.

Section 1.6

17. See textbook. 39. See textbook.

Section 1.7

3. See textbook.

4. Use a proof by cases to show that min(a, min(b, c)) = min(min(a, b), c) whenever a,b, and c are real numbers.

There are three main cases, depending on which of the three numbers is smallest. If a is smallest (or tied for smallest), then clearly a min(b, c) and and so the left hand side equals a. On the other hand, for the right-hand side we have min(a, c) = a as well. In the secon case, b is smallest (or tied for smallest). The same reasoning shows us that the right-hand side equals b; and the left-hand side is min(a, b) = b as well. In the final case, in which c is smallest (or tied for smallest), the left-hand side is min(a, c) = c, whereas the right-hand side is clearly also c. Since one of the three has to be smallest we have taken care of all the cases.

Not from the book

2. Consider problem 27 of section 1.5 on page 74 of the text book. (a) Give propositions for the two hypothesis and the conclusion by applying appropriate universal and existential instantiations. Hypothesis 1:

x(P (x) (Q(x) S(x))) P (a) (Q(a) S(a)) ?P (a) (Q(a) S(a)) (?P (a) Q(a)) (?P (a) S(a))

Hypothesis 2:

x(P (x) R(x)) P (a) R(a)

Conclusion:

x(R(x) S(x)) R(a) S(a)

1

(b) Convert the above propositions into clauses.

Clauses for Hypothesis 1: ?P (a) Q(a) and ?P (a) S(a) Clauses for Hypothesis 2: P (a) and R(a) Clauses for Conclusion: R(a) and S(a).

(c) Prove the above conclusion based on refutation procedure ( i.e., derive a contradiction based on resolution inference rule.).

?R(a) ?S(a) ?P (a) Q(a) ?P (a) S(a) P (a) R(a)

negation of conclusion

1. Prove by contradictions that there are infinitely many primes.

Assume that there are finitely many primes, say k of them. Let us write them as p1, p2, p3, . . . , pk. Thus, p1 = 2, p2 = 3, and so on. Consider the integer n = 1 + p1 ? p2 ? . . . ? pk, thus the integer n is 1 plus the product of the primes. Since n > pj for all j = 1, 2, . . . , k, the integer n itself is not a prime ( because we have assumed that only p1, p2, p3, . . . , pk are the primes and certainly n is bigger than each one of them). However, every integer can be written as a product of primes (e.g., factoring of integers). Therefore, n can be written as a product of primes. Therefore, at least one of pj will divide n. Since each pj divides n - 1 (because n - 1 = p1 ? p2 ? . . . ? pk, from the definition of n), at least one pj divides both n - 1 and n, but this is impossible (two integers which differs by only 1 cannot be divided by the same prime else the difference of the two integers which is 1 will also be divided by the prime).

2

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download