Основные понятия теории множеств. Алгебра множеств ХНУРЭ, кафедра ПО ЭВМ, Тел , Лекции 1-2 Н.В. Белоус Факультет компьютерных наук Кафедра ПО ЭВМ, ХНУРЭ Компьютерная дискретная математика

Множество. Элементы множества Множество – это некоторая совокупность элементов, идей, понятий. Элементы множества – это объекты, которые образуют данное множество, могут обладать некоторыми свойствами и находиться в некоторых отношениях между собой или с элементами других множеств. 2

Обозначения Множества обозначают заглавными, а элементы множеств – строчными латинскими буквами или строчными латинскими буквами с индексами. Запись А={a,b,d,h} означает, что множество А состоит из четырех элементов a, b, d, h. Утверждение, что конечное множество A состоит из n элементов, записывается так: A={a 1,a 2,...,a n }. 3

Обозначения Принадлежность элемента множеству обозначается символом : a A (читают: элемент а принадлежит множеству А). В противном случае обозначают a A (читают: элемент а не принадлежит множеству А). Элементами множеств могут быть другие множества, тогда эти элементы могут обозначаться заглавными буквами. 4

Обозначения Пример Пример. A = {D,C}, D={a, b}, C={c, d, e}. При этом D A, C A, но a A и с A. Пример Пример. A = {{x,y},z}. Эта запись означает, что множество A содержит два элемента: множество {x,y} и элемент z. 5

Конечные и бесконечные множества Множество называется конечным, если оно содержит конечное число элементов и бесконечным, если оно содержит неограниченное число элементов. Пример Пример. Множество A={1,2,3,4,5,6,7,8,9,0} цифр в десятичной системе счисления конечно. Множество точек окружности бесконечно. 6

Упорядоченные множества Упорядоченным считается такое множество, в котором важен порядок следования элементов. Например, упорядоченным является множество, в котором каждый элемент имеет свой порядковый номер. Обозначают упорядоченное множество, как правило, либо круглыми, либо треугольными скобками. A=, в общем случае: A=, n N; В=(а,b,с). 7

Способы задания множеств Перечислением элементов А = {a 1, a 2,..., a n }. Пример Пример. Множество отличников в классе 1а обозначим Z 1а и зададим его перечислением: Z 1а = {Иванов, Петров, Сидоров, Кукушкина} 8

Способы задания множеств Определяющим свойством Множество Х = {х | Р(x)}, где Р(х) означает, что элемент х обладает свойством P(x). Пример Пример. Множество N 10 всех натуральных чисел, меньших 10 можно задать так: N 10 ={x | x N, x

Способы задания множеств Рекурсивно Множество значений рекурсивной функции является рекурсивно – заданным множеством F={f 1, f 2, f 3, …}. f 1 =1 f 2 =1 ………………………. f n = 3f n-2 + f n-1, n=3,4,… Так, f 3 = 3f 1 +f 2 = 3 1+1=4, f 4 =3f 2 +f 3 =3 1+4=7 и т.д. 10

Подмножество Множество А, все элементы которого принадлежат множеству В, называется подмножеством множества В. Обозначение: A B; A B. Пример Пример. A – множество действительных чисел; B – множество натуральных чисел. Множество В является подмножеством множества А. 11

Равенство множеств Неупорядоченные множества равны, если они содержат одинаковый набор элементов. Обозначается A=B. Если множества не равны, это обозначается A B. 12

Равенство множеств. Двухстороннее включение А=В тогда и только тогда, когда из условия x A следует x B и из условия y B следует y A. Пример Пример. Пусть заданы множества A = {1,2,3,4,5}; B – множество натуральных чисел от 1 до 5; С = {c | 1 c 5, c N}; D = {4,1,5,2,3}. Эти множества содержат один набор элементов, поэтому A=B=C=D 13

Равенство множеств Пример Пример. Пусть заданы множества: A={Иванов, Петров, Сидоров}; B={Иванов, Петров, Сидоров}. A=B, если речь идет об одних и тех же людях. В противном случае A B. 14

Равенство множеств Пример Пример. Пусть A - множество остатков, получаемых при последовательном делении натуральных чисел {3, 4, 5, 6,…} на 3: A={0, 1, 2, 0, 1, 2, 0, 1, 2, 0, …}. Это множество содержит всего три элемента: 0, 1, 2. Поэтому его можно записать в виде A={0, 1, 2}. 15

Мощность множества Число элементов в конечном множестве М называется мощностью М и обозначается |M|. Пример Пример. Пусть задано множество A={x| 5 x 10, x N}, тогда |A|= Пример Пример. B – множество всех видов шахматных фигур, С – множество всех шахматных фигур, участвующих в одной игре. |B|= 6 (пешка, ладья, слон, конь, ферзь, король) |С|= 32 (16 белых и 16 черных).

Строгое и нестрогое включение Нестрогое включение обозначается А В, означает, что А – подмножество множества В, возможно совпадающее с В. Строгое включение обозначается А В, и означает, что А – подмножество множества В, не совпадающее с B. А В читается А включено в В. 17

Строгое и нестрогое включение. Равенство множеств Выполнение соотношений А В и В А возможно только при А = В. А = В, если А В и B А. Эти соотношения являются признаком равенства множеств через отношение включения. Иногда в литературе символом обозначают "нестрогое" включение, допускающее и равенство множеств. В этом случае символ не используется, а строгое включение записывают двумя соотношениями A B, A B. 18

Строгое и нестрогое включение Пример Пример. X – множество студентов группы КН-05-7, Y – множество отличников в группе КН Тогда Y X, Z – множество студентов потока КН-05-7,8,9,10. Тогда X Z. Включение X в Z строгое, поскольку кроме учеников класса Х, в школе обязательно присутствуют ученики других классов. 19

Универсальное множество Универсальным называется множество, содержащее все возможные элементы, встречающиеся в данной задаче. Универсальное множество обозначается символом U. Универсальное множество U может отличаться для каждой отдельной задачи и определяется условием задачи. 20

Пустое множество Пустым называется такое множество, которое не содержит никаких элементов. Пустое множество обозначается специальным символом. Пустое множество является подмножеством любого множества, т.е. А, где А – любое множество. 21

Пустое множество Пустое множество – это множество, поэтому, если некоторое множество A не содержит ни одного элемента, то A= ; |A|=0. Запись A={ } означает, что A содержит один элемент –, |A|=1. 22

Множество-степень (булеан) Множество всех подмножеств множества X назовем множеством-степенью X или булеаном и обозначим P (X). Для произвольного множества X из n элементов его множество-степень P (X) содержит 2 n элементов: P (X) = 2 X =2 X = 2 n Пример Пример. A={a, b, c}. 2 A ={,{a},{b},{c},{a,b},{b,c},{a,c},{a,b,c}} Пустое множество имеет только одно подмножество – само пустое множество, поэтому P ( )={ }. 23

Геометрическая интерпретация множеств : диаграммы Венна Построение диаграммы Венна заключается в разбиении плоскости на 2 n ячеек с помощью n замкнутых фигур (где n – число изображаемых множеств). Каждая фигура на диаграмме представляет отдельное из 2 n подмножеств множество. 24

Диаграммы Венна для двух множеств Диаграмма Венна для двух множеств A и B выглядит следующим образом. 25 Демонстрация

Диаграммы Венна для трех множеств Диаграмма Венна для трех множеств A, B и C выглядит следующим образом. 26 Демонстрация

Диаграммы Венна для четырех множеств Диаграмму Венна для четырех множеств A, B, C и D можно изобразить следующим образом. 27 Демонстрация

Круги Эйлера Индивидуальные отношения между заданными множествами изображают с помощью кругов Эйлера. 28 А = {1, 4, 6}; В = {1, 5, 8}; Общий элемент – 1 A B А = {1, 4, 6}; В = {1, 6}; B A А = {1, 4, 6}; С = {3, 5, 8}; Нет общих элементов A и B. A B

Алгебра множеств Множество 2 U всех подмножеств универсального множества U, с заданными на нем четырьмя операциями, составляют алгебру множеств. 29

Операции над множествами Объединение (сумма) A B есть множество, которое содержит все элементы, входящие либо в A, либо в B, либо в A и B одновременно. A B={x | x A или x B}. 30 Демонстрация A B

Операции над множествами Пример Пример. Пусть даны множества: А={a, b, m}; В={m, n, c, p}. А В= 31 {a, b, c, m, n, p}

Операции над множествами Пересечение (произведение) A B есть множество, содержащее только элементы, входящие в A и B одновременно. A B={x | x A и x B}. 32 Демонстрация A B

Операции над множествами Пример Пример. Пусть даны множества: А={a, b, m}; В={m, n, c, p}. А В = 33 {m}{m}

Операции над множествами Дополнение (отрицание) Ā (читается не А) есть множество U\A. 34 Демонстрация = {x | x A}.

Операции над множествами Пример Пример. Z = {…,-2,-1,0,1,2,…}. В этой задаче U=Z. Пусть Z - – множество отрицательных чисел и 0, тогда Z - = {… -2, -1, 0}. Дополнением к множеству Z - будет множество натуральных чисел N={1,2,…}. 35

Операции над множествами Разность A\B есть множество, содержащее все элементы A, не входящие в B. А\В В\А 36 Демонстрация A\B A\B = A B А\В={x|x A,x B};

Операции над множествами Пример Пример. Пусть даны множества: А={a, b, m}; В={m, n, c, p}. А \ В = 37 {a,b} В \ А = {n,c,p}

Приоритет операций в алгебре множеств Приоритет операций в алгебре множеств следующий. 1. A 2. A B 3. A B 4. A\B 38

Приоритет операций в алгебре множеств Пример Пример. Расставить скобки (определить последовательность выполнения операций) в формуле: E=A\B A D\B 39 E=A\B ( A) D\B.E=A\B (( A) D)\B.E=A\(B (( A) D))\B. E=(A\(B (( A) D)))\B.

Законы алгебры множеств 1. Коммутативные законы A B=B A 2. Ассоциативные законы A (B C)=(A B) C 3. Дистрибутивные законы A (B C)=(A B) (A C) 40

Законы алгебры множеств 4. Свойства пустого и универсального множеств 41

Законы алгебры множеств 5. Законы идемпотентности A A=A 6. Закон инволюции (двойного отрицания) 7. Закон противоречия 8. Закон исключенного третьего 42

Законы алгебры множеств 9. Закон элиминации (поглощения) A (A B)=A 10. Законы де Моргана. 43

Законы алгебры множеств Пример Пример. Доказать с помощью диаграмм Венна дистрибутивный закон. А (В С)=(А В) (А С). 44

Законы алгебры множеств Продолжение примера Продолжение примера. 45 A B C U В С A B C U А (В С) A B C U A B C U

Законы алгебры множеств Продолжение примера Продолжение примера. 46 A B C U A B C U A B C U (А В) Демонстрация (А С) (А В) (А С) A B C U A B C U A B C U

Законы алгебры множеств Пример Пример. Записать формулу, соответствующую заштрихо- ванной части диаграммы Венна 47 AB U C A B U C A B U C (А В) В результате получили формулу (А В)\С

Законы алгебры множеств Пример Пример. Упростить выражение 48 Ответ:

Бесконечные множества. Взаимно-однозначное соответствие. Взаимно-однозначным называется такое соответствие между множествами A и B, при котором каждому элементу a A отвечает один и только один элемент b B и каждому элементу b B отвечает один и только один элемент a A. Функция, определяющая взаимно-однозначное соответствие называется биективной функцией или биекцией. 49

Бесконечные множества. Эквивалентные множества. Множества A и B называются эквивалентными (A B), если между ними существует биекция (хотя бы одна). Эквивалентные множества называют равномощными, что обозначается так: |A| = |B|. Эквивалентными друг другу оказываются все конечные множества с одинаковым числом элементов n (мощность каждого из этих множеств равна n). 50

Бесконечные множества. Счетные множества Множество A называется счетным, если оно эквивалентно натуральному ряду N (A N). С помощью биекции =N A можно пересчитать все элементы из A, снабдив их индексами. Можно записать, что A = {a n }, n=1,2,…,. 51

Бесконечные множества. Счетные множества Множество четных натуральных чисел N ч ={2,4,…,m,…}, всех натуральных чисел N={1,2,…,n, …}, целых чисел Z и рациональных чисел Q последовательно вложены: N ч N Z Q. Хотя для любых двух из этих множеств нет равенства, они эквивалентны друг другу, то есть, имеют одинаковую мощность и являются счетными: |N ч | = |N| = |Z| = |Q|. 52

Бесконечные множества. Несчетные, континуальные множества Существуют бесконечные несчетные множества, и их мощность естественно считать большей, чем |N|. Множество точек отрезка [0, 1] = {x R; 0 x 1} не является счетным (теорема Г. Кантора). Его мощность называется континуум и обозначается малой буквой c: |[0, 1]|=c. Множество [0, 1] и любое эквивалентное ему множество называются континуальными. 53

Бесконечные множества. Континуальные множества На вещественной оси R континуальными (и значит эквивалентными друг другу и отрезку [0, 1]) являются, например, множества: [a,b], (a, b), при любом a

Примеры Пример автоматического построения диаграммы Венна по вводимой формуле Пример построения формулы алгебры множеств по диаграмме Венна Пример построения диаграммы Венна по заданной формуле 55