В.Н. Нефедов - Алгебра множеств, бинарные отношения в примерах и задачах (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 )  AB C   ABC   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 ) выполняется:xAxAнетдаданетТабл.

1.1xAxBx AB x AB x A\ BxB \ A x A B  ( A \ B)  ( B \ A)даданетнетданетданетдададанетданетнетнетнетданетнетТабл. 1.29нетнетданетнетдаданетИспользуя эти таблицы, докажем табличным методом справедливость уже доказанного тождества (1.1). Действительно, для произвольного x  U имеем:xAxBxCдадададанетнетнетнетдаданетнетдаданетнетданетданетданетданет***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):AUAUТабл. 1.3Соответственно, табл. 1.2 идентична табл. 1.4 (в том же смысле,что и для таблиц 1.1,1.3)AUUBUUA BUUUA BUA\ BUB\ AUA BUUТабл.1.4Из идентичности приведенных таблиц следует, что справедливостьлюбого тождества можно проверить табличным методом, проверяя егосправедливость лишь при значениях символов множеств, входящих в10него, выбираемых из {U , }.

Описанный табличный метод обладаетрядом достоинств: (а) описан в виде алгоритма с простыми легко выполняемыми шагами; (б) легко программируется на ЭВМ; (в) если проверяемое тождество не верно, то при использовании табличного методаполучаем пример множеств, для которых оно не выполняется.Пример 1.9. Проверим справедливость тождества A \ ( B \ C )  A \ (C \ B). Составим соответствующую таблицу и сравним столбцыв этой таблице, выделенные символами * и **):ABCUUUUUUUUUUUUB\CUU***A \ (B \ C)A \ (C \ B)UUUC\BUUUUUИз приведенной таблицы следует, что, например, при 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 ) – формулы алгебры множеств.

Характеристики

Список файлов книги