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

Доказать, что (а) A  B    B  A ; (б)A\ B    B  A .20Решение. (а) Используя (1.4), имеем A  B    B  A    B \ A    B  A . (б) Используя (а), имеем A \ B    A B    B  A .Задача 1.5. Выразить операции ,,\ через (а) , ; (б) , ; (в)\,  .Решение. (а) Для сокращения записи будем, как и ранее, писатьAB вместо A  B и считать  самой «сильной» двухместной операцией, выполняемой в первую очередь. Используя тождество 13, имеем( A  B) AB   , а следовательно (см.

задачу 1.3), ( A  B)  AB  ( A  B)  AB  ( A \ B)  ( B \ A)  AB  AB  BA  AB  A( B  B )  BA  AU  BA  A  BA  ( A  B)( A  A )  ( A  B)U  A  B ; ( A  B) A  [( A \ B)  ( B \ A)] A  ( A \ B) A  ( B \ A) A  AB A  BA A  AB  A \ B .(б) Используя выкладки из задачи 1.3, получаем( A  B)  ( A  B)  AB ; ( A  B)  B  [( A  B) \ B] [ B \ ( A  B)]  ( A  B) B  B( A  B)  AB  BB  BA B  AB  A \ B .(в) ( A \ B)  B  AB  B  [( AB ) \ B]  [ B \ ( AB )]  AB B  B AB  AB  B( A  B)  AB  B  ( A  B)( B  B)  A  B ;A \ ( A \ B)  A( AB )  A( A  B)  AA  AB  AB.Задача 1.6. Доказать, что нельзя выразить (а) \ через , ; (б) через ,\ .Решение.

(а) Предположим, что A \ B  f ( A, B) , где f – формулаалгебры множеств, в которой используются только операции , ;A, B – произвольные множества (точнее, произвольные подмножестванекоторого универсального множества U ). Тогда при подстановкеA  U , B  U слева получаем  , а справа U , т.е. пришли к противоречию.21(б) Предположим, что A  B  f ( A, B) , где f – формула алгебрымножеств, в которой используются только операции ,\ ; A, B – произвольные множества (точнее, произвольные подмножества некоторогоуниверсального множества U ).

Обозначим через l ( f ) количество операций ,\ в формуле f («длина» формулы f ). Докажем индукциейпо длине формулы f , что найдутся A, B  {,U } такие, чтоA  B  U и f ( A, B)   . Если l ( f )  0 , то либо f  A , либоf  B . В первом случае f (,U )   , во втором f (U , )   и  U  U    U . Предположим, что для некоторого n  0 указанное утверждение выполняется для любой формулы f с l ( f )  n .Покажем его справедливость для любой формулы f с l ( f )  n  1.Возможны случаи: f ( A, B)  f1 ( A, B)  f 2 ( A, B) , f ( A, B)  f1 ( A, B) \ f 2 ( A, B) , где l ( f1 )  n , l ( f 2 )  n . В силу индуктивногопредположения в любом из этих случаев для f 1 найдутсяA, B  {,U } такие, что A  B  U и f1 ( A, B)   .

Но тогда иf ( A, B)   , в то время, как A  B  U , т.е. для формулы f любойдлины не может выполняться A  B  f ( A, B) .Задача 1.7. Доказать или опровергнуть следующие утверждения:(а) A  B  B \ C  A  B  C; (б) A  B  B  C  A  B \ C; (в)A  B  B  C  A  C \ B; (г) A  B  B  C  A  B  C .Решение.

(а) В силу утверждения 1.6, проверка этого утверждениясводится к проверке выполнения тождества ( A  B)  ( B \ C )  A  ( B  C ) , для чего составим таблицуABCABB\C( A  B)  ( B \ C )BCA  (B  C)UUUUUUUUUUUUUUUUUUUUUUUU22UUUUСравнивая шестой и восьмой столбцы этой таблицы, заключаем осправедливости проверяемого тождества (см. утверждение 1.3), а такжео справедливости проверяемого утверждения.

Остальные утвержденияпроверяются аналогично.Задача 1.8. Доказать или опровергнуть следующие утверждения:(а) A \ (C \ B)  A  B  A \ C  A  B; (б) A  B  B  ( A  C )  C  A; (в) A  (C \ B)  A  C  A  C  B ; (г) A  ( B  C)  A  C  C  B; (д) A \ (C \ B)  A \ B  C  A  B;(е) A \ ( B  C )  A \ B  B  A  C .Решение. (а) В силу утверждения 1.7, проверка этого утверждениясводится к проверке выполнения тождества ( A \ (C \ B))  ( A  B)  ( A \ C ) \ ( A  B) , которое легко проверяется с помощью таблицы(см.

утверждение 1.3). Остальные утверждения проверяются аналогично.Задача 1.9. Найти необходимое и достаточное условие для X (вида g ( A, B)  X  f ( A, B) , где g ( A, B), f ( A, B) – формулы алгебрымножеств), если A  X  B  X .Решение. Последовательно применяя шаги 1– 6 алгоритма 1.1, используя (1.5), получаем:A  X  B  X  AX  BX    ( AX \ BX )  ( BX \ AX )    AX BX  BX AX    AX ( B  X )  BX ( A  X )    AX B  AX X  BX A  BX X    ABX  B AX    ( AB  B A) X    [( A \ B)  ( B \ A)] X    ( A  B)  X    X  A  B .Задача 1.10. Решить систему уравнений относительно неизвестного множества X :23 A \ X  B, A  X  C.(1.13)Решение.

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

Решить систему уравнений относительно неизвестного множества X :A  X  B  X ,A  X  C  X.(1.14)24Решение. Последовательно применяя шаги 1– 6 алгоритма 1.1, получаем:(1.14)  [( A  X )  BX ]  [ AX  (C  X )]    [( A  X ) \ BX ]  [ BX \ ( A  X )]  [ AX \ (C  X )]  [(C  X ) \ AX ]    [( A  X ) BX ]  BX ( A  X )  AX (C  X )  (C  X ) AX    ( A  X )( B  X )  BXA X  AXC X  (C  X )( A  X )    AB  AX  XB  XX  CA  CX  A X  XX    AB  A C  , ( A  B )  X  , ( A  C )  X  .Необходимым и достаточным условием существования решенияэтой системы является (см.

утверждение 1.11) AB  A C  ,A  C  A  B  A  B , что, в силу (1.3), (1.4), равносильно условиюC  A  B (очевидно, что C  A  B  A  C  A  A  B ). В силуутверждения 1.11, единственным решением системы (1.14) в случаеC  A  B, является X  A .Тема №2. Упорядоченные пары. Прямое произведение множеств.Бинарные отношения. ФункцииПрямое произведение множеств. Упорядоченная параa, b ин-туитивно определяется как совокупность двух предметов a и b , расположенных в строго определенном порядке. Основное свойство упорядоченных пар состоит в том, что a, b  c, d  a  c, b  d.Упражнение 2.1.

Пустьa, b  {{a},{a, b}} . Доказать, чтоa, b  c, d  a  c, b  d.Указание. Отдельно рассмотреть случаи: a  b , a  b .Аналогично определяется упорядоченная n -ка25a1 , a2 ,..., an .Замечание 2.1. Можно определить: a1 , a2 , a3 a1 , a2 , a3 ,a1 , a2 , a3 , a4  a1 , a2 , a3 , a4 , и т.д.Основное свойство упорядоченных n -ок заключается в следующем:a1 , a2 ,..., an  b1 , b2 ,..., bn  a1  b1 ,..., an  bn .Прямым (декартовым) произведением множеств A1 , A2 ,..., An называется множество A1  A2      An  { a1 ,..., an | a1  A1 ,...,a n  An } .

В случае A1  A2      An  A будем кратко писатьA1  A2      An  An .Упражнение 2.2. Доказать, что если A1 , A2 ,..., An – конечные множества, то A1  A2      An nAi .i 1Указание. Воспользоваться рассуждениями, аналогичными доказательству утверждения 1.1.Пример 2.1.

Пусть A  {2;3}, B  {0;1;2}. Тогда A  B  { 2,0 ,2,1 , 2,2 , 3,0 , 3,1 , 3,2 }, B  A  { 0,2 , 0,3 , 1,2 , 1,3 , 2,2 , 2,3 }.Заметим, что в приведенном примере A  B  B  A , т.е. операция  вобщем случае не является коммутативной.Пример 2.2. Пусть A  [0;2], B  [0;1] . Тогда A  B   a, b a  [0;2], b  [0;1] – прямоугольник (см. рис.2.1).11Рис.2.1262Пример 2.3.

Пусть A – множество юношей, B – множество девушек. Тогда A B – множество супружеских пар, которые можно составить из A и B .Приведем некоторые тождества, связанные с прямым произведением множеств. Для любых множеств A, B, C, являющихся подмножествами некоторого универсального множества U , справедливы равенства:1. ( A  B)  C  ( A  C )  ( B  C );1 . A  ( B  C )  ( A  B)  ( A  C );2. ( A  B)  C  ( A  C )  ( B  C );2.

A  ( B  C )  ( A  B)  ( A  C );3. ( A \ B)  C  ( A  C ) \ ( B  C );3. A  ( B \ C )  ( A  B) \ ( A  C );4. ( A  B)  C  ( A  C )  ( B  C ) .4. A  ( B  C )  ( A  B)  ( A  C ) .Докажем тождество 1. Для любых x, y  U имеем:x, y  ( A  B)  C  x  A  B, y  C x  A  x, y  A  C y  C, xAxBx,yBC x, y  ( A  C )  ( B  C ) .С другой стороны, для любых x, y  U имеем:x, y  ( A  C )  ( B  C ) x, y  A  C  x  A, y  C x, y  A  C  x, y  B  C  x  B, y  C  x  A  B, y  C  x, y  ( A  B)  C .Докажем тождество 2. Для любых x, y  U имеем: x, y  ( A  B)  C  x  A  B, y  C  x  A, x  B, y  C  x, y  A  C, x, y  B  C  x, y  ( A  C )  ( B  C ) .Докажем тождество 3.

Для любых x, y  U имеем: x, y  ( A \ B)  C  x  A \ B, y  C  x  A, x  B, y  C  x, y  A  C, x, y  B  C  x, y  ( A  C ) \ ( B  C ) .27Докажем тождество 4. В силу доказанных тождеств 1, 3 имеем:( A  B)  C  [( A \ B)  ( B \ A)]  C  [( A \ B)  C]  [( B \ A)  C]  [( A  C) \ ( B  C)]  [( B  C ) \ ( A  C)]  ( A  C )  ( B  C ) .Тождества 1  4 доказываются аналогично тождествам 1– 4.Бинарные отношения. Введем понятие бинарного отношения.Бинарным отношением между элементами множеств A и B называется любое подмножество  прямого произведения A B . Если A  B ,то бинарное отношение  называется бинарным отношением на множестве A .

Вместо x, y   часто пишут xy .Пример 2.4. Пусть Л – множество всех людей. Рассмотрим бинарное отношение о  Л 2 такое, что  x, y  о  x является отцом y. Таким образом, о – бинарное отношение отцовства. Аналогичным образом можно определить бинарное отношение материнства м ,а также большое многообразие бинарных отношений на множестве всехлюдей Л : дружбы, любви, ненависти, вражды и т.д. (в том числе,большое многообразие родственных отношений: брат, сестра, двоюродный брат, сводный брат, племянник, внук и т.д.). Например, бинарноеотношение внук на множестве людей Л определяется следующимобразом: x внук y  z : [( y о z или y м z ) , ( z о x или z м x)] .Пример 2.5.