242 CHAPTER 4 Functions
- Prove Theorem 3.
- Using the numbering scheme for the letters of the alphabet as given in Section 4.1.8,
encrypt the message DISCRETE MATH IS GREAT using the function F(letter) =
17(lettervalue) + 9(mod26). List the letters of the encrypted message. Find the in-
verse function, and decrypt the message. (Hint: 23. 17 = 1 (mod 26).) - Using the numbering scheme for the letters of the alphabet given in Section 4.1.8,
encrypt the message DISCRETE MATH IS GREAT using the function F(letter) =
(11 (letter value) + 13) mod 26. List the letters of the encrypted message. Find the in-
verse function, and decrypt the message. (Hint: 19. 11 = 1 (mod 26).) - For the American history fan: Consider the list of U.S. presidents up through Harry
Truman. Define the following "function" on all presidents before Harry Truman: The
successor of X is the person who followed X as president. Why is successor not a
function? - Define a function F : N --+ N such that F(n) = n - 10 if n > 100 and F(n) =
F(F(n + 11)) ifn < 100.
(a) Show that F(99) = 91.
(b) Prove that F(n) = 91 for all n such that 0 < n < 100.- Let A, B, and C be sets, and let F : A -- C and G : B -- C be functions.
(a) What condition must F and G satisfy for F U G to be a function from A U B
to C?
(b) Give conditions on A and B such that F U G is a function for every F : A --+ C
and G: B --+ C.
- Let F be a function, and let C, D C domain(F).
(a) Prove that range(F IcnD) S; range(F 1c) n range(F ID).
(b) Show by example that equality need not hold in part (a). - If looked at appropriately, the definition of a function as a set of ordered pairs and the
intuitive notion that a function is something given by a rule are equivalent. Develop
that equivalence here. Assume that F has a finite domain {0, 1, 2. n - 11 and a
finite codomain t0, 1, 2 ... , m - 1}.
(a) Suppose F is a function given as a set of ordered pairs. For an input xl, give a rule
for calculating F(xl). Use F (or its graph) in your rule.
(b) Suppose the function F is given by a rule. Express F as a set of ordered pairs. - Find a combinatorial circuit for each of the following boolean functions:
(a)
p Iq F(p, q)I I I
1 0 1
0 1 0
0 0 0