Дискретная математика. Краткий курс. Учебное пособие. Александр Анатольевич Казанский

A

      B = {1, 2, 5, 6, 7}; A

      C = {1, 2, 6, 7, 8, 9}; B

      C = = {3, 5, 8, 9};

      (d) A ∪ (B ∩ C) = {1, 2, 3, 4, 6, 7};

      (e) (A ∩ B)C = {1, 2, 5, 6, 7, 8, 9};

      (f) (A ∪ B) ∩ (B ∩ C)C = {1, 2, 3, 5};

      (g) AC ∩ BC ∩ C = {8, 9}.

      1.10. Пусть

      S4 – множество всех положительных целых чисел, которые делятся без остатка на 4,

      S10 – множество всех положительных целых чисел, которые делятся без остатка на 10,

      S15 – множество всех положительных целых чисел, которые делятся без остатка на 15.

      Найти множество, которое будет их пересечением, т. е. множество S4 ∩ S10 ∩ S15.

      Наименьшее число множества пересечения можно найти простым перебором – оно должно делиться на каждое из чисел 4, 10 и 15. Запишем разложение на простые множители, для них 4 = 2 × 2, 10 = 2 × 5 и 15 = 3 × 5. Следовательно, в разложении этого наименьшего числа должны присутствовать числа 2, 3 и 5, их должно быть наименьшее количество, но при этом в разложении должны присутствовать все три пары 2 × 2, 2 × 5 и 3 × 5. Нетрудно написать такое разложение, это будет 2 × 2 × 3 × 5 = 60. Поэтому

      S4 ∩ S10 ∩ S15 = {60×k} = {60, 120, 180, …} и k = 1, 2, 3, …

      1.11. Показать, что для множеств А, В, С выполняется

      (А\В) ∩ (А\С) = А\(В ∪ С).

      Пусть A={1, 2, 3, 4, 7, 8}, B={4, 5, 6, 7}, C={6, 7, 8, 9}.

      Тогда A\B={1, 2, 3, 8}, A\C={1, 2, 3, 4} и их пересечение (А\В)∩(А\С)={1, 2, 3}. Затем найдем (B∪C)={4, 5, 6, 7, 8, 9} и А\(В∪С)={1, 2, 3}.

      1.12. Пусть А, В и С – целые числа. Тогда из равенства А – В = С, следует, что А = В + С. Можно ли иметь такое же соответствие для множеств? Если А, В и С множества и выполняется, что А\В = С, то верно и что А = В ∪ С.

      Такой случай возможен, например, для следующих множеств:

      A = {1, 2, 3, 4}, B = {3, 4}, C = {1, 2}.

      Здесь А\В = {1, 2} и равно С. Объединение В ∪ С = {1, 2, 3, 4} и равно А.

      Диаграммы Венна и подсчет количества элементов множеств

      1.13. Показать на диаграммах Венна справедливость следующего равенства:

      A\B = A ∩ ВC.

      Нарисуем две пересекающиеся области, помеченные А и В, как на рис. 1.24.

      Рис. 1.24

      На левом рис. 1.24 заштрихована область А\В, на среднем – область ВС и на правом двойной штриховкой показана область пересечения A ∩ ВC. Поскольку двойная штриховка правой диаграммы и штриховка левой диаграммы задают одну и ту же область (одно и то же множество), то это значит, что равенство доказано.

      1.14. Обозначим через n(A) количество элементов конечного множества А (называемое также мощностью множества). Пусть имеется два конечных множества А и В и требуется найти количество элементов их объединения, т. е. n(А ∪ В).

      Если эти множества не пересекаются, то тогда

      n(A ∪ B) = n(A) + n(B).

      Если имеется пересечение, то тогда разобьем их на подмножества. Множество А разобьем на два непересекающихся подмножества А ∩ ВС и A ∩ В, а множество В на два непересекающиеся подмножества В ∩ АС и A ∩ В, как показано на рис. 1.25

      Рис. 1.25

      Тогда n(A) = n(А ∩ ВС) + n(А ∩ В) и

      n(B) = n(B ∩ AС) + n(А ∩ В).

      Сложим эти равенства почленно и получим

      n(A) + n(B) = n(А ∩ ВС) + n(B ∩ AС) + n(А ∩ В) + n(А ∩ В).

      Из диаграммы видно, что