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

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

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

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

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

Таблица 1.13

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

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

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

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

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

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

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

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