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

Метод заключается в том, что для заданной формулы мысленно составляется дизъюнктивная нормальная форма, содержащая всевозможные конъюнкции из одного, двух и т. д. и наконец, всех переменных, входящих в формулу. Рассмотрим формулу с тремя переменными X, Y и Z.

В соответствии с каждой конъюнкцией дизъюнктивной нормальной формы коэффициент (какую-либо букву, например A) будем записывать с нижними и верхними индексами следующим образом:

1. вхождения X, Y и Z в конъюнкцию будем отмечать цифрами соответственно 1, 2 и 3, ставя их в качестве нижних индексов;

2. если значение переменной в данной конъюнкции 0 или 1, на соответствующем месте ставим 0 или 1 в качестве верхних индексов.

Например, конъюнкциям X, XY, XZ, YZ, XYZ, XYZ соответствуют коэффициенты , , , , , .

Пусть некоторая формула задана таблицей:

X	Y	Z	Значение формулы
0	0	0	0
0	0	1	0
0	1	0	1
0	1	1	0
1	0	0	1
1	0	1	0
1	1	0	1
1	1	1	0

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













=

0;













=

0;













=

1;













=

0;













=

1;













=

0;













=

1;













=

0.

Суммы равны 0 тогда и только тогда, когда все слагаемые равны 0, выпишем коэффициенты, равные 0.

= = = = = = = = = = = = = = = = = = = =0.

В оставшихся суммах, которые равны единице, исключим слагаемые, равные 0:

 =1;

 =1;

  =1;

Таким образом, получаем следующую ДНФ:

YZXYZXZXYZXZYZXYZ;

т. е. YZXYZXZXYZXYZ.

Согласно закону поглощения нетрудно заключить, что полученная формула равносильна формуле YZXZ, которая и является минимальной ДНФ формулы, заданной нашей таблицей.

Прежде чем построить схему, вынесем Z за скобку: (XY)Z.