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

Аналогично если при n переменных объединение состоит из n литералов, то его называют фундаментальным объединением, и если заменить операции объединения на операции пересечения, а операции пересечения на операции объединения, то можно получить нормальную форму пересечения объединений и полную нормальную форму пересечения объединений. Выражение Е4 имеет нормальную форму пересечения объединений, а Е5 – полную нормальную форму пересечения объединений.

Любое выражение может быть преобразовано к эквивалентному выражению, имеющему нормальную форму. Одно из отличий нормальной формы в том, что в таком выражении операция дополнения применяется только к переменным. Чтобы избавиться от дополнений, применяемых к выражениям, надо применять закон де Моргана.

Алгоритм 1.1для преобразования выражения к нормальной форме объединения пересечений.

Пусть имеется исходное выражение алгебры множеств Е.

Шаг 1. Используя законы де Моргана и инволюции, приведем каждую скобку, к которой применяется операция дополнения, к виду, в котором операция дополнения применяется только к переменным.

Шаг 2. Используя закон дистрибутивности объединения относительно пересечения, раскроем скобки, содержащие объединения литералов относительно операций пересечения.

Шаг 3. Используя законы ассоциативности, дополнения и идемпотентности, преобразуем каждое пересечение литералов либо в Ø, либо в произведение.

Шаг 4. Используя законы поглощения и тождества, упростим выражение Е, и если оно состоит из объединения пересечений, то нормальная форма получена, если же нет, то переходим к шагу 2.

Пример 1.7

Применим данный алгоритм для преобразования к нормальной форме следующего выражения:

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

Шаг 1. Используя законы Де Моргана и инволюции, получим

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

Шаг 2. Используя закон дистрибутивности, раскроем скобки в правой части выражения:

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

Шаг 3. Преобразуем пересечение литералов в произведение:

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

Шаг 4. Поскольку В С включается в А ∩ В С, то А ∩ В С поглощается, также С С включается в В С ∩ С С и А ∩ С С, поэтому оба эти пересечения поглощаются и выражение Е принимает следующий вид:

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

Здесь снова надо раскрывать скобки, поэтому переходим к шагу 2.

Шаг 2. Раскроем скобки и получим:

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

Шаг 3. Преобразуем пересечение литералов в произведение:

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

Шаг 4. Пересечение А ∩ В С включается в А ∩ В С ∩ С , поэтому последнее поглощается и нормальная форма для Е имеет вид

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

Следует отметить, что терминология этого раздела не стандартизирована, так по аналогии с булевой алгеброй полные нормальные формы иногда называют совершенными нормальными формами. Рассмотрим выражение Е = Е( x 1, x 2, … x n), состоящее из объединения произведений, т. е. представленное в нормальной форме. Если каждое произведение состоит точно из n литералов, то такое выражение называется полной нормальной формой объединения пересечений.

Теорема 1.2. Любое выражение алгебры множеств может быть преобразовано к эквивалентному ему выражению в полной нормальной форме, и такое представление является единственным.

В предыдущем разделе было показано, как преобразовать любое выражение алгебры множеств к эквивалентному выражению в нормальной форме. Далее рассмотрим алгоритм, позволяющий трансформировать это выражение в эквивалентное ему выражение в полной нормальной форме. Идея этого алгоритма состоит в том, что если какое-то произведение Р в выражении Е не содержит i-й переменной, то ее можно вести в Е, образуя произведение Р ∩( x i∪ xic ) при i < n .

Алгоритм 1.2для преобразования выражения к полной нормальной форме объединения пересечений.

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

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

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

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

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

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

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

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

После раскрытия скобок в Е образуется два одинаковых фундаментальных произведения А ∩ В С ∩ С С. Одно из них необходимо удалить. Теперь Е представлено в полной нормальной форме:

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

Таким образом, если имеется выражение, представленное в нормальной форме, то данный алгоритм позволяет алгебраическими преобразованиями привести его к полной нормальной форме. Однако этот способ не единственный. Для этой же цели можно также использовать и диаграммы Венна.