Inducción Matemática

110

Chapter 6. Relations

introduccd so far in the book. Describe ihe initial siate 01' your systcrn and provc its iniualization ihcorcm.

6.5

Summary

7
Functions

The notauon introduced in this chapter has inc reased our abil ity lO capture specifications 01' software systerns to the extent that we concludcd with the specification 01' a modest , but nonetheless realistic, system.We ha ve described what a relation is and started to describe its vital importance in the modcling 01' state-based systems. We have described sorne useful properties 01' relations that a110w us to categorize them, and sorne useful cornbinators that allow us lo construct new relations from old ones. Finally, in our case study, we have started to introduce a way of presenting the rnathemaucs thatwe use to specify software: the sehema.

This chapter introduces the notion of a mathematical function . Many examples of functions are given as we build up a useful co11ection 01'operators on the constructs that we have introduced in previous chapters, namely sets and relations. To illustrate the usefulness of all this notation, a case study is includcd which develops a sma11 system which keepstrack of how resources are being used by a group of users.

7.1

An Introduction to Functions

An idea central to both mathernati cs and co rnputation is that 01' fu nction,"A ~n¡s- sornething thal~ delerministic answer to sorne questio ji. lt is deterrninistic in the sense that 11 always replies with thc sarnc an swer lo a particular qucstion . 11' asked "What is the squarc root 01' 4?" wewould feel .just ífied in giving either 01' the answers "+ 2" or "·2 ." In tacr, we coukí be ·capricious and vary the cho ice between the answers in order on each occasion so We as lo cause maximum inconvenience lo lhe questio ne r.:.... c,.t:!:!a.in.I.Y _~(~u l c.!.n1 be depended on .,T he point is, "What is the square root?" is not a funetion , bUI "W'hal-is tñe positive square root?" and"":Whatis the negativesquare root?" both are functions.

a

1 This

is a panicular kind of nondererrn in ism callcd dem onic nondrtcnninism .
111

112

Chapler 7. Functions

7.1 . An Introduction to Functions

We define a parlia/ junclion f rom A 10 8 to oc sornething that maps an elernent frorn A onto at most one elernent of B . We denote the set of all sucfi partial funetions from aset A to a set B

if X is in the dornain of f, then f relates x. That is,
xE dom f s» (xt-tf x)

X

stands for that elerneru of B to which

e¡

These funetions are partial in the sense that there is no neeessity for all the rnernbers of A to be rnapped to mernbers of B. the function rnight be defined on only a subset of A.
EXAMPLE 7.1:

where dom f is the dornairr' off. This smallpiece of insight allows us to tre, functions just as special cases of relations. As an example, let

u

~ {U¡,U2 •. . . ,U¡;o}

Let psqrt be the partial function rnapping nurnbers into their exacto positive square roots . Then ,
psqrt :

B ~ {l. 2..... lOO} then we can define a funetion frorn B to U: dir : B
-+t

N

-+t

N
O

U

This is a partial function because, for exarnple, 7is not in the domain of psqrt, That dir is a relation between B and U is quite c1ear; we have, however, al obligation to show that it is also functional. Happily, this is easy, sinee eviderul each elernent of its dornain is rnapped onto preeisely one elernent of its range. I is a partial function, since we can find an elernent of B. for exarnple 99, whirl is not rnapped onto anything in U .Whenever we define sorncthing and c1ain that it is a function , we should carry out such an argurnent. Figure 7. 1 shows dir represented as a picture. Thc doma in of dir is on the left of the picture, and the range is on the right. The rnaplets are represented by arrows frorn dornain elements to range elernents. As the domain and range are both fairly large, we have only included those elernents in...