Алгоритмы минимизации булевых функций.

Число элементов элементарной конъюнкции назовем ее длиной.

Дизъюнктивная форма называется минимальной если она содержит наименьшее число букв из всех возможных дизъюнктивных форм представляющих данную функцию.

Свойства:

xy\/x x; xy\/x x (склеивание); xy\/ x xy\/ x \/x(полусклеивание)

Алгоритм QWAIN

Пусть функция задана в виде СДНФ считаем что длина конъюнкции = n

1) Проводим все возможные полусклеивания для элементарных конъюнкций длины n

2) Проводим все возможные поглащения конъюнкций длины n полученные в результате 1 пункта конъюнкциями длины n-1

3) Повторяем 1, 2 пункты с заменой n-1, n-2 т.д. до естественного обрыва процесса

Дизъюнктивная форма полученная при использовании алгоритма Qwain’а называется сокращенной.

Построение минимизирующей таблицы.

Отметим те случаи, когда короткая конъюнкция является частью длинной.

Очевидно, что короткая конъюнкция равна 1 в таблице истинности на той же строчке.

Выберем из элементарных конъюнкций сокращенные формы, подмножества конъюнкций таким образом, чтобы в каждом столбце было хоть по одной звездочке.