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

f(x1; x2; x3) =

=(x1 © 1)(x2 © 1)x3 © (x1 © 1)x2x3 © x1(x2 © 1)x3 =

=(x1x2 © x1 © x2 © 1)x3 ©x1x2x3 © x2x3©x1x2x3 © x1x3 =

=x1x2x3 © x1x3 © x2x3 © x3© x1x2x3 © x2x3©x1x2x3 © x1x3 =

=x1x2x3 © x3:

Подчеркнуты подобные удаляемые ЭК:

x1x2x3 © x1x2x3 © x1x2x3 = x1x2x3; x1x3 © x1x3 = 0: J

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

если

g(x1; : : : ; xn) ) f(x1; : : : ; xn);

или, что то же самое,

g(x1; : : : ; xn) ! f(x1; : : : ; xn) = 1:

Другими словами, g(x1; : : : ; xn) есть импликанта функции f(x1; : : : ; xn), если на всех тех векторах a1 ¢ ¢ ¢ an, на которых,

если g(a1; : : : ; an) = 1, то f(a1; : : : ; an) = 1: Таким образом, если K – любая ЭК из ДНФ функции f(x1; : : : ; xn), то K есть

импликанта этой функции.

Определение. Импликанта Ki функции f(x1; : : : ; xn) называется простой, если ее не поглощает никакая другая импликанта Kj этой функции.

ДНФ, состоящая из всех простых импликант функции f(x1; : : : ; xn); называется сокращенной ДНФ этой функции.

ДНФ называется минимальной, если она имеет наименьший ранг из всех ДНФ функции f(x1; : : : ; xn) (содержит наименьшее число литералов).

ДНФ называется кратчайшей, если она имеет наименьшую длину из всех ДНФ функции f(x1; : : : ; xn) (содержит наименьшее число ЭК).

ДНФ называется безызбыточной, если из нее нельзя удалить ни одной переменной и ни одной импликанты так, чтобы она оставалась равносильной исходной ДНФ.

З а м е ч а н и я. Любые минимальные и кратчайшие ДНФ являются безызбыточными. Кратчайшая ДНФ не обязательно минимальна, но поиск минимальной ДНФ проводится среди кратчайших. I

Задачи минимизации булевой функции: найти кратчайшую или минимальную ДНФ; найти все кратчайшие или все минимальные ДНФ. Каждый раз задача конкре-

тизируется. В любом случае сначала находятся все простые импликанты функции (сокращенная ДНФ). Из сокращенной ДНФ находят нужные ДНФ.

Пусть K; K1; K2 – элементарные конъюнкции, входящие в СДНФ, или в уже полученные ДНФ, реализующие исходную булеву функцию f(x1; : : : ; xn): Для минимизации ДНФ используются следующие свойства.

ДНФ, полученная в результате многократного применения склеек и поглощений, является сокращенной ДНФ, а все ЭК – простыми импликантами функции f(x1; : : : ; xn):

Примеры 3.21. 1. f(x1; x2; x3) = x¹1x¹2x¹3_x¹1x¹2x3_x1x¹2x¹3_x1x¹2x3:

Все импликанты простые, ни одна из них не поглощает другую.

Склеиваем импликанты 1, 3 и 2, 4 по переменной x1.

f(x1; x2; x3) = x¹2x¹3 _ x¹2x3:

Снова все импликанты простые, ДНФ сокращенная. Еще ода склейка по переменной x3:

f(x1; x2; x3) = x¹2:

ДНФ сокращенная, кратчайшая, минимальная, равносильная исходной функции (все преобразования были равносиль-

ными). В результате склеек были удалены и фиктивные переменные x1 и x3:

2. Мажоритарная функция.

f(x1; x2; x3) = x¹1x2x3 _ x1x¹2x3 _ x1x2x¹3 _ x1x2x3:

Склеиваем импликанты 1, 4 по переменной x1 и импликанты 2, 4 по переменной x2 :

f(x1; x2; x3) = x2x3 _ x1x3 _ x1x2 _ x1x2x¹3 = x1x2 _ x1x3 _ x2x3:

Импликанта x1x2x¹3 поглощена импликантой x1x2: J

Исторически идея нахождения сокращенной ДНФ путем многократных склеиваний/поглощений формулируется как теорема Квайна.

Теорема 3.8 (Квайна) Для получения сокращенной ДНФ из СДНФ нужно выполнить все возможные неполные склеивания соседних импликант, а затем все поглощения импликант.

Д о к а з а т е л ь с т в о . Действительно, после всех склеиваний и поглощений все оставшиеся импликанты будут простыми (никакая из импликант не поглощает другую), а ДНФ – сокращенной. £

Алгоритм строит сокращенную ДНФ из таблицы функции или буквенной записи СДНФ. Алгоритм основан на теореме Квайна. Модификация МакКласки заключается в упорядочении импликант по весам. Рас-

смотрим на примере последовательность шагов алгоритма. Пример 3.22. Найти сокращенную ДНФ булевой функции.

1. Импликанты СДНФ задаются таблицей, состоящей из их двоичных номеров (векторов). Векторы группируются по весам (числу единиц в векторе). Номер группы Gi равен весу векторов в группе. Таким образом, соседние импликанты находятся в соседних по номерам группах.

2. Выполняются неполные склеивания всех соседних импликант в соседних группах Gi и Gi+1. Разбиение на группы позволяет сократить число попарных сравнений при склеивании. Склеиваемые импликанты помечаются значком ¤. Результаты склеиваний (склейки) вместе с непомеченными импликантами заносятся в новую таблицу (без повторений). В склейках значком £ помечается переменная, по которой выполнена склейка (вес значка £ равен 0). В правом столбце показаны номера склеенных импликант из предыдущей таблицы.

3. Если полученная таблица непуста, то с ней выполняется 2-й шаг алгоритма. Импликанты в этой таблице уже упорядочены по весам. Склеивание можно выполнять только для тех импликант, у которых £ находятся в одинаковых позициях. Получаем новую таблицу.

Первая импликанта получена при склеивании импликант (1; 4) и (2; 3) из предыдущей таблицы, импликанты 2); 3) внесены как непомеченные. В этой таблице нет соседних импликант, работа алгоритма закончена. В результате получена сокращенная ДНФ f = abc _ ad¹ _ bcd длины 3 и ранга 8.

Алгоритм нахождения сокращенной ДНФ из СДНФ или равносильной ей ДНФ основан на выполнении всех возможных обобщенных склеиваний и всех возможных поглощений. Исторически идея этого алго-

ритма формулируется как теорема Блейка.

Теорема 3.9 (Блейка) Сокращенную ДНФ булевой функции можно получить, выполнив все обобщенные склеивания и все возможные поглощения.

Рассмотрим на примере работу алгоритма. Пример 3.23. Булева функция задана ДНФ

Представим импликанты ДНФ троичными векторами, заменив недостающие переменные значком £. В обобщенном склеивании xK1 _ xK¹ 2 = xK1 _ xK¹ 2 _ K1K2 участвуют только смежные импликанты, ортогнальные по переменной x. Результат обобщенного склеивания K1K2 вносится в таблицу (без повторений) со следующим по счету номером; при этом в графу С вносятся номера склеиваемых векторов; в строку графы П вносится номер вектора, который ее поглощает.

Вектор 5 сразу поглощается вектором 6; вектор 7 получается при склеивании векторов 1 и 2, вектор 8 – из 1 и 3, вектор 9 – из 1 и 6, вектор 10 – из 3 и 4; вектор 4 поглощается вектором 10; из склеивания векторов 3 и 7 получается вектор 11, который поглощает векторы 2, 3, 7 и 8. Склеивания других векторов дают повторения: например, склеивание векторов 9 и 11 дает вектор 1.

Непоглощенные векторы есть простые импликанты полученной сокращенной ДНФ:

Алгоритмы Квайна – МакКласки и Блейка

– Порецкого находят сокращенную ДНФ булевой функции. На втором этапе минимизации выполняется поиск кратчайшей

или минимальной ДНФ. Для этого нужно в сокращенной ДНФ найти такие подмножества импликант, которые поглощают все импликанты СДНФ.

Матрица, строкам которой соответствуют импликанты СДНФ, а строкам импликанты сокращенной ДНФ, называется таблицей Квайна Q = kqijk. Элемент таблицы qij = 1, если импликанта столбца j поглощает импликанту строки i, qij = 0 в противном случае.