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

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

Представим функцию ff(xx₁,xx₂,xx₃) в виде следующей ДНФ:

f(x₁,x₂,x₃=K₁¹x₁ÚK₁⁰`x<sub>1</sub>ÚK<sub>2</sub><sup>1</sup>x<sub>2</sub>ÚK<sub>2</sub><sup>0</sup>`x₂ÚK₃¹x₃ÚK₃⁰`x<sub>3</sub>Ú
ÚK<sub>12</sub><sup>11</sup>x<sub>1</sub>x<sub>2</sub>ÚK<sub>12</sub><sup>10</sup>x<sub>1</sub>`x₂ÚK₁₂⁰¹`x<sub>1</sub>x<sub>2</sub>ÚK<sub>12</sub><sup>00</sup>`x₁`x<sub>2</sub>Ú
ÚK<sub>13</sub><sup>11</sup>x<sub>1</sub>x<sub>3</sub>ÚK<sub>13</sub><sup>10</sup>x<sub>1</sub>`x₃ÚK₁₃⁰¹`x<sub>1</sub>x<sub>3</sub>ÚK<sub>13</sub><sup>00</sup>`x₁`x<sub>3</sub>Ú
ÚK<sub>23</sub><sup>11</sup>x<sub>2</sub>x<sub>3</sub>ÚK<sub>23</sub><sup>10</sup>x<sub>2</sub>`x₃ÚÚK₂₃⁰¹`x<sub>2</sub>x<sub>3</sub>ÚK<sub>23</sub><sup>00</sup>`x₂`x<sub>3</sub>Ú
ÚK<sub>123</sub><sup>111</sup>x<sub>1</sub>x<sub>2</sub>x<sub>3</sub>ÚK<sub>123</sub><sup>110</sup>x<sub>1</sub>x<sub>2</sub>`x₃ÚK₁₂₃¹⁰¹x₁`x<sub>2</sub>x<sub>3</sub>Ú
ÚK<sub>123</sub><sup>100</sup>x<sub>1</sub>`x₂`x<sub>3</sub>ÚK<sub>123</sub><sup>011</sup>`x₁x₂x₃ÚK₁₂₃⁰¹⁰x₁`x<sub>2</sub>x<sub>3</sub>Ú
ÚK<sub>123</sub><sup>001</sup>`x₁`x<sub>2</sub>x<sub>3</sub>ÚK<sub>123</sub><sup>000</sup>`x₁`x<sub>2</sub>`x₃

Здесь представлены всевозможные конъюнктивные члены, которые могут входить в ДНФ функции f(x₁,x₂,x₃). Коэффициенты K с различными индексами являются неопределенными и подбираются так, чтобы получающаяся после этого дизъюнктивная форма была минимальной. Если задавать всевозможные наборы значений аргументов <x₁, x₂, x₃> и приравнивать полученное после этого выражение (отбрасывая нулевые конъюнкции) значению функции на выбранных наборах, получим систему 2ⁿ уравнений для определения коэффициентов K:

Пусть таблично задана некоторая функция f(x₁,x₂,x₃). Если набор <x₁,x₂,x₃> таков, что функция на этом наборе равна 0, то в правой части соответствующего уравнения будет стоять 0. Для удовлетворения этого уравнения необходимо приравнять 0 все коэффициенты K, входящие в левую часть рассматриваемого уравнения.

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

ПримерПример 5.f(x₁,xx₂,x₃)=x₁xx₂xx₃Úxx₁xx₂`x<sub>3</sub>Úxx<sub>1</sub>`xx₂xx₃Úxx₁`xx<sub>2</sub>`xx₃Ú`xx<sub>1</sub>`xx₂`xx₃.

Составляем систему:

Из пятого, шестого и седьмого уравнений вытекает, что

K₁⁰=K₂⁰=K₂¹=K₃⁰=K₃¹=K₁₂⁰⁰=K₁₂⁰¹=K₁₃⁰⁰=K₁₃⁰¹=K₂₃⁰¹=K₂₃¹⁰=K₂₃¹¹=K₁₂₃⁰⁰¹=
=K₁₂₃⁰¹⁰=K₁₂₃⁰¹¹=0.

В результате данная система примет вид

Приравняем 0 в каждом уравнении все коэффициенты, кроме тех, которые отвечают конъюнкциям, содержащим наименьше число переменных:

K₁₂¹¹=K₁₂⁰¹=K₁₃¹¹=K₁₃¹⁰=K₁₂₃¹¹¹=K₁₂₃¹¹⁰=K₁₂₃¹⁰¹=K₁₂₃¹⁰⁰=K₁₂₃⁰⁰⁰=0.

После этого получаем систему

Отсюда находим МДНФ для данной функции: f(x₁,x₂,x₃)=x₁Ú`x<sub>2</sub>`x₃.

Описанный метод эффективен лишь для минимизации функций, число аргументов в которых не больше 5-6. Это связано с тем, что число уравнений равно 2ⁿ.