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

Этот метод можно использовать при решении задачи минимизации БФ с большим числом переменных. Этот метод опирается на теорему Жегалкина, в соответствии с которой любую логическую функцию можно представить в нормальной форме[1,3].

Рассмотрим булеву функцию трех переменных. Тогда ДНФ такой функции может быть записана так

(1.1)

В данном случае фиксируем все возможные конъюнктивные термы. Коэффициенты с различными индексами называются неопределенными коэффициентами. Их необходимо определить таким образом, что бы ДНФ была минимальной. Очевидно, если каким-либо способом заданы наборы БФ, то получаем алгебраическую систему уравнений, решение которой и есть значение коэффициентов . Критерий минимальности – минимальное количество букв в записи ДНФ. При определении ДНФ используют следующие свойства: если , , если хотя бы один из членов уравнения равен единице. Если на соответствующем наборе переменных, то все коэффициенты, входящие в это уравнение, равны нулю. Тогда и во всех остальных уравнениях следует вычеркнуть эти коэффициенты, а из оставшихся уравнений, равных единице, найти коэффициенты, определяющие конъюнкцию наименьшего ранга в каждом из уравнений.

Пример 1.6. Минимизировать СДНФ, которая задана таблицей истинности (табл. 1.13)

Таблица 1.13

Таблица истинности булевой функции

Для всех восьми наборов БФ составим систему уравнений с неопределенными коэффициентами:

(1.2)

Из второго, третьего, четвертого уравнений системы (1.2), в соответствии с основными тождествами булевой алгебры, получаем

Записанные выше коэффициенты подставляем в систему (1.2) и ее перепишем так:

(1.3)

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

Теперь мы можем записать окончательную систему уравнений:

(1.4)

Используя (1.4) можно получить МДНФ данной БФ. Неопределенный коэффициент соответствует простой импликанте , которая покрывает четыре уравнения системы (1.4), а последнее уравнение покрывается простой импликантой , которой и соответствует коэффициент .

Окончательное соотношение для минимальной ДНФ запишем так

.

Дата добавления: 2015-07-08