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/26/00; due 2/2/00 Read: Prologue, 0.1-0.3 (pp. 1-39)

Section   Number          Points    Comments/Hints
Prologue: 7 		  2
0.1: 	  10(b),(d) 	  6         VENN DIAGRAMS AREN'T ENOUGH HERE (DESPITE
		 		    WHAT IT SAYS IN THE TEXT).  YOU NEED AN ENGLISH
		 		    PROOF.
    	  12 	          4     
	  14 	          5 	    If you don't think D-B=A, give acounterexample.
          15 	          2
 	  17 	          4
0.2       6(b),(c) 	  4
	  10(b) 	  3
          12(b),(c) 	  4
0.3 	  8 		  10 	    If you don't think a function is injective/surjective,        
                                    give a counterexample.
0.4 	  19 		  2

One more problem:

1.

[4 points] What is 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)}

---