Functions
In the study of mathematics, functions provide an important unifying concept. Functions
are also familiar in computer science as components of programs that formalize the rela-
tionship between the input and the output for a computation. The problem of designing a
combinatorial circuit often starts by defining a function that describes the behavior of the
circuit for each possible input. Using functions to describe the behavior of a circuit, we
can use techniques of Sections 2.5.2 and 2.5.4 to draw the combinatorial circuit with the
same behavior. Since functions are special kinds of sets or relations, we will study them
here using the ideas introduced in Chapters 1 and 3.
First, we define both functions and several fundamental properties of functions. Next,
we deal with operations on functions, and basic properties of functions resulting from the
operations introduced are explored. We explain special properties of functions, such as how
many objects are related to a single object by a given function. Examples of functions with
each property are given to help understand and differentiate among the properties that func-
tions may possess. We discuss the Pigeon-Hole Principle and the Generalized Pigeon-Hole
Principle, the applications of which include such different ideas as proving that rational
numbers have a repeating decimal expansion and that two students in a small class will
have a birthday on the same day of the week. Finally, we show how functions provide a
way to formalize the notion of counting, and we see how to count the number of elements
in both finite and infinite sets. In the context of counting rational and real numbers, Can-
tor's first and second diagonal arguments are introduced. These diagonal arguments come
up in many computer science contexts, especially in the theory of computation and the
analysis of algorithm complexity.rn Basic Definitions
Intuitively, a function is a black box into which we put objects and out of which come
other objects. A function must satisfy two rules. First, if an object is put in, then something
must come out. Second, for each object input, there is only one possible output. If the same
object is put in several times, then the same output must come out each time. No matter
how many times one asks on what day Julius Caesar was born, the answer is always the
same.
219