используемое в правиле соседства:
(А ∩ В) ∪ (АС ∩ С) ∪ (В ∩ С) = (А ∩ В) ∪ (АС ∩ С).
Построим граф для этой формулы. Для этого найдем полную нормальную форму объединения пересечений:
Е = (А ∩ 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 не является натуральными числами. Возникает вопрос – почему же тогда задаются
