В.Н. Нефедов - Алгебра множеств, бинарные отношения в примерах и задачах (1013084), страница 2
Текст из файла (страница 2)
Для любого x U имеем: x A B x A B x A, x B x A, x B x A B .Докажем тождество 8. Применим тождество 8 к A, B и воспользуемся очевидным тождеством 11: A B A B A B, а следовательно, A B A B, откуда A B A B, ч.и т.д.Докажем тождество 10.
Используя доказанное тождество 3, имеем:( A B) ( A B ) A ( B B ) A A.Докажем тождество 10. Используя доказанное тождество 3, имеем: ( A B) ( A B ) A ( B B ) A U A.Докажем тождество 12. Для любого x U имеем:x A \ B x A, x B x A, x B x A B .Докажем тождество 13. Используя доказанные ранее тождества,имеем:8( A B) \ ( A B) ( A B) ( A B) ( A B) ( A B ) ( A A) ( A B ) (B A) (B B ) ( A B ) ( B A ) ( A \ B) ( B \ A) A B.Докажем теперь тождество (ассоциативность +):A ( B C) ( A B) C.(1.1)Будем в последующих выкладках для сокращения записи вместоA B писать AB и считать операцию более «сильной» операцией,чем ,\, (т.е.
выполняемой в первую очередь). Имеем:A ( B C ) [ A \ ( B C )] [( B C ) \ A] [ A \ ( BC CB )] [( BC CB ) \ A] A( BC CB ) ( BC CB ) A A( B C )(C B) A BC A B C A( B C CC B B CB) (1.2) A BC A B C AB C ABC A BC A B C.С другой стороны, обозначив A C, C A и используя (1.2),имеем: ( A B) C C ( A B) C ( B A) A ( B C ) AB C ABC A BC A B C C BA CBA C BA C BA A B C ABC A BC AB C A ( B C ).Табличный метод доказательства тождеств. Заметим, что дляпроизвольного x U (в каждой строке, следующей за первой, указывается один из возможных случаев для x ) выполняется:xAxAнетдаданетТабл.
1.1xAxBx AB x AB x A\ BxB \ A x A B ( A \ B) ( B \ A)даданетнетданетданетдададанетданетнетнетнетданетнетТабл. 1.29нетнетданетнетдаданетИспользуя эти таблицы, докажем табличным методом справедливость уже доказанного тождества (1.1). Действительно, для произвольного x U имеем:xAxBxCдадададанетнетнетнетдаданетнетдаданетнетданетданетданетданет***x B C x A (B C)нетдаданетнетдаданетданетнетданетдаданетx A B x ( A B) CнетнетдадададанетнетданетнетданетдаданетСравнивая столбцы, выделенные символами * и **, получаем,что x A ( B C ) x ( A B) C , ч. и т.д.Заметим теперь, что табл.1.1 идентична табл.
1.3 (т.е. слову «да»в табл.1.1 соответствует символ U в табл. 1.3, а слову «нет» в табл. 1.1– символ в табл.1.3):AUAUТабл. 1.3Соответственно, табл. 1.2 идентична табл. 1.4 (в том же смысле,что и для таблиц 1.1,1.3)AUUBUUA BUUUA BUA\ BUB\ AUA BUUТабл.1.4Из идентичности приведенных таблиц следует, что справедливостьлюбого тождества можно проверить табличным методом, проверяя егосправедливость лишь при значениях символов множеств, входящих в10него, выбираемых из {U , }.
Описанный табличный метод обладаетрядом достоинств: (а) описан в виде алгоритма с простыми легко выполняемыми шагами; (б) легко программируется на ЭВМ; (в) если проверяемое тождество не верно, то при использовании табличного методаполучаем пример множеств, для которых оно не выполняется.Пример 1.9. Проверим справедливость тождества A \ ( B \ C ) A \ (C \ B). Составим соответствующую таблицу и сравним столбцыв этой таблице, выделенные символами * и **):ABCUUUUUUUUUUUUB\CUU***A \ (B \ C)A \ (C \ B)UUUC\BUUUUUИз приведенной таблицы следует, что, например, при A U ,B U , C рассматриваемое равенство не выполняется.Всюду далее под формулой алгебры множеств будем интуитивнопонимать формулу f ( A1 ,..., An ) (где n 1 ) с переменными A1 ,..., An ,обозначающими произвольные множества (являющиеся подмножествами заданного универсального множества U ), в которой эти переменныесвязаны между собой с помощью скобок, двухместных операций:,,\, , а также одноместной операцией абсолютного дополнения(строгое определение формулы аналогично определению формулы логики высказываний (см., например, [2, стр.
26,27]).Пример 1.10. Примерами формул алгебры множеств являются:A1 \ ( A2 A3 ), ( A1 A2 ) ( A3 \ ( A4 A1 )) .Будем далее формулы алгебры множеств обозначать буквамиf , g , h , возможно с индексами.11Для краткости утверждение, заключающееся в том, что для некоторых формул алгебры множеств f ( A1 ,..., An ) , g ( A1 ,..., An ) выполняется равенство f ( A1 ,..., An ) = g ( A1 ,..., An ) для любых Ai 2U ,i 1,2,..., n (т.е. выполняется тождество алгебры множеств), будем записывать следующим образом: f g .Кроме того, для краткости, утверждение, заключающееся в том,что для некоторой формулы алгебры множеств f ( A1 ,..., An ) выполняется равенство f ( A1 ,..., An ) ( f ( A1 ,..., An ) U ) для любыхAi 2U , i 1,2,..., n , будем записывать следующим образом: f ( f U ) .
Используя таблицы 1.3,1.4, получаем, что справедливоУтверждение 1.2. Пусть f ( A1 ,..., An ) – формула алгебры множеств. Тогда для любых Ai {U , } , i 1,2,..., n, выполняетсяf ( A1 ,..., An ) {U , }.Сформулируем также в виде утверждения приведенный ранее табличный метод доказательства тождеств.Утверждение 1.3. Пусть f ( A1 ,..., An ) , g ( A1 ,..., An ) – формулы алгебры множеств. Тождество алгебры множеств f ( A1 ,..., An ) g ( A1 ,..., An ) справедливо тогда и только тогда, когда для любыхAi {U , } , i 1,2,..., n, выполняется равенство f ( A1 ,..., An ) g ( A1 ,..., An ) .Следствие 1.1.
Если для некоторых формул алгебры множествf ( A1 ,..., An ) , g ( A1 ,..., An ) выполняется тождество f g при некотором универсальном множестве U , то это тождество будет справедливым и для любого другого универсального множества U .Табличный метод доказательства (или опровержения) утверждений алгебры множеств. Будем использовать следующее:12Утверждение 1.4.
Пусть f ( A1 ,..., An ) , g ( A1 ,..., An ) – формулы алгебры множеств. Тогда утверждение f g выполняется тогда и только тогда, когда f g.Действительно, если f g , то f g . В обратнуюсторону, пусть f g . Тогда, в силу утверждения 1.2, Ai {U , }, i 1,2,..., n, f g , откуда, в силу утверждения 1.3, f g .Утверждение 1.5.
Пусть A, B – произвольные множества. ТогдаA B A , B ,(1.3)A \ B A B A B,(1.4)A B A B,(1.5)A B A B.(1.6)Доказательство. Утверждение (1.3) очевидно. Докажем справедливость (1.4). Пусть A \ B . Предположим, что не выполняетсявключение A B . Тогда a A : a B, откуда a A \ B, что противоречит условию A \ B . Пусть теперь A B . Предположим, чтоA \ B .
Тогда a A : a B, а это противоречит условию A B .Для доказательства (1.5) воспользуемся (1.4), а также тождеством 11:A B A B A B . Утверждение (1.6) являетсяследствием утверждений (1.3),(1.4). Действительно, в силу (1.3),(1.4),имеем: A B ( A \ B) ( B \ A) A \ B , B \ A A B, B A A B.Покажем теперь, что справедливоУтверждение 1.6. Пусть f1 ( A1 ,..., An ), f 2 ( A1 ,..., An ), g1 ( A1 ,..., An ) ,g 2 ( A1 ,..., An ) – формулы алгебры множеств. Тогда утверждениеf1 f 2 g1 g 2 выполняется тогда и только тогда, когда справедливо тождество алгебры множеств f1 f 2 g1 g 2 .13Действительно, используя (1.6), а также утверждение 1.4, получаем: [ f1 f 2 g1 g 2 ] [ f1 f 2 g1 g 2 ] f 1 f 2 g1 g 2 .Кроме того, справедливо следующееУтверждение 1.7.
Пусть f1 ( A1 ,..., An ), f 2 ( A1 ,..., An ), g1 ( A1 ,..., An ) ,g 2 ( A1 ,..., An ) – формулы алгебры множеств. Тогда(а) [ f1 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 ] f1 \ f 2 g1 \ g 2 .Докажем (а) (доказательство (б), (в) аналогично). Используя утверждения 1.4, (1.4),(1.6), получаем: [ 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.3.Утверждение 1.8. Пусть f ( A1 ,..., An ) – формула алгебры множеств. Тождество f ( f U ) справедливо тогда и только тогда,когда для любых Ai {U , } , i 1,2,..., n, выполняется равенствоf ( A1 ,..., An ) ( f ( A1 ,..., An ) U ) .Для доказательства достаточно в утверждении 1.3 положитьg ( A1 ,..., An ) A1 A1 ( g ( A1 ,..., An ) A1 A1 U ).Покажем теперь, что справедливоУтверждение 1.9.
Пусть f ( A1 ,..., An ) , g ( A1 ,..., An ) – формулы алгебры множеств. Тогда утверждение f g выполняется тогда и только тогда, когда справедливо тождество g \ f .Действительно, если справедливо утверждение f g ,то при Ai {U , } , i 1,2,..., n, в силу утверждения 1.2, выполняетсяравенство g ( A1 ,..., An ) \ f ( A1 ,..., An ) , а следовательно, в силу ут14верждения 1.8 справедливо тождество g \ f . Рассуждение в обратную сторону очевидно.Используя (1.4),(1.6), а также утверждение 1.9, нетрудно показатьсправедливость следующего утверждения.Утверждение 1.10. Пусть f1 ( A1 ,..., An ) , f 2 ( A1 ,..., An ) ,g1 ( A1 ,..., An ) , g 2 ( A1 ,..., An ) – формулы алгебры множеств.