КВАЙНА МЕТОД МИНИМИЗАЦИИ

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

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

При этом переход от к осуществляют по следующему правилу. В ДНФ выполняют все операции неполного склеивания, применимые к элементарным произведениям длины . В результате в представлении ф-ции образуются произведения длины Поскольку склеивать можно только произведения с одинаковым к-вом букв, ни с одним из полученных произведений произведения длины склеиваться не будут. Поэтому после выполнения операции склеивания исключаются все те элементарные произведения длины , которые могут быть исключены в результате применения операции элементарного поглощения.

На втором этапе используют т. н. таблицу простых импликант, представляющую собой прямоугольную таблицу с двумя входами. Столбцы такой таблицы отмечаются конституэнтами единицы минимизируемой ф-ции, строки — ее различными простыми импликантами. Если в некоторую конституэнту входит какая-либо из простых импликант, то на пересечении соответствующих столбца и строки ставится метка.

Построение тупиковых ДНФ с помощью таблицы простых импликант связано с построением на ее основе т. н. сокращенной таблицы простых импликант. Такая таблица получается при вычеркивании из таблицы простых импликант 1) тех столбцов, которые содержат только по одной метке, 2) тех строк, импликанты которых содержат метки в вычеркнутых столбцах, 3) одного из тех двух столбцов, у которых имеются метки в одинаковых столбцах, 4) тех строк, которые в результате вычеркивания в соответствии с 1) — 3) не содержат ни одной метки. Построению тупиковой ДНФ при этом соответствует выбор такой совокупности простых импликант, которая включает все те импликанты, которые принадлежат строчкам, вычеркнутым в соответствии с п. 2) (т. н. ядро булевой ф-ции), и, кроме того, некоторую систему импликант из сокращенной таблицы, метки которых по крайней мере один раз накрывают все ее столбцы. В отличие от ядра такая система в общем случае может содержать различные наборы простых импликант. Выбор набора импликант с минимальным суммарным числом букв при нескольких возможных вариантах соответствует построению минимальной ДНФ заданной ф-ции.

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

Лит.: Глушков В. М. Синтез цифровых автоматов. М., 1962 библиогр. 464—469].