8. Минимизация булевых функций

Всякую булеву функцию можно привести к дизъюнктивной нормальной форме (гл. 1,6) вида

где так называемые элементарные конъюнкции, т. е. конъюнкции, составленные из аргументов взятых с отрицанием или без него. Например, элементарными конъюнкциями являются выражения

Элементарная конъюнкция, в которую входят все аргументы, называется конституентой. Дизъюнктивная нормальная форма, составленная из конституент, называется совершенной дизъюнктивной нормальной формой. Используя формулу (1.17), можно записать всякую булеву функцию в совершенной дизъюнктивной нормальной форме.

Представление данной булевой функции в дизъюнктивной нормальной форме можно осуществить не единственным образом, например

В связи с этим может быть поставлен вопрос о приведении булевой функции к такой дизъюнктивной нормальной форме, которая была бы в некотором смысле наиболее простой (минимальной) по сравнению с другими дизъюнктивными нормальными формами.

В дальнейшем будем исходить из следующего определения: дизъюнктивная нормальная форма называется минимальной, если она содержит по сравнению с другими эквивалентными ей нормальными формами минимальное количество букв. (При подсчете букв учитывается каждое вхождение букв в форму).

Будем говорить, что функция своим значением накрывает значение функции если на некотором наборе аргументов

Функцию назовем импликантой функции если она своими нулями накрывает все нули функции

Справедливы следующие теоремы [6]:

Теорема 1. Рхли импликанты булевой функции то

также являются импликантами функции

Теорема 2. Если функция есть импликанта функции то функции также являются импликантами функции

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

Например, простыми импликантами функции являются конъюнкции

Теорема 3. Дизъюнкция всех простых импликант булевой функции совпадает с этой булевой функцией.

Дизъюнктивная нормальная форма, составленная из простых импликант, называется сокращенной нормальной формой. Может случиться, что некотррые простые импликанты, входящие в сокращенную дизъюнктивную нормальную форму, могут быть удалены и при этом значение функций не изменится ни в одной точке. Такие простые импликанты называются лишними. Сокращенная дизъюнктивная нормальная форма, из которой удалены все лишние импликанты, называется Туликовой дизъюнктивной нормальной, формой. Можно показать [6], что всякая минимальная дизъюнктивная нормальная форма является тупиковой.

Приведенные выше вспомогательные результаты дают возможность рассмотреть один из наиболее распространенных (методов минимизации — метод Квайна [6]. В методе Квайна используются две операции: склеивания и поглощения.

Операция склеивания определяется тождеством

Так как получим тождество, представляющее запись так называемой операции неполного склеивания

Операция поглощения определяется тождеством

Метод Квайна основывается на справедливости следующей теоремы.

Теорема Квайна. Если в совершенной дизъюнктивной нормальной форме произвести все возможные неполные склеивания, а затем все возможные поглощения, получим сокращенную дизъюнктивную нормальную форму.

Рассмотрим применение метода Квайна на следующем примере:

Пример 1. Пусть функция задана в совершенной дизъюнктивной нормальной форме

Склеивая 1-ю элементарную конъюнкцию последовательно со 2, 3, 4-й имеем:

После применения операции поглощения получим сокращенную дизъюнктивную форму в виде

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

Пример 2. Пусть функция задана совершенной дизъюнктивной нормальной формой

Применяя метод Квайна, получим сокращенную дизъюнктивную нормальную форму

Импликантная матрица строится так, как показано в табл. 4. Каждой простой импликанте соответствует строка таблицы. Под коиституентами, в которые входит данная простая импликанта, поставим звездочки. Каждая из конституент равна единице лишь для одного набора аргументов. Для этого набора аргументов будут равны единице те простые импликанты, которые расположены в строках, отмеченных звездочками. Поэтому чтобы накрыть единицами все единицы функции достаточно оставить

такие простые импликанты, чтобы в каждом столбце была хотя бы одна звездочка.

Таблица 4 (см. скан)

Из табл. 4 видно, что если вычеркнуть простую импликанту в каждом столбце будет по одной звездочке. Поэтому

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

С другими методами минимизации формул булевой алгебры (Мак-Класки, Блейка и др.) можно познакомиться по работам [6, 7, 20].