Раздел II. БИнарные отношения и алгебраические структуры

Литература

1. Новиков, Ф.А, Дискретная математика для программистов. – Санкт-Петербург: Питер, 2007. – 304 с.

2. Белоусов, А.И. Дискретная математика. – М.: МГТУ им. Баумана, 2009.

3. Кузнецов, О.П. Дискретная математика для инженеров: [учебник для вузов] (гриф Пр. — 5-е изд., стер. — СПб. : Лань, 2007.— 400 с.

4. Яблонский, С.В. Введение в дискретную математику: Учебное пособие для Вузов/ Под ред. В.А. Садовничего – 3-е изд. стер. – М.: Высш. шк., 2006. – 384 с.

5. Гаврилов А.И., Сапоженко С.В. Задачи и упражнения по курсу дискретной математики. - М.: Наука, 1992. - 408 с.

6. Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математической логике и теории алгоритмов. - М.: Наука, 1984. - 223 с.

7. Колмогоров А.Н., Фомин С.В. Элементы теории функций и функционального анализа. - М.: Наука, 1981. - 544 с.

8. Юдин Д. Б. Вычислительные методы теории принятия решений [Текст] / М.: Наука, 1989. 320 с.

Тема 4. Бинарные отношения

1. Бинарные отношения и операции над ними

Def. Пусть А₁, А₂, . . . , А_n – некоторые множества. Их прямым или декартовым произведением называется множество упорядоченных наборов из n элементов, т.е.

А₁А₂ . . . А_n = {(а₁, а₂, . . . , а_n) | a_iA_i }.

Если все множества A_i совпадают A = А₁ = А₂ = . . . = А_n, то прямое произведение А₁А₂ . . . А_n = Aⁿ называют прямой n-ой степенью множества А.

Отношением (n-арным отношением) между элементами множеств А₁, А₂, . . . , А_n называется любое подмножество R  А₁А₂ . . . А_n.

Бинарным отношением между элементами множеств А и В называется любое подмножество R  AB. Если множества A и B совпадают А = В, то R называют бинарным отношением на множестве А.

Если (x, y)R, то это обозначают еще xRy и говорят, что между элементами x и y установлено бинарное отношение R.

Примеры бинарных отношений

Пусть A = B = R, пара (x, y) является точкой вещественной плоскости. Тогда бинарное отношение

R_А = { (x, y) | x² + y²  1 }

определяет замкнутый круг единичного радиуса с центром в точке (0, 0) на плоскости, отношение

R_Б = { (x, y) | x  y }

полуплоскость, а отношение

R_В= { (x, y) |  |x – y|  2 }

полосу.

Диагональ множества AA, т.е. множество ={(x,x) | xA}, называется единичным бинарным отношением или отношением равенства в A.

Областью определения бинарного отношения R называется множество _R = { xA |  yB, (x, y) R }– множество первых элементов пар (x, y).

Областью значений бинарного отношения R называется множество _R = { yB |  xA, (x, y)R }– множество вторых элементов пар (x, y).

Как для любых множеств, для бинарных отношений можно определить понятия нестрогого и строгого включения и равенства. Так, например, R₁ содержится в R₂  (R₁ R₂), если любая пара (x, y), которая принадлежит отношению R₁ а также принадлежит и отношению R₂. Например, R_А  R_В, т.к. все точки (x, y), принадлежащие кругу R_А принадлежат также полосе R_в.

Операции над бинарными отношениями определяются подобно операциям над соответствующими множествами. Пусть А – произвольное множество на котором введены бинарные отношения R, R₁, R₂,...

1) Дополнение к отношению ={ (x, y) | (x, y)(AA) \ R}.

2) Объединение двух бинарных отношений R₁ и R₂ – это отношение

R₁  R₂ = { (x, y) | (x, y)R₁ или (x, y)R₂ }.

3) Пересечение двух бинарных отношений R₁ и R₂ – это отношение

R₁  R₂ = { (x, y) | (x, y)R₁ и (x, y)R₂ }.

4) Обратное отношение R ^–1 = { (x, y) | (y, x)R}.

5) Двойственное отношение R^d = .

6) Композиция (суперпозиция) отношений R = R₁oR₂  содержит пару (x, y) тогда и только тогда, когда существует такое zA, что (x, z)R₁ и (z, y)R₂.