Метод неопределённых коэффициентов.
Предназначен для получения линейных форм логических формул, может быть применен для минимизации логических формул для любого числа переменных. В ручном варианте применяют для числа переменных не более пяти. Логическую функцию представляют в виде ДНФ. В общем виде, например, для трех переменных она имеет следующий вид:
f(x1,x2,x3) = k11x1Ú k01x1Ú k12x2Ú k02x2Ú k13x3Ú k03x3Ú k1112x1x2Ú k1012x1x2Ú k12x1x2Ú k0112x1x2 Ú k0012x1x2 k1113x1x3Ú k1013x1x3Ú k0013x1x3 Ú k1123x2x3 Ú k1023x2x3Ú k0123x2x3Ú k0023x2x3Ú k111123x1x2x3Ú k110123x1x2x3Ú k101123x1x2x3Ú k100123x1x2x3Ú k011123x1x2x3Ú k010123x1x2x3Ú k001123x1x2x3Ú k000123x1x2x3
В этой дизъюнктивной норм. форме коэффициенты с индексами – это определенный коэффициент, принимающий значение 0 и 1 и подбирается таким образом, чтобы ДНФ была минимальная. Задавая различные наборы переменных x1,x2,x3 и приравнивая полученные выражения соответствующим значениям функции, получают систему уравнений для определения коэффициента к:
f(0,0,0) = k01Ú k02 Ú k03Ú k0012Ú k0023Ú k000123
f(0,0,1) = k01Ú k02 Ú k13Ú k0012Ú k0113Ú k0123Ú k001123
……………………………………………
f(1,1,1) = k11Ú k12 Ú k13Ú k1112Ú k1113Ú k1123Ú k111123
f(x1,x2,x3) = 0 Ú 1
Задание некоторой функции определяет значение первых частей системы: если f = 0 на соответствующем наборе переменных, то все коэффициенты входящие в уравнение, будут равны нулю. Это следует из свойства дизъюнкции. Тогда и в уравнении, где функция принимает единичное значение, надо вычеркивать все нулевые коэффициенты. Из оставшихся коэффициентов надо выбрать такой, который определяет темп наименьшего, и приравнять его к единице. А остальные коэффициенты приравнять к 0. Т.о. единичные коэффициенты определяют искомую ДНФ для системы уравнений.
Рассмотрим f(x1,x2,x3) = Ú F(0,2,4,7), так называется десятичная форма записи для логического выражения f(x1,x2,x3)= ,, Ú , x2, Ú x1,, Ú x1, x2, x3
Для получения коэффициентов: 1) Выбрать строку, в которой функция равна нулю, и все коэффициенты приравнять к нулю. Если все нулевые строки просмотрены, то переходим к шагу 2. 2) Просмотрим строки, где функция равна еденице, и в этих строках вычеркиваем коэффициенты, которые принадлежат строкам с нулевым значением функции. 3)Переписывают все модифицированные уровнения.
В полученной системе уравнений просматривают каждую строку и вычеркивают максимально возможное количество коэффициентов таким образом, чтобы ранг оставшихся терминов был минимальным.
k0023Ú k0013Ú k000123=1
k0013Ú k000123=1
k0023Ú k000123=1
k000123=1
В модифицированной системе вычеркивают коэффициенты максимального ранга. Оставшиеся коэффициенты позволяют получить минимальную форму:
f*(x1,x2,x3)= ,Ú , Ú x1,x2,x3