Компьютерная дискретная математика: теория множеств

1. Предмет «Компьютерная дискретная математика» лектор Григорьев Александр Владимирович доцент кафедры «Программная инженерия»

2.

Курс КДМ посвящен новой,
неклассической математике, на
которой строится искусственный
интеллект, компьютеры и вообще
все программирование.
Является базовым курсом.

3.

Темы курса:
1. Способы задания множеств.
Операции над множествами. Основные
соотношения алгебры множеств.
2. Отношения на множествах.
3. Основные понятия комбинаторики.
4. Булевы функции. Законы алгебры
логики. Аналитические способы описания.
Полные системы функций.
5. Методы минимизации функций
алгебры логики.
6. Исчисление высказываний.
7. Исчисление предикатов.

4. Тема 1: ТЕОРИЯ МНОЖЕСТВ 1. Основные определения

Множество
–
совокупность
определенных и различимых между
собой объектов.
Множество A состоит из объектов: a1 ,a 2 ,...,a n
A a1 , a2 ,...,an .
Объекты аi называются
множества А.
элементами

5.

Множество, состоящее из конечного
числа элементов, называется
конечным, а множество, состоящее из
бесконечного числа элементов бесконечным.

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

Имеются два способа задания множеств:
Перечисление элементов.
А = {-10,1,3,5,6,889}
Задание определяющего свойства.
X = { x | 1 ≤ х ≤ 5, x є N };
А = {a2 | a - четное число}.

7.

Число элементов конечного множества –
мощность, норма, кардинальное число:
|А|.
Пустое множество – множество, не
содержащее ни одного элемента.
Пустое множество обозначается или {}.

8.

Универсальное
множество – множество
всех, всевозможных, рассматриваемых в
данном
классе
задач
элементов.
Универсальное множество обозначается
как U.
Примеры U:
- Буквы русского алфавита (элементы слов, как
множеств букв);
- Цифры от 0 до 9 (элементы целых чисел, как
множеств цифр);
- …….

9.

Утверждение
"а является элементом
множества А" записывается в виде
а А (а принадлежит множеству А).
Утверждение
"а
не
является
элементом
множества
А"
записывается в виде а А
(а не
принадлежит множеству А).

10. 3. Отношения на множествах

Множества А и В называются равными
или тождественно равными, тогда и
только тогда, когда они состоят из одних
и тех же элементов (обозначается А = В
или А ≡ В).
Множества А и В называются равными
или тождественно равными, тогда и
только тогда, когда каждый элемент
множества А есть элемент множества В и
наоборот, иначе множества не равны
(А ≠ В).

11.

Если же каждый элемент множества А
является также элементом множества В,
то говорят, что А содержится или
включается
в
В,
А В (нестрогое включение).
Множество
A
–
подмножество
множества B, если A B.

12.

В
тех случаях, когда одновременно
имеют место соотношения
A B и A B,
говорят, что A строго включается в B,
в этом случае пишут A B.
Символ
строгого включения ставится
тогда, когда необходимо подчеркнуть,
что, в множестве В содержатся не
только элементы множества А.

13.

Пример.
Пусть имеются буквенные множества.
A={a,b,c,d} B={b,c} C={c,d,a,b}
Отношения между множествами:
A=C (множества А и С являются равными
или тождественно равными)
A C (множество A – подмножество
множества С).
B A (множество B строго включается в A).

14.

4. Свойства подмножеств
1) Пустое множество Ø является
подмножеством любого множества:
Ø А.
2) Само множество является своим
подмножеством: А А.
3)
Любое
множество
является
подмножеством
соответствующего
универсального множества U : A U.

15.

4) Для любого множества А его
подмножествами
всегда
являются
пустое множество
и само
множество А.

16. 5. Графическое представление множеств

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

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

Объединение множеств A и B
(обозначается A B) – множество,
состоящее из всех элементов,
принадлежащих хотя бы одному из этих
U
множеств,
A B = а а A или а B .
A B

18.

Пересечение множеств A и B
(обозначается А ∩ B) – множество,
состоящее из всех элементов,
принадлежащих каждому из этих
множеств, т.е.
А ∩ B = а а А и а B .
U
A B

19.

Разность
множеств
А и B
(обозначается А \ B) – множество,
состоящее
из
всех
элементов
множества A, не принадлежащих
множеству B, т.е.
А \ B = а а А и а B .
U
A\B

20.

Дополнение
множества
А
в
универсальном
множестве
U
(обозначается A )
– множество,
состоящее
из
всех
элементов
универсального множества U, не
принадлежащих множеству А, т.е.
A = U \ A.
U
A
A

21.

Симметрическая разность множеств A
и B (A B или A B) – множество, состоящее
из всех элементов, принадлежащих в
точности одному из этих множеств, т.е.
A B а либо а A и а B, либо а A и а B ;
A B = (A \ B) (B \ A) = (A B) \ (A B).
U
A
B
A B

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

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

23. Основные законы алгебры множеств

1)Коммутативные
законы
(переместительные)
А В=В А
А В=В А
А В=В А
Ассоциативные
законы
2)
(сочетательные)
А (В С) = (А В) С
А (В С) = (А В) С

24.

3) Дистрибутивные
(распределительные) законы
А (В С) = (А В) (А С)
А (В С) = (А В) (А С)
4) Законы с и U
U
U
А =А
А =
А U=А
А U=U
A A U
A A

25.

5) Законы идемпотентности
А А=А
А А=А
6) Законы поглощения
А (А В) = А
А (А В) = А
7) Законы де Моргана
A B A B
A B A B
8) Законы склеивания
(A B) ( A B) B
(A B) ( A B) B
A A

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

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

27.

Наивысший приоритет имеют операции
дополнения – они выполняются в
первую очередь.
Затем выполняются операции
пересечения.
Затем выполняются операции
объединения, разности и
симметрической разности, которые
имеют одинаковый приоритет.
Последовательность выполнения операций может быть изменена скобками.

28. Примеры числовых множеств

29. 8. Понятие «булеан» для множеств

Рассмотрим
конечное множество
содержащее n элементов:
А,
A a1 , a2 ,...,an ,
Множество
всех,
всевозможных
подмножеств конечного множества А
(включая пустое множество и само
множество А) называют булеаном
и
обозначают Ρ(А).

30. Теорема о мощности булеана

Для любого множества А, состоящего
из n элементов существует
различных подмножеств, т.е.
мощность булеана равна:
2
n
P( A ) 2 .
n
Если два множества равномощны,
то равномощны и их булеаны.

31. Пример 1:

Пусть дано множество
A a , b .
Найти булеан множества А.
Р( A ) , a , b , a , b .
Множество А имеет мощность =2.
Мощность булеана Р(А) = 2*2=4.
n
P( A ) 2 .

32.

Пример 2:
Рассмотрим алфавит русского языка.
Его булеан - это все его возможные
подмножества, включая пустое
множество и сам алфавит
(гласные, согласные, шипящие …).

33.

Понятие булеана позволяет
перейти к классификации
множества подмножеств любого
множества А.
Можно ввести понятия разбиения
и покрытия множества А.
Это подмножества булеана,
обладающие своими
специфическими свойствами.

34. 9. Разбиения и покрытия множества

Покрытием непустого множества
A называется совокупность
подмножеств ( A ) { A1 , A 2 ,..., A n }
n
таких, что: A i A , n N,
i 1
i 1, n A i ,
i 1, n A i A.

35.

Т.е., Покрытием множества A
называется семейство непустых
подмножеств этого множества,
объединение которых совпадает с A.
При этом подмножества могут
пересекаться.

36.

Разбиением
непустого множества A
называется совокупность
подмножеств ( A ) { A1 , A 2 ,..., A n }
n
таких, что: A i A, n N
i 1
i 1, n A i ,
i 1, n A i A,
i, j 1, n, i j, A i A j .

37.

Т.е., разбиением множества A
называется семейство непустых,
попарно непересекающихся
подмножеств, объединение
которых совпадает с A.
Разбиение есть частный случай
покрытия.

38. Например

Пусть A N 4 {1, 2, 3,4}
( A) { {1}, {1,2}, {1,2,3,4} }
( A) { {1}, {2}, {3,4} }
( A) { {1,2}, {3,4} }

39.

Пример 1. Пусть задано
множество A студентов, учащихся в
одной группе.
Следующие семейства
множеств являются покрытием
множества A, поскольку могут
пересекаться между собой:

40.

– «студенты, родившиеся с 1
января по 31 июня», «студенты,
родившиеся с 1 апреля по 1
октября», «студенты, родившиеся с
1 сентября по 31 декабря»;
– «студенты, имеющие в зачетке
хотя бы одну тройку», «студенты,
имеющие в зачетке хотя бы одну
четверку», «студенты, имеющие в
зачетке хотя бы одну пятерку»;

41.

Следующие семейства множеств
являются разбиением множества A,
поскольку не могут пересекаться между
собой:
– «студенты мужского пола» и
«студенты женского пола»;
– «отличники», «хорошисты»,
«троечники»;
– «студенты, родившиеся зимой»,
«студенты, родившиеся весной»,
«студенты, родившиеся летом»,
«студенты, родившиеся осенью».