1 Конечные и бесконечные множества Конечное множество- множество, состоящее из конечного числа элементов. Бесконечное множество – непустое множество, не являющееся конечным. Пример: Множество натуральных чисел является бесконечным. Упорядоченное множество – множество, каждому элементу которого поставлено в соответствие некоторое число (номер этого элемента) от 1 до n, где n – число элементов множества.

2 Взаимно однозначное соответствие А В (a, b)

3 Мощность множества Мощность множества, кардинальное число множества – характеристика множеств (в том числе бесконечных), обобщающая понятие количества (числа) элементов конечного множества.

4 Множество подмножеств Например, возьмем множество из 2-х элементов: РАЗ, ДВА (и обчелся). Подмножествами этого множества будут 4 множества(!): 1) РАЗ, ДВА - (любое множество подмножество самого себя) 2) РАЗ 3) ДВА 4) пустое - (т.е. "обчелся").

5 Булеан Другой пример: А И Б (сидели на трубе) Подмножествами этого множества из трех элементов будет 8 множеств: 1) А, И, Б 2) А, И 3) А, Б 4) И, Б 5) А 6) И 7) Б 8) пустое

6 Бинарные отношения Бинарным отношением между элементами множеств А и В называется любое подмножество R A B. Если множества A и B совпадают А=В, то R называют бинарным отношением на множестве А. (однородное отношение) Если (x, y) R, то это обозначают еще xRy и говорят, что между элементами x и y установлено бинарное отношение R. n-местным (n-арным) отношением, заданным на множествах M 1, M 2,…, M n, называется подмножество прямого произведения этих множеств. Иногда понятие отношения определяется только для частного случая M=M 1 =M 2 =…=M n.

7 Примеры Отношение a= {(4, 4), (3, 3), (2, 2), (4, 2)} на множестве X = {4, 3, 2} можно определить как свойство "Делится" на этом подмножестве целых чисел. Из школьного курса На множестве целых чисел Z отношения "делится", "делит", "равно", "больше", "меньше", "взаимно просты"; на множестве прямых пространства отношения "параллельны", "взаимно перпендикулярны", "скрещиваются", "пересекаются", "совпадают"; на множестве окружностей плоскости "пересекаются", "касаются", "концентричны".

8 Пример Пусть A=B=R, пара (x, y) является точкой вещественной плоскости. Тогда бинарное отношение R 1 = { (x, y) | x 2 + y 2 1 } определяет замкнутый круг единичного радиуса с центром в точке (0,0) на плоскости, отношение R 2 = { (x, y) | x y } полуплоскость, а отношение R 3 = { (x, y) | |x-y| 1 } полосу.

9 Способы задания Перечисление всех пар из базового множества А и базового множества В A={a 1,a 2 } B={b 1,b 2,b 3 }, ={(a 1, b 1 ), (a 1,b 3 ), (a 2, b 1 )} Отношения могут задаваться формулами: формулы y = x 2 +5x - 6 или x + y < 5 задают бинарные отношения на множестве действительных чисел; формула x + y = любовь, задает бинарное отношение на множестве людей.

10 Графический метод задания a= {(a, d), (a, c), (b, b), (c, a), (e,d), (e, a)}

11 Графовое представление Граф - фигура состоящая из точек (вершин) соединенных линиями (дугами). Вершины графа соответствуют элементам множества А, то есть x i, а наличие дуги, соединяющей вершины x i и x j, означает, что (x i,x j ) R. Чтобы подчеркнуть упорядоченность пары на дуге ставится стрелка. А={(a, b), (a, c), (b, d), (c, e), (e,b), (e, e)}

12 Матричная форма задания Пусть на некотором конечном множестве X задано отношение А. Упорядочим каким-либо образом элементы множества X = {x 1, x 2,..., x n } и определим матрицу отношения A = [a ij ] следующим образом:

13 Определения Диагональ множества A A, т.е. множество ={(x,x) | x A}, называется единичным бинарным отношением или отношением равенства в A. Областью определения бинарного отношения R называется множество R={ x A | y B, (x, y) R }. Областью значений бинарного отношения R называется множество R={ y B | x A, (x, y) R }. Образом множества X относительно отношения R называется множество R(X) = { y B | x X, (x, y) R }; прообразом X относительно R называется R -1(X).

14 Операции над бинарными отношениями Пересечение двух бинарных отношений R 1 и R 2 - это отношение R 1 R 2 = { (x, y) | (x, y) R 1 и (x, y) R 2 }. = > Объединение двух бинарных отношений R 1 и R 2 - это отношение R 1 R 2 = { (x, y) | (x, y) R 1 или (x, y) R 2 }. Разностью отношений R 1 и R 2 называется такое отношение, что: R 1 \R 2 = { (x, y) | (x, y) R 1 и (x, y) R 2 } Дополнение к отношению R={ (x, y) | (x, y) (A A)\R}.

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

16

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

18 Свойства отношений R 1 содержится в R 2 (R 1 R 2 ), если любая пара (x, y), которая принадлежит отношению R 1 также принадлежит и отношению R 2 Рефлексивность xM (xRx) Антирефлексивность xM ¬(xRx)

19 Рефлексивность отношений Обозначим через Ix отношение на множестве X, состоящее из пар вида (a, a), где a X: Ix = {(a, a)| a X}. Отношение Ix обычно называют диагональю множества X или отношением тождества на X. Очевидно, что отношение R на множестве X рефлексивно, если диагональ Ix является подмножеством множества a: Ix R. Отношение антирефлексивно, если диагональ Ix и отношение R не имеют ни одного общего элемента: Ix R = Ø.

20 Свойства отношений Симметричность xRy yRx или R=R -1

21 Свойства отношений Антисимметричность Пусть А - множество людей в данной очереди. Отношение R "не стоять за кем-то в очереди" будет антисимметричным. Пусть х=ВАСЯ, а y=ИВАНОВ. Тот факт, что (x, y) R означает, что "ВАСЯ не стоит в очереди за ИВАНОВЫМ", (y, x) R - "ИВАНОВ не стоит за ВАСЕЙ". Очевидно, что одновременное выполнение обоих включений может быть, только если ВАСЯ и есть ИВАНОВ, т.е. x = y. Отношение " " также антисимметрично: если x y и y x, то x=y. Асимметричность Асимметричность эквивалентна одновременной антирефлексивности и антисимметричности отношения.

22 Свойства отношений Для любого отношения R вводятся понятия симметричной части отношения R s = R R -1 и асимметричной части отношения R a = R \ R s. Если отношение R симметрично, то R= R s, если отношение R асимметрично, то R= R a. Примеры. Если R - " ", то R -1 - " ". Транзитивность отношений

23 Нетранзитивное отношение Отношение R, определенное на некотором множестве и отличающееся тем, что для любых х, у, z этого множества из xRy и yRz не следует xRz. Пример нетранзитивного отношения: «x отец y» Нетранзитивным является отношение " ". Пусть x=2, y=3, z=2, тогда справедливо x y и y z, но x=z, т.е. (x, z) R.

24 Негатранзитивность отношений (x,y) R и (y, z) R (x, z) R В графе негатранзитивного отношения отсутствие дуг от х к у и от у к z приводит к отсутствию дуги от х к z. Отношения R 1 - ">" и R 2 - " " негатранзитивны, так как отношения R 1 доп - " ", R 2 доп - "=" транзитивны. Возможно одновременное выполнение свойств транзитивности и негатранзитивности. Например, отношение R 1 одновременно транзитивно и негатранзитивно, а R 2, как известно, транзитивным не является.

25 Свойства бинарных отношений Полнота (x, y) X либо xRy либо yRx, либо и то и другое одновременно – полносвязное или связное отношение Ацикличность Отношение R называется ацикличным, если из наличия какого-либо пути между вершинами соответствующего графа следует отсутствие обратной дуги (обратного пути) между этими вершинами (в графе отсутствуют любые циклы ). n x 1 Rx 2 x 2 Rx 3 x 3 Rx 4 … x n-1 Rx n но не наоборот.