В.Н. Нефедов - Алгебра множеств, бинарные отношения в примерах и задачах, страница 3

Тогда(а) [ f1  f 2  g1  g 2 ]  ( g1  g 2 ) \ ( f1  f 2 )  ;(б) [ f1  f 2  g1  g 2 ]  ( g1 \ g 2 ) \ ( f1  f 2 )  ;(в) [ f1  f 2  g1  g 2 ]  ( g1  g 2 ) \ ( f1 \ f 2 )  ;(г) [ f1  f 2  g1  g 2 ]  ( g1 \ g 2 ) \ ( f1 \ f 2 )  .Из утверждений 1.8,1.10 следует, что для любых формул алгебрымножеств f 1 , f 2 , g1 , g 2 проверка утверждений вида: f1  f 2  g1  g 2 ; f1  f 2  g1  g 2 ; f1  f 2  g1  g 2 ; f1  f 2  g1  g 2 может быть осуществлена описанным выше табличным способом.Пример 1.11. Доказать или опровергнуть: A  B  A  C  B \ C  A . В силу утверждения 1.10, проверка этого утверждениясводится к проверке выполнения тождества f ( A, B, C )  [( B \ C ) \ A] \ [( A  B)  ( A  C)]   .

Составим таблицу для f :Используя утверждение 1.8, получаем, что f   , а следовательно, в силу утверждения 1.10, рассматриваемое утверждение верно.15Решение системы уравнений в алгебре множеств относительнонеизвестного множества X . Нам понадобится следующееУтверждение 1.11. Пусть A, B – некоторые множества, являющиеся подмножествами некоторого универсального множества U   . Тогда (а) система уравнений A  X  ,B  X  (1.7)(1.8)относительно неизвестного множества X имеет решение тогда и только тогда, когда B  A ; (б) решениями системы (1.7),(1.8) являются любые множества X такие, что B  X  A .Доказательство. (а) Пусть система (1.7),(1.8) имеет решение X .Тогда, используя (1.4), (1.5), имеем: (1.7), (1.8)  B  X , X  A  B  A.

Обратно, пусть B  A . Тогда, например, для X  B (илидля X  A ), используя (1.4), (1.5), имеем B  X  A  X  A,B  X  A  X  , B  X  , т.е. X действительно является решением системы (1.7), (1.8). (б) Пусть B  A . Тогда, как доказано в (а),существует решение системы (1.7), (1.8).

Причем, в силу (1.4), (1.5),имеем: (1.7), (1.8)  X  A, B  X  B  X  A, т.е. решениямисистемы (1.7), (1.8) являются все множества X такие, что B  X  A .Приведем теперь алгоритм решения произвольной системы уравнений в алгебре множеств относительно одного неизвестного множества X . Для сокращения записи будем, как и ранее, писать AB вместоA  B и считать  самой «сильной» двухместной операцией (т.е. выполняемой в первую очередь).Пусть f i ( A1 ,..., An , X ) , g i ( A1 ,..., An , X ) , i  1,2,..., m, – формулыалгебры множеств, где A1 ,..., An – некоторые множества, являющиесяподмножествами некоторого универсального множества U , X – неизвестное множество.

Рассмотрим систему уравнений (относительно X )(1.9)f i ( A1 ,..., An , X ) = g i ( A1 ,..., An , X ) , i  1,2,..., m .16Алгоритм 1.1 решения системы уравнений (1.9)1) Используя (1.3), (1.6), имеем: (1.9)  f1  g1  ,..., f m  g m    ( f1  g1 )  ...

 ( f m  g m )   , т.е. можно считать, что система (1.9) имеет вид: f ( A1 ,..., An , X )   , где f  ( f1  g1 )  ...  ( f m  g m ).2) «Избавляемся» в f ( A1 ,..., An , X ) от операций: \,  , используятождества: A \ B  AB , A  B  AB  BA .3) Используя законы де Моргана, приводим f ( A1 ,..., An , X ) к виду,при котором знак абсолютного дополнения может находиться тольконад символами множеств: A1 ,..., An , X (см.

замечание 1.1). Пример:f ( A1 ,..., An , X )  A1 ( A2  X ) X  A3 X  A4 X  ( A4 X  A5 ) A5 .4) Используя дистрибутивность  относительно  , приводимf ( A1 ,..., An , X ) к виду «объединение пересечений» (аналогичному алгебраическому многочлену, где роль умножения играет  , а роль сложения –  ). Пример (продолжение примера на шаге 3 алгоритма; см.также замечание 1.1):f ( A1 ,..., An , X )  A1 A2 X  A3 X  A4 X  A4 A5 X  A5 .5) Группируем члены в f ( A1 ,..., An , X ), образуя 3 группы:« без X », « с X », « с X ». Во второй группе выносим X за скобки, втретьей выносим за скобки X :f ( A1 ,..., An , X )  h1 ( A1 ,..., An )  h2 ( A1 ,..., An ) X  h3 ( A1 ,..., An ) X .Пример (продолжение примера на шаге 4 алгоритма):f ( A1 ,..., An , X )  A5  ( A1 A2  A3  A4 A5 ) X  A4 X . h1  ,6) Используя (1.3), получаем: f    h2  X  ,h  X  , 3откуда, в силу утверждения 1.11, необходимым и достаточным ус17ловием существования решения системы уравнений (1.9) являетсяh1   , h3  h2 ,(1.10)и в случае выполнения (1.10) решениями системы уравнений (1.9) являются все множества X , удовлетворяющие условию: h3  X  h2 .Замечание 1.1.

На шаге 3 алгоритма используется также тождествоA  A , а на шаге 4 – тождества: A  A  A, A  A  A , A  A   ,A    , A    A .Замечание 1.2. Описанный алгоритм может быть применен и ксистеме уравнений относительно многих неизвестных X 1 ,..., X k . Приэтом производится последовательное исключение неизвестных.Замечание 1.3.

Система (1.9) может также иметь иной вид (свключениями вместо равенств):(1.11)f i ( A1 ,..., An , X )  g i ( A1 ,..., An , X ) , i  1,2,..., m .В этом случае модифицируется шаг 1 алгоритма, а именно, используя (1.3),(1.4), имеем: (1.11)  f1 \ g1  ,..., f m \ g m    ( f1 \ g1 )  ...  ( f m \ g m )   , т.е. система (1.11) сводится к единственному уравнению f ( A1 ,..., An , X )   , где f  ( f1 \ g1 )  ...  ( f m \ g m ).Используя (1.3), (1.4), (1.6), нетрудно также модифицировать шаг 1алгоритма и в случае, когда в рассматриваемую систему входит конечное число равенств и конечное число включений.Пример 1.12.

Пусть A, B – заданные множества, являющиеся подмножествами некоторого универсального множества U . Найти необходимое и достаточное условие для X (вида g ( A, B)  X  f ( A, B) ,где g ( A, B), f ( A, B) – формулы алгебры множеств), если X  A  X  B . Последовательно применяя шаги 1–6 алгоритма 1.1, и, используя (1.4), получаем:X  A  X  B  ( X  A)  ( X  B)    [( X  A) \ ( X  B)]  [( X  B) \ ( X  A)]   18 ( X  A)( X  B)  ( X  B)( X  A)    ( X  A) X B  ( X  B) X A    X X B AX B X X AB X A  A X B  B X A    ( AB  BA ) X    ( A  B) X    ( A  B)  X .Пример 1.13.

Пусть A, B, C – заданные множества, являющиесяподмножествами некоторого универсального множества U . Решитьсистему уравнений относительно неизвестного множества X : A  X  B, A  X  C.(1.12)Последовательно применяя шаги 1–6 алгоритма 1.1, получаем:(1.12)  ( AX  B)  [( A  X )  C]    ( AX \ B)  ( B \ AX )  [( A  X ) \ C ]  [C \ ( A  X )]    AXB  B( A  X )  ( A  X )C  CA X    AXB  BA  BX  AC  XC  CA X    ( A B  AC )  ( AB  C ) X  ( B  A C ) X    A B  AC  , ( AB  C )  X  , ( B  A C )  X  .В силу утверждений 1.11, (1.3), (1.4), необходимым и достаточнымусловием существования решения этой системы, равносильной (1.12),являетсяA B  AC   , B  A C  AB  C  A B  , AC  , B  A C  ( A  B)C  B  A  C, B  A C  BC  A C  B  A  C,так как, в случае B  C , выполняется BC  B, BC  A C  B  A C .В силу утверждения 1.11, единственным решением этой системы вслучае B  A  C является X  B  A C .19ЗадачиЗадача 1.1.

Используя основные тождества алгебры множеств, доказать тождества: (а) A \ ( B \ C )  ( A \ B)  ( A  C ) ; (б)( A \ B) \ C  ( A \ C ) \ ( B \ C ) ; (в) A \ ( B  C)  ( A \ B) \ C .Решение. (а) A \ ( B \ C )  A \ ( B  C )  A  ( B  C )  A  ( B  C )  ( A  B )  ( A  C )  ( A \ B)  ( A  C ) ;(б) ( A \ C ) \ ( B \ C )  ( A  C )  ( B  C )  ( A  C )  ( B  C)  ( A  C  B )  ( A  C  C)  ( A  B  C )    ( A  B )  C  ( A \ B) \ C ; (в) A \ ( B  C )  A  ( B  C )  A  ( B  C )  ( A  B )  C  ( A \ B) \ C .Задача 1.2. Используя основные тождества алгебры множеств, атакже утверждения (1.4), (1.5), доказать утверждения: (а) A  B C   A  B  C ; (б) A  B  C  A \ B  C .Решение.

(а) A  B  C  ( A  B) \ C    ( A  B)  C    A  (B  C )    A  B  C  B  C ;(б) A  B  C  A \ ( B  C )    A  ( B  C )    A  ( B  C )    ( A  B )  C    ( A \ B) \ C    A\ B  C.Задача 1.3. Доказать, что A  B    A  B  A  B .Решение. Используя тождество 13, имеем A  B  A  B , откуда( A  B) \ ( A  B)   , а следовательно, A  B  A  B  ( A  B)  ( A  B)    ( A  B) \ ( A  B)    ( A  B) \ [( A \ B)  ( B \ A)]  ( A  B)( AB  BA )    ( A  B)( A  B)( A  B )  ( A  B)( A B  AB)  AA B  AAB  BA B  BAB  AB   ;Задача 1.4.