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

АС ∩ ВС ∩ С, поглощаемое AC ∩ С)

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

      (для соседних произведений (А ∩ ВС ∩ СС) и (АС ∩ ВС ∩ СС) добавлено (ВС ∩ СС))

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

      (удалены (А ∩ ВС ∩ СС) и (АС ∩ ВС ∩ СС) поглощаемые (ВС ∩ СС))

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

      (для соседних произведений (ВС ∩ СС) и (AC ∩ С) добавлено (AC ∩ ВС))

      = (AC ∩ ВС) ∪ (ВС ∩ СС) ∪ (AC ∩ С)

      (для соседних произведений (AC ∩ С) и (А ∩ В ∩ С) добавлено (В ∩ С))

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

      (удалено (А ∩ В ∩ С), поглощаемое (В ∩ С))

      = (AC ∩ ВС) ∪ (ВС ∩ СС) ∪ (AC ∩ С) ∪ (В ∩ С).

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

      E = (AC ∩ ВС), (ВС ∩ СС), (AC ∩ С) и (В ∩ С).

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

      Алгоритм 1.4 для нахождения минимальной формы в выражении, представляющем собой объединение простых импликантов.

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

      Шаг 1. Представим каждый простой импликант в виде объединения фундаментальных произведений (используя алгоритм преобразования выражения к полной нормальной форме объединения пересечений).

      Шаг 2. Последовательно удалим из Е каждый такой имликант, все фундаментальные произведения которого имеются среди фундаментальных произведений остающегося выражения.

      Пример 1.11. Применим этот алгоритм для выражения, полученного в примере 1.10:

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

      Выразим каждый простой импликант в виде объединения фундаментальных произведений:

      AC ∩ ВС= (АС ∩ ВС ∩ С) ∪ (АС ∩ ВС ∩ СС),

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

      AC ∩ С = (АС ∩ В ∩ С) ∪ (АС ∩ ВС ∩ С),

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

      Удалим импликант AC ∩ ВС, поскольку его фундаментальное произведение (АС ∩ ВС ∩ С) входит в выражение для третьего импликанта, а (АС ∩ ВС ∩ СС) входит в выражение для второго импликанта. Из оставшихся трех импликантов ни один этим свойством не обладает, поэтому алгоритм прекращает свою работу и минимальная форма для Е выглядит следующим образом:

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

      Заметим также, что метод соседних произведений можно использовать и при эквивалентных преобразованиях выражений, чтобы уменьшить число произведений, входящих в упрощаемый многочлен. Это