Компьютерная математика: Часть 1. Теория множеств и комбинаторика. Волченская Т.В - 30 стр.

UptoLike

ВУЗ: 

ПГУ | Пенза

Составители: 

Рубрика: 

30
2. Отношения и функции
2.1. Основные понятия отношений
Часто в вычислениях необходимо выбирать элементы множеств, ко-
торые удовлетворяют некоторому “отношению”. Это понятие довольно об-
щее, поэтому широко применимо. При соответствующем выборе отноше-
ния его аргументы могут быть связаны какой-либо формулой, иногда доста-
точно простой, если возможно найти удачное описание.
Рассмотрим пример, иллюстрирующий
понятие отношения (рис. 26):
Предположим, что P
– множество про-
грамм; D – конечное множество данных; R –
множество результатов.
Если мы выберем конкретное значение
из D, то оно может использоваться в некото-
рых программах из P и для каждой программы
из P существует совокупность значений из D,
которые в ней используются. Таким образом,
мы имеем соответствие между значениями
данных и
программами, и, следовательно, су-
ществуют элементы D
×P, представляющие интерес. Аналогично, если мы
сведем рассмотрение к p
∈ P, то p связывает соответствующие данные из D
с результатами из R.
Можно рассматривать данные, приводящие к остановке, или резуль-
таты, которые не могут быть получены из p. Следовательно, мы приходим к
подмножеству D
×R.
Определение. n-местным отношением R на множествах A
1
, ..., A
n
называется подмножество прямого произведения A
1
x...x A
n
.
Другими словами, элементы x
1
, ..., x
n
(где x
1
∈A
1
, ...…, x
n
∈A
n
) связаны
отношением R тогда и только тогда, когда (x
1
, x
2
, …..., x
n
)∈R, а (x
1
, x
2
, …...,
x
n
) – упорядоченный набор из n элементов.
Наиболее часто встречаются отношения при n = 2; в этом случае они
называются бинарными отношениями. Следовательно, бинарные отноше-
ния между множествами A и B являются просто подмножеством A
×B. Если
эти множества эквивалентны (скажем, равны A), то будем говорить, что
подмножество A
2
определяет отношения на A.
Отношения не являются чем-то новым. Можно построить отношения,
которые несомненно будут знакомы вам.
Рис. 26 
                     2. Отношения и функции
               2.1. Основные понятия отношений
       Часто в вычислениях необходимо выбирать элементы множеств, ко-
торые удовлетворяют некоторому “отношению”. Это понятие довольно об-
щее, поэтому широко применимо. При соответствующем выборе отноше-
ния его аргументы могут быть связаны какой-либо формулой, иногда доста-
точно простой, если возможно найти удачное описание.
                                   Рассмотрим пример, иллюстрирующий
                             понятие отношения (рис. 26):
                                   Предположим, что P – множество про-
                             грамм; D – конечное множество данных; R –
                             множество результатов.
                                   Если мы выберем конкретное значение
                             из D, то оно может использоваться в некото-
                             рых программах из P и для каждой программы
                             из P существует совокупность значений из D,
                             которые в ней используются. Таким образом,
            Рис. 26
                             мы имеем соответствие между значениями
                             данных и программами, и, следовательно, су-
ществуют элементы D×P, представляющие интерес. Аналогично, если мы
сведем рассмотрение к p ∈ P, то p связывает соответствующие данные из D
с результатами из R.
        Можно рассматривать данные, приводящие к остановке, или резуль-
таты, которые не могут быть получены из p. Следовательно, мы приходим к
подмножеству D×R.
       Определение. n-местным отношением R на множествах A1, ..., An
называется подмножество прямого произведения A1x...x An.
       Другими словами, элементы x1, ..., xn (где x1∈A1, ...…, xn∈An) связаны
отношением R тогда и только тогда, когда (x1, x2, …..., xn)∈R, а (x1, x2, …...,
xn) – упорядоченный набор из n элементов.
       Наиболее часто встречаются отношения при n = 2; в этом случае они
называются бинарными отношениями. Следовательно, бинарные отноше-
ния между множествами A и B являются просто подмножеством A×B. Если
эти множества эквивалентны (скажем, равны A), то будем говорить, что
подмножество A2 определяет отношения на A.
       Отношения не являются чем-то новым. Можно построить отношения,
которые несомненно будут знакомы вам.


                                    30

Страницы