Примеры

1. Установленные нами тождества позволяют упрощать различные сложные выражения, содержащие множества, подобно тому как такие упрощающие тождественные преобразования делаются в алгебре.

Приведем три примера.

( a) А  В  В = Ā  В  В = Ā  В.

( Ь) (А  В  С)  (Ā  В  С)  В  С = [(А  Ā)  В  С]  В  С = = [U  В  С]  В  С = (В  С)  В  С = U.

( с) (А  В  С  Х)  (Ā  С)  (В  С)  (С  Х) = (А  В  С  Х)  [(Ā ВХ)  С] = [(А  В  Х)  А  В  Х]  С = U  С = С.

2 . В алгебре множеств имеется своя теория уравнений, значительно отличающаяся от той, которую мы знаем из курса алгебры. В качестве иллюстрации мы опишем здесь метод решения одного уравнения с одним «неизвестным», т. е. выражения, построенного с помощью последователь­ного связывания знаками ,  и (И знаком равенства. – Прим. перев.) символов А₁ А₂, ... , А_n, обозна­чающих некоторые фиксированные подмножества некоего универсального множества U, и символа X, обозначающего некоторое подмножество мно­жества U, причем условием, определяющим X, как раз и является дан­ное уравнение. Средствами алгебры множеств удается ответить на вопрос, при каких условиях такое уравнение имеет решение, и, если эти усло­вия выполнены, найти все такие решения. Опишем этот метод; доказа­тельство того, что он является таковым (вернее, доказательство правильности каждого шага), предоставляем читателю в качестве упражнения (см. упражнение 7).

I ш а г. Два множества равны в том и только в том случае, если их симметрическая разность равна ф. Следовательно, любое уравнение (от­ носительно X) равносильно некоторому уравнению, в правой части кото­ рого стоит .

II ш а г. Любое уравнение (относительно X), в правой части которого стоит , равносильно некоторому уравнению вида

( А  Х)  (В  Х) = ,

где А и В — обозначения некоторых множеств, не содержащие символа X.

III ш а г. Объединение двух множеств равно  в том и только в том случае, когда каждое из них равно . Значит, уравнение, получаемое на II шаге, равносильно системе двух уравнений

А  Х = , В  Х = .

IV ш а г. Выписанная на III шаге пара уравнений, а следовательно и исходное уравнение имеет решение тогда и только тогда, когда В  Ā . При этом условии любое множество X такое, что В  Х  Ā, является решением данного уравнения.

В качестве примера найдем необходимое и достаточное условие суще­ствования решения уравнения Х  С = D:

Х  С = D,

[(Х  С)  D]  [D  (X  C)] = , (I шаг)

[ (X  C)  D]  [D  X  C] = ,

( X  D)  (C  D)  (D  X  C) = ,

( D  X)  [(C  D)  (X  X)]  (D  C  X) = .

(Введение в предыдущее уравнение члена Х  Х обсуждается ниже, в упражнении 7(b).)

( D  X)  (C  D  X)  (C  D  X)  (D  C  X) = ,

{ [D  (C  D)]  X}  {[(C  D)  (D  C)]  X} = ,

( D  X)  [(C + D)  X] = , (II шаг),

D  X =  и (C + D)  X = . (III шаг).

Итак, уравнение X  C = D имеет решение в том и только в том случае, когда

C + D  D. (IV шаг).

Предоставляем читателю показать, что это условие можно упростить, приведя его к виду С  D.

Упражнения

1. Доказать, что соотношения 3', 4' и 5' из теоремы 1.1 являются тождествами.

2. Доказать соотношения 6—13 теоремы 1.2, исходя из отношения принадлежности. Попробуйте получить эти же результаты, пользуясь только теоремой 1.1. Хотя бы для одного такого доказательства выпишите соотношения, двойственные каждому его шагу, чтобы получить дока­зательство двойственного утверждения.

3. С помощью только теорем 1.1 и 1.2 докажите, что следующие равенства являются тождествами:

(а) (A  B  X)  (A  B  C  X  Y)  (A  X  Ā) = A  B  X;

( b) (A  B  C)  (Ā  B  C)  B  C = U;

( с) (A  B  C  X)  ( Ā  C)  (BC)  (CX) = C;

( d) [(A  B)  (A  C)  (Ā  X  Y)] 

 [(Ā  В  С)  (Ā  X  Y)  (Ā  В  Y)] =

= (A  B)  ( Ā  B  X  Y).

4. Выполнить упражнение 9 (b) из § 1.4, пользуясь только средст­вами алгебры множеств, описанными в настоящем параграфе.

5. Пусть A₁ A₂ . . . , A_n — множества; пусть далее

S_k = A₁  A₂  ...  А_k (k =1, 2, ... , n).

Доказать, что

U = {А₁, A₂- S₁, A₃- S₂, …, A_n- S_n-1}

есть расчлененная система множеств и что

S_n = А₁  (A₂-S₁)  …  (A_n- S_n-1).

При каких условиях U есть разбиение множества S_n?

6. Доказать, что для произвольных множеств A₁, А₂, ... , А_п (п ≥ 2) А₁  А₂  ...  A_п = (А₁- A₂)  (A₂—A₃)  ...  (A_n-1 – A_n ) 

 (A_n – A₁)  (A₁  A₂  … A_n).

7. В связи с примером 2 доказать следующие утверждения:

1. Для любых множеств А и В А=В тогда и только тогда, когда A + В = .

2. У равнение X с  в качестве правой части может быть при­ ведено к виду (А  Х)  (В  Х) = .

У к а з а н и е. Доказательство можно провести по следующей схеме. Прежде всего применять законы де Моргана до тех пор, пока операция дополнения не будет относиться лишь к отдельным множествам. Затем развертывать левую часть уравне­ния согласно дистрибутивным законам, пока она не преобразуется в объединение нескольких членов Т_i, каждый из которых представляет собой пересечение нескольких отдельных множеств. Далее, если в какое-либо Т_i не входит ни X, ни X, заменить такое Т_i на T_i  (X  X) и развернуть согласно предыдущему пункту. В заключение сгруппировать вместе члены, содержащие X, и отдельно, члены, содержащие X, и при­менить к полученному выражению второй дистрибутивный закон.

(c) Для любых множеств А и В А  В =  тогда и только тогда, когда А = В = .

4. У равнение (А  X)  (В  X) =  имеет решение тогда и только тогда, когда В  Ā, причем решением является любое такое X, что B  X  Ā.

5. Другая форма решения уравнения из (d) есть X =(B  T)  Ā, где Т — произвольное множество.

8. Доказать, что для произвольных множеств А, В, С, D и X:

1. [ (А  X)  (В  X)] = (Ā  X)  (В  X);

2. [ (A  X)  (B  X)]  [(C  X)  (D  X)] =

= [(A  C)  X]  [(B  D)  X];

( c) [(A  X)  (B  X)]  [(C  X)  (D  X)] =

= [(A  C)  X]  [(B  D)  X].

9. Пользуясь результатами упражнений 7 и 8, доказать, что урав­нение

( A  X)  (B  X) = (C  X)  (D  X)

имеет решение в том и только в том случае, когда B + D  A + C. Найти в этом случае все решения.