324 ~ Theory of Computer Science
In the follO\ving definition, we introduce an operation on functions over X.
Definition 11.1 If fl. f2, ..., fk are partial functions of n variables and g is
a partial function of k variables, then the composition of g with f1, 12, .. .Jk
is a partial function of 11 variables defined by
g(j1(XI, Xl> •.. , x ll ), h(x1o X2, ..., XII)' ... , fk(.>::l, X2, ..., XII))
If. for example, f1, f2 and f, are partial functions of two variables and g
is a partial function of three variables, then the composition of g with f1, 12,
f, is given by g(jl (Xl, X2), h(x)o X2), f,(X1, X2))'
EXAMPLE 11.1
Let f1(X, y) =X + y, f2(x, y) = 2x,h(x, y) =.tT and g(.>::, y, z) =X + Y + z be
functions over N. Then
g(jI(X, y), f2(X, y),h(x, y)) = g(x + y, 2x, xy)
=x+y+2x+xy
Thus the composition of g with f1, .h. 13 is given by a function h:
hex, y) =x + y + 2x + xy
Note: Definition 11.1 generalizes the composition of two functions. The
concept is useful where a number of outputs become the inputs for a subsequent
step of a program.
The composition of g with!J. .. ·,fll is total when g,fj, f2, .. ·,fn are total.
The function given in Example 11.1 is total as !J. f2, 13 and g are total.
EXAMPLE 11.2
Let f1 (x, y) =X - y, f2(X, y) =Y - X and g(x, y) =x + y be functions over
N. The function fl is defined only when x ~ y and 12 is defined only when
y ~ x. So f1 and 12 are defined only when x = y. Hence when X = y,
g(jl (x. y), f2(X, y)) = g(x - x, x - x) = g(O, 0) = 0
Thus the composition of g with fl and 12 is defined only for (x, x), where
x E N.
EXAMPLE 11.3
Let fl (:>:1' X2) = X1 X2, h(x)o X2) = A, 13(x)o X2) = Xl> and g(x)o X2, x3) = X2X3
be functions over L. Then
g(jI(Xlo X2), h(xI, X2), 13(x1, X2)) = g(XIX2, A, x[) = Ax 1 = Xl
So the composition of g with !J. 12, 13 is given by a function h, where
h(x)o x:) =Xl'