CSc 318 Test 1 Wednesday 29 September 1999

SUGGESTED ANSWERS

Closed book. Closed notes.

1. ( 12 pts) Let A={1,2,3}, B={3,4}, C={5,6}. Find

1. (AÇ B)´ C {3}´ C = {(3,5),(3,6)}
2. (AÈ B)Ç C N
3. A´ B {(1,3),(1,4),(2,3),(2,4),(3,3),(3,4)}
4. C´ (a-b) {5,6}´ {1,2} = {(5,1),(5,2),(6,1),(6,2)}
5. 2^AÇ 2^B {f , {3}}
6. 2^{(AÇ B)´ C} 2^{{(3,5),(3,6)}} = {f , {(3,5)}, {(3,6)}, {(3,5),(3,6)}}

1. ( 16 pts) Let f={(1,5), (2,6)}, g={(1,5), (2,5),(3,6)}, h={(1,5),(4,6)}, s={(2,5), (3,5)}, and let A, B, and C be the sets from question 1. For each set below determine whether it is only a relation or whether it is a partial or total function from A to C, or from B to C, or from AÈ B to C. For example, you might write "Such and such a set is a partial function from AÈ B to C."

1. f a partial function from A to C
2. g a total function from A to C
3. h a partial function from (AÈ B) to C
4. fÈ g only a relation on (AÈ B) and C
5. fÇ g a partial function from A to C
6. h-g a partial function from B to C
7. hÈ s a total function from (AÈ B) to C
8. fÈ h a partial function from (AÈ B) to C

1. ( 9 pts) Fill out the following truth table.

P Q R PÙ ~Q ~PÚ (QÙ ~R) P® ~Q

---------------------------------------------------

T F F T F T

F T F F T T

T T T F F F

2. (20 pts) Let f:A® A be a total, 1-1, function. Prove that f o f is 1-1.

We need to show that (f o f)(x) = (f o f)(y) Þ x= y.

(f o f)(x) = (f o f)(y) Þ (f(f(x)) = f((f(y)) Þ f(x)=f(y) Þ x=y.

3. (20 pts) Prove that for any two sets |A´ B|=|B´ A|.

Define f:A´ B® B´ A by f((x,y))=(y,x).

First, I show f is 1-1. f((x,y))=f((z,w)) Þ (y,x)=(w,z) Þ y=w and x=z Þ (x,y)=(w,z)

Second, I show f is onto: for (x,y)Î B´ A, (y,x)Î A´ B and f(y,x)=(x,y).

4. (23 pts) Prove that the set of equivalence classes for an equivalence relation, R, on a set A partitions A.