1.3. Решение уравнений с неизвестным множеством

Пусть U– произвольное множество, «универсум». Мы будем рассматриватьтеоретико-множественные выражения, которые получаются из символов с помощью операций над множествами, например .

Определение.Теоретико-множественное выражениеH=H(X₁, …, X_m), полученное из подмножеств (X₁, …, X_m)U, определяется по индукции:

1. X₁, …,X_m,U,– теоретико-множественные выражения.

2. Если H– теоретико-множественное выражение, то – теоретико-множественное выражение.

3. Если H₁иH₂– теоретико-множественные выражения, то (H₁H₂), (H₁H₂), (H₁\H₂), (H₁H₂) – теоретико-множественные выражения.

Наша цель – научиться решать уравнения H(X, A₁, …, A_n)= , гдеH(X, A₁, …, A_n)– теоретико-множественное выражение, полученное из подмножествX, A₁, …, A_nU.

Предложение. Для всякого теоретико-множественного выраженияH(X, A₁, …, A_n)существуют такие теоретико-множественные выраженияR(A₁, …, A_n), S(A₁, …, A_n),

T(A₁, …, A_n), что для любогоXUследующие условия равносильны

1. H(X, A₁, …, A_n)= .

2. R(A₁, …, A_n)(S(A₁, …, A_n)X)(T(A₁, …, A_n) ) =  .

Доказательство. ПосколькуP\Q=P иPQ = (P  Q)\(P  Q), то можно считать, чтоHпостроена с помощью операцийP Q,P Qи . Далее применяется индукция по количеству операций вH(X, A₁, …, A_n).

Следствие. В условиях предыдущего предложения, уравнениеH(X, A₁, …, A_n)=  будет иметь решения тогда и только тогда, когда будут выполнены соотношения:

1. S(A₁, …, A_n)X = ,

2. T(A₁, …, A_n) = ,

3. R(A₁, …, A_n) = .

Метод решения уравнения H₁(X, A₁, …, A_n)= H₂(X, B₁, …, B_m).

Здесь A₁, …, A_nиB₁, …, B_m- некоторые заданные множества. Обозначим символом 0 пустое множество.

Это уравнение сначала приводят к уравнению H(X, A₁, …, A_n)= 0,где

H(X,A₁,…, A_n)= (H₁(X, A₁, …, A_n)\ H₂(X, B₁, …, B_m))  ( H₂(X, B₁, …, B_m)\ H₁(X, A₁, …, A_n)).

Потом для полученного уравнения находим формулы для R, S, Tиз предыдущего предложения. И наконец, применим предыдущее следствие. Разберем этот метод решение на следующем примере.

Пример. Рассмотрим, например, уравнение

AX = B.

Оно равносильно уравнению вида

= 0.

Следующим шагом решения будет преобразование левой части к объединению пересечений множеств. Это достигается с помощью формул P\Q=P де Моргана. После применения формул получим

= 0.

А после применения формул де Моргана приходим к уравнению

= 0.

С помощью закона дистрибутивности получаем уравнение

= 0.

Поскольку и , то это уравнение примет вид

=0.

Последнее равенство выполнено тогда и только тогда, когда Xудовлетворяет системе уравнений

Первое уравнение равносильно включению , а второе -. Отсюда вытекает следующий ответ

.

1.4. Перечисление подмножеств

Пусть M– произвольное множество. Его мощность обозначается |M|. Если множествоMсостоит из конечного числа элементов, то |M| –число его элементов. Обозначим через 2^M = { A : A  M } – множество всех подмножеств множестваM.

Теорема.Если множество М имеет конечное число элементов, то | 2^M | = 2^{| M |}.

Доказательство. Пусть M = {a₀, a₁, , a_n-1 } . Каждому подмножеству можно поставить в соответствие битовую строку, состоящую из n разрядов, равных 0 или 1. Эта битовая строка представляет собой двоичную запись некоторого неотрицательного целого числа. Ее i-й разряд равен 1, если a_i A, и равен 0, в других случаях. Хорошо известно, что количество двоичных n-разрядных чисел равно 2ⁿ . Следовательно, количество подмножеств будет равно 2^{| M |}.

Упражнение. Докажите предыдущую теорему с помощью индукции по числу элементов множестваM.

Замечание. Получаем алгоритм перебора подмножеств. Каждому подмножеству соответствует неотрицательное целое число, двоичная запись которого содержит единичные разряды, соответствующие элементам этого подмножества. Прибавляя по 1, получаем все подмножества. Например, для M = {a, b, c} этот алгоритм можно проиллюстрировать с помощью таблицы 1.1.

Таблица 1.1.

Перебор подмножеств множества {a,b,c}

Номер	Двоичная запись	Подмножество
0	000	
1	001	{c}
2	010	{b}
3	011	{b, c}
4	100	{a}
5	101	{a, c}
6	110	{a, b}