Discrete Mathematics for Computer Science

246 CHAPTER 4 Functions

Definition 2. Let F = {(x, y) E X x Y : F(x) = y} be a function. The inverse of F,

denoted by F , is the relation

F-1 = {(y,x) E Y x X: F(x) =y}

Example 3. Consider a business where each employee has an employee number and no

two employees have the same number. The function

EmplNoOf : Employees --* EmplNos

and its inverse, EmplNoOf-1, are pictured below in Figure 4.23.

Employees Employee

• 31,852Records
  I Er~tpI With
  EmplAkO• f 43,765

EmplMoOf 37,895

S EmttplMoOf 45,722

Ettpi Wth

EmplMof 15,242

EmpiWith

Figure 4.23 Employee functions.

The function EmplWith, as shown in Figure 4.23, would normally be a partial function

since employee numbers are very rarely a set of consecutive integers. The gaps between

employee numbers would represent values for which the function is not defined.

Example 4. Define two functions, Succ and Pred, from Z to Z. Let Succ(z) = z + 1 and

Pred(z) = z - 1. We can show that Pred-^1 = Succ.

Solution.

Pred = {(z, z - 1) : z c Z}

And

Succ = {(z, z + 1)': z G Z

= {(zI - 1, zl) :z Z 2 } (substitute z= z +l)

= {(z - 1, z) : z E Z) (substitute z for zI--since z is no longer in use,

it can be reused)

= Pred-1 I