1.6. Минимизация функций

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

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

Нахождение минимальной ДНФ функции называется минимизацией.

Рассмотрим минимизацию логических функций, заданных таблично, методом неопределенных коэффициентов.

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

f(x,y,z) = a₁x a₂y a₃z a₄ a₅ a₆ b₁xy b₂xz b₃yz

b₄ y b₅ z b₆ x b₇ z b₈ x b₉ y b₁₀

b₁₁ b₁₂ c₁xyz c₂ yz c₃ xz c₄ xy

c₅ z c₆ y c₇ x c₈ . (1.9)

Найдем значения правых частей (1.9) при разных наборах переменных. Например, при x = y = z = 0 получим:

f( 0,0,0 ) = a₄ a₅ a₆ b₁₀ b₁₂ c₈ .

Подставляя в (1.9) всевозможные наборы переменных, получим систему уравнений:

a₄ a₅ a₆ b₁₀ b₁₁ b₁₂ c₈ = f( 1,1,0 ),

a₃ a₄ a₅ b₅ b₇ + b₁₂ c₅ = f( 0,0,1 ),

a₂ a₄ a₆ b₄ b₉ b₁₁ c₆ = f( 0,1,0 ),

a₂ a₃ a₄ b₃ b₄ b₅ c₂ = f( 0,1,1 ), (1.10)

a₁ a₅ a₆ b₃ b₆ b₈ c₇ = f( 1,1,0 ),

a₁ a₃ a₅ b₂ b₆ b₇ c₃ = f( 1,0,1 ),

a₁ a₂ a₆ b₁ b₈ b₉ c₄ = f( 1,1,0 ),

a₁ a₂ a₃ b₁ b₂ b₃ c₁ = f( 1,1,1 ).

Подставляя в правые части уравнений системы (1.10) значения f( x,y,z ), взятые из таблицы задания функции, получим более простую систему уравнений. Решая эту систему, найдем значения коэффициентов a_i, b_i, и c_i.

Пример. Найти минимальную форму для функции, заданной следующей таблицей:

Таблица 1.16

Подставляя значение f( 0, 0, 0 ) = 0 в первое уравнение системы (1.10) получим

a₄ = a₅ = a₆ = b₁₀ = b₁₁ = b₁₂ = c₈ = 0.

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

c₅ = 1

b₁ c₄ = 1 (1.11)

b₁ c₁ = 1

Так как мы ищем минимальную формулу, то во втором уравнении системы (1.11) надо положить, что c₄ = 0. Тогда получим, что b₁ = 1. Аналогично в третьем уравнении. Полагаем, что c₁ =0. Окончательно имеем: b₁ = 1, c₅ = 1, а остальные коэффициенты в (1.9) все равны нулю. Подставляя найденные коэффициенты в (1.9) получим минимальную дизъюнктивную форму данной функции в виде:

f ( x,y,z ) = x y z.

Далее полезно найти СДНФ этой функции и попытаться ее упростить. Результат упрощения может быть не однозначным. Кроме того, одна и та же функция может иметь несколько минимальных форм.

Пример. Для функции f( x,y,z ) = z y x z xy xyz существуют две эквивалентные минимальные дизъюнктивные формы:

xz y и x y z.

Следует отметить, что данный метод минимизации удобен для функции с числом переменных ≤ 5. Для функций с большим числом переменных разработаны различные алгоритмы минимизации. Тривиальный алгоритм решения этой задачи сводится к перебору всех эквивалентных формул (для данной функции), с числом букв, не превосходящих максимально возможного числа СНФ. В результате такого перебора будет обнаружено минимальное представление заданной функции. Однако, даже для функций, зависящих от небольшого числа переменных, такой алгоритм практически невыполним.

Обычно пользуются разными алгоритмами (более эффективными) для упрощения СНФ. Однако применение этих алгоритмов не гарантирует получения минимальных форм, но позволяет получать формы близкие к минимальным. В [2] дается алгоритм минимизации, основанный на операциях склеивания и поглощения.