двумя импликантами, что и доказывает минимальное покрытие на рис. 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 и
<