Дискретная математика. Краткий курс. Учебное пособие. Александр Анатольевич Казанский
Читать онлайн книгу.
АС ∩ ВС ∩ С, поглощаемое 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 ∩ С) ∪ (В ∩ С).
Заметим также, что метод соседних произведений можно использовать и при эквивалентных преобразованиях выражений, чтобы уменьшить число произведений, входящих в упрощаемый многочлен. Это