Дискретная математика. Краткий курс. Учебное пособие. Александр Анатольевич Казанский
Читать онлайн книгу.
же элементы данного множества. Например, пусть имеются два выражения в нормальной форме:
Е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 = АС ∩ ВС