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

(b) AB = {1, 2}; BA = {5, 6, 7}; AC = {1, 2, 3}; BC = {3, 5};

(c) 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}.

Тогда AB={1, 2, 3, 8}, AC={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. Показать на диаграммах Венна справедливость следующего равенства:

AB = 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(А ∩ В).

Из диаграммы видно, что объединение множеств (А ∩ ВС) ∪ (B ∩ AС) представляет собой множество А ∪ В, из которого удалено пересечение А ∩ В, поэтому сумма n(А ∩ ВС) + + n(B ∩ AС) эквивалентна n(А ∪ В) – n(А ∩ В), отсюда

n(A) + n(B) = n(А ∪ В) – n(А ∩ В) + n(А ∩ В) + n(А ∩ В) = = n(А ∪ В) + n(А ∩ В). Поэтому для любых конечных множеств А и В справедливо равенство

n(А ∪ В) = n(A) + n(B) – n(А ∩ В).

При трех множествах количество элементов объединения находится по формуле

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

Математической индукцией можно получить дальнейшее обобщение этого результата для любого конечного числа множеств m.

n(A1 ∪ A2 ∪ …Am) = n(A1) + n(A2) + … n(Am) – n(А1 ∩ A2) – … – n(Аm-1 ∩ Am) + n(A1 ∩ A2 ∩ A3) + … + n(Аm-2 ∩ Am-1 ∩ Am) – … – (-1)m-1n(A1 ∩ A2 ∩ … ∩ Am).

Знак плюс в этой формуле ставится, когда пересечение берется для нечетного числа множеств, а минус, если это число четно.

1.15. В логистическом центре торговой компании имеется информация о наличии на ее 56 торговых терминалах трех марок автомобилей: «рено», «ягуар» и «понтиак».

23 терминала имеют «рено»;

26 терминалов имеют «ягуары»;

30 терминалов имеют «понтиаки»;

10 терминалов имеют «рено» и «ягуары»;

14 терминалов имеют «рено» и «понтиаки»;

12 терминалов имеют «ягуары» и «понтиаки»;

6 терминалов имеют все три марки автомобилей.

Обозначим через А, В и С множество терминалов имеющих «рено», «ягуары» и «понтиаки» соответственно. Эта информация может быть представлена диаграммой Венна, как на рис. 1.26.

Рис. 1.26

Необходимо заполнить количеством терминалов каждую из 8 областей диаграммы, а также найти количество терминалов, на которые поступила только одна марка автомобиля.

Определим количество терминалов, на которых имеет хотя бы один автомобиль одной из трех марок, т. е. найдем количество элементов объединения n(А ∪ В ∪ C).

n(А ∪ В ∪ C) = n(A) + n(B) + n(C) – n(А ∩ В) – n(А ∩ ∩ C) – n(B ∩ C) + n(А ∩ В ∩ C) = 23 + 26 + 30–10 – 14–12 + 6 = 49.

Теперь можно найти количество терминалов, на которых нет ни одного автомобиля 56–49 = 7.

Все три марки имеются на 6 терминалах, отсюда:

10 – 6 = 4 терминала имеют «рено» и «ягуары», но не имеют «понтиаков»;

14 – 6 = 8 терминалов имеют «рено» и «понтиаки», но не имеют «ягуаров»;

12 – 6 = 6 терминалов имеют «ягуары» и «понтиаки», но не имеют «рено»;

23 – 4–8 – 6 = 5 имеют только «рено»;

26 – 4–6 – 6 = 10 имеют только «ягуары»;

30 – 8–6 – 6 = 10 имеют только «понтиаки».

Заполним диаграмму на рис. 1.27.

Рис. 1.27

Только одну марку автомобиля имеют 5 + 10 + 10 = 25 терминалов, что и видно из диаграммы на рис. 1.24.

Алгебра множеств и двойственность

1.16. Написать двойственное для каждого из выражений, представленных ниже: