Discrete Mathematics for Computer Science

220 CHAPTER^4 Functions

Figure 4.1 shows a picture to keep in mind when thinking about functions.

x

F

I

F(x)

Figure 4.1 Function.

Example 1.

(a) Visualize a classroom in which every student is seated at a chair. A function called

SeatOf, outputs the chair at which a student is sitting for each student in the class.

(b) One may specify a function even though one does not have enough information

whether in some or in all cases, to calculate its values. Let BirthDate be the func-

tion that accepts as input any person whose name appears in the current edition of the

Encyclopedia Britannica and that outputs that person's birth date. No one knows the

true birth date of Euclid, but Euclid, like every other person, did have a birth date. So,

the function BirthDate still makes perfectly good sense. 0

Example 2.

(a) Let Zero R be the function that accepts as input any real number r and that always

outputs 0. A function may be quite simple!

(b) Let X be any set. Let Idx be the function that accepts as input any x in X and that

outputs the same x. Idx is called the identity function on X.

(c) The function Floor accepts any real number as input and outputs the integer formed

by truncating the fractional part of the number input. For example, Floor(3.14159) =

L3.14159] = 3.

(d) The function Ceiling accepts any real number as input and outputs the smallest in-

teger greater than or equal to the number input. For example, Ceiling(3.14159) =

[3.141591 = 4. This function is also referred to as the greatest integer function. U

The output of a function may be more complex to determine.

Example 3. Let the function ParentsOf accept a person as input and output the ordered

pair

(person's mother, person's father)

Example 4.

(a) By contrast with Example 3, there is no function ParentOf that picks out a person's

parent. Such a rule is not a function, since there are two parents, from which one must

be chosen as output.

(b) There is no function ChildOf that picks out a person's child. One reason this may not

be a function is that some people have no children and, consequently, no object can be