1.2. Операции над множествами

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

П одмножеством A множества B (AB) или (A содержится в B) называется множество A, каждый элемент которого принадлежит B. Графически это изображается с помощью кругов Эйлера, как показано на рисунке.

Пустое множество есть подмножество любого множества.

Совокупность всех подмножеств множества А называется множеством-степенью и обозначается P(А), то есть P(А)={ВВА}.

Множества A и B называются равными (A=B), если AB и BA.

Множество, не содержащее ни одного элемента, называется пустым и обозначается Ø. Совокупность всех допустимых объектов в рамках решаемой задачи называется универсальным множеством и обозначается U.

Дополнением множества A называется множество Ā, состоящее из элементов универсального множества, не являющихся элементами множеством A.

Пересечение множеств AB, есть множество элементов принадлежащих A и B.

Объединение AB есть множество всех элементов принадлежащих A или B. Следует иметь в виду, что существуют два значения союза или:

1) «исключающее или» - либо то, либо другое и третьего не дано;

2) «не исключающее или» - то или другое, или то и другое вместе.

В определении объединения множеств подразумевается второе “не исключающее или”, то есть элемент может принадлежать только A, только B, а также одновременно этим множествам

Разность A\B, есть множество, состоящее из элементов A, не входящих в множество В.

Симметричная разность

1.3. Алгебраические свойства операций над множествами

1. идемпотентность
1.1. AA=A	1.2. AA=A
2. коммутативность
2.1. A B=BA	2.2 AB=BA
3. ассоциативность
3.1. A(BC)=(AB)C	3.2 A(BC)=(AB)C
4 дистрибутивность
4.1.A(BC)=(AB)(AC)	4.2 A(BC)=(AB)(AC)
5. поглощение
5.1. A(AB)=A	5.2. A(AB)=A
6. свойства нуля
6.1. AØ=A	6.2. AØ=A
7. свойства единицы
7.1. AU= U	7.2. AU=A
8. инволютивность
9. законы де Моргана
9.1.	9.2
10. дополнительность
10.1. AĀ=U	10.2 AĀ=Ø

Тема 2. Элементы комбинаторики

2.1. Основные правила комбинаторики

Комбинаторика – раздел математики, связанный с решением задач выбора и размещения элементов конечного множества в соответствии с заданными правилами.

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

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

Большинство комбинаторных задач решается с помощью двух основных правил - правила суммы и правила произведения.

Правило суммы. Пусть A, B – конечные множества, |A| = n, |B| = m.

,

следовательно

.

Комбинированная интерпретация.

Если некоторый объект A можно выбрать n способами, а другой объект B можно выбрать m способами, то выбор "либо A, либо B" можно осуществить n+m способами.

Правило произведения. Если мощность |A| = n, |B| = m, то .

Комбинаторная интерпретация.

Если объект A можно выбрать n способами, а после каждого такого выбора другой объект B можно выбрать (независимо от выбора объекта A) m способами, то пары объектов A и B можно выбрать способами.

Пусть , и |А| - число элементов множества A. Составим декартово произведение множеств A и B, т.е. множество пар .

Тогда правило произведения записывается следующим образом:

Пример. Сколько всего существует двузначных чисел?

Решение. Поскольку в двузначном числе цифра, обозначающая число десятков, должна быть отлична от нуля, то A = {1, 2, ..., 9}, B = {0, 1, 2, ..., 9} и _,