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/30/08; due 2/6/08 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. Note: all assignments are taken from the 3rd edition of the text, Discrete Algorithmic Mathematics. If you have the second edition, the version of the problem in the second edition is listed under DAM2, under the comments.

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).
(In case this doesn't appear right on your computer screen, it should say "R - (S union T) = (R - S) intersect (R - T).)

(b) Prove that R ∩ (S − R) = {} (the empty set).
(The left-hand side is "R intersect (S - R)".)
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.

---