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

же элементы данного множества. Например, пусть имеются два выражения в нормальной форме:

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

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

      Эти формулы эквивалентны, что нетрудно проверить, если преобразовать каждую из них к полной нормальной форме, которая и для Е1 и для Е2 одна и та же:

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

      Для того чтобы определить, какая из эквивалентных формул «проще», введем следующие обозначения. Пусть Е – выражение в нормальной форме и пусть L(E) – количество литералов в этом выражении (считаются все вхождения) и F(E) – количество произведений, из которых образовано Е. Так, для Е1 значение L(E1) = 2 + 2 = 4 и F(E1) = 2, а L(Е2) = 2 + 2 + 3 = 7 и F(E2) = 3.

      Пусть Е1 и Е2 эквивалентные выражения в нормальной форме. Тогда Е1 проще Е2 если

      L(E1) < L(Е2) и F(E1) < L(Е2) или

      L(E1) < L(Е2) и F(E1) < L(Е2).

      Выражение Е, представленное в нормальной форме, называется минимальным, если не существует никакого другого эквивалентного ему выражения, которое проще, чем Е. Следует заметить, что может существовать более одного эквивалентного минимального выражения.

      Произведение Р называется простым импликантом, для выражения Е, если

      Р ∪ Е = Е

      и нет никакого другого произведения, содержащегося в Р, которое обладает этим свойством. Например, пусть

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

      Можно показать, что выражение

      (АС ∩ В) ∪ Е = Е, но АС ∪ Е ≠ Е и В ∪ Е ≠ Е.

      Поэтому АС ∩ В является простым импликантом Е.

      Теорема 1.3. Любое выражение Е, представленное в минимальной форме, является объединение простых импликантов Е.

      Методы определения минимальных форм обычно базируются на алгоритмах, которые позволяют находить простых импликантов и выбирать из них те, которые и дают выражения в минимальной форме. Для определения простых импликантов имеется метод соседства (его также называют методом консенсуса), который состоит в следующем. Пусть Pi и Pj – такие два произведения, что одно из них содержит литерал Х, а другое ХС (т. е. какая-то переменная в одно произведение входит без дополнения, а в другое с дополнением и других переменных с этим свойством в данных произведениях нет). Тогда соседством Pi и Pj будет называться произведение (без повторений), составленное из литералов Pi и Pj, из которых удалены Х и ХС, а сами Pi и Pj называются соседними. Соседство не определено, если Pi = X и Pj = XC.

      Из определения соседства следует следующее утверждение:

      если S является соседством Pi и Pj, то тогда

      Pi ∪ Pj ∪ S = Pi ∪ Pj.

      Пример 1.9. Найти соседство S для P1 и Р2.

      1) P1 = (А ∩ В) и Р2 = (ВС ∩ СС), удалим В и ВС и образуем пересечение P1 и Р2 получим S = А ∩ СС.

      2) P1 = АС ∩ ВС ∩ С и Р2 = ВС ∩ СС, удалим С и СС, получим без повторений S = АС ∩ ВС.

      3) P1 = В и Р2 = ВС ∩ СС, удаление В и ВС дает S = СС.

      4) P1 = АС ∩ ВС