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

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

f(x₁,x₂,x₃) = k¹₁x₁ k⁰₁x₁ k¹₂x₂ k⁰₂x₂ k¹₃x₃ k⁰₃x₃ k¹¹₁₂x₁x₂ k¹⁰₁₂x₁x₂ k₁₂x₁x₂ k⁰¹₁₂x₁x₂  k⁰⁰₁₂x₁x₂ k¹¹₁₃x₁x₃ k¹⁰₁₃x₁x₃ k⁰⁰₁₃x₁x₃  k¹¹₂₃x₂x₃  k¹⁰₂₃x₂x₃ k⁰¹₂₃x₂x₃ k⁰⁰₂₃x₂x₃ k¹¹¹₁₂₃x₁x₂x₃ k¹¹⁰₁₂₃x₁x₂x₃ k¹⁰¹₁₂₃x₁x₂x₃ k¹⁰⁰₁₂₃x₁x₂x₃ k⁰¹¹₁₂₃x₁x₂x₃ k⁰¹⁰₁₂₃x₁x₂x₃ k⁰⁰¹₁₂₃x₁x₂x₃ k⁰⁰⁰₁₂₃x₁x₂x₃

В этойдизъюнктивной норм. форме коэффициенты с индексами – это определенный коэффициент, принимающий значение 0 и 1 и подбирается таким образом, чтобы ДНФ была минимальная. Задавая различные наборы переменныхx₁,x₂,x₃ и приравнивая полученные выражения соответствующим значениям функции, получают систему уравнений для определения коэффициента к:

f(0,0,0) = k⁰₁ k⁰₂  k⁰₃ k⁰⁰₁₂ k⁰⁰₂₃ k⁰⁰⁰₁₂₃

f(0,0,1) = k⁰₁ k⁰₂  k¹₃ k⁰⁰₁₂ k⁰¹₁₃ k⁰¹₂₃ k⁰⁰¹₁₂₃

……………………………………………

f(1,1,1) = k¹₁ k¹₂  k¹₃ k¹¹₁₂ k¹¹₁₃ k¹¹₂₃ k¹¹¹₁₂₃

f(x₁,x₂,x₃) = 0  1

Задание некоторой функции определяет значение первых частей системы: если f= 0 на соответствующем наборе переменных, то все коэффициенты входящие в уравнение, будут равны нулю. Это следует из свойства дизъюнкции. Тогда и в уравнении, где функция принимает единичное значение, надо вычеркивать все нулевые коэффициенты. Из оставшихся коэффициентов надо выбрать такой, который определяет темп наименьшего, и приравнять его к единице. А остальные коэффициенты приравнять к 0. Т.о. единичные коэффициенты определяют искомую ДНФ для системы уравнений.

Рассмотрим f(x₁,x₂,x₃) =F(0,2,4,7), так называется десятичная форма записи для логического выраженияf(x₁,x₂,x₃)= ,, ,x₂, x₁,, x₁,x₂,x₃

Для получения коэффициентов:1) Выбрать строку, в которой функция равна нулю, и все коэффициенты приравнять к нулю. Если все нулевые строки просмотрены, то переходим к шагу 2.2) Просмотрим строки, где функция равна еденице, и в этих строках вычеркиваем коэффициенты, которые принадлежат строкам с нулевым значением функции.3) Переписывают все модифицированные уровнения.

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

k⁰⁰₂₃k⁰⁰₁₃k⁰⁰⁰₁₂₃=1

k⁰⁰₁₃k⁰⁰⁰₁₂₃=1

k⁰⁰₂₃k⁰⁰⁰₁₂₃=1

k⁰⁰⁰₁₂₃=1

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

f^*(x₁,x₂,x₃)= ,, x₁,x₂,x₃