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

… – (-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. Написать двойственное для каждого из выражений, представленных ниже:

      (a) A = (A ∩ BC) ∪ (A ∩ B),

      (b) B = (B ∩ U) ∪ (A ∩ B),

      (c) АС ∩ (AС ∪ U)С = Ø,

      (d) (AC ∪ BC) ∪ (A ∩ B) = U,

      (e) A ∩ BC ∩ C = (A ∩ C) ∩ (AC ∪ BC ∪ CC).

      Заменим все ∩, ∪,Ø и U в каждом равенстве и получим двойственные равенства:

      (a) A = (A ∪ BC) ∩ (A ∪ B),

      (b) B = (B ∪ Ø) ∩ (A ∪ B),

      (c) АС ∪ (AС ∩ U)С = U,

      (d) (AC ∩ BC) ∩ (A ∪ B) = Ø,

      (e) A ∪ BC ∪ C = (A ∪ C) ∪ (AC ∩ BC ∩ CC).

      1.17. Пусть имеются множества А, В, С и пусть универсальное множество U = A ∪ B ∪ C. Доказать следующие равенства:

      (a) A ∩ B ∩ CС = (A ∩ В)\(A ∩ B ∩ C),

      (b) A ∩ BC ∩ C = (A ∩ C)\(A ∩ B ∩ C),

      (c) AC ∩ B ∩ C = (B ∩ C)\(A ∩ B ∩ C),

      (d) AC ∩ BC ∩ CС= Ø,

      (e) AС ∩ BС ∩ C = AС ∩ ВС,

      (f) AC ∩ B ∩ CС= AС ∩ СС,

      (g) A ∩ BC ∩ CС= BС ∩ СС,

      (h) A ∩ B ∩ C = (A ∩ В)\(А ∩ В ∩ СС).

      (a) Преобразуем правую часть равенства

      (A