a) Show that if a set S has cardinality m, where m is a

Problem 80E Show that a set S is infinite if and only if there is a proper subset A of S such that there is a one-to-one correspondence between A and S.

Problem 1E Why is / not a function from R to R if

Problem 2E Determine whether f is a function from Z to R if

Problem 4E Find the domain and range of these functions. Note that in each case, to find the domain, determine the set of elements assigned values by the function. a) the function that assigns to each nonnegative integer its last digit ________________ b) the function that assigns the next largest integer to a positive integer ________________ c) the function that assigns to a bit string the number of one bits in the siring ________________ d) the function that assigns to a bit string the number of bits in the string

Problem 3E Determine whether f is a function from the set of all bit strings to the set of integers if a) f(S) is the position of a 0 bit in S. ________________ b) f(S) is the number of I bits in S. ________________ c) f(S) is the smallest integer i such that the ith bit of, S is 1 and f (s) = 0 when S is the empty string, the string with no bits.

Problem 5E Find the domain and range of these functions. Note that in each ease, to find the domain, determine the set of elements assigned values by the function. a) the function that assigns to each bit string the number of ones in the string minus the number of zeros in the string ________________ b) the function that assigns to each bit string twice the number of zeros in that siring ________________ c) the function that assigns the number of bits left over when a bit string is split into bytes (which arc blocks of 8 bits) ________________ d) the function that assigns to each positive integer the largest perfect square not exceeding this integer

Find the domain and range of these functions. a) the function that assigns to each pair of positive integers the first integer of the pair b) the function that assigns to each positive integer its largest decimal digit c) the function that assigns to a bit string the number of ones minus the number of zeros in the string d) the function that assigns to each positive integer the largest integer not exceeding the square root of the integer e) the function that assigns to a bit string tie longest string of ones in the string

Problem 7E Find the domain and range of these functions. a) the function that assigns to each pair of positive integers the maximum of these two integers ________________ b) the function that assigns to each positive integer the number of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 that do not appear as decimal digits of the integer ________________ c) the function that assigns to a bit string the number of times the block 11 appears ________________ d) the function that assigns to a bit string the numerical position of the first 1 in the string and that assigns the value 0 to a bit string consisting of all 0s

Find these values. a) \(\lfloor 1.1\rfloor\) b) \(\lceil 1.1\rceil\) c) \(\lfloor-0.1\rfloor\) d) \(\lceil-0.1\rceil\) e) \(\lceil 2.99\rceil\) f) \(\lceil-2.99\rceil\) g) \(\left\lfloor\frac{1}{2}+\left\lceil\frac{1}{2}\right\rceil\right\rfloor\) h) \(\left\lceil\left\lfloor\frac{1}{2}\right\rfloor+\left\lceil\frac{1}{2}\right\rceil+\frac{1}{2}\right\rceil\) Equation Transcription: Text Transcription: L floor 1.1 r floor L ceil 1.1 r ceil Lfloor-0.1 rfloor L ceil-0.1 r ceil L ceil 2.99 r ceil L ceil-2.99 r ceil l floor ½ +left l ceil ½ r ceil r floor L ceil l floor ½ r floor + l ceil ½ r ceil + ½ r ceil

Problem 9E Find these values.

Problem 10E Determine whether each of these functions from [a, b, c, d] to itself is one-to-one.

Problem 11E Which functions in Exercise 10 are onto?

Problem 12E Determine whether each of these functions from Z to Z is one-to-one.

Problem 13E Which functions in Exercise 12 are onto?

Determine whether \(f: \mathbf{Z} \times \mathbf{Z} \rightarrow \mathbf{Z}\) is onto if a) \(f(m, n)=2 m-n\). b) \(f(m, n)=m^{2}-n^{2}\). c) \(f(m, n)=m+n+1\). d) \(f(m, n)=|m|-|n|\). e) \(f(m, n)=m^{2}-4\). Equation Transcription: Text Transcription: f; Z x Z right arrow Z f(m,n)=2m=n f(m,n)=m^2-n^2 f(m,n)=m+n+1 f(m,n)=|m|-|n| f(m,n)=m^2-4

Problem 15E Determine whether the function f: Z x Z ? Z is onto if

Consider these functions from the set of students in a discrete mathematics class. Under what conditions is the function one-to-one if it assigns to a student his or her a) mobile phone number. b) student identification number. c) final grade in the class. d) home town.

Problem 17E Consider these functions from the set of teachers in a school. Under what conditions is the function one-to-one if it assigns to a teacher his or her a) office. ________________ b) assigned bus to chaperone in a group of buses taking students on a field trip. ________________ c) salary. ________________ d) social security number.

Problem 18E Specify a codomain for each of the functions in Exercise 16. Under what conditions is each of these functions with the codomain you specified onto? EXERCISE 16: Consider these functions from the set of students in a discrete mathematics class. Under what conditions is the function one-to-one if it assigns to a student his or her a) mobile phone number. b) student identification number. c) final grade in the class. d) home town.

Problem 19E Specify a codomain for each of the functions in Exercise 17. Under what conditions is each of the functions with the codomain you specified onto? Exercise 17: Consider these functions from the set of teachers in a school. Under what conditions is the function one-to-one if it assigns to a teacher his or her: 1. Office 2. Assigned bus to chaperone in a group of buses taking students on a field trip 3. Salary 4. Social security number

Problem 20E Give an example of a function from N to N that is a) one-to-one but not onto. ________________ b) onto but not one-to-one. ________________ c) both onto and one-to-one (but different from the identity function). ________________ d) neither one-to-one nor onto.

Problem 21 Give an explicit formula for a function from the set of integers to the set of positive integers that is a) one-to-one, but not onto. ________________ b) onto, but not one-to-one. ________________ c) one-to-one and onto. ________________ d) neither one-to-one nor onto.

Problem 22E Determine whether each of these functions is a bijection from R to R.

Determine whether each of these functions is a bijection from \(\mathbf{R}\) to \(\mathbf{R}\). a) \(f(x)=2 x+1\) b) \(f(x)=x^{2}+1\) c) \(f(x)=x^{3}\) d) \(f(x)=\left(x^{2}+1\right) /\left(x^{2}+2\right)\) Equation Transcription: Text Transcription: R f(x)=2x+1 f(x)=x^2+1 f(x)=x^3 f(x)=(x^2+1/(x^2+2)

Problem 24E Let f: R ? R and let f(x) > 0 for all .x ? R. Show that f(x) is strictly increasing if and only if the function g(x) = 1 /f(x) is strictly decreasing.

Problem 25E Let f: R ? R and let f(x) > 0 for all .x ? R. Show f(x) is strictly decreasing if and only if the function g(x) = 1/f(x) is strictly increasing.

Problem 27E a) Prove that a strictly decreasing function from R to itself is one-to-one.

Problem 26E a) Prove that a strictly increasing function from R to it self is one-to-one. ________________ b) Give an example of an increasing function from R lo itself that is not one-to-one.

Problem 28E Show that the function f(x) = ex from the set of real numbers to the set of real numbers is not invertible, but if the codomain is restricted lo the set of positive real numbers, the resulting function is invertible.

Problem 29E Show that the function f(x) = |x| from the set of real numbers to the set of nonnegative real numbers is not invertible, but if the domain is restricted to the set of non- negative real numbers, the resulting function is invertible.

Problem 30E Let S= {?1, 0, 2, 4, 7}. Find f(S) if

Let \(f(x)=\left\lfloor x^{2} / 3\right\rfloor\). Find \(f(S)\) if a) \(S=\{-2,-1,0,1,2,3\}\). b) \(S=\{0,1,2,3,4,5\}\). c) \(S=\{1,5,7,11\}\). d) \(S=\{2,6,10,14\}\). Equation Transcription: . Text Transcription: f(x)=?x^2/3? f(S) S={?2,?1,0,1,2,3} S={0,1,2,3,4,5} S={1,5,7,11} S={2,6,10,14}

Problem 32E Let f(x) = 2x where the domain is the set of real numbers. What is

Problem 33E Suppose that g is a function from A to B and f is a function from B to C. a) Show that if both f and g are one-to-one functions, then f o g is also one-to-one. ________________ b) Show that if both f and g arc onto functions, then f o g is also onto.

Problem 34E If f and f o g are one-to-one. does it follow that g is one-to-one? Justify your answer.

Problem 35E If f and f o g are onto, does it follow that g is onto? Justify your answer.

Problem 36E Find f o g and g o f, where f(x) — x2 + 1 and g(x) = .x + 2. are functions from R to R.

Problem 37E Find f + g and fg for the functions f and g given in Exercise 36.

Problem 38E Let f(x) = ax + b and g(x) = cx + J. where a, b, c. and d arc constants. Determine necessary and sufficient conditions on the constants a, b, c, and d so that f o g = g o f.

Problem 39E Show that the function f(x) = ax + b from R to R is invertible. where a and b are constants, with a ? 0. and find the inverse of f.

Problem 40E Let f be a function from the set A to the set B. Let S and T be subsets of .4. Show that

Problem 41E a) Give an example to show that the inclusion in part (b) in Exercise 40 may be proper ________________ b) Show that if f is one-to-one, the inclusion in part (b) in Exercise 40 is an equality. Let f be a function from the set A to the set B. Let S be a subset of B. We define the inverse image of S to be the subset of A whose elements are precisely all pre-images of all elements of S. We denote the inverse image of S by f-l (S). so f-1(S) {a.? A| f (a) ? S}. (Beware: The notation f-1 is used in two different ways. Do not confuse the notation introduced here with the notation f-1(y) for the value at y of the inverse of the invertible function f. Notice also that f-1(S), the inverse image of the set S, makes sense for all functions f, not just invertible functions.)

Problem 42E Let f be the function from R to R defined by f(x) = x2. Find

Let \(g(x)=\lfloor x\rfloor\). Find a) \(g^{-1}(\{0\})\). c) \(g^{-1}(\{x \mid 0<x<1\})\). b) \(g^{-1}(\{-1,0,1\})\). Equation Transcription: . . Text Transcription: g(x)=?x? g^?1({0}) g^?1({x?0<x<1}) g^?1({?1,0,1})

Let \(f\) be a function from \(A\) to \(B\). Let \(S\) and \(T\) be subsets of \(B\). Show that a) \(f^{-1}(S \cup T)=f^{-1}(S) \cup f^{-1}(T)\). b) \(f^{-1}(S \cap T)=f^{-1}(S) \cap f^{-1}(T)\). Equation Transcription: . Text Transcription: f A B S T f^?1(S cup T)=f^?1(S) cup f^?1(T) . f^?1(S cap T)=f^?1(S) cap f^?1(T)

Problem 45E Let f be a function from the set A to the set B. Let S be a subset of B. We define the inverse image of S to be the subset of A whose elements are precisely all pre - images of all elements of S. We denote the inverse image of S by , so {a A |}. (Beware: the notation is used in two different ways. Do not confuse the notation introduced here with the notation for the value at y of the inverse of the invertible function f. Notice also that , the inverse image of the set S, makes sense for all functions f, not just invertible functions.) Let f be a function from A to B. Let S be a subset of B. Show that

Problem 46E Show that is the closest integer to the number .x, except when x is midway between two integers, when it is the larger of these two integers.

Show that \(\left\lceil x-\frac{1}{2}\right\rceil\) is the closest integer to the number \(x\), except when \(x\) is midway between two integers, when it is the smaller of these two integers. Equation Transcription: Text Transcription: ?x?1/2? x

Show that if \(x\) is a real number, then \(\lceil x\rceil-\lfloor x\rfloor=1\) if \(x\) is not an integer and \(\lceil x\rceil-\lfloor x\rfloor=0\) if \(x\) is an integer. Equation Transcription: Text Transcription: x ?x???x?=1 ?x???x?=0

Show that if \(x\) is a real number, then \(x-1<\lfloor x\rfloor \leq x \leq\) \(\lceil x\rceil<x+1\). Equation Transcription: Text Transcription: x x?1<?x? < or =x < or = ?x?<x+1

Show that if \(x\) is a real number and \(m\) is an integer, then \(\lceil x+m\rceil=\lceil x\rceil+m\). Equation Transcription: Text Transcription: x m ?x+m?=?x?+m

Problem 51E Show that if x is a real number and n is an integer, then

Show that if \(x\) is a real number and \(n\) is an integer, then a) \(x \leq n\) if and only if \(\lceil x\rceil \leq n\). b) \(n \leq x\) if and only if \(n \leq\lfloor x\rfloor Equation Transcription: Text Transcription: x n x < or = n l ceil x r ceil < or = n n < or =x n < or = l floor x r floor

Problem 53E Prove that if n is an integer, then [n/2]= n/2 if n is even and (n – 1)/2 if n is odd.

Problem 54E Prove that if x is a real number, then and

Problem 55E The function INT is found on some calculators, where INT(x) = when x is a nonnegative real number and INT(x) = when x is a negative real number. Show- that this INT function satisfies the identity INT(—x) = —INT(x).

Problem 56E Let a and b be real numbers with a < b. Use the floor and or ceiling functions to express the number of integers n that satisfy the inequality a < n < b.

Problem 57E Let a and b be real numbers with a<b. Use the floor and/or ceiling functions to express the number of integers n that justify the inequality a<n<b.

Problem 58E How many bytes are required to encode n bits of data where n equals a) 4? ________________ b) 10? ________________ c) 500? ________________ d) 3000?

How many bytes are required to encode \(n\) bits of data where \(n\) equals a) 7? b) 17? c) 1001? d) 28,800?

Problem 60E How many ATM cells (described in Example 28) can be transmitted in 10 seconds over a link operating at the following rates? a) 128 kilobits per second (1 kilobit = 1000 bits) ________________ b) 300 kilobits per second ________________ c) 1 megabit per second (1 megabit = 1.000,000 bits)

Problem 61E Data are transmitted over a particular Ethernet network in blocks of 1500 octets (blocks of 8 bits). How many blocks are required to transmit the following amounts of data over this Ethernet network? (Note that a byte is a synonym for an octet, a kilobyte is 1000 bytes, and a megabyte is 1,000.000 bytes.) a) 150 kilobytes of data ________________ b) 384 kilobytes of data ________________ c) 1.544 megabytes of data ________________ d) 45.3 megabytes of data

Problem 62E Draw the graph of the function f(n) = 1 — n2 from Z to Z.

Problem 63E Draw the graph of the function f(x)= [2x] from R to R.

Problem 64E Draw the graph of the function f(x) = [x/2] from R to R.

Problem 65E Draw the graph of the function f(x) =[x] + [x/2] from R to R.

Problem 66E Draw the graph of the function f(x) = [x] + [x/2] from R to R.

Draw graphs of each of these functions. a) \(f(x)=\left\lfloor x+\frac{1}{2}\right\rfloor\) b) \(f(x)=\lfloor 2 x+1\rfloor\) c) \(f(x)=\lceil x / 3\rceil\) d) \(f(x)=\lceil 1 / x\rceil\) e) \(f(x)=\lceil x-2\rceil+\lfloor x+2\rfloor\) f) \(f(x)=\lfloor 2 x\rfloor\lceil x / 2\rceil\) g) \(f(x)=\left\lceil\left\lfloor x-\frac{1}{2}\right\rfloor+\frac{1}{2}\right\rceil\) Equation Transcription: ?? ?? ?? ?? ?? ?? ???? ???? Text Transcription: f(x)=l floor x+½ r floor f(x)=l floor 2x+1r floor f(x)=l ceil x/3 r ceil f(x)=l ceil 1/x r ceil f(x)=l ceil x-2 r ceil+l floor x+2 r floor f(x)=l floor 2x r floor l ceil x/2r ceil f(x)=l ceil l floor x-½ r floor + ½ r ceil

Problem 68E Draw graphs of each of these functions.

Problem 69E Find the inverse function of f(x) = x 3 + 1.

Problem 70E Suppose that S is an invertible function from Y to Z and g is an invertible function from X to Y. Show that the inverse of the composition f o g is given by (f o g)-1 =g-1 o f-1.

Let \(S\) be a subset of a universal set \(U\). The characteristic function \(f_{S}\) of \(S\) is the function from \(U\) to the set \(\{0,1\}\) such that \(f_{S}(x)=1\) if \(x) belongs to \(S\) and \(f_{S}(x)=0\) if \(x\) does not belong to \(S\). Let \(A\) and \(B\) be sets. Show that for all \(x \in U\) , a) \(f_{A \cap B}(x)=f_{A}(x) \cdot f_{B}(x)\) b) \(f_{A \cup B}(x)=f_{A}(x)+f_{B}(x)-f_{A}(x) \cdot f_{B}(x)\) c) \(f_{\bar{A}}(x)=1-f_{A}(x)\) d) \(f_{A \oplus B}(x)=f_{A}(x)+f_{B}(x)-2 f_{A}(x) f_{B}(x)$\) Equation Transcription: Text Transcription: S U f_S {0, 1} f_S(x) = 1 f_S(x) = 0 x A B f_A cap B (x) = f_A(x) f_B(x) f_A cap B(x) = f_A(x) + f_B(x) ? f_A(x) f_B(x) F_bar A(x) =1-f_A(x) f_A oplus B(x) = f_A(x) + f_B(x)-2f_A(x)f_B(x)

Problem 72E Suppose that f is a function from A to B. where A and B are finite sets with |A| = |B|. Show that f is one-to-one if and only if it is onto.

Problem 73E Prove or disprove each of these statements about the floor and ceiling functions.

Problem 74E Prove or disprove each of these statements about the floor and ceiling functions.

Problem 75E Prove that ifa is a positive real number, then

Problem 76E Let x be a real number. Show that [3x] =

Problem 77E For each of these partial functions, determine its domain, codomain, domain of definition, and the set of values for which it is undefined. Also, determine whether it is a total function.

a) Show that a partial function from \(A\) to \(B\) can be viewed as a function \(f^{*}\) from \(A\) to \(B \cup\{u\}\), where \(u\) is not an element of \(B\) and \(f^{*}(a)= \begin{cases}f(a) & \text { if } a \text { belongs to the domain } \\ & \text { of definition of } f \\ u & \text { if } f \text { is undefined at } a .\end{cases}\) b) Using the construction in (a), find the function \(f^{*}\) corresponding to each partial function in Exercise 77. Equation Transcription: { Text Transcription: A B f cup {u} f(x)= {_u if f is undefined at a ^f(a) if a belongs to the domain of definition of f

Problem 79E a) Show that if a set S has cardinality m, where m is a positive integer, then there is a one-to-one correspondence between S and the set {1. 2,...,m). ________________ b) Show that if S and T are two sets each with m elements. where m is a positive integer, then there is a one-to-one correspondence between S and T.