2015-02-27
1624
Метод применим для минимизации функций алгебры логики от любого числа переменных.
Рассмотрим случай трех переменных. Булева функция в ДНФ может быть представлена в виде всевозможных конъюнктивных членов, которые могут входить в ДНФ:
где kО{0,1} ‑ коэффициенты. Метод заключается в подборе коэффициентов таким образом, чтобы получаемая ДНФ была минимальной.
Если теперь задать всевозможные значения переменных от 000 до 111, то получим 2n (23 =8) уравнений для определения коэффициентов k:
;
;
;
;
;
;
;
.
Рассматривая наборы, на которых функция принимает нулевое значение, определяют коэффициенты, которые равны 0, и вычеркивают их из уравнений, в правой части которых стоит 1. Из оставшихся коэффициентов в каждом уравнении к единице приравнивают по одному коэффициенту, определяющему конъюнкцию наименьшего ранга. Остальные коэффициенты приравнивают к 0. Итак, единичные коэффициенты k определяют соответствующую минимальную форму.
Пример. Минимизировать заданную функцию
,
если известны значения: 
; 
; 
; 
; 
; 
; 
; 
.
Решение.
=1;
=0;
=0;
=0;
=1;
=1;
=1;
=1.
После вычеркивания нулевых коэффициентов получим:
=1;
=1;
=1;
=1;
=1.
Приравняем к единице коэффициент 
, соответствующий конъюнкции наименьшего ранга и обращающий четыре последних уравнения в 1, а в первом уравнении целесообразно приравнять к 1 коэффициент 
. Остальные коэффициенты приравнивают к 0.
Ответ: вид минимизированной функции 
.
Следует отметить, что метод неопределенных коэффициентов эффективен, когда число переменных невелико и не превышает 5-6.
