ДИСКРЕТНАЯ МАТЕМАТИКА
1 семестр:
Раздел 1. Множества. Отношения. Графы. Раздел 2. Математическая логика.
2 семестр:
Раздел 3. Алгоритмы на графах.
Раздел 1. Множества. Отношения. Графы.
Тема 1. Множества и их спецификации
1.1. Множества
1.1.1. Понятие множества
Немецкий математик Гео́рг Ка́нтор
нем. Georg Ferdinand Ludwig Philipp Cantor
3 марта 1845, Санкт-Петербург — 6 января 1918, Галле (Заале)
«Множество – это объединение в одно целое объектов, хорошо различимых
нашей интуицией или мыслью».
Множество – совокупность элементов, обладающих двумя свойствами:
1)все элементы различны;
2)относительно каждого элемента можно сказать, принадлежит или не принадлежит он этому множеству.
Запись a A означает, что элемент а принадлежит множеству А,
запись a A означает, что элемент а не принадлежит множеству А.
Множества, состоящие из конечного числа элементов, называются конечными.
Множества, состоящие из бесконечного числа элементов, называются
бесконечными.
Число элементов в конечном множестве А называется мощностью множества А и обозначается |А|.
Множества могут быть заданы перечислением своих элементов. Список обычно
заключается в фигурные скобки.
Пример.
1.Конечное множество А = {2, 4, 6, 8} в качестве элементов содержит натуральные четные числа 2, 4, 6, 8. В этом случае можно записать, что 2 А, но 3 А. Кроме того, мощность множества |А| = 4.
2.Бесконечное множество В = {1, 8, 27, …, т3, …} содержит кубы всех натуральных чисел. При этом 27 В, но 30 В.
Также множества могут быть заданы с помощью характеристического свойства
его элементов: А = {x | x обладает свойством P}. Способ задания множества должен быть адекватен, т.е. полностью определять множество.
Характеристическое свойство может представлять собой формулу.
Пример.
1.Множество А = {х | х=2п+1, n N, n 10} содержит конечное число элементов: 3, 5, 7, 9, 11, 13, 15, 17, 19.
2.Множество В = {х | x 32 n, n Z } содержит бесконечное число элементов: , 2 , 2 ,32 ,52 , 72 ,
Множество А есть подмножество множества В (обозначается A B), если
каждый элемент множества А есть элемент множества В; т.е. если x A, то x B.
В частности, каждое множество есть подмножество самого себя.
Если А не является подмножеством множества В, это записывается как A B; т.е. если существует элемент x A, такой, что x B.
Пример.
1.Очевидно, что {a, c, d} {a, b, c, d, e}, но {a, c, k} {a, b, c, d, e}.
2.Пусть А = {х | х – победитель олимпиады по математики среди студентов 1 и 2 курсов данного университета}, В = {y | y – участник олимпиад, проводимых среди студентов 1 и 2 курсов данного университета}, С = {t | t – участник
ежегодной студенческой конференции данного университета}. Тогда А В, но
С В.
Множества равны, если они содержат одни и те же элементы.
Пример.
Если множество А = {1, 3, 5}, а множество В = {x | х – все положительные натуральные нечетные числа не больше 5}, то множества А и В являются равными.
Пусть А и В – некоторые множества. Говорят, что множество А равно множеству В (А = В), если для любого элемента х имеем: x A x B. Иначе говоря, A B A Bи B A.
Если A B и A B, то записывают A B и говорят, что множество А есть
собственное подмножество множества В.
В теории множеств введены два противоположных друг другу понятия.
Множество, не содержащее элементов, называется пустым множеством и обозначается или {}.
При этом мощность | | = 0.
Пустое множество есть подмножество любого данного множества А, поскольку каждый элемент пустого множества содержится в А. Можно сказать, что не существует элементов пустого множества, которые не принадлежали бы множеству А.
Если все рассматриваемые в данной задаче множества являются подмножествами некоторого множества U, то такое множество U называется
универсальным множеством.
Множество-степень – множество всех подмножеств множества А.
Обозначение: Р(А).
Если | A | n, то | P(A) | 2n.
Пример.
Пусть A {a,b}.
Тогда P(A) { , {a}, {b}, {a,b}}. При этом | A | 2, | P(A) | 22 4.