Основные понятия теории множеств. Алгебра множеств

1. Основные понятия теории множеств. Алгебра множеств

2. Множество. Элементы множества

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

3. Обозначения

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

4. Обозначения

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

5. Обозначения

Пример.
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

6. Конечные и бесконечные множества

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

7. Способы задания множеств

Перечислением элементов
А = {a1, a2,... , an}.
Пример.
Множество отличников в классе 1а обозначим
Z1а и зададим его перечислением:
Z1а = {Иванов, Петров, Сидоров, Кукушкина}
7

8. Способы задания множеств

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

9. Способы задания множеств

Рекурсивно (порождающей процедурой)
Множество значений рекурсивной функции
является рекурсивно – заданным множеством
F={f1, f2, f3, …}.
f1=1
f2=1
……………………….
fn= 3fn-2+ fn-1, n=3,4,…
Так, f3 = 3f1+f2= 3 1+1=4 , f4=3f2+f3=3 1+4=7 и
т.д.
9

10. Подмножество

10

11. Равенство множеств

Пусть A и B – некоторые множества.
Говорят, что A равно B, если для любого элемента
х имеем: х A тогда и только тогда, когда х В.
Обозначается A=B.
Иначе говоря, A=B тогда и только тогда, когда
A B и B A.
Если множества не равны, это обозначается A B.
Пустое множество есть подмножество любого
множества A, т.е. A.
11

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
12

13. Универсальное множество

13

14. Булеан множества

Множество всех подмножеств множества X
называют булеаном множества X и обозначают
P (X).
Для произвольного множества X из n элементов
его булеан P (X) содержит 2n элементов
(подмножеств X) и иначе обозначается 2Х
Пример.
A={a, b, c}. Тогда его булеан
P(A) = 2A={ ,{a},{b},{c},{a,b},{b,c},{a,c},{a,b,c}}
Булеан пустого множества?
P( )={ }.
14

15. Мощность множества

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

16. Алгебра множеств

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

17. Операции над множествами

Объединение множеств A B есть множество,
которое содержит все элементы, входящие либо
в A, либо в B, либо в A и B одновременно.
A B={x | x A или x B}.
A B
17

18. Операции над множествами

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

19. Операции над множествами

Пересечение
множеств
A B
есть
множество, содержащее только элементы,
входящие в A и B одновременно.
A B={x | x A и x B}.
A B
19

20. Операции над множествами

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

21. Операции над множествами

Разность A\B есть множество, содержащее все
элементы A, не входящие при этом в B.
А\В={x | x A и x B};
Заметим, что А\В В\А
A\B
A\B = A B
Пример. Докажите равенство на кругах Эйлера.
21

22. Операции над множествами

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

23. Симметрическая разность множеств A и B есть множество, содержащие элементы, принадлежащие либо A, либо B, но не A и B

одновременно: A∆B = (А \ В) (В \ А).
А
B

24. Операции над множествами

Пример.
Пусть даны множества:
А={a, b, m};
В={m, n, c, p}.
Тогда
A∆B = {a, b, n, c, p}
24

25. Операции над множествами

Дополнение
множества
A
до
универсального U есть множество Ā (не-А),
состоящее их элементов, принадлежащих U, но
не пренадлежащих A, т.е. Ā = U \ A.
A= {x | x U и x A}.
Очевидно, что A Ā = U.
25

26. Операции над множествами

26

27. Законы алгебры множеств

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

28. Законы алгебры множеств

4. Свойства пустого и универсального множеств
A A
A U U
A U A
A
28

29. Законы алгебры множеств

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

30. Законы алгебры множеств

9. Закон поглощения
A (A B)=A
A (A B)=A
10. Законы де Моргана.
A B A B
A B A B
30

31. Декартово произведение

Пусть А и В два непустых множества.
Определение. Прямым (или декартовым)
произведением двух множеств А и В называется
множество всех упорядоченных пар, в котором
первый элемент пары принадлежит А, второй принадлежит В:
A×В = {(а, b)| а ∈ A, b ∈ В }.
Пример. Пусть A={1, 2, 3}, В = {r, s}. Найти A×В и В×A.
A×В = {(1, r), (1, s), (2, r), (2, s), (3, r), (3, s)}.
В×A = {(r ,1) (r, 2), (r, 3), (s, 1), (s, 2), (s, 3)}.
31

32. Декартово произведение

32

33. Задачи

1.1. На рисунке 1 изображены множества A, B и C , а также универсальное множество U .
Рис. 1
Построить следующие множества:
1) M ( A ∩ B) ∪ C;
2) K ( A ∩ B) \ C;
3) T A \ (B ∪ C);
4) D (C ∪ B) \ ( A B).
33

34. Задачи

1.1. Пусть A 1, 2, 3, 4, 5, 6, 7 , B 4, 5, 6, 7, 8, 9,10 , C 2, 4, 6, 8,10 , а
U 1, 2, 3, 4, 5, 6, 7, 8, 9,10 . Определить следующие множества:
1) A ∪ C ;
4) A B ;
2) A ∩ B ;
5) ( A ∩ B) ∪ C ;
3) A \ C ;
6) ( A ∪ C) \ B .
1.1. Доказать, что для произвольных множеств A, B, C и универсального
множества U справедливы следующие равенства:
1) A ∩ (B ∪ C) ( A ∩ B) ∪ ( A ∩ C) ;
2) A ∪ B A ∩ B ;
3) A \ ( A \ B) A ∩ B;
4) A \ (B ∪ C) ( A ∩