Минимизация в классе дизъюнктивных нормальных форм

Наиболее известным алгоритмом построения сокращенной д. н. ф., повидимому, является алгоритм Блейка—Порецкого, описанный во многих руководствах. ЭТОТ алгоритмстроит сокращенную д. н. ф. по д. н. ф. произвольного вида.

Алгоритм СОСТОИТ в применении к исходной д. н. ф. правила обобщенного склеивания хА\/хВ=хА\/хВ\/АВ до тех пор, пока это возможно, и последующем применении правила поглощения AVA-S—А. Считается, что преобразования выполняются слева направо.

Квайн предложил алгоритм построения сокращенной д. н. ф. по совершенной. Этот алгоритм аналогичен алгоритму Блейка—Порецкого и отличается тем, что вместо операции обобщенного склеивания применяется обычное склеивание xA\JxA=A.

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

В работе Нельсона предложен алгоритм построения сокращенной д. и. ф. по произвольной конъюнктивной нормальной форме (к. н. ф.). Метод состоит в переходе от к. н. ф. кд. н. ф. с помощью раскрытия скобок и последующего применения правил х-х—0, 'х-х=х, А\/АВ — А.

Для построения сокращенной д. н. ф. «вручную» для функций, зависящих от небольшого числа переменных,1 удобным

средством являются карты Карно и диаграммы Вейтча. Графико-механические и матричные способы получения сокращенной д. н.'ф. предлагались в работах.

Суть метода Квайна весьма проста. Основу его составляет теорема склеивания, которая применяется к каждой паре минтермов заданной функции.