МАК-КЛАСКИ АЛГОРИТМ

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

Если номера конституэнт записываются в двоичной системе счисления, то элементарные произведения при заранее фиксированной нумерации переменных представляются с помощью последовательностей нулей, единиц и меток. Переменной без отрицания соответствует «1», переменной с отрицанием , а отсутствию переменной — метка (например, при обозначается и т. п.).

М.-К. а. при такой записи состоит в следующем. Номера конституэнт заданной булевой ф-ции разбиваются по числу единиц в двоичной записи на непересекающиеся группы, и каждой группе присваивается такой индекс, что в группу с индексом входят все конституэнты, в двоичной записи номеров которых содержится г единиц. Между номерами конституэнт, входящими в группы, индексы которых отличаются на единицу, производятся попарные сравнения. Если сравниваемые номера отличаются значением некоторого разряда (например, 0001 и 0101), на его месте ставят метку (0—01), а номера, над которыми выполнено сравнение, отмечаются. Сравнение номеров конституэнт и получение в результате некоторых новых номеров с метками, представляющих элементарные произведения, соответствует выполнению операции склеивания сравниваемых конституэнт. К полученным номерам снова применяют операцию попарного сравнения, которая в этом случае уже соответствует склеиванию элементарных произведений. Номера с метками, над которыми выполнено сравнение, снова отмечаются. Сокращенная ДНФ заданной ф-ции получается в результате выполнения всех возможных операций попарного сравнения и содержит только те элементарные произведения, номере которых после всех сравнений останутся неотмеченными. Выбор только неотмеченных элементарных произведений соответствует выполнению всех возможных операций поглощения. Наряду с двоичной системой счисления для записи номеров конституэнт иногда используют десятичную (т. н. усовершенствованный М.-К. а.). При такой записи не нужны спец. метки в представлении номеров элементарных произведений. Однако для отображения результатов сравнения номеров конституэнт и представлений элементарных произведений в этом случае приходится формировать дополнительные признаки, являющиеся некоторым упорядоченным мн-вом номеров и их разностей. Это приводит к усложнению процедуры сравнения. Более сложным при использовании десятичной системы счисления оказывается и переход от получающегося в результате работы М.-К. а. представления импликант к их записи в явном виде.

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

Лит.: Глушков В. М. Синтез цифровых автоматов. М., 1962 [библиогр. с. 464-469]; Мс СIuSkеу Е. J. Minimization of boolean functions. «The bell system technical journal». 1956, v. 35, № 6.

Ю. Л. Ивасъкив.