8.8. Минимизация переключательных функций методом неопределенных коэффициентов

Можно показать, что любая переключательная функция представима в так называемой универсальной нормальной форме (УНФ), например, для n=2:

Такое выражение – дизъюнкция всевозможных импликант каждой конституенты. В УНФ каждый из неопределенных коэффициентов описывает вхождение () или невхождение () соответствующей импликанты в выражение функции. Путем определения этих коэффициентов и производится минимизация. Представим УНФ в несколько иной форме:

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

Минимизируем, например, функцию «импликация» которая равна нулю на единственном наборе 10. Тогда получим:

Видим, что импликанта покрывает наборы 00(0) и 01(1), импликанта x₂ – наборы 11(3) и 01(1). Поэтому

Что и требовалось показать.