Mathematics for Computer Science

Chapter 4 Mathematical Data Types72

whereyandzrange over binary strings, or

f 3 .x;n/WWDthe pair.n;x/

wherenranges over the nonnegative integers.
A function with a finite domain could be specified by a table that shows the value
of the function at each element of the domain. For example, a functionf 4 .P;Q/
wherePandQare propositional variables is specified by:

P Q f 4 .P;Q/

T T T

T F F

F T T

F F T

Notice thatf 4 could also have been described by a formula:

f 4 .P;Q/WWDŒP IMPLIESQç:

A function might also be defined by a procedure for computing its value at any
element of its domain, or by some other kind of specification. For example, define
f 5 .y/to be the length of a left to right search of the bits in the binary stringyuntil
a 1 appears, so

f 5 .0010/ D 3;

f 5 .100/ D 1;

f 5 .0000/ is undefined:

Notice thatf 5 does not assign a value to any string of just 0 ’s. This illustrates an
important fact about functions: they need not assign a value to every element in the
domain. In fact this came up in our first examplef 1 .x/D1=x^2 , which does not
assign a value to 0. So in general, functions may bepartial functions, meaning that
there may be domain elements for which the function is not defined. If a function
is defined on every element of its domain, it is called atotal function.
It’s often useful to find the set of values a function takes when applied to the
elements ina setof arguments. So iff WA!B, andSis a subset ofA, we define
f.S/to be the set of all the values thatf takes when it is applied to elements ofS.
That is,
f.S/WWDfb 2 Bjf.s/Dbfor somes 2 Sg:

For example, if we letŒr;sçdenote the interval fromrtoson the real line, then
f 1 .Œ1;2ç/DŒ1=4;1ç.