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:

9/1/04; due 9/8/04 Read: Prologue, 0.1-0.3 (pp. 1-39)

Section   Number          Points    Comments/Hints
Prologue: 7 		  2         Same problem in DAM2
0.1: 	  11 	          4         DAM2: problem 12
          14 	          2         DAM2: problem 15
 	  16 	          4         DAM2: problem 17
          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)
          15(b),(d),(f)   6         DAM2: problem 0.4, 10(b),(d),(f)
          17              3         DAM2: problem 0.4, 14
          22 		  2         DAM2: problem 0.4, 19

Two more problems:

1. [6 points]

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

• 9/2/04: Note that I corrected this problem: it used to have a ∪ on the r.h.s.

(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.

---