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