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

Теоретически решение задачи минимизации представления БФ может быть получено путем полного перебора всех возможных эквивалентных представлений. При этом максимально возможное число букв в представлении БФ от переменных будет равно .

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

,

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

При значениях аргументов данная ДНФ примет следующий вид:

.

Последовательно перебирая все наборы входных переменных и подставляя их в ДНФ, получаем систему из уравнений:

.

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

На основании изложенного подхода составим формальный алгоритм минимизации представления БФ и продемонстрируем его функционирование на примере минимизации представления функции

.

1. Для заданной в произвольной форме БФ заполняется таблица истинности (для нашей функции – табл. 2.1).

Таблица 2.1

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

.

3. Из свойств алгебры логики следует, что тождество выполняется только при . Поэтому все коэффициенты из уравнений с нулем в правой части будут равны нулю. Для нашей функции из первого, второго, третьего и пятого уравнений получаем:

4. Все нулевые коэффициенты подставляем в оставшиеся уравнения с единицей в правой части. Для нашей функции будут упрощены четвертое, шестое, седьмое и восьмое уравнения:

.

5. Полученная на предыдущем шаге система уравнений допускает дальнейшее упрощение. Для этого нужно в каждом уравнении оставить коэффициенты, соответствующие наименьшим конъюнкциям. Из первого уравнения следует: , из второго – , из третьего – . Так как нам уже известно, что , из четвертого уравнения следует: .

Итак, оптимальным решением системы уравнений является: . Следовательно, минимальная ДНФ заданной БФ запишется так: .