Множества. Операции над множествами.
Множество - это совокупность объектов, рассматриваемая как одно целое. Объекты, составляющие данное множество, называются его элементами. Два множества A и B называются равными, если они состоят из одних и тех же элементов, т. е. если каждый элемент множества A принадлежит B и, обратно, каждый элемент B принадлежит A. Тогда пишут A = B. Если каждый элемент множества A входит во множество B, то A называется подмножеством B, а B называется надмножеством A. Если каждый элемент множества A входит в B, но множество B содержит хотя бы один элемент, не входящий в A, то A называется собственным подмножеством B, а B - собственным надмножеством A. Объединением множеств A и B называется множество элементов, принадлежащих по крайней мере одному из данных множеств. Пересечением множеств A и B называется множество элементов, принадлежащих одновременно и A и B. Разностью множеств A и B называется множество элементов, принадлежащих A и не принадлежащих B.
Законы алгебры множеств.
1.Коммуникативность
объединения.
2.
Ассоциативность объединения.
3. Дистрибутивность объединения относительно пересечения
4
Законы действия с пустым и универсальным
множествами:
;
;
5.
Закон идемпотентности объединения
6.
Закон де Моргана
7.
Закон поглощения
8.
Закон склеивания
9.
Закон двойного отрицания
.
Мощность множества. Теорема о числе подмножеств конечного множества.
Мощность множества — это обобщение понятия количества (числа элементов множества), которое имеет смысл для всех множеств, включая бесконечные. Другими словами мощность множества – это количество его элементов.
Теорема. Пусть дано мн-во А. Тогда число всех его подмножеств равно 2^n.
Док-во проведем методом мат. Индукции. При n=1 наша формула верна 2=2^1.
При n=k, 2^k. Посчитаем число всех подмножеств. Любое подмножество последний элемент a=k+1 либо содержит либо не содержит. Число всех подмножеств которые элемент a=k+1 не содержит равно числу всех подмножеств мн-ва а, а следовательно оно равно 2^k по предположению. А число всех подмножеств элементы которых k+1 равна, следовательно число всех подмножеств равна 2^k+2^k=2*2^k=2^(k+1).
Бинарные отношения и их типы
Бинарным отношением между элементами множества А называется любое подмножество из декартового произведения АхА.
Типы бинарных отношений. Бинарным отношением R между элементами множества А называется рефлексивным если для любого элемента а из А пара (а,а) принадлежит R. Симметричным – если из того, что пара (а,б) пренадлежит R следует, что пара (б,а) принадлежит R. Транзитивным – если из того что пара (а,б) и пара (а,с) принадлежит R следует что пара (а,с) принадлежит R.
Отношение эквивалентности. Теорема о разбиении множества на классы.
Бинарное отношение R называется отношением эквивалентности, если оно рефлексивно, симметрично и транзитивно. Например отношение параллельности.
Теорема. Каждое множество А на котором задано отношение эквивалентности можно разбить на классы таким образом, что 2 элемента а и б попадают в один и тот же класс, когда пара (а,б) принадлежит R. Под разбиением множества А на классы мы понимаем совокупность не пустых подмножеств, которые обладают свойствами: 1) объединение. 2) попарно они не пересекаются.