применяется операция дополнения, к виду, в котором операция дополнения применяется только к переменным.
Шаг 2. Используя закон дистрибутивности объединения относительно пересечения, раскроем скобки, содержащие объединения литералов относительно операций пересечения.
Шаг 3. Используя законы ассоциативности, дополнения и идемпотентности, преобразуем каждое пересечение литералов либо в Ø, либо в произведение.
Шаг 4. Используя законы поглощения и тождества, упростим выражение Е, и если оно состоит из объединения пересечений, то нормальная форма получена, если же нет, то переходим к шагу 2.
Пример 1.7
Применим данный алгоритм для преобразования к нормальной форме следующего выражения:
Е = ((А ∩ ВС) ∪ (В ∩ СС)С) ∩ (((В ∩С) ∪ (АС ∩ С))С ∪ (А ∩ В)).
Шаг 1. Используя законы Де Моргана и инволюции, получим
Е = ((А ∩ ВС) ∪ ВС ∪ С) ∩ ((ВС ∪ СС) ∩ (А ∪ СС) ∪ (А ∩ В)).
Шаг 2. Используя закон дистрибутивности, раскроем скобки в правой части выражения:
Е = ((А ∩ ВС) ∪ ВС ∪ С) ∩ ((А ∩ ВС) ∪ (ВС ∩ СС) ∪ (А ∩ ∩ СС) ∪ (СС ∩ СС) ∪ (А ∩ В)).
Шаг 3. Преобразуем пересечение литералов в произведение:
Е = ((А ∩ ВС) ∪ ВС ∪ С) ∩ ((А ∩ ВС) ∪ (ВС ∩ СС) ∪ (А ∩ СС) ∪ ∪ СС ∪ (А ∩ В)).
Шаг 4. Поскольку ВС включается в А ∩ ВС, то А ∩ ВС поглощается, также СС включается в ВС ∩ СС и А ∩ СС, поэтому оба эти пересечения поглощаются и выражение Е принимает следующий вид:
Е = (ВС ∪ С) ∩ ((А ∩ ВС) ∪ СС ∪ (А ∩ В)).
Здесь снова надо раскрывать скобки, поэтому переходим к шагу 2.
Шаг 2. Раскроем скобки и получим:
Е = (А ∩ ВС ∩ВС) ∪ (ВС ∩ СС) ∪ (А ∩ В ∩ ВС) ∪ (А ∩ ВС ∩ ∩ С) ∪ (С ∩ СС) ∪ (А ∩ В ∩ С).
Шаг 3. Преобразуем пересечение литералов в произведение:
Е = (А ∩ ВС) ∪ (ВС ∩ СС) ∪ Ø ∪ (А ∩ ВС ∩ С) ∪ Ø ∪ (А ∩ ∩ В ∩ С).
Шаг 4. Пересечение А ∩ ВС включается в А ∩ ВС ∩ С, поэтому последнее поглощается и нормальная форма для Е имеет вид
Е = (А ∩ ВС) ∪ (ВС ∩ СС) ∪ (А ∩ В ∩ С).
1.13. Полные нормальные формы
Следует отметить, что терминология этого раздела не стандартизирована, так по аналогии с булевой алгеброй полные нормальные формы иногда называют совершенными нормальными формами. Рассмотрим выражение Е = Е(x1, x2, … xn), состоящее из объединения произведений, т. е. представленное в нормальной форме. Если каждое произведение состоит точно из n литералов, то такое выражение называется полной нормальной формой объединения пересечений.
Теорема 1.2. Любое выражение алгебры множеств может быть преобразовано к эквивалентному ему выражению в полной нормальной форме, и такое представление является единственным.
