2-3. МЕТОД НЕОПРЕДЕЛЕННЫХ КОЭФФИЦИЕНТОВ

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

Представим функцию в виде следующей ДНФ:

Здесь представлены все возможные конъюнктивные члены, которые могут входить в дизъюнктивную форму представления Коэффициенты К с различными индексами являются неопределенными и подбираются так, чтобы получающаяся после этого дизъюнктивная форма была минимальной. Если теперь задавать всевозможные наборы значений аргументов и приравнивать полученное после этого выражение (отбрасывая нулевые конъюнкции) значению функции на выбранных наборах, то получим систему 23 уравнений

для определения коэффициентов К:

Пусть таблично задана некоторая функция Задание некоторой конкретной функции определяет значения правых частей системы (2-11). Если набор таков, что функция на этом наборе равна нулю, то в правой части соответствующего уравнения будет стоять нуль. Для удовлетворения этого уравнения необходимо приравнять нулю все коэффициенты К, входящие в левую часть рассматриваемого уравнения. (Это вытекает из того, что дизъюнкция равна нулю только тогда, когда все члены, входящие в нее, равны нулю).

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

сделать, так как дизъюнкция обращается в единицу, если хотя бы один член ее равен единице). Единичные коэффициенты определят из (2-10) соответствующую ДНФ.

Пример 2-6.

Составляем систему (2-11):

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

После этого данная система примет вид:

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

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

Отсюда находим МДНФ для данной функции:

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

Более эффективным является выписывание не всех возможных конъюнкций для функции переменных, а только тех, которые могут присутствовать в ДНФ, эквивалентной минимизируемой функции. Этот прием позволяет уменьшить таблицу и перебор, который мы проводим с целью нахождения МДНФ. В следующем параграфе опишем метод, основанный на подобной идее.