Текст книги "Дискретная математика. Краткий курс. Учебное пособие"

1.16. Минимизация формул алгебры множеств на графе

Задание множества многочленом, представляющим собой объединение фундаментальных произведений (или этот многочлен образован каким-либо другим способом), может привести к достаточно сложному выражению. Часто на практике для определения его элементов необходимо иметь более простое выражение для задания того же самого множества. Кроме метода определения минимальных форм, рассмотренного в параграфе 1.14, известны методы минимизации, использующие матрицы, а также метод, основанный на картах Карно (Karnaugh maps). Однако наиболее простым и эффективным является метод, использующий неориентированные двудольные графы.

Декартовым произведением графовG1 × G2 называется граф, множество вершин которого состоит из всех упорядоченных пар (u, v) декартова произведения множеств U × V (где U – вершины из графа G1, а V — вершины из графа G2). Две вершины произведения соединены ребром тогда и только тогда, когда либо первые вершины пары совпадают, а вторые смежны в исходном графе, либо вторые вершины совпадают, а первые смежны в исходном графе.

Граф, называемый n-мерным кубом Qn, определяется рекурсивно:

Q1 = K2 (полный граф с двумя вершинами, или ребро),

Qn = K2 × Qn-1.

Каждый n-куб имеет 2n вершин и n × 2n ребер.

Найдем граф Q2, представляющий собой декартово произведение К2 × К2.

Образуем все пары декартова произведения U×V:

(u1v1) (u1v2) (u2v1) (u2v2).

Пары (u1v1) и (u1v2) образуют ребро, поскольку первая вершина каждой пары одна и та же u1, а вторые вершины v1 и v2 смежны. Пары (u1v1) и (u2v2) не образуют ребра, потому что нет совпадения вершин ни для первой, ни для второй пары. Граф Q2 показан на рис. 1.16.

Рис. 1.16

Кубы Q3 и Q4 показаны на рис. 1.17.

Рис. 1.17

Связь между фундаментальными произведениями и вершинами графа – это фактически связь между областями на диаграмме Венна. Если связать таким образом все области диаграммы Венна при двух переменных, то образуется граф, изоморфный графу Q2, при трех – графу Q3, при n – Qn. Граф Q3 для диаграммы Венна при трех переменных показан на рис. 1.18.

Рис. 1.18

Теорема 1.5

Каждое покрытие вершин графа, соответствующего формуле для n переменных, наименьшим числом кубов Qp, наибольшей размерности p (p = 0, 1, 2, …, n – 1), определяет все эквивалентные ей минимальные формулы.

Минимальная форма представляет собой объединение импликант покрытия. Каждый куб Qp задает один импликант минимальной формы.

Чтобы найти импликант для куба Qp, надо рассмотреть фундаментальные произведения для всех 2р вершин этого куба, выбрать из них те литералы, которые не изменяются ни на одной из вершин этого куба, и составить из них пересечение (без повторений).

Куб Q0 – это одна вершина, и поэтому импликант для него соответствует фундаментальному произведению.

Куб размерности 1 – это ребро, и его импликант имеет на один литерал меньше, чем фундаментальное произведение вершины, например если куб задается фундаментальными произведениями AС ∩ BС ∩ C и AС ∩ B ∩ C, то здесь не изменяются литералы AС и С. Поэтому импликант состоит из их пересечения АС ∩ С.

Куб размерности 2 состоит из четырех вершин, и если размерность задачи больше 2, то импликант имеет на две переменные меньше, чем фундаментальное произведение вершины. Например, если куб задается фундаментальными произведениями

A ∩ B ∩ C, A ∩ B ∩ CС, A ∩ BС ∩ C, A ∩ BС ∩ CС, то здесь только литерал А не изменяется во всех четырех фундаментальных произведениях, поэтому А и будет импликантом для этого куба.

Куб размерности 3 (при числе переменных больше 3) порождает импликант, у которого на три переменные меньше, чем в фундаментальном произведении, и т. д.

Пример 1.13. Найти минимальную форму для следующей формулы:

Е = (B ∩ C) ∪ (AС ∩ B ∩ C) ∪ (AС ∩ B) ∪ (AС ∩ CС).

Определим все фундаментальные произведения для формулы Е и получим

Е = (А ∩ B ∩ C) ∪ (AС ∩ B ∩ C) ∪ (AС ∩ B ∩ CС) ∪ (AС ∩ BС ∩ CС).

Разобьем вершины на четыре группы и получим следующий граф (рис. 1.19):

Рис. 1.19

Для минимального покрытия вершин этого графа необходимо два куба размерности 2 (два ребра) – рис. 1.20):

Рис. 1.20

Это покрытие дает минимальную форму для исходной формулы

Е = (B ∩ C) ∪ (АС ∩ CС).

Использование графов позволяет понять многие методы, используемые при определении минимальных форм. Например, упрощение, используемое в правиле соседства:

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

Построим граф для этой формулы. Для этого найдем полную нормальную форму объединения пересечений:

Е = (А ∩ B ∩ C) ∪ (A ∩ B ∩ СС) ∪ (Ac ∩ BС ∩ C) ∪ (Аc ∩ B ∩ C).

Разбив вершины на две группы, получим граф (рис. 1.21):

Рис. 1.21

Этот граф состоит из трех кубов размерности 2 (три ребра), однако наименьшее число кубов, которыми можно покрыть все его вершины, только два (все четыре вершины закрываются двумя ребрами А ∩ В и АС ∩ С). Поэтому вместо трех импликантов, имеющихся в представлении данного множества, оно имеет эквивалентное задание двумя импликантами, что и доказывает минимальное покрытие на рис. 1.21.

Пример 1.14. Найти минимальную форму для следующей формулы

Е = (A ∩ B ∩ CС) ∪ (A ∩ B ∩ C) ∪ (ВС ∩ C) ∪ (AС ∩ B ∩ C).

Определим все пять фундаментальных произведений для формулы Е и получим

Е = (А ∩ B ∩ C) ∪ (A ∩ B ∩ CС) ∪ (A ∩ BС ∩ C) ∪ (AС ∩ BС ∩ C) ∪ ∪ (AС ∩ B ∩ C).

Разобьем вершины на четыре группы, построим граф и найдем два его минимальных покрытия (рис. 1.22 и 1.23), т. е. имеются две эквивалентные минимальные формы.

Рис. 1.22

Рис. 1.23

Е1 = А ∩ B ∪ А ∩ С ∪ AС ∩ B;

Е2 = А ∩ B ∪ ВС ∩ С ∪ AС ∩ B и при этом

А ∩ B ∪ А ∩ С ∪ AС ∩ B = А ∩ B ∪ ВС ∩ С ∪ AС ∩ B.

1.17. Решенные задачи

Множества и подмножества

1.1. Определить, какие из следующих множеств правильно определены:

А = {1, 2, 3, 4 },

B = { a, d, c, d, f },

C = {x: x ∈ N и

=2},

D = { A, B, C },

Все множества определены правильно.

Множество А состоит из чисел. Строго говоря, числа – выдуманные объекты, их не существует. Они придуманы для того, чтобы записывать результаты счета. Поэтому более точно следовало бы говорить о множестве символов чисел, или множестве их имен. Однако очень часто, когда необходимо представить множество каких-то объектов, обычно представляют их имена.

Множество В задано списком букв, однако буква d повторяется дважды. С точки зрения определения это множество эквивалентно следующему: { a, d, c, f }, а такие разные списки могут приводить к недоразумениям. Поскольку во втором списке буква d выброшена из множества, то получается, что d ∉ B, в то же время очевидно, что d ∈ B. Чтобы избежать подобных недоразумений, более рационально задавать множества перечислением элементов без повторения одинаковых.

Множество С не содержит ни одного элемента, т. е. является пустым (C = Ø). В данном случае x должно быть равным нулю или – 8 и тогда

= 2, или

= 2, но ни 0, ни – 8 не является натуральными числами. Возникает вопрос – почему же тогда задаются пустые множества, если они не существуют? Причина в том, что это не всегда заранее известно. Например, если множество задано формулой и производится преобразование этой формулы, то может оказаться, что какая-то часть этой формулы не имеет элементов. Но наличие пустых множеств и наличие правил действий с ними позволяет выполнять преобразования и таких формул. С другой стороны, в настоящее время имеется множество улиц Москвы, на которых в течение дня бывают пробки. Однако никто не может дать гарантии, что не наступит время, когда это множество станет пустым.

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

1.2. Найти список элементов для каждого из множеств:

(а) А = {x: x ∈ N, x – нечетно и x < 10},

(b) B = {x: x ∈ N,

∈N и x < 50},

(c) C = {x: x ∈ N и

 < 3x}.

(a) А состоит из нечетных натуральных чисел, меньших 10, поэтому

A = {1, 3, 5, 7, 9};

(b) B состоит из натуральных чисел, меньших 50, для которых квадратный корень из выражения 4х + 1 является натуральным числом, поэтому

В = {2, 6, 12, 20, 30, 42};

(с) C состоит из натуральных чисел, для которых квадратный корень меньше кубического корня из утроенного х. Это выполняется для первых 8 натуральных чисел, поэтому

С = {1, 2, 3, 4, 5, 6, 7, 8 }.

1.3. Имеются следующие множества:

А = {1, 2}, B = { 1, 3, 5 }, C = {1, 2, 7, 9 }, D = {{1}, {2}}.

Определить, корректно ли поставлены символы ∈ и ⊆

(a) A ∉ C, потому что элементами множества C не являются множества.

(b) Ø ⊆ A, потому что Ø является подмножеством каждого множества.

(c) В ⊄ С, потому что элемент 4 ∈ В, но 4 ∉ С.

(d) A ⊆ С, потому что все элементы А также принадлежат и С.

(e) А ∉ D, потому что D не имеет элемента {1, 2}.

(f) 1 ∉ D, потому что элементом множества D является не число 1, а множество {1}.

(g) A ⊆ {1, 2,{1, 4}}, поскольку все элементы А являются элементами {1, 2,{1, 4}}

(h) {3} ∉ B, потому что 3 является элементом В, а {3} – нет.

1.4. Показать, что A = {2, 3, 4, 5} не является подмножеством В = {x: x ∈ N и х – простое число}.

Для доказательства необходимо показать, что в А есть по крайней мере один элемент, которого нет в В. Рассмотрим элемент 4 ∈ А, и поскольку 4 разлагается на произведение 4 = 2 * 2, то оно не является простым и поэтому не принадлежит множеству В.

1.5. Показать, что множество А = {a, d, c, d} является собственным подмножеством B = {a, b, c, d, f, g}.

Поскольку каждый элемент А принадлежит В, то А ⊆ В. Но в В есть элемент f ∉ A, поэтому А ≠ В и, следовательно, А является собственным подмножеством В, т. е. А ⊂ В.

1.6. Для множества А = {4, 6, 8, 10} найти его несобственное подмножество.

Несобственное подмножество А должно состоять из тех же самых элементов, что и само множество А, т. е. это множество {4, 6, 8, 10}.

Операции над множествами

1.7. Найти все пересечения и объединения следующих множеств:

A = (1, 2, 3, 4, 6}, B = {3, 4, 5, 7 }, C = {6, 7, 8}.

Пересечение множеств А и В состоит только из тех элементов, которые входят и в А и в В, а объединение – из тех элементов, которые входят в А, входят в В, а также тех, которые являются общими для них, т. е. входят в их пересечение:

А ∩ В = {3, 4} А ∩ C = {6} B ∩ C = {7} А ∩ В ∩ C = Ø,

A ∪ B = {1, 2, 3, 4, 5, 6, 7} A ∪ C = {1, 2, 3, 4, 6, 8} B ∪ C ={3, 4, 7, 8},

A ∪ B ∪ C = {1, 2, 3, 4, 5, 6, 7, 8}.

1.8. Даны пересечения и объединения множеств А, В и С.

А ∩ В = {4} А ∩ C = {5} B ∩ C = {7}

A ∪ B = {1, 2, 3, 4, 5, 6, 7} A ∪ C = {1, 2, 3, 4, 5, 7, 8, 9} B ∪ C = {4, 5, 6, 7, 8, 9}.

Найти множества A, B, C.

Нетрудно видеть, что А ∩ В ∩ C = Ø, потому что нет ни одного элемента, общего для всех трех пересечений А ∩ В, А ∩ C и B ∩ C. Найдем элементы множества А. Ясно, что А содержит элементы 4 и 5, поскольку они входят в пересечение А с В и А с C. Рассмотрим пересечение множеств A ∪ B и A ∪ C, оно состоит из элементов {1, 2, 3, 4, 5, 7} и включает в себя все элементы множества А и все элементы пересечения B ∩ C = {7}. Убрав элемент 7, мы и получим множество А = {1, 2, 3, 4, 5}.

Такое же рассуждение позволяет найти и множество В. Сначала найдем пересечение двух объединений A ∪ B и B ∪ C. Это будет множество {4, 5, 6, 7}. Затем удалим из него пересечение А ∩ C = {5}, которое не входит в В, и получим множество B ={4, 5, 6}.

Чтобы найти элементы С, найдем пересечение A ∪ C и B ∪ C, которое состоит из элементов {4, 5, 7, 8, 9}, и удалим из него пересечение А ∩ В = { 4}. Элемент 4 не может входить в С, поскольку он входит и в А, и в В. Если бы он входил и в С, то тогда пересечение А ∩ В ∩ C состояло бы из элемента 4, но оно пусто. Поэтому C = {5, 7, 8, 9}.

Найти множества А, В, С можно и при помощи других рассуждений. Например, найдем множество А. Для этого удалим из множества A ∪ B все элементы множества B ∪ C и получим множество {1, 2, 3}. Оно состоит из элементов множества А и не содержит тех элементов А, которые входят в пересечение А с В и А с С. Добавив эти элементы, мы и получим множество А = {1, 2, 3, 4, 5}.

1.9. Дано универсальное множество U = {1, 2, 3, 4, 5, 6, 7, 8, 9} и множества

A = { 1, 2, 3, 4} B = {3, 4, 5, 6, 7} C = {4, 6, 7, 8, 9}.

Найти:

(a) АС, ВС, СС;

(b) AB, BA, AC, BC;

(c) A

B, A

C, B

C;

(d) A ∪ (B ∩ C);

(e) (A ∩ B)C;

(f) (A ∪ B) ∩ (B ∩ C)C;

(g) AС ∩ BC ∩ C.

Вспомним, что:

дополнение АС состоит из тех элементов универсального множества, которые не входят в А;

разность множеств АВ состоит из тех элементов А, которые не принадлежат В;

симметрическая разность A

B состоит из тех элементов А или В, которые не входят в пересечение А и В.

(a) АС = {5, 6, 7, 8, 9}; BC = {1, 2, 8, 9}; CC = {1, 2, 3, 5};

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

(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 ∩ В)(A ∩ B ∩ C) = (A ∩ В) ∩ (AC ∪ BC ∪ CC) = тождество упражнения 1.13.

= (A ∩ В) ∩ (AC ∪ BC ∪ CC) =

= (A ∩ B ∩ АC) ∪ (A ∩ B ∩ ВС) ∪ (A ∩ B ∩ CC) = дистрибутивность

= Ø ∪ Ø ∪ (A ∩ B ∩ CC) = по закону дополнения

= A ∩ B ∩ CC по закону тождества.

(b) (A ∩ C)(A ∩ B ∩ C) = (A ∩ C) ∩ (AC ∪ BC ∪ CC) =

= (A ∩ C ∩ АC) ∪ (A ∩ C ∩ ВС) ∪ (A ∩ C ∩ CC) =

= Ø ∪ (A ∩ C ∩ BC) ∪ Ø = A ∩ B ∩ CC.

(c) (B ∩ C)(A ∩ B ∩ C) = (B ∩ C) ∩ (AC ∪ BC ∪ CC) =

= (B ∩ C ∩ АC) ∪ (B ∩ C ∩ ВС) ∪ (B ∩ C ∩ CC) =

= (B ∩ C ∩ АC) ∪ Ø ∪ Ø = AC ∩ B ∩ C.

(d) AC ∩ BC ∩ CС = (A ∪ B ∪ C)C = по закону де Моргана

= (U)C = Ø. замена и дополнение

(e) AС ∩ ВС = (AС ∩ ВС) ∩ (С ∪ CC) = поскольку (С ∪ CC) = U

= (AС ∩ ВС ∩ С) ∪ (AС ∩ ВС ∩ СC) = (AС ∩ ВС ∩ С) ∪ Ø = = (AС ∩ ВС ∩ С).

(f) AС ∩ СС = (AС ∩ CС) ∩ (B ∪ BC) = поскольку (B ∪ BC) = U

= (AС ∩ В ∩ СC) ∪ (AС ∩ ВС ∩ СC) = (AС ∩ В ∩ СC) ∪ Ø = = (AС ∩ В ∩ СC).

(g) BС ∩ СС = (BС ∩ CС) ∩ (A ∪ AC) = поскольку (A ∪ AC) = U

= (A ∩ ВC ∩ СC) ∪ (AСВС ∩ СC) = (A ∩ ВC ∩ СC) ∪ Ø = = (A ∩ ВC ∩ СC).

(h) (A ∩ В)(А ∩ В ∩ СС) = (A ∩ В) ∩ (А ∩ В ∩ СС)С = тождество упражнения 1.13.

= (A ∩ В) ∩ (AС ∩ ВС ∩ С) = (А ∩ В ∩ АC) ∪ (А ∩ В ∩ ВС) ∪ ∪ (А ∩ В ∩ C) =

= Ø ∪ Ø ∪ (A ∩ B ∩ CC) = по закону тождества

= A ∩ B ∩ C.

1.18. Доказать, что для заданного универсального множества U и любого множества А ⊆ U дополнение этого множества АС единственно.

Для доказательства используем стандартный математический подход, применяемый при доказательстве единственности. Предположим, что существует два различных дополнения для А и обозначим их как А1c и А2c. Тогда каждое из них должно удовлетворять условиям дополнения

А1c ∩ А = А2c ∩ А = Ø и А1c ∪ А = А2c ∪ А = U.

Поэтому

А1c = А1c ∩ U = А1c ∩ (А2c ∪ А) = по закону дистрибутивности

= (А1c ∩ А2c) ∪ (А1c ∩ А) = по закону дополнения

= (А1c ∩ А2c) ∪ Ø = по закону тождества

= А1c ∩ А2c.

Отсюда следует, что каждый х ∈ А1c является также и элементом

А1c ∩ А2c и из этого следует, что А1c является подмножеством А1c ∩ А2c, т. е. А1c ⊆ А1c ∩ А2c, но поскольку А1c ⊆ А2c по определению, то тогда А1c ⊆ А2c.

Пусть теперь

А2c = А2c ∩ U = А2c ∩ (А1c∪ А) =

Выполнив преобразования, как и в первом случае, получим

= А1c ∩ А2c, т. е. А2c ⊆ А1c, но из этого следует, что

А1c = А2c = АС.

Итак, мы предположили, что существует два дополнения, а затем показали, что они совпадают, и это доказывает единственность дополнения множества А.

1.19. Известно, что для чисел операция равенства является транзитивной, т. е. если a = b и b = c, то из этого следует, что a = c. Свойство транзитивности во многих случаях оказывается очень полезным. Например, если необходимо знать, равны ли все три числа a, b и c, то достаточно проверить равенство только двух любых пар, допустим a = b и b = c, третье равенство a = c можно не проверять – оно будет выполнено в силу транзитивности. Однако если рассматривать операцию ≠, то транзитивность не выполняется. Например, a = 2, b = 3, c = 2 и тогда a ≠ b, b ≠ c, но a = c. Для множеств также операция включения множеств А ⊆ В транзитивна, но операция ⊄ не является транзитивной. Доказать, что если А ⊄ В и В ⊄ С, то из этого не следует А ⊄ С.

Для доказательства достаточно рассмотреть следующий случай. Пусть А и В непустые непересекающиеся множества, и пусть А = С. Тогда А ⊄ В и В ⊄ С, но А ⊆ С.

1.20. Для любых множеств А, В и С доказать ложность следующего утверждения:

если A ∪ B = B ∪ C, то А = В.

Если С непустое множество, С = А и множество В = Ø, тогда А ∪ Ø = Ø ∪ С и А ≠ В.

1.21. Пусть А, В и С непустые попарно пересекающиеся подмножества U. Доказать ложность следующих утверждений:

(a) если А ⊆ (В ∩ С), то неверно, что А ∩ В ⊆ В ∩ С и А ∩ С ⊆ В ∩ С;

(b) если А ∩ В ⊆ В ∩ С и А ∩ С ⊆ В ∩ С, то тогда А ⊆ (В ∩ С);

(c) если А ⊆ (В ∩ С), то А ∩ В ≠ А ∩ С.

(a) Если А ⊆ (В ∩ С), то по определению пересечения А ⊆ В, А ⊆ С, но из этого следует, что А ∩ В = А и А ∩ С = А, т. е. А ∩ В = А ∩ С = А, и, значит, верно, что А ∩ В ⊆ В ∩ С и А ∩ С ⊆ В ∩ С. Поэтому исходное утверждение ложно.

(b) Для доказательства рассмотрим следующие множества. Пусть А = {1, 2, 3}, B = {3, 4, 5, 6}, C = {3, 4, 5}. Найдем

А ∩ В = {3}, В ∩ С = (3, 4, 5}, А ∩ С ={3}. Здесь оба пересечения и А ∩ В и А ∩ С включаются в В ∩ С, но множество А не включается в В ∩ С. Поэтому исходное утверждение ложно.

(c) Если А содержится в В ∩ С, то по определению операции пересечения оно сдержится и в В, и в С. Но если А содержится в В, то пересечением А ∩ В будет множество А. Поскольку А содержится в С, то пересечением А ∩ С также будет множество А. Значит, оба множества и А ∩ В и А ∩ С состоят из одних и тех же элементов и поэтому они равны, т. е. А ∩ В = А ∩ С.

1.22. Доказать, что операция разности множеств не ассоциативна, т. е.

(АВ)С ≠ А(ВС).

Преобразуем левую часть неравенства:

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

Преобразуем правую часть:

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

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

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

Множество левой части не совпадает с множеством правой части, и это доказывает, что операция разности множеств не ассоциативна.

1.23. Доказать, используя элементный метод, что если А, В и С подмножества универсального множества U и если А ⊆ В, то ВС ⊆ АС.

Пусть А, В и С подмножество универсального множества U. Рассмотрим любой элемент х ∈ ВС. По определению дополнения ВС ∩ В = Ø, поэтому если х является элементом ВС, то он не может быть элементом В, т. е. х ∉ В. Элемент х также не может принадлежать и множеству А, поскольку А ⊆ В, т. е. х ∉ А, но тогда х ∈ АС. Таким образом, показано, что для любого элемента х из множества ВС этот элемент принадлежит и множеству АС, т. е. ВС ⊆ АС.

1.24. Доказать, используя элементный метод, что если А ⊆ В, то

(a) А ∩ С ⊆ В ∩ С,

(b) А ∪ С ⊆ В ∪ С.

(a) Пусть х ∈ А ∩ С. Тогда х ∈ А и х ∈ С и поскольку А ⊆ В, то х ∈ В. Из того, что х принадлежит и В и С, следует, что он принадлежит их пересечению х ∈ В ∩ С. Это означает, что для любого х, входящего в множество А ∩ С, элемент х входит и в множество В ∩ С, т. е. А ∩ С ⊆ В ∩ С.

(b) Поскольку А ⊆ В, то ВС ⊆ АС (задача 1.23). Тогда для любого множества СС его пересечение с ВС будет включаться в его пересечением с АС (потому что нет ни одного элемента ВС, входящего в пересечение ВС ∩ СС и не являющегося элементам АС, но ВС ∩ СС могут быть элементы из АС, не являющиеся элементами ВС), т. е. ВС ∩ СС ⊆ АС ∩ СС. Затем, снова применяя результат задачи 1.23, получим, что (АС ∩ СС)С ⊆ (ВС ∩ СС)С. По закону де Моргана получим А ∪ С ⊆ В ∪ С, что и доказывает искомый результат.

1.25. Дано множество А = {1,2, 3, 4, 5, 6, 7, 8,9}. Какие из приведенных ниже семейств множеств являются разбиениями:

(a) {{1, 2, 3}, {2, 4, 5}, {6, 9}, {7, 8}},

(b) {{1, 3, 5}, { 7, 6}, {2, 4, 8, 9}},

(c) {{1, 2}, {3, 5, 6, 7}, {4, 8, 9}, {1, 2}},

(d) {{1, 2}, {3, 4, 5}, {7, 8}, {9}}.

(a) Не разбиение, потому что элемент 2 входит в {1, 2, 3} и {2, 4, 5}.

(b) Разбиение, потому что каждый элемент А принадлежит точно одному блоку.

(c) Разбиение, потому что можно игнорировать факт, что {1, 2} встречается дважды.

(d) Не разбиение, потому что нет элемента 6.

1.26. Пусть А и В непересекающиеся множества. Обозначим через Sa разбиение множества А, а через Sb – разбиение множества В. Доказать, что Sa ∪ Sb является разбиением множества А ∪ В.

Пусть х ∈ А ∪ В. Тогда х принадлежит либо А, либо В, поскольку эти множества не пересекаются. Если х∈А, тогда он принадлежит точно одному блоку Sa, а если х ∈ В, то он принадлежит точно одному блоку Sb. Отсюда х принадлежит точно одному блоку Sa ∪ Sb.

1.27. Симметрическая разность множеств А

В = (АВ) ∪ ∪ (ВА) = (А ∩ ВС) ∪ (АС ∩ В). Из определения очевидно, что симметрическая разность коммутативна, А

В = В

А. Пусть U является универсальным множеством. Доказать следующие свойства

:

(a) ассоциативность, т. е. (А

В)

С = А

(В

С),

(b) А

А = Ø,

(c) А

АС= U.

(a) Для доказательства ассоциативности (А

В)

С = = А

(В

С) преобразуем сначала левую часть выражения:

(А

В)

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

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

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

А

(В

С) = А

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

Преобразования обеих частей дают один и тот же результат, что и доказывает ассоциативность симметрической разности множеств:

(b) А

А = (А ∩ АС) ∪ (АС ∩ А) = Ø ∪ Ø = Ø,

(c) А

АС = (А ∩ (АС)С) ∪ (АС ∩ АС) = А ∪ АС = U.

Представление множеств формулами

1.28. Имеется универсальное множество U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} и множества А = {1, 2, 3, 6, 7, 8}, B = {3, 4, 5, 6, 7}, C = {6, 7, 8, 9, 10}. Найти формулу, задающую множество М = {3, 6, 7, 9, 10}. Нарисовать диаграмму Венна.

Множества А, В и С образуют покрытие множества U, потому что U = А ∪ В ∪ С. Однако множества покрытия могут пересекаться, поэтому, чтобы избежать дублирования, построим разбиение множества U фундаментальными произведениями множеств А, В, С. Для этого найдем их дополнения и фундаментальные произведения:

АС ={4, 5, 9, 10 }, ВС ={1, 2, 8, 9, 10 }, АС ={1, 2, 3, 4, 5 }.

АС ∩ ВС ∩ СС= Ø, АС ∩ В ∩ С = Ø

АС ∩ ВС ∩ С = {9, 10}, А ∩ ВС ∩ С = {8}

АС ∩ В ∩ СС = {4, 5}, А ∩ В ∩ СC = {3}

А ∩ ВС ∩ СС = {1, 2}, А ∩ В ∩ С = {6, 7}.

Чтобы покрыть множество М, необходимо ровно три фундаментальных произведения:

Для упрощения формулы, определяющей множество М, вынесем из первых двух произведений А ∩ В, получим

M = (А ∩ В ∩ СC) ∪ (А ∩ В ∩ С) ∪ (АС ∩ ВС ∩ С) = (А ∩ В) ∩ (СC ∪ С) ∪ (АС ∩ ВС ∩ С) = (А ∩ В) ∪ (АС ∩ ВС ∩ С).

Таким образом, получена формула М = (А ∩ В) ∪ (АС ∩ ВС ∩ С), однозначно определяющая множество М, заданное элементами {3, 6, 7, 9, 10}.

Нарисуем диаграмму Венна (рис. 1.28), множество М заштриховано.

Рис. 1.28

1.29. Даны множества А = {1, 2, 3, 4}, B = {2, 4, 6}, C = {4,5,6,7}. Универсальное множество U = А ∪ В ∪ С ∪ {8}. Определить, пересекаются или нет множества D и E, заданные следующими формулами:

D = (A ∩ BC) ∪ (A ∩ C),

E = (AC ∩ B) ∪ (AC ∩ CC).

Найдем дополнения множеств:

АС = {5, 6, 7, 8}, BC = {1, 3, 5, 7, 8}, CC = {1, 2, 3, 8} и пересечения:

A ∩ BС = {2,3}, A ∩ C = {4}, AC ∩ B = {6}, AC ∩ CC = {8}. Поэтому

D = {2,3} ∪ {4} = {2, 3, 4} и E = {6} ∪ {8} = {6, 8}. Отсюда, множества D и E не имеют общих элементов и, следовательно, их пересечение пусто.

Решить эту задачу можно и алгебраическим методом, без определения элементов множеств. Для этого образуем формулу, задающую пересечение множеств D ∩ E и, используя закон дистрибутивности, раскроем скобки в полученном выражении:

D ∩ E = ((A ∩ BC) ∪ (A ∩ C)) ∩ ((AC ∩ B) ∪ (AC ∩ CC)) = (A ∩ BC ∩ AC ∩ B) ∪ ((A ∩ BC ∩ AC ∩ CC) ∪ (A ∩ C AC ∩ B) ∪ ∪ (A ∩ C ∩ AC ∩ CC) = Ø ∪ Ø ∪ Ø ∪ Ø = Ø. Здесь также получается пустое множество, поскольку пересечение множеств D и E пусто.