Основные понятия теории множеств. Алгебра множеств ХНУРЭ, кафедра ПО ЭВМ, Тел. 7021-446, e-mail: belous@kture.Kharkov.ua Лекции 1-2 Н.В. Белоус Факультет. - презентация

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

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

6 Конечные и бесконечные множества Множество называется конечным, если оно содержит конечное число элементов и бесконечным, если оно содержит неограниченное число элементов. Пример Пример. Множество A= цифр в десятичной системе счисления конечно. Множество точек окружности бесконечно. 6

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

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

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

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

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

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

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

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

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

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

31 Операции над множествами Пример Пример. Пусть даны множества: А=; В=. А В= 31

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

33 Операции над множествами Пример Пример. Пусть даны множества: А=; В=. А В = 33

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

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

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

37 Операции над множествами Пример Пример. Пусть даны множества: А=; В=. А \ В = 37 В \ А =

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

39 Приоритет операций в алгебре множеств Пример Пример. Расставить скобки (определить последовательность выполнения операций) в формуле: 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.

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

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

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

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

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

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

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

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

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

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

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

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

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

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