2.3.1.2. Алгоритм Квайна–МакКласки
1. Представим совершенную ДНФ булевой функции f( ,…, ) списком двоичных векторов.
2. Упорядочим элементы списка по возрастанию весов векторов. В результате список разобьется на равновесные подмножества векторов.
3. Выполним операции склеивания над векторами соседних по весу подмножеств. Результаты склеиваний занесем в новый список, а векторы, участвующие в склеивании, отметим символом *. В каждом новом списке векторы оказываются разбитыми на равновесные подмножества.
4. Если новый список пуст, переходим к п. 5 алгоритма. Иначе переходим к п. 3 и работаем с новым списком векторов.
5. Выпишем из всех полученных списков, в том числе из исходного упорядоченного списка булевых векторов, векторы, не отмеченный символом *. Образуем из выписанных векторов список, представляющий сокращенную ДНФ булевой функции f( ,…, ).
6. Переходим, если это требуется, к записи сокращенной ДНФ в виде дизъюнкции конъюнкций.
Приведем пример построения сокращенной ДНФ функции по ее совершенной ДНФ:
.
Представим эту ДНФ списком булевых векторов:
0001 |
0011 |
0100 |
0101 |
1001 |
1111 |
1010 |
1100 |
Упорядочим элементы списка по возрастанию весов и разобьем на равновесные подмножества:
1 |
0001 * |
2 |
0100 * |
|
|
3 |
0011 * |
4 |
0101 * |
5 |
1001 * |
6 |
1010 |
7 |
1100 * |
|
|
8 |
1111 |
Выполним операции простого склеивания над элементами множеств с весами 1, 2. Получим новый список векторов. В нем слева указаны номера элементов предыдущего списка, участвующих в склеивании. Элементы предыдущего списка, участвующие в склеивании, отмечаются символом *. Новый список представляется в виде
(1,3) |
00–1 |
(1,4) |
0–01 |
(1,5) |
–001 |
(2,4) |
010– |
(2,7) |
–100 |
Новый список состоит из одного подмножества, следовательно, склеивание его элементов невозможно. Переходим к п. 5 алгоритма. Получаем следующий список троичных векторов:
1010 |
1111 |
00–1 |
0–01 |
–001 |
010– |
–100 |
Сокращенная ДНФ имеет вид
.
Отметим, что при реализации алгоритма на этапе склеиваний троичных векторов может потребоваться большой объем вычислений, несмотря на то, что взвешивание троичных векторов позволяет просматривать вместо всевозможных пар векторов – кандидатов на склеивание – только векторы соседних по весу подмножеств.
Для получения минимальных и кратчайших ДНФ из сокращенной, как правило, необходимо выбрасывать некоторые конъюнкции. Ответ на вопрос, какие конъюнкции подлежат исключению, можно получить, построив таблицу Квайна.
КАДР