ОСНОВНЫЕ ОПЕРАЦИИ НАД МНОЖЕСТВАМИ

Включение (объединение)

Множество А входит (включено) в множество В, или А является подмножеством В.

Если всякий объект, обладающий свойством , также обладает свойством , то говорят, что свойство включает свойство , т.е.

Сумма

Сумма множеств А и В есть множество С, включающее в себя все элементы множество А и В.

Объект входит во множество если он входит во множество А или во множество В.

Пересечение (произведение)

Пересечением множество А и В называется новое множество С. Элементы множества С принадлежат множеству А (обладают его свойствами) и множеству В (обладают его свойствами).

Вычитание (разность)

Разность множеств А и В есть множество С, элементы которого обладают свойствами множества А и не обладают свойствами множества В или принадлежат множеству А и не принадлежат множеству В.

Дополнение

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

 

ГРАФИЧЕСКОЕ ПРЕДСТАВЛЕНИЕ

(Диаграммы Эймера, Венна)

 

1.

 

2.

 

В

А

3.

 

 

U

4.

 

 

4. ПРЯМОЕ ПРОИЗВЕДЕНИЕ А х В

 

Прямым произведением множеств А и В называется множество М всех пар ( ), таких, что

Если А=В, то такое произведение называется

Аналогично можно вывести операцию прямого произведения большего числа множеств.

Если в частности одинаковы то получаем

(Например, множество точек на плоскости являются прямым произведением двух множеств).

 

Если множества конечные, мощность произведений равна мощности произведений

 

 

ОСНОВНЫЕ ТОЖДЕСТВА АЛГЕБРЫ МНОЖЕСТВ

Независимость расположения:

(1)

(2)

Ассоциативность:

(3)

(4)

Дистрибутивность:

 

 

(7)

(8)

(9)

(10)

(11)

(12)

 

ЗАКОНЫ де Моргана

 

6. ЭЛЕМЕНТЫ КОМБИНАТОРИКИ И ИХ ПРИМЕНЕНИЕ В ТЕОРИИ МНОЖЕСТВ

 

Основная задача комбинаторики – пересчет и перечисление элементов в конечных множествах.

 

1. Если нас интересует, сколько элементов принадлежащих данному конечному множеству обладают некоторым свойством, то это задача пересчета.

2. Если необходимо выделить все элементы множества, об­ладающие заданными свойствами, то это задача перечисления.

 

Рассмотрим следующие элементы комбинаторики, позволяющие решать вышеупомянутые задачи. К таким объектам относятся:

- перестановки (с повторением и без них);

- размещения (с повторением и без них);

- сочетания (с повторением и без них);

 

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

Перестановки с повторениями вычисляются по формуле:

, где - число повторений элементов каждого вида.

 

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

(без повторения)

 

(с повторением)

 

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

(без повторения)

 

(с повторением)