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

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

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

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

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

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

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

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

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

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

	(1.53)
	(1.54)

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

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

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

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

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

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

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

.

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

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

.