Задание множеств конституентами (числом)

Формула алгебры множеств, представляющая собой пересечение, в которое входят по одному разу все множества (со знаками дополнения или без дополнений) на данном универсуме, называется конституентой единицы [9]. Формула, представляющая собой объединение, в которое входят по одному разу все множества (со знаками дополнения или без дополнений) на данном универсуме, называется конституентой нуля. Каждое множество, за исключением пустого, может быть задано объединением конституент единицы. Каждое множество за исключением универсального может быть задано пересечением конституент нуля. Рассмотрим задание множества путем указания его конституент единицы. Пусть на некотором универсуме рассматриваются два взаимно пересекающихся множества: А и В.

Зададим их графически с помощью диаграмм Эйлера (рис. 9).

Рис. 9. Диаграмма Эйлера для двух взаимно пересекающихся

множеств А и В на универсуме I

Тогда каждый из четырех сегментов (четырех «кусочков») этой диаграммы может быть закодирован конституентой, содержащей символы А и В:

– сегмент 00 – не А и не В;

– сегмент 10 – А, но не В;

– сегмент 01 – не А и В;

– сегмент 11 – А и В.

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

Таблица 4

Задание множества А двоичным числом

23	22	21	20

Множество А закодировано двоичным числом 1100. Этому двоичному числу соответствует десятичное число 12.

При таком задании множеств легко выполняются операции над ними. Например, получим пересечение множества №12 и множества №5. Результатом будет множество №4. Действительно, результат пересечения – множество, в котором при его двоичном представлении, имеются единицы в разрядах, соответствующих совпадениям единиц в исходных множествах (табл. 5).

Таблица 5

Пересечение множеств №12 и №5

Основные понятия комбинаторики

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

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

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

При этом под решением задачи оптимизации «в сильном смысле» понимается нахождение всех элементов минимизирующих (максимизирующих) целевую функцию, а под решением задачи оптимизации «в слабом смысле» – нахождение единственного произвольного элемента [24].

Рассмотрим основополагающие правила комбинаторики – правила суммы и произведения.

Пусть Х – конечное множество, состоящее из n элементов х. Тогда говорят, что элемент х из Х может быть выбран n способами и пишут |Х|=n. Эта запись совпадает с записью мощности множества Х.

Пусть Х₁,..., Х_k – попарно непересекающиеся множества, т.е. Х_iIХ_j=Æ, i¹ j.

Очевидно, что в этом случае

.

Таково комбинаторное правило суммы. Для k=2 оно формулируется следующим образом. Если объект х может быть выбран n способами из множества Х, а объект y из непересекающегося с ним множества Y, – другими m способами, то выбор «х или y» может быть осуществлен n+m способами.

Правило произведения для k=2 формулируется следующим образом. Если объект х может быть выбран n способами и после каждого из таких выборов объект y в свою очередь может быть выбран m способами, то выбор упорядоченной пары – вектора (х, y) может быть осуществлен n× m способами.

Например, Х: {x₁, x₂}, Y: {y₁, y₂}.

Тогда упорядоченные пары (x, y) описываются декартовым произведением

X× Y={(x₁, y₁), (x₁, y₂), (x₂, y₁), (x₂, y₂)}.

Выбор упорядоченной последовательности из k объектов вектора (х₁, х₂,..., х_k) может быть осуществлен n₁·n₂·...·n_k способами, где n_i – число способов выбора i-го объекта х_i, i меняется от 1 до k (записывается: ).

В частности, если все n_i равны, что может быть, например, в случае, когда элементы принадлежат одному и тому же множеству, т.е. рассматривается декартово произведение Х^k, то число способов равно n^k.

Набор элементов х_i1,..., x_ikиз множества Х={x₁,..., x_n} (вектор) называется выборкой (комбинацией) объема k из n элементов или, иначе, (n, k) выборкой.

Выборка называется упорядоченной, если порядок следования элементов в ней задан. Две упорядоченные выборки, различающиеся лишь порядком следования элементов, считаются различными.

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

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