style="font-size:15px;"> Е = (А ∩ ВС) ∩ (С ∪ СС) ∪ (ВС ∩ СС) ∪ (А ∩ В ∩ С) = (А ∩ ВС ∩ С) ∪ (А ∩ ВС ∩ СС) ∪ (ВС ∩ СС) ∪ (А ∩ В ∩ С).
Шаг 2. Поскольку в Е имеется произведение ВС ∩ СС, которое не содержит переменной А, то снова переходим к шагу 1 и образуем произведение (ВС ∩ СС) ∩ (А ∪ АС),
Е = (А ∩ ВС ∩ С) ∪ (А ∩ ВС ∩ СС) ∪ (ВС ∩ СС) ∩ (А ∪ АС) ∪ ∪ (А ∩ В ∩ С).
После раскрытия скобок в Е образуется два одинаковых фундаментальных произведения А ∩ ВС ∩ СС. Одно из них необходимо удалить. Теперь Е представлено в полной нормальной форме:
Е = (А ∩ ВС ∩ С) ∪ (А ∩ ВС ∩ СС) ∪ (АС ∩ ВС ∩ СС) ∪ (А ∩ ∩ В ∩ С).
Таким образом, если имеется выражение, представленное в нормальной форме, то данный алгоритм позволяет алгебраическими преобразованиями привести его к полной нормальной форме. Однако этот способ не единственный. Для этой же цели можно также использовать и диаграммы Венна.
Рассмотрим пример. Пусть имеется разбиение множества U, показанное на рис. 1.10. Выделим множество, которое задается формулой (нормальной формой объединения пересечений) А ∪ (ВС ∩ С). Она задает объединение двух множеств: А = {4, 5, 6, 7} и множества, представляющего собой пересечение множеств ВС и С, т. е. множества ВС ∩ С = {1, 5}. Поэтому множество А ∪ (ВС ∩ С) = {1, 4, 5, 6, 7}. На рис. 1.12 это множество заштриховано. Из диаграммы видно, что множество А ∪ (ВС ∩ С) задается объединением пяти фундаментальных произведений: множеству {4} соответствует фундаментальное произведение А ∩ ВС ∩ СС, множеству {6} – А ∩ В ∩ СС, множеству {7} – А ∩ В ∩ С, множеству {5} – А ∩ ВC ∩ С и множеству {1} – АC ∩ ВС ∩ С. Объединение этих фундаментальных произведений и дает полную нормальную форму
(А ∩ ВС ∩ СС) ∪ (А ∩ В ∩ СС) ∪ (А ∩ В ∩ С) ∪ (А ∩ ВС ∩ ∩ С) ∪ (АС ∩ ВС ∩ С).
Рис. 1.12
Заметим, что для любого множества существует не только единственная полная нормальная форма объединения пересечений, но и единственная полная нормальная форма пресечения объединений. Эту форму также можно найти двумя способами. Так, для множества из предыдущего примера А ∪ (ВС ∩ С) раскроем скобки и получим выражение в нормальной форме пересечения объединений (А ∪ ВС) ∩ (А ∪ С). В первой скобке нет переменной С, а во второй переменной В. Поскольку выражение (С ∩ СС) = Ø, то следующее выражение эквивалентно исходному
((А ∪ ВС) ∪ (С ∩ СС)) ∩ ((А ∪ С) ∪ (В ∩ ВС)) = (А ∪ ВС ∪ С) ∩ (А ∪ ВС ∪ СС) ∩ (А ∪ В ∪ С) ∩ (А ∪ ВС ∪ С) = (А ∪ ВС ∪ С) ∩ (А ∪ ВС ∪ СС) ∩ (А ∪ В ∪ С).
Последнее выражение и будет полной нормальной формой пересечения объединений для исходной формулы.
Найти данное выражение можно также и при помощи диаграммы Венна. Поскольку в исходное множество {1, 4, 5, 6, 7} не вошли элементы {0, 2, 3 }, то необходимо образовать пересечение таких объединений, которые не содержат эти три множества. Объединение А ∪ В ∪ С не содержит
