4. Разбиения и покрытия.

Одной из операций над множествами является разбиением множеств на систему подмножеств.

Рассмотрим множество М и систему подмножеств m={x₁,x₂…x_n}

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

1. любое множество х из m является подмножеством множества М:

х m х М

2. любые 2 подмножества x_i и x_j, принадлежащие m не пересекаются

x_i  x_j=

3)объединение всех множеств x_i, принадлежащих mравно множеству М.

x_im x_i=М

Семейство m называются покрытием М, если каждый элемент множества М принадлежит хотя бы одному из множеств x_i.

5. Свойства операций над множествами. Доказательства.

1.Иденпотентность

AA=A; AA=A

2.Коммутативность

AB=BA; AB=BA

3.Ассоциативность

A(BC)=(AB)C

A(BC)=(AB)C

4.Дистрибутивность

A(BC)=(AB)(AC)

A(BC)=(AB)(AC)

5.Поглощение

(AB)A=A;

(AB)A=A

6.Свойства нуля

A=A; A=

7.Свойство единицы

AU=U; AU=A

8.Инволютивность

=A

9.Закон де Моргана

= ; =

10. Свойство дополнения

A=U; A=

11. Свойство выражения для разности

A/B=A

Для док-ва этих св-в можно использовать следующие способы:

а) построить диаграммы Эйлера для левой и правой частей равенства и убедиться, что граф. представления одинаковые;

б) провести формальные рассуждения (выбираем произв. эл-т, принадл. левой части равенства , и показыв., что он принадлежит правой части равенства.)

6. Универсальное множество. Булеан.

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

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

Булеан - множества подмножеств множества М называют булеаном и обозначаются 2^М

М:={1,3,5}

2^М - , {1}, {3}, {5}, {1,3}, {1,5}, {1,5}, {3,5}, {1,3,5}.

Теорема Для конечного множества М мощность булеана равняется 2^М

2^М  = 2^М

7. Представление множеств в эвм.

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

Для множества представления подразумевают описания способа хранения информации об элементе, принадлежащему множеству, описаний алгоритмов выполняющих объединение, пересечение и другие операции.

Один и тот же объект(множество) может быть представлен разными способами, выбор зависит от особенности и операций, которые над ними должны выполняться.

8. Реализация операций над подмножествами заданного универсума.

U < n

U = {U₁, U₂, U₃,…}

Число элементов в универсуме не превосходит разрешающимися сети компьютера.

Подмножество А универсума U представляется двоичным кодом(машинным кодом, битовой шкалой)

C_i= 1, U_iA

0, U_iA

Пересечение А и В являются поразрядным логическим произведением кодом множеств А и В.

Код объединений множеств А и В является поразрядной логической суммой кодов множеств А и В.

Код дополнения множества А является инверсией кода множества А.