3) f:N→R. Функция f всюду определена, но не сюръективна, т.е. f есть отображение N в R.

4) f:R→N. Функция f частично определена и сюръективна, поскольку область значений f(x) = 2ⁿ при заданном типе функции f представляет множество натуральных чисел, т.е. пр₂f = N, значит не для всех х R₊ функция f определена, т.е. пр₁f R₊. Следовательно, f:R₊ →N не является отображением.

5) f:R→R. Функция f всюду определена, но не сюръективна (f не имеет отрицательных значений). Следовательно, f – отображение R в R.

6) f: R→R₊ . Функция всюду определена и сюръективна, т.е. является отображением R на R₊.

Кроме названных свойств во всех случаях f есть функциональное соответствие, а для случаев 2 и 6 – взаимно однозначное.

Пример 3. Дано множество А = {a, b, c, d} и два преобразования этого множества (т.е. функции типа А →А, являющихся отображением А в А):

α = (1 → 3, 2 → 3, 3 → 1, 4 → 2); β = (1 → 2, 2 → 1, 3 → 1, 4 → 3).

Обычно преобразования конечных множеств записываются так:

; .

Чему равна композиция преобразований?

• Композиция преобразований – это новое преобразование:

; .

Пример 8. Пусть X множество людей.

Для каждого человека обозначим Gx множество его детей. Тогда G²x – его внуки, G³x – его правнуки, G^–1x – его родители, G^–2x – дедушка и бабушка и т.д.

Изобразив людей точками, а отображения стрелками, получим родословную человека.

Если применить операцию прямого транзитивного замыкания для данного примера, то получим прямых потомков человека x.

Для получения всех предков человека следует применить обратное транзитивное замыкание.

2.4. Контрольные вопросы

3. ОТНОШЕНИЯ

Отношения – один из способов задания взаимосвязей между элементами множеств. Чаще всего используются унарные и бинарные отношения.

Унарные (одноместные) отношения отражают наличие какого–то определенного признака R (свойства и т.п.) у элементов множества М (например, "быть четным" на множестве натуральных чисел). Тогда все такие элементы а из множества М, которые отличаются данным признаком R, образуют некоторое подмножество в М, называемое унарным отношением R, т.е. и .

Бинарные (двухместные) отношения используются для определения каких–то взаимосвязей, которыми характеризуются пары элементов множества М (так, на множестве людей могут быть заданы, например, следующие бинарные отношения: "жить в одном городе", "быть моложе", "быть сыном", "работать в одной организации" и т.п.). Тогда все пары (а, b) элементов из М, между которыми имеет место данное отношение R, образуют подмножество пар из множества всех возможных пар элементов = М², называемое бинарным отношением R, т.е. , при этом .

В общем случае могут рассматриваться п–местные (n–арные) отношения, например отношения между тройками элементов – трехместные (тернарные) отношения и т.д.

Под п–местным отношением понимают подмножество R прямого произведения п множеств: .

Говорят, что элементы а₁, а₂, ..., а_n находятся в отношении R, если

Если n–местное отношение R задано на множестве М, т.е.

M₁= M₂ =…= M_n, то

3.1. Бинарные отношения

Двухместным, или бинарным, отношением R называется подмножество пар прямого произведения , т.е. . При этом множество М₁ называют областью определения отношения R, множество М₂ – областью значений. Часто рассматривают отношения R между парами элементов одного и того же множества М, тогда . Если а, b находятся в отношении R, это часто записывается как аRb.

С отношениями связаны еще два понятия

область определения D(R) и

область значений Q(R),

определяемые соответственно:

, .

Н
а рис. 3.1 приведен условный пример отношения .

Рисунок 3.1

Способы задания бинарных отношений – любые способы задания множеств (так как отношения это подмножества некоторых множеств – прямых произведений).

Отношения, определенные на конечных множествах, обычно задаются:

1. Списком (перечислением) пар, для которых это отношение выполняется. Например, R = {(а, b), (а, с), (b,d)}.

2. Матрицей – бинарному отношению , где M = {а₁, а₂,..., а_п}, соответствует квадратная матрица порядка п, в которой элемент c_ij, стоящий на пересечении i–ой строки и j–ого столбца, равен 1, если между a_i и а_j имеет место отношение R, или 0, если оно отсутствует:

3. Графом – бинарному отношению , где M = {а₁, а₂,..., а_п}, соответствует граф, вершины которого взаимно однозначно соответствуют элементам множества М, а дуги соответствуют отношениям между элементами множества М. Например, дуга, соединяющая пару элементов а и b в направлении от а к b, показывает наличие отношения aRb. (Подробнее см. пример 1 и пример 2 п. 3.2.)

Пример 1. Пусть М = {1, 2, 3, 4, 5, 6}. Задать в явном виде (списком), матрицей и графом отношение , если R означает – "быть строго меньше".

• Отношение R как множество содержит все пары элементов а, b из М такие, что а < b:

Тогда

R = {(1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (2, 3), (2, 4), (2, 5), (2, 6), (3,4), (3, 5),

(3, 6), (4, 5), (4, 6), (5, 6)}.

Матрица отношения приведена на рис. 3.2,а.

Граф отношения приведен на рис. 3.3

Пример 2. Пусть М = {1, 2, 3, 4, 5, 6}. Составить матрицы отношений , если:

1) R₁ – "быть делителем";

2) R₂ – "иметь общий делитель, отличный от единицы";

3) R₃ – "иметь один и тот же остаток от деления на 3".

1) и выполняется для пар {(1,1), (1,2), (1,3), (1, 4), (1, 5), (1, 6), (2, 2), (2, 4), (2, 6), (3,3), (3, 6), (4,4), (5, 5), (6, 6)}.

Эти пары , определяют наличие единиц в матрице отношения на пересечении строки элемента а и столбца элемента (рис. 3.2, б);

2)

Матрица отношения R₂ представлена на рис. 3.2, в;

3) a и b имеют один и тот же остаток от деления на 3}. Матрица отношения R₃ приведена на рис. 3.2, г

Рисунок 3.2

3.2. Свойства бинарных отношений

Отношения делятся на различные виды в зависимости от того, какими свойствами они обладают.

Пусть R – отношение на множестве М, . Тогда: