1 Понятие множества Понятие множества является одним из наиболее общих и наиболее важных математических понятий. Множества обозначают прописными латинскими буквами A, B, …, Z, а элементы, принадлежащие данным множествам – строчными a, b, …, z. А = {а,b,с,d}

2 Принадлежность Запись а М означает: элемент a принадлежит множеству М, т. е. элемент a обладает некоторым признаком. Аналогично а М читается: элемент a не принадлежит множеству М.

3 Способы задания множеств Множество задается либо перечислением (указанием) всех его элементов, заключенных в фигурные скобки, например A={1, 3, 5, 7, 9} Множество может быть задано с помощью характеристического свойства его элементов, например А={x| 0

4 Пустое множество Среди множеств выделяют особое множество – пустое множество. Пустое множество, по определению, не содержит элементов; число элементов пустого множества есть нуль. Пустое множество является частью любого множества. Обозначение

5 Универсальное множество Множество, содержащее все элементы, находящиеся в рассмотрении, называется универсумом или универсальным множеством и обозначается как U.

6 Подмножества Множество K называется подмножеством множества M (К М), если для любого x K выполняется x М (т. е. x K влечёт x М ). Необходимо учитывать различие в употреблении знаков включения и принадлежности для множества множеств.

7 Отношения между множествами Множество А называют подмножеством множества В, если каждый элемент множества А является в то же время элементом множества В. А В или В А. Множества А и В равны, если они состоят из одних и тех же элементов. Равенство множеств А и В записывают в виде А=В.

8 Иллюстрации множеств Операции множеств и связанные с ними соотношения представляются наглядно с помощью диаграмм Эйлера-Венна (названных по имени русского математика Леонарда Эйлера ( гг.) и английского логика Джона Венна ( гг.). На этих диаграммах любые множества изображаются кругами, пересекающими друг друга, исходя из того, что внутренними точками круга изображаются элементы множества. Общей частью двух кругов, пересекающих друг друга, представляются возможные общие элементы двух множеств. Универсальное множество изображается в виде прямоугольника.

9 Операции над множествами Пересечение двух множеств А В={x| x A и x B} Объединение двух множеств А В={x| x A или x B} U AB U AB

10 Операции над множествами Разность множеств A\B={x| x A и x B} Симметрическая разность A÷B=АВ={x| x A и x B или x В и x А} U AB U AB

11 Дополнение множества Дополнение множества А Ā=U\A={x| x A} Старшинство операций Дополнение Разность Пересечение Объединение Симметрическая разность Ā A

12 Свойства операций Коммутативность А В = B A Ассоциативность А (В C) = (А В) C

13 Свойства операций Дистрибутивность А (В С) = (А В) (А С) Идемпотентность А А = А

14 Введем обозначения для наиболее часто используемых множеств: N – множество всех натуральных чисел; Z – множество всех целых чисел; Z+ – множество целых неотрицательных чисел (Z+=N {0}); Z– – множество целых неположительных чисел (Z– =Z\N); Q – множество всех рациональных чисел; R – множество всех действительных чисел; R+ – множество неотрицательных действительных чисел; R– – множество неположительных действительных чисел.

15 Декартово произведение Декартовым или прямым произведением двух множеств А и В (обозначается А В) называется множество всех таких упорядоченных пар (a,b), что a A и b В. Пусть, например, А={a,b,c} и B={l, m}. Тогда А В={(a,l), (b,l), (c,l), (a,m), (b,m), (c,m)}.

16 Декартово произведение Декартовым или прямым произведением множеств A 1, A 2,...,A n называется множество {(x 1, x 2,...,x n )|x 1 A 1, x 2 A 2,..., x n A n }, обозначаемое через A 1 ×A 2 ×...×A n. Если A 1 =A 2 =...=A n, то множество A 1 ×A 2...×A n называется n-ой декартовой степенью множества A и обозначается A n. Положим по определению A 0 =. Если хотя бы одно из множеств A i пусто, то A 1 ×A 2...×A n =.

17 Парадокс Рассела Одному деревенскому брадобрею приказали «брить всякого, кто сам не бреется, и не брить того, кто сам бреется». Как он должен поступить с самим собой?

18 Парадокс Тристрама Шенди В романе «Жизнь и мнения Тристрама Шенди, джентльмена» герой обнаруживает, что ему потребовался целый год, чтобы изложить события первого дня его жизни, и еще один год понадобился, чтобы описать второй день. В связи с этим герой сетует, что материал его биографии будет накапливаться быстрее, чем он сможет его обработать, и он никогда не сможет ее завершить. «Теперь я утверждаю, возражает на это Рассел, что если бы он жил вечно и его работа не стала бы ему в тягость, даже если бы его жизнь продолжала быть столь же богатой событиями, как вначале, то ни одна из частей его биографии не осталась бы ненаписанной».

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

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

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

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

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

24 Бинарные отношения Бинарным отношением между элементами множеств А и В называется любое подмножество 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.

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

26 Пример Пусть 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 } полосу.

27 Способы задания Перечисление всех пар из базового множества А и базового множества В 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 = любовь, задает бинарное отношение на множестве людей.

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

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

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

31 Определения Диагональ множества 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).

32 Операции над бинарными отношениями Пересечение двух бинарных отношений 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}.

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

34

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

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

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

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

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

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

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

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

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