2.5. Задание множеств конституентами

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

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

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

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

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

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

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

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

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

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

Таблица 4

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

11	10	01	00
2^3	2^2	2^1	2^0
1	1	0	0

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

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

Таблица 5

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

1	1	0	0	№12
0	1	0	1	№5
0	1	0	0	№4=(№12)(№5)

2.6. Решение уравнений в алгебре множеств.

При решении уравнений в алгебре множеств исходят из того, что: 1) два множества равны тогда и только тогда, когда их симметрическая разность пуста; 2) определяются условия, при которых уравнения имеют решение [23].

Например, XC=D. Преобразуем уравнение к виду (XC)D=Æ. Любое уравнение, в правой части которого указано пустое множество может быть преобразовано в уравнение с декомпозицией по X:

(F₁X)(F₂)=,

где F₁, F₂ – формулы, не содержащие X.

Очевидно, что объединение пусто тогда и только тогда, когда объединяемые множества пусты:

(F₁X)= и (F₂)=.

Два полученных уравнения и исходное уравнение имеют решение тогда и только тогда, когда:

.

Поэтому необходимо определить F₁, F₂, что и является результатом решения уравнения.

Итак, (XC)D=Æ. Декомпозицию по X выполним, с помощью формулы симметрической разности двух множеств, использующей только операции объединения, пересечения и дополнения:

,

где – разность,– разность.

Выполним алгебраические операции:

.

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

.

Далее раскрываем скобки и применяем законы алгебры множеств:

.

Здесь налицо поглощение , поэтому:

.

Выносим за скобку:

.

Обращаем внимание, что , поэтому:

.

Таким образом: , т.е.– это и есть ответ.

Само собой, в этом случае может быть множество решений для конкретных C, D.

Пусть C={2,3,6,9}, D={1,2,3,5,6,7,8,9}. Тогда (CD)={1,5,7,8}D. X может быть, например, таким: X={1,2,5,7,8,9}, т.е. соотношение (CD)XD – выполняется.

Пусть C={2,3,4,6,9}, при том же D={1,2,3,5,6,7,8,9}. Тогда (CD)={1,4,5,7,8} не включается в D={1,2,3,5,6,7,8,9}. В этом случае решения нет!