Module 07 Written Assignment - Solutions 1 There are five exercises in this assignment, one per page. Use as much space as you like to answer the following exercises. Put your answers in the green-edged boxed provided. 1. Let X ={2,1, 0,1 } and Y ={2,1, 0,1 } . Define a function F : X Y follows: 2 F ( x )=x + x1 . Prove that F is neither 1 - 1 nor onto. as Module 07 Written Assignment - Solutions 2. For each of the following functions, either prove that the function is 1 - 1 or find a counterexample to show that the function is not 1 - 1. a. F:RR { 2 F ( x )= x 2for x 0 x for x 0 b. F:ZZ F ( n) = { n1 for n even n3 for n odd 2 Module 07 Written Assignment - Solutions 3 3. The first 3 parts of Theorem 2 are repeated below for your convenience. Also, recall that Theorem 2a was already proven in the Lesson. Prove Theorem 2, parts b and c. (Hint: once you have proven part b, you can use parts a and b to prove part c.) Theorem 2: Let F: X Y and G:Y Z be functions. Then a. If F and G are both 1 - 1 then G F is 1 - 1. b. If F and G are both onto then G F is onto. c. If F and G are both 1 - 1 correspondences then G F is a 1 - 1 correspondence. Module 07 Written Assignment - Solutions 4. Let X ={1, 2,3, 4, 5 } . Let three functions be defined as follows: F : X X with F ( 1 )=3, F ( 2 )=2, F ( 3 ) =2, F ( 4 )=2, F ( 5 )=5 G: X X with G ( 1 ) =1,G ( 2 )=3, G (3 )=4, G ( 4 )=5, G ( 5 ) =2 H: XX with H (1 ) =2, H ( 2 )=4, H ( 3 )=1, H ( 4 )=3, H ( 5 )=5 It is easier to do the problem if you write the functions in pair form: F={( 1, 3 ) , ( 2, 2 ) , ( 3, 2 ) , ( 4,2 ) , ( 5,5 ) } G={ (1, 1 ) , (2, 3 ) , ( 3, 4 ) , ( 4, 5 ) , (5, 2 ) } H={ (1, 2 ) , ( 2, 4 ) , ( 3,1 ) , ( 4, 3 ) , ( 5, 5 ) } Find each of the following. Give your answers as sets of ordered pairs. a. F G b. HF c. G H d. F G H e. F1 f. G g. H 1 h. Of 1 F 1 , 1 G , and H any) of these are functions? 1 , which (if 4 Module 07 Written Assignment - Solutions 5 5. Consider the following Boolean function F of two variables p and q defined by a table: p q 1 1 0 0 1 0 1 0 F(p,q ) 0 0 1 1 Is the combinatorial (logic) circuit shown below the correct circuit to represent this function? If not, describe how you would correct the circuit in order to make it accurately represent the function. Circuit p q F(p, q) p