MATHIOS.PDF

(161 KB) Pobierz
MATHEMAT ICAL
BACKGROUND
This supplementary chapter (present on the CD-ROM version of the book only) describes
some of the mathematical concepts behind the graphical techniques introduced in chapter
32
of
Object-Oriented Software Construction, second edition.
It is extracted from the ISE
manual on EiffelBuild
[M 1995e].
The conventions, and any cross-reference that you may encounter in this chapter,
are those of
[M 1995e]
rather than the rest of
Object-Oriented Software Construction.
Pages are numbered 1076.1, 1076.2 and so on to avoid any confusion with the page
numbers of the rest of the book, as they appear in the printed version.
1076.2
This page intentionally blank
§
1076.3
This page intentionally blank
§
32A
Mathematical background
32A.1 OVERVIEW
EiffelBuild relies on simple properties of functions. This chapter presents a summary of
the necessary notions.
You can use EiffelBuild without having read this discussion, and in fact if you are
eager to get your hands on EiffelBuild you may prefer to skip this chapter on first reading
and move immediately to the following chapter and the Guided Tour. But an
understanding of the elementary mathematical notions discussed below will help you get
the most out of EiffelBuild, especially for advanced uses.
“Introduction to the Theory
of Programming
Languages”, Prentice Hall,
1991, ISBN 0-13-498510-9
(0-13-498502-8 pbk).
Many of the topics of this chapter are also useful for the formal study of
programming languages, and are covered in more details in the book
Introduction to the
Theory of Programming Languages.
32A.2 FINITE SETS, CARTESIAN PRODUCT
A finite set may be given by the list of its members in braces, for example
∆
PERSON
= {Hélène,
Kiyoko, Laura, Roberto, Helmut}
∆
COUNTRY
= {Japan,
France, Italy, UK}
∆
where = means “is defined as”.
A note about naming conventions: the example sets used in this chapter, such as
PERSON
and
COUNTRY,
follow the Eiffel rules for types (classes): they are written in upper-case
letters, and use the singular rather than the plural. So
PERSON
denotes a set of persons and
COUNTRY
a set of countries. A mathematical text might call these sets
PEOPLE
and
COUNTRIES,
but for a programmer it is more attractive to think of declarations of the form
Hélène: PERSON
-- (Eiffel syntax)
meaning “Hélène represents an object of type
PERSON
”, hence the singular.
If
X
and
Y
are sets, then
X
×
Y,
called the cartesian product of these sets, is the set
of all pairs of the form <x,
y>
where
x
is a member of
X
and
y
is a member of
Y.
For
example the set
PERSON
×
COUNTRY
contains all the pairs such as <Hélène,
Japan>,
<Hélène,
France>,
..., <Kiyoko,
Japan>,
<Kiyoko,
France>
and so on.
Cartesian product is also applicable to infinite sets. For example if
N
is the set of
natural (non-negative) integers, then
N
×
N
is the set of all possible pairs of natural
integers.
1076.5
TH E CON CEPTS §32A.3
32A.3 RELATIONS
Let
X
and
Y
be two sets. A relation with source set
X
and target set
Y
is a set of pairs of
the form <x,
y>
such that, in every such pair,
x
is a member of
X
and y is a member of
Y.
In other words, a relation is one particular subset of the cartesian product
X
×
Y.
For example. the set of pairs
∆
citizenship
=
{<Kiyoko,
Japan>,
<Hélène,
France>,
<Laura,
Italy>,
<Roberto,
Italy>,
<Hélène,
UK>}
is a relation with
PERSON
as source set and
COUNTRY
as target set. This relation could
represent the intuitive notion “x is a citizen of
y”.
Note that Hélène would then be a person
with dual citizenship. As indicated, this relation will be called
citizenship.
This example is a finite relation. We can also have infinite relations; for example
with the set of natural integers
N
serving both as source set and target set, we can define
the infinite set of pairs
∆
neighbors
=
{<0,
1>,
<1,
0>,
<1,
2>,
<2,
1>,
<2,
3>,
<3,
2>,
<3,
4>,
...}
denoted more precisely and concisely (with the bar | used to mean “such that”) as
{<x,
y>
∈
N
×
N
|
y
=
x + 1
or
y
=
x – 1}
and representing the relation whose pairs all contain elements that differ from each other
by either +1 or –1. This relation, as indicated, will be called
neighbors.
The set of all possible relations between two sets
X
and
Y
is written
X
↔
Y.
For
example the relation
citizenship
is a member of the set
PERSON
↔
COUNTRY;
and the
relation
neighbors
is a member of
N
↔
N.
The precise definition of
X
↔
Y is
that it is the
set
P
(X
×
Y),
using the notation
P
(A), for any set
A,
to mean the powerset of
A,
that is to
say, the set of all possible subsets of
A.
The
domain
of a relation is the set consisting of all elements
x
such that the relation
contains a pair of the form <x,
y>
for some
y
— that is to say, a pair with
x
as its first
element. The domain is a subset of the source set. In the case of relation
citizenship,
the
source set is {Hélène,
Kiyoko, Laura, Roberto};
it does not contain
Helmut,
even though
this element has been listed as a member of the source set
PERSON,
because no pair in
citizenship
has it as its first element. (The relation does not give any information about
the citizenship of
Helmut.)
The
range
of a relation is the inverse notion: the set consisting of all members of
the target set that appear as second element of at least one pair in the relation.
A relation is
total
if its domain covers its entire source set — that is to say, if for
every member
x
of its source set there is at least one pair of the form <x,
y>
(for some
y)
in the relation. It is
partial
otherwise. If we say “relation” without further qualification

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin