4.8.1. Метод Квайна-МакКласки

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

Простая импликанта – это импликанта в виде элементарной конъюнкции, которая перестает быть импликантой при удалении любого литерала. Заметим, что удаление литералов до пустого множества приводит к конъюнкции, представляющей константу 1. Характеристическим множеством простой импликанты является максимальный интервал, т. е. интервал, целиком содержащийся в единичной области М¹ функции f и не являющийся подмножеством другого интервала из М¹.

Дизъюнкция всех простых импликант некоторой булевой функции называется сокращенной ДНФ этой функции.

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

Первый этап выполняется путем применения операции простого склеивания над конъюнкциями. Пусть п – число аргументов заданной функции f. Рассмотрим последовательность множеств С₀, С₁, … , C_k, где С₀ – множество конъюнкций ранга п, составляющих совершенную ДНФ функции f, С_i – множество конъюнкций ранга п – i, полученных путем склеивания конъюнкций из множества C_i – 1, и C_k – множество конъюнкций ранга п – k, где нет ни одной пары соседних конъюнкций и дальнейшее склеивание невозможно. Если склеиваемым конъюнкциям приписывать некоторую метку, то неотмеченные конъюнкции составят множество всех простых импликант.

Выразим этот процесс через операции простого склеивания над булевыми и троичными векторами. Булева функция при этом задана своим характеристическим множеством М¹ – множеством элементов булева пространства, на которых она имеет значение 1. Удобно при этом сгруппировать исходные булевы векторы в подмножества, состоящие из векторов, имеющих одинаковое число единиц, и упорядочить эти подмножества по возрастанию (или убыванию) числа единиц в векторе. Тогда для каждого вектора соседние с ним векторы будут находиться только в соседних подмножествах в полученной последовательности.

В качестве примера рассмотрим булеву функцию, заданную следующей матрицей:

.

Используя для множеств векторов те же обозначения, что использовались для соответствующих конъюнкций, получим следующую последовательность матриц, где склеиваемые строки отмечены знаком «*»:

С₀ = ,С₁ = ,С₂ = .

Сокращенная ДНФ, которая является результатом выполнения первого этапа минимизации, представится следующей матрицей:

.

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

Продолжая решать наш пример и пользуясь обозначениями из гл. 7, поставим задачу следующим образом. Заданы множество А = М¹ и совокупность подмножеств В₁, В₂, … , В_т множества А в виде матриц

и .

Требуется выделить минимум подмножеств B_i, покрывающих все множество А. Перейдя к матричной форме этой задачи, получим следующую матрицу:

.

Здесь надо выбрать минимальное количество строк так, чтобы каждый столбец имел единицу хотя бы в одной из них.

Строка В₆ является единственной строкой, которая покрывает столбцы а₆ и а₇. Поэтому ее включаем в решение. Удалив эту строку и покрываемые ею столбцы, получим матрицу

.

Строки В₃ и В₅ удаляются по правилу редукции, как покрываемые строками В₁ и В₄ соответственно. Из оставшихся строк строки В₁ и В₄ покрывают оставшиеся столбцы. Таким образом, искомое кратчайшее покрытие составляют строки В₁, В₄ и В₆, а кратчайшая ДНФ, которая является также минимальной для заданной булевой функции, представляется матрицей

.

В алгебраической форме это решение имеет вид х₁х₂х₄  х₁х₂х₃  х₃ х₄.

Иногда бывает возможность уменьшить размерность матрицы покрытия, выделив интервалы, входящие в любую безызбыточную ДНФ. Если некоторый элемент булева пространства m_i  M¹ принадлежит лишь одному из максимальных интервалов U  M¹, то очевидно, что любое кратчайшее покрытие множества М¹ максимальными интервалами содержит этот интервал. Элемент m_i в этом случае назовем определяющим элементом, а интервал U – обязательным интервалом.

Чтобы определить, является ли некоторый элемент m_i определяющим, достаточно найти в М¹ все соседние с ним элементы, а затем построить содержащий их минимальный поглощающий интервал.

Минимальный поглощающий интервал U для элементов m₁, m₂, … , m_k булева пространства М представляется вектором u, который получается следующим образом: если i-я компонента во всех векторах m₁, m₂, … , m_k имеет значение 0, то вектор и имеет в этой компоненте 0, если 1, то 1. Если i-я компонента имеет различные значения в этих векторах, то i-я компонента вектора и имеет значение «–».

Например, для элементов булева пространства (0 0 1 0 1 0), (0 0 1 0 1 1) и (0 0 0 0 1 1) минимальный поглощающий интервал представляется вектором (0 0 – 0 1 –).

Если все элементы полученного таким образом интервала U принадлежат М¹, то он является максимальным в М¹ и притом обязательным, а m_i является определяющим элементом. В противном случае U не содержится целиком в М¹, а m_i не является определяющим ни для какого интервала.

Чтобы определить, содержится ли интервал U во множестве М¹, достаточно для матрицы, представляющей множество М¹, построить минор, определяемый столбцами, где вектор и имеет значение «–», и строками, не ортогональными вектору и. Число строк в этом миноре не превышает 2^р, где р – число компонент вектора и, имеющих значение «–». Очевидно, интервал U целиком содержится в М¹ тогда и только тогда, когда число строк в этом миноре равно 2^р.

Обратимся к рассмотренному выше примеру. Элемент (0 0 0 0) не является определяющим. Действительно, минимальный поглощающий интервал для него и соседних с ним элементов (0 0 1 0) и (1 0 0 0) задается троичным вектором (– 0 – 0). Соответствующий минор матрицы, представляющей М¹, имеет вид

,

где число строк меньше чем 4 = 2².

Аналогичным образом устанавливается, что элементы (0 0 1 0), (1 0 0 0), (0 0 1 1) и (1 0 0 1) также не являются определяющими. Что касается элемента (0 1 1 1), то для него и соседних с ним элементов (0 0 1 1) и (1 1 1 1) соответствующим троичным вектором является (– – 1 1) и соответствующим минором –

,

число строк которого равно 4. Следовательно, элемент (0 1 1 1) является определяющим, а интервал, представляемый вектором (– – 1 1), – обязательным.

Этот интервал включается в решение, и все покрываемые им элементы исключаются из рассмотрения. Очевидно, что если среди них имеется какой-либо определяющий элемент, то он определяет тот же самый интервал. Затем отыскиваются интервалы, содержащие непокрытые элементы. Для этих элементов и интервалов решается задача покрытия, представляемая матрицей

.

Дальнейший ход решения не отличается от предыдущего, и в итоге получается тот же результат: х₁х₂х₄  х₁х₂х₃  х₃ х₄.