Discrete Mathematics for Computer Science

222 CHAPTER 4 Functions

It is important to realize that the code itself is not the function. Rather, the code is just

one way to implement the rule that defines the function. The function is just the relationship

between input and output. Consequently, many different rules may give rise to the same

function.

Example 6. The following two algorithms compute the same function:

(a) For any n e N, output cos(n • 7r).

(b) For any n e N, output (-1)n.

The formal definition of equality of functions is given in Section 4.1.5. We will leave it to

the reader to verify that rules (a) and (b) define the same function.

Example 7. Show that the following rule does not define a function: Let F be the rule

with domain and codomain equal to N that outputs n^4 - 3n for each n input.

Solution. F(1) is not defined (since -2 is not in the codomain), so F is not a

function. U

4.1.2 Functions as Sets

We can use the notion of a relation to define a function by allowing the elements that are

related to belong to different sets. With this notion of a relation, a function is a special kind

of binary relation. For sets X and Y, any subset of X x Y that "obeys" the following two

rules is a function:

1. Each input corresponds to some output.


2. Each input corresponds to only one output.
   The set X is the domain of the function. The set Y is the codomain of the function. The
   idea is that a relation consists of the set of ordered pairs for which every element of X is
   the first element of exactly one pair.

Definition 1. Let X and Y be sets. A function F with domain X and codomain Y is

a subset of X x Y such that, for each x E X, there is exactly one y E Y with (x, y) E F.

F is also called a function from X to Y. A function F from X to Y is often denoted by

F : X -- Y.

From this point on, rather than identifying the domain and the codomain of a function

as sets, we will assume that the notation F : X --. Y implies this.

Example 8.

(a) Suppose a class consists of three students. Jean sits at the second chair in the first row,

Michele sits at the sixth chair in the fourth row, and Paul sits at the 37th chair in the

53rd row. For this class, the function SeatOf is the set

{(Jean, RowlSeat2), (Michele, Row4Seat6), (Paul, Row53Seat37)}

(b) Let

DayOfWeek = {Monday, Tuesday, Wednesday, Thursday,

Friday, Saturday, Sunday)