Discrete Mathematics for Computer Science

Exercises 251

W Exercises

1. Let X = {1,2, 3, 4} and Y = {5, 6, 7, 8,9}. Let F = {(1, 5), (2,7), (4,9), (3, 8)}.

Show that F is a function from X to Y. Find F-^1 , and list its elements. Is F-^1 a

function? Why, or why not?

2. Let S = {(0, 8), (1, 10), (2, 12), (3, 14), (4, 16), (5, 18), (6, 20), (7, 22)). Is S a function?
   Why, or why not? Find S-1, and list its elements. Is S-1 a function? Why, or why not?
   Identify the domain of S-1.

3. Let X = {1, 2, 3, 41. Let F : X -* IR be a function defined as the set of ordered pairs

{(1, 2), (2, 3), (3, 4), (4, 5)}. Let G : R -* IR be the function defined as G(x) = x^2.

What is G o F?

4. Let F : R -- R be defined as F(x) = 2x + 8. Let G : R -- R be defined as G(y) =
   (y - 8)/2. Prove that F o G = IdR and G o F = IdR.


5. Define the functions F, G, and H as indicated in the following diagrams:

1 --- a a -- ee e *--- r

2~ .b b *1ý f fe- es

3 c C - eg g e- t

4 e d d ./ed h

F G H

Find the following:

(a) G o F

(b) H o (G o F)

(c) (H o G) o F

6. Let X = {0, I, 21 _ IR. List all eight strictly increasing sequences of elements of X.

The ordering is < on IR. List all subsequences of the sequence x, y, z.

7. Let A = {1, 2, 3, 4}. Let the functions F, G, and H be given with domain and

codomain A defined as

F(1) = 3, F(2) = 2, F(3) = 2, and F(4) = 4

G(1) = 1, G(2) = 3, G(3) = 4, and G(4) = 2

H(1) = 2, H(2) = 4, H(3) = 1, and H(4) = 3

Find the following:

(a) F o G

(b) H o F

(c) Go H

(d) FoGoH

8. Let A be a rule for defining a function F : N --* N such that F is 1-1 and onto. Show

how to construct a rule for defining F-^1.

9. For sets X, Y, and Z, let F : X ->. Y and G : Y -* Z be 1-1 correspondences. Prove

that (G o F)-^1 = F-^1 o G-^1.