Discrete Mathematics for Computer Science

244 CHAPTER 4 Functions

Definition 1. Let both F : X --* Y and G : Y --> Z be partial functions. The composi-

tion of G and F is

GoF={(x,z) eXxZ: forsomeyEY, y=F(x)andz=G(y)}

Thus, (G o F)(x) = G(F(x)).

It turns out that the composition of two functions is always a function.

Example 1. Start with the SeatOf function for a class:

SeatOf = {(Jean, Seat2), (Michele, Seat5), (Paul, Seat3)}

Assume that just before the class started, workers finished repainting the desks in the fol-

lowing colors:

ColorOjSeat = {(Seatl, red), (Seat2, red), (Seat3, green), (Seat4, green), (Seat5, red)}

The definition of ColorOJSeat o SeatOf is

{(x, z) : for some y, y = SeatOf(x) and z = ColorOfSeat(y)}

Now, unravel that definition. Start with x = Jean. Since SeatOf is a function, there is ex-

actly one object y = SeatOf (Jean), which is Seat2. Figure 4.21 shows this procedure.

Jean SeatOf (Jean) = Seat 2

Figure 4.21 Jean and SeatOf(Jean).

Since ColorOfSeat is a function, there is exactly one object z = ColorOJSeat(Seat2), which

is red. This object can also be referred to as ColorOfSeat(SeatOf(Jean)). Figure 4.22 shows

this procedure.

Jean SeatOf(Jean) = Seat 2 ColorOjSeatOf(Jean) = Red

Figure 4.22 Jean, SeatOf(Jean) and ColorOfSeat(SeatOf(Jean)).

The same sort of analysis holds also for ColorOfSeat (SeatOf(Michele)) and ColorOf-

Seat(SeatOflPaul)). The function is given as

ColorOf o SeatOf = [(Jean, red), (Michele, red), (Paul, green)}

In general, composition of functions is a function. The operation can even be stated

for partial functions.