- •Раздел II. БИнарные отношения и алгебраические структуры
- •Тема 4. Бинарные отношения
- •1. Бинарные отношения и операции над ними
- •2. Свойства операций над отношениями
- •3. Способы задания отношений
- •4. Применение отношений в информационных технологиях
- •5. Свойства бинарных отношений
- •Тема 5. Специальные бинарные отношения.
- •1. Упорядочение и безразличие
- •2. Слабый порядок
- •3. Разбиение и эквивалентность
- •4. Качественный порядок
- •Тема 6. Нечеткие отношения
- •Операции над нечеткими отношениями
Раздел II. БИнарные отношения и алгебраические структуры
Литература
Новиков, Ф.А, Дискретная математика для программистов. – Санкт-Петербург: Питер, 2007. – 304 с.
Белоусов, А.И. Дискретная математика. – М.: МГТУ им. Баумана, 2009.
Кузнецов, О.П. Дискретная математика для инженеров: [учебник для вузов] (гриф Пр. — 5-е изд., стер. — СПб. : Лань, 2007.— 400 с.
Яблонский, С.В. Введение в дискретную математику: Учебное пособие для Вузов/ Под ред. В.А. Садовничего – 3-е изд. стер. – М.: Высш. шк., 2006. – 384 с.
Гаврилов А.И., Сапоженко С.В. Задачи и упражнения по курсу дискретной математики. - М.: Наука, 1992. - 408 с.
Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математической логике и теории алгоритмов. - М.: Наука, 1984. - 223 с.
Колмогоров А.Н., Фомин С.В. Элементы теории функций и функционального анализа. - М.: Наука, 1981. - 544 с.
Юдин Д. Б. Вычислительные методы теории принятия решений [Текст] / М.: Наука, 1989. 320 с.
Тема 4. Бинарные отношения
1. Бинарные отношения и операции над ними
Def. Пусть А1, А2, . . . , Аn – некоторые множества. Их прямым или декартовым произведением называется множество упорядоченных наборов из n элементов, т.е.
А1А2 . . . Аn = {(а1, а2, . . . , аn) | aiAi }.
Если все множества Ai совпадают A = А1 = А2 = . . . = Аn, то прямое произведение А1А2 . . . Аn = An называют прямой n-ой степенью множества А.
Отношением (n-арным отношением) между элементами множеств А1, А2, . . . , Аn называется любое подмножество R А1А2 . . . Аn.
Бинарным отношением между элементами множеств А и В называется любое подмножество R AB. Если множества A и B совпадают А = В, то R называют бинарным отношением на множестве А.
Если (x, y)R, то это обозначают еще xRy и говорят, что между элементами x и y установлено бинарное отношение R.
Примеры бинарных отношений
Пусть A = B = R, пара (x, y) является точкой вещественной плоскости. Тогда бинарное отношение
RА = { (x, y) | x2 + y2 1 }
определяет замкнутый круг единичного радиуса с центром в точке (0, 0) на плоскости, отношение
RБ = { (x, y) | x y }
полуплоскость, а отношение
RВ= { (x, y) | |x – y| 2 }
полосу.
Диагональ множества AA, т.е. множество ={(x,x) | xA}, называется единичным бинарным отношением или отношением равенства в A.
Областью определения бинарного отношения R называется множество R = { xA | yB, (x, y) R }– множество первых элементов пар (x, y).
Областью значений бинарного отношения R называется множество R = { yB | xA, (x, y)R }– множество вторых элементов пар (x, y).
Как для любых множеств, для бинарных отношений можно определить понятия нестрогого и строгого включения и равенства. Так, например, R1 содержится в R2 (R1 R2), если любая пара (x, y), которая принадлежит отношению R1 а также принадлежит и отношению R2. Например, RА RВ, т.к. все точки (x, y), принадлежащие кругу RА принадлежат также полосе Rв.
Операции над бинарными отношениями определяются подобно операциям над соответствующими множествами. Пусть А – произвольное множество на котором введены бинарные отношения R, R1, R2,...
1) Дополнение к отношению ={ (x, y) | (x, y)(AA) \ R}.
2) Объединение двух бинарных отношений R1 и R2 – это отношение
R1 R2 = { (x, y) | (x, y)R1 или (x, y)R2 }.
3) Пересечение двух бинарных отношений R1 и R2 – это отношение
R1 R2 = { (x, y) | (x, y)R1 и (x, y)R2 }.
4) Обратное отношение R –1 = { (x, y) | (y, x)R}.
5) Двойственное отношение Rd = .
6) Композиция (суперпозиция) отношений R = R1oR2 содержит пару (x, y) тогда и только тогда, когда существует такое zA, что (x, z)R1 и (z, y)R2.