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

пересечений.

      Шаг 1. Пусть имеется выражение Е = Е(x1, x2, …xn), представленное в нормальной форме. Найдем произведение Р в выражении Е, которое не содержит i-й переменной, и образуем произведение Р∩(xi∪xic). Это не нарушает эквивалентности выражения, поскольку (xi∪xic) = U, а Р ∩ U = Р. Удалим повторяющиеся произведения (это возможно, поскольку Р ∪ Р = Р).

      Шаг 2. Повторяем шаг 1 до тех пор, пока каждое произведение в Е не станет фундаментальным произведением, т. е. каждое произведение не будет включать в себя все n переменных.

      Пример 1.8. Применим данный алгоритм для выражения Е в нормальной форме, полученного в примере 1.7, чтобы преобразовать его к полной нормальной форме.

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

      Шаг 1. Находим произведение А ∩ ВС, которое не содержит переменной С, и образуем произведение (А ∩ ВС) ∩ (С ∪ СС), получим

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

      Шаг 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

      Заметим, что для любого множества существует не только единственная полная нормальная форма объединения пересечений, но и единственная полная нормальная форма пресечения объединений. Эту форму также можно найти двумя способами. Так, для множества из предыдущего примера