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

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

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

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

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

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

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

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

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

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

      Пример 1.7

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

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

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

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

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

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

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

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

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

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

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

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

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