Метод неопределенных коэффициентов

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

Рассмотрим случай трех переменных. Булева функция в ДНФ может быть представлена в виде всевозможных конъюнктивных членов, которые могут входить в ДНФ:

где kО{0,1} ‑ коэффициенты. Метод заключается в подборе коэффициентов таким образом, чтобы получаемая ДНФ была минимальной.

Если теперь задать всевозможные значения переменных от 000 до 111, то получим 2ⁿ (2³ =8) уравнений для определения коэффициентов k:

;

;

;

;

;

;

;

.

Рассматривая наборы, на которых функция принимает нулевое значение, определяют коэффициенты, которые равны 0, и вычеркивают их из уравнений, в правой части которых стоит 1. Из оставшихся коэффициентов в каждом уравнении к единице приравнивают по одному коэффициенту, определяющему конъюнкцию наименьшего ранга. Остальные коэффициенты приравнивают к 0. Итак, единичные коэффициенты k определяют соответствующую минимальную форму.

Пример. Минимизировать заданную функцию

,

если известны значения: ; ; ; ; ; ; ; .

Решение.

=1;

=0;

=0;

=0;

=1;

=1;

=1;

=1.

После вычеркивания нулевых коэффициентов получим:

=1;

=1;

=1;

=1;

=1.

Приравняем к единице коэффициент , соответствующий конъюнкции наименьшего ранга и обращающий четыре последних уравнения в 1, а в первом уравнении целесообразно приравнять к 1 коэффициент . Остальные коэффициенты приравнивают к 0.

Ответ: вид минимизированной функции .

Следует отметить, что метод неопределенных коэффициентов эффективен, когда число переменных невелико и не превышает 5-6.