В.Н. Нефедов - Алгебра множеств, бинарные отношения в примерах и задачах (1013084), страница 3
Текст из файла (страница 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 AB 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.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
