Результат минимизации: y(x1,x2,x3)=(x1 x2)(x1 x3 )( x1 x3).
Изложенный вариант алгоритма Квайна является его простейшей версией и обладает существенным недостатком: в результате работы алгоритма может быть получена форма, для которой дальнейшее склеивание невозможно, однако в действительности эта форма не является минимальной. Такие результаты минимизации по алгоритму Квайна называют тупиковыми формами. Поясним проблему тупиковых форм на примере.
Пусть задана булева функция в виде
y(x1,x2,x3)= x1 x2 x3 x1 x2 x3 x1 x2x3 x1 x2 x3 x1x2 x3 x1x2x3.
На рис. 5.4 показаны все возможные объединения.
y(x1,x2,x3)=x1 x2 x3 x1 x2 x3 x1 x2x3 x1 x2 x3 x1x2 x3 x1x2x
Рис. 5.4. Избыточное количество пар объединяемых компонент
В результате первой же процедуры объединения приходим к форме, не подлежащей дальнейшему склеиванию:
а) y(x1,x2,x3)= x1 x2 x2 x3 x1 x3 x2x3 x1 x3 x1x2.
Результаты минимизации позволяют оценить их как весьма скромные и обращают внимание на то, что все компоненты исходной формы склеиваются дважды, в то время как для минимизации любой из компонент достаточно склеить её один раз. Сокращённые и полный варианты объединений показаны на рис. 5.5, где компоненты СДНФ условно обозначены кружками с цифрами-номерами.
В соответствии с вариантами объединений, показанными на рис. 5.5, можно выписать еще три формы булевой функции:
б) y(x1,x2,x3) = x1 x2 x1 x3 x1 x3 x1x2;