Computer Science 280: Homework 1

Important Note: In problems where the reasoning isn't totally obvious, EXPLAIN your reasoning. This is an important part of the thinking process (and also gives you a chance for partial credit).

Homework 1:

1/31/07; due 2/7/07 AT THE BEGINNING OF CLASS Read: Chapters 0, 1, 2.1-2.3
In the induction problems, please use the format outlined in lecture. If you don't, points will be deducted. More generally, in problems where the reasoning isn't totally obvious, EXPLAIN your reasoning. This is an important part of the thinking process (and also gives you a chance for partial credit). Note that there are solutions to some of the problems (but not any of the ones assigned for homework) at the back of the book. You may want to check them out to get ideas for the assigned problems.

Section   Number          Points    Comments/Hints
0.1: 	  11 	          4         DAM2: problem 12
          14 	          2         DAM2: problem 15
          27(b),(c)       4         DAM2: problem 0.2, 6(b),(c)
 	  33 		  10 	    DAM2: problem 0.3, 8
                                    If you don't think a function is injective/surjective,        
                                    give a counterexample.
0.2 	  7(b)            1         DAM2: problem 0.4, 6(b)
          17              3         DAM2: problem 0.4, 14

0.4: 	  3(b) 		  3         DAM2: problem 0.5, 3(c)
	  8 		  3         DAM2: problem 0.5, 8
2.2 	  5 		  5         DAM2: problem 2.2, 6
	  7 		  4         DAM2: problem 2.2, 8
	  16 		  4         DAM2: same problem

Two more problems:

1. [6 points]

(a) Prove that R − (S ∪ T) = (R − S) ∩ (R − T).

(b) Prove that R ∩ (S − R) = {} (the empty set).
Although Venn diagrams are helpful here, they are not a proof. You'll have to prove in each case that the left side is a subset of the right side, and that the right side is a subset of the left.

2. [10 points] Give the transitive closure of the following relations:

(a) {(1,3), (1,4), (2,4), (3,1), (3,2)}.

(b) {(1,3), (1,4), (1,5)}.

(c) the "brother-of" relation.

(d) the ≤ relation.

(e) the "+1" relation, consisting of all pairs (n,n+1), where n is a natural number.

---