Метод неопределенных коэффициентов и минимизирующих карт

Аналитическая минимизация

Постановка задачи минимизации в классе ДНФ

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

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

Выполняется в соответствии с основными теоремами алгебры логики, приведенными в разделе 1.8.

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

Вначале опишем наиболее простой по своим идеям метод неопределенных коэффициентов.

Представим функцию f(x123) в виде следующей ДНФ (1.53, 1.54).

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

(1.53)
 
(1.54)

Пусть таблично задана некоторая функция f(x1,x23). Задание некоторой конкретной функции определяет значения правых частей системы (1.54). Если набор 1,x2, х3> таков, что функция на этом наборе равна нулю, то в правой части соответствующего уравнения будет стоять нуль. Для удовлетворения этого уравнения необходимо приравнять нулю все коэффициенты К, входящие в левую часть рассматриваемого уравнения. Это вытекает из того, что дизъюнкция равна нулю только тогда, когда все члены, входящие в нее, равны нулю.

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

Рассмотрим пример.

 

Составляем систему (1.54).

 

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

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

 

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

.  

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

 

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

.