Лекция 1. Теория множеств

Лекция 1. Теория множеств

2008 г.

Дискретная математика. Математическая логика

Мифи

Иоп

Проф., д.т.н. Гусева А.И. , доцент Порешин П.П., аспирант Цыплаков А.C.

Понятие множества

Множество – совокупность объектов, хорошо различимых нашей интуицией или мыслью, обладающих неким сходством и объединенных в одно общее

Элемент a принадлежит множеству A, в противном случае

.

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

Количество элементов в множестве называется мощностью, или кардинальным числом Мощность множества M={a,b,c} ?M?=3 Множества конечные и бесконечные Пустое множество Мощность пустого множества равна 0

Равномощность множеств

Множества равномощны, если их мощности равны Множества D= {{синий, красный зеленый}, {шар, куб, цилиндр, пирамида}} и К={a,b} равномощны

Множества конечные и бесконечные

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

Множества счетные и несчетные

Множество счетно, если оно состоит из конечного числа элементов, т.е. его кардинальное число совпадает с одним из натуральных чисел Множество счетно-бесконечно, если оно равномощно множеству натуральных чисел Множество несчетное, если оно бесконечно и неравномощно множеству натуральных чисел

Подмножества и собственные подмножества

Множество A называется подмножеством B, если каждый элемент из A, , принадлежит одновременно и множеству B, , Если в множестве B найдется хотя бы один элемент , который не принадлежит A , то A собственное подмножество B, Пустое множество всегда является подмножеством любого множества А

Равные множества

Множества A и B равны, если являются подмножествами (надмножествами) друг друга

Универсум и булеан

Для каждого множества М можно построить новое множество, элементами которого являются все подмножества М и только они Тогда множество М называют универсумом I, а множество всех его подмножеств – булеаном Если мощность универсума равна m, то мощность его булеана всегда равна

Пример

Возьмем в качестве универсума I множество натуральных чисел на отрезке [1, 3], I={1, 2, 3}, тогда булеан B(I)={ ,{1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}

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

Перечислить элементы множества, M= {1, 2, 3, 4, 5} Использовать характеристический предикат M= {x / x N и x<6} С помощью производящей функции M= {x / for I:=1 to 5 do x:= i}

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

Декартовым произведением двух множеств А и В является новое множество С, элементами которого являются все пары (a,b), Порядок в паре очень важен, в общем виде

Операции над множествами (1)

Объединением двух множеств А и В называется новое множество С, элементы которого удовлетворяют следующему условию: Пересечением двух множеств А и В называется новое множество С, элементы которого удовлетворяют следующему условию:

Операции над множествами (1)

Дополнением множества А называется новое множество С, элементы которого удовлетворяют следующему условию:

Операции над множествами (2)

Разностью двух множеств А и В называется новое множество С, элементы которого удовлетворяют следующему условию: Симметрической разностью двух множеств А и В называется новое множество С, элементы которого удовлетворяют следующему условию:

Диаграммы Эйлера-Венна

А)

Б)

В)

Г)

Д)

Свойства операций над множествами (1)

Идемпотентность Коммутативность Ассоциативность

Свойства операций над множествами (2)

Дистрибутивность Поглощение