Page 176 - Discrete Mathematics and Its Applications

2.3 Functions 155

59. How many bytes are required to encode n bits of data 72. Suppose that f is a function from A to B, where A and B
where n equals are finite sets with |A|=|B|. Show that f is one-to-one
a) 7? b) 17? c) 1001? d) 28,800? if and only if it is onto.
60. How many ATM cells (described in Example 28) can be 73. Prove or disprove each of these statements about the floor
transmitted in 10 seconds over a link operating at the fol- and ceiling functions.
lowing rates? a) x = x for all real numbers x.
a) 128 kilobits per second (1 kilobit = 1000 bits) b) 2x = 2 x whenever x is a real number.
b) 300 kilobits per second c) x + y −ˆx + y = 0 or 1 whenever x and y are
c) 1 megabit per second (1 megabit = 1,000,000 bits) real numbers.
61. Data are transmitted over a particular Ethernet network d) xy = x y for all real numbers x and y.

x

x + 1
in blocks of 1500 octets (blocks of 8 bits). How many e) = for all real numbers x.
blocks are required to transmit the following amounts of 2 2
data over this Ethernet network? (Note that a byte is a 74. Prove or disprove each of these statements about the floor
synonym for an octet, a kilobyte is 1000 bytes, and a and ceiling functions.
megabyte is 1,000,000 bytes.) a) x = x for all real numbers x.
a) 150 kilobytes of data b) x + y = x + y for all real numbers x and y.
b) 384 kilobytes of data c) x/2 /2 = x/4 for all real numbers x.
√
√
c) 1.544 megabytes of data d) x = x for all positive real numbers x.
d) 45.3 megabytes of data
e) x + y + x + y ≤ 2x + 2y for all real
2
62. Draw the graph of the function f (n) = 1 − n from Z numbers x and y.
to Z. 75. Prove that if x is a positive real number, then
√
√
63. Draw the graph of the function f(x) = 2x from R a) x = x .
√
√
to R. b) x = x .
64. Draw the graph of the function f(x) = x/2 from R 76. Let x be a real number. Show that 3x =
to R. 1 2
x + x + + x + .
3
3
65. Drawthegraphofthefunctionf(x) = x + x/2 from 77. For each of these partial functions, determine its domain,
R to R.
codomain, domain of definition, and the set of values for
66. Drawthegraphofthefunctionf(x) = x + x/2 from
which it is undefined.Also, determine whether it is a total
R to R.
function.
67. Draw graphs of each of these functions. a) f : Z → R, f (n) = 1/n
1
a) f(x) = x + b) f(x) = 2x + 1
2 b) f : Z → Z, f (n) = n/2
c) f(x) = x/3 d) f(x) = 1/x c) f : Z × Z → Q, f (m, n) = m/n
e) f(x) = x − 2 + x + 2 d) f : Z × Z → Z, f (m, n) = mn
1 1
f) f(x) = 2x x/2 g) f(x) = x − +
2 2 e) f : Z × Z → Z, f (m, n) = m − n if m>n
68. Draw graphs of each of these functions. 78. a) ShowthatapartialfunctionfromAtoB canbeviewed
∗
a) f(x) = 3x − 2 b) f(x) = 0.2x as a function f from A to B ∪{u}, where u is not an
2
c) f(x) = −1/x d) f(x) = x element of B and
e) f(x) = x/2 x/2 f) f(x) = x/2 + x/2
1 ⎧
g) f(x) = 2 x/2 +
2 ⎨f(a) if a belongs to the domain
∗
3
69. Find the inverse function of f(x) = x + 1. f (a) = of definition of f
⎩ u if f is undefined at a.
70. Suppose that f 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 ◦ g is given by b) Using the construction in (a), find the function f ∗
(f ◦ g) −1 = g −1 ◦ f −1 . corresponding to each partial function in Exercise 77.
71. Let S be a subset of a universal set U. The characteristic 79. a) Show that if a set S has cardinality m, where m is a
positive integer, then there is a one-to-one correspon-
function f S of S is the function from U to the set {0, 1}
such that f S (x) = 1if x belongs to S and f S (x) = 0if x dence between S and the set {1, 2,...,m}.
does not belong to S. Let A and B be sets. Show that for b) Show that if S and T are two sets each with m ele-
all x ∈ U, ments, where m is a positive integer, then there is a
one-to-one correspondence between S and T .
a) f A∩B (x) = f A (x) · f B (x)
b) f A∪B (x) = f A (x) + f B (x) − f A (x) · f B (x) ∗ 80. Show that a set S is infinite if and only if there is a proper
c) f (x) = 1 − f A (x) subset A of S such that there is a one-to-one correspon-
A
d) f A⊕B (x) = f A (x) + f B (x) − 2f A (x)f B (x) dence between A and S.