CSE 191                                                Homework 4 Fall 2016

Due: Friday 10/28/2016

This assignment will touch on different properties and concepts of functions. We have numerous ways to define a function. The most familiar representation of a function is of the form f(x) = ..., but, fundamentally, a function is nothing more than a set of pairs representing a relation between an input and an output.

As a reminder: You may not use outside references when completing the homework. You must complete all your work on your own. By submitting your homework you are stating that it is your original work (not your friend’s work or found from somewhere on the internet). When collaborating with other students in the class, you should not write anything while discussing homework problems. If you do not write solutions in front of one another, then you will have no issues completing problems in your own words and will avoid using the words of someone else. Academic integrity violations will result in an F in the course. If you have questions regarding this, please feel free to ask prior to any incidents and prior to submission.

There are a total of 100 points on the assignment.

The drawing below shows the arrow diagram for a function f1. (4 points each for 12 points total) a·

b·

c·

d·

e·

Answer each question below by describing each set in set notation.

(1a) What is domain(f1)?

(1b) What is codomain(f1)?

(1c) What is range(f1)?

Consider the sets X2 = {1,2,3,4,5} and Y2 = {0,1,2,3,4} and the function f2 : X2 → Y2 defined by f2(x) = |x − 2|. (8+2 points for 10 points total)

(2a) Draw the arrow diagram for f2.

(2b) What is the range of f2? (describe the set representing range(f2))

Let X3 = {1,2,3,4} and Y3 = {1,2,3,4,5}. Using the formal definition of a function, determine which of the following subsets of X3 × Y3 correspond to functions of X3 → Y3. Justify your answer by providing reasons why each is or is not a function. (6 points each for 18 points total)

(3a) f = {(1,4),(2,3),(1,2),(3,1),(4,1)} (3b) f = {(1,0),(2,1),(3,1)}

(3c) f = {(1,0),(2,1),(3,1),(4,2),(1,0)}

Consider the mapping f4 : R → R where. Prove that f4 is not a function.

(6 points)

Suppose g : A → B is a function. Let A1,A2 ⊆ A. Prove that

g(A1 ∪ A2) = g(A1) ∪ g(A2).

Hint: show set equality by taking an element in the left set and showing it belongs to the right set, then complete the other direction. (12 points)

Consider the following functions from Z×Z → Z. Which functions are onto? Justify your answer (modified from zyBooks exercise 4.3.1). (6 points each for 18 points total)

Consider the following functions. For each function, determine if it is 1-1, onto, and invertible. If a function is invertible, provide the inverse function. Justify each of your answers (modified from zyBooks exercise 4.3.4). (12 points each for 24 points total)

(7a) Let A5 = {1,2,3,4,5,6,7,8}. Let f5 : P(A5) → {0,1,2,3,4,5,6,7,8} be the function defined by f5(X) = |X| (note that X ⊆ A5).

(7b) Let f6 : {a,b}3 → {a,b}3 defined by f6(x,y,z) = (z,y,x). (note: A3 is shorthand for A × A × A)

(Bonus) Consider the following function from N × N → N defined by

.

Prove this function is 1-1 and onto (taken from Homer Selman “Computability and Complexity Theory”).

Hint: Use the fact that x + y = k is the equation for the kth line in the figure below, together with the identity that

.

y

This function is known as a pairing function. It is useful since we can use a single number z to represent a pair of numbers (x,y) by computing z = f7(x,y), while still begin able to recover the original pair of numbers from z by inverting f7 (and thus can treat a function taking a pair of inputs as a function with only one variable as input). (8 points each for

16 points total)

CSE 191Homework 4Fall 2016Due: Friday 10/28/2016This assignment will touch on different properties and concepts of functions. We have numer-ous ways to define a function. The most familiar representation of a function is of the formf(x) =..., but, fundamentally, a function is nothing more than a set of pairs representing arelation between an input and an output.As a reminder:You may not use outside references when completing the homework. You mustcomplete all your work on your own. By submitting your homework you are stating that it isyour original work (not your friend’s work or found from somewhere on the internet). Whencollaborating with other students in the class, you should not write anything while discussinghomework problems. If you do not write solutions in front of one another, then you will have noissues completing problems in your own words and will avoid using the words of someone else.Academic integrity violations will result in an F in the course. If you have questions regardingthis, please feel free to ask prior to any incidents and prior to submission.There are a total of 100 points on the assignment.(1) The drawing below shows the arrow diagram for a functionf1. (4 points each for 12 pointstotal)a·b·c·d·e·w·x·y·z·Answer each question below by describing each set in set notation.(1a) What isdomain(f1)?(1b) What iscodomain(f1)?(1c) What isrange(f1)?(2) Consider the setsX2={1,2,3,4,5}andY2={0,1,2,3,4}and the functionf2:X2→Y2defined byf2(x) =|x-2|. (8+2 points for 10 points total)(2a) Draw the arrow diagram forf2.(2b) What is the range off2? (describe the set representingrange(f2))

(3) LetX3={1,2,3,4}andY3={1,2,3,4,5}. Using the formal definition of a function,determine which of the following subsets ofX3×Y3correspond to functions ofX3→Y3.Justify your answer by providing reasons why each is or is not a function. (6 points eachfor 18 points total)(3a)f={(1,4),(2,3),(1,2),(3,1),(4,1)}(3b)f={(1,0),(2,1),(3,1)}(3c)f={(1,0),(2,1),(3,1),(4,2),(1,0)}(4) Consider the mappingf4:R→Rwheref4(x) =1(x2-4). Prove thatf4is not a function.(6 points)(5) Supposeg:A→Bis a function. LetA1,A2⊆A. Prove thatg(A1∪A2) =g(A1)∪g(A2).Hint: show set equality by taking an element in the left set and showing it belongs to theright set, then complete the other direction. (12 points)(6) Consider the following functions fromZ×Z→Z. Which functions are onto? Justify youranswer (modified from zyBooks exercise 4.3.1). (6 points each for 18 points total)(6a)f(x,y) = 2x-4y(6b)f(x,y) =|x| - |y|(6c)f(x,y) =bx+y3c(7) Consider the following functions. For each function, determine if it is 1-1, onto, andinvertible. If a function is invertible, provide the inverse function. Justify each of youranswers (modified from zyBooks exercise 4.3.4). (12 points each for 24 points total)(7a) LetA5={1,2,3,4,5,6,7,8}. Letf5:P(A5)→ {0,1,2,3,4,5,6,7,8}be the functiondefined byf5(X) =|X|(note thatX⊆A5).(7b) Letf6:{a,b}3→ {a,b}3defined byf6(x,y,z) = (z,y,x).(note:A3is shorthand forA×A×A)

(8)(Bonus)Consider the following function fromN×N→Ndefined byf7(x,y) =12(x2+ 2xy+y2+ 3x+y).Prove this function is 1-1 and onto (taken from Homer Selman “Computability and Com-plexity Theory”).Hint: Use the fact thatx+y=kis the equation for thekth line in the figure below,together with the identity that1 + 2 +···+k=12k(k+ 1).xyx+y= 0x+y= 1x+y= 2(0,0)(0,1)(1,0)(2,0)(1,1)(0,2)This function is known as a pairing function. It is useful since we can use a single numberzto represent a pair of numbers (x,y) by computingz=f7(x,y), while still begin able torecover the original pair of numbers fromzby invertingf7(and thus can treat a functiontaking a pair of inputs as a function with only one variable as input). (8 points each for16 points total)

• 1494473224-homework04.pdf

ComputerScienceExpert

(11)

Status NEW Posted 11 May 2017 03:05 AM My Price 9.00

-----------

Attachments

file 1494473227-Solutions file 2.docx preview (51 words )

H-----------ell-----------o S-----------ir/-----------Mad-----------am ----------- Th-----------ank----------- yo-----------u f-----------or -----------you-----------r i-----------nte-----------res-----------t a-----------nd -----------buy-----------ing----------- my----------- po-----------ste-----------d s-----------olu-----------tio-----------n. -----------Ple-----------ase----------- pi-----------ng -----------me -----------on -----------cha-----------t I----------- am----------- on-----------lin-----------e o-----------r i-----------nbo-----------x m-----------e a----------- me-----------ssa-----------ge -----------I w-----------ill----------- be----------- qu-----------ick-----------ly -----------onl-----------ine----------- an-----------d g-----------ive----------- yo-----------u e-----------xac-----------t f-----------ile----------- an-----------d t-----------he -----------sam-----------e f-----------ile----------- is----------- al-----------so -----------sen-----------t t-----------o y-----------our----------- em-----------ail----------- th-----------at -----------is -----------reg-----------ist-----------ere-----------d o-----------n -----------THI-----------S W-----------EBS-----------ITE-----------. ----------- Th-----------ank----------- yo-----------u -----------

Not Rated(0)

• Buy Answer