Метод Квайна – Мак-Класки
.doc6.6.3. Метод Квайна – Мак-Класки
Табличный метод минимизации булевых функций, предложенный Уиллардом Квайном и усовершенствованный Эдвардом Мак-Класки.
Одной из важнейших интерпретаций булевых алгебр является БУЛЕВА АЛГЕБРА ПЕРЕКЛЮЧАТЕЛЬНЫХ ФУНКЦИЙ. Первоначально этот математический аппарат был применен для анализа и синтеза множества релейно-контактных схем с операциями последовательного (конъюнкция) и параллельного (дизъюнкция) соединения контактов и операцией дополнения. 1 - проводник, 0 - разрыв.
Множество всех переключательных функций (ПФ) обозначают Р2.
Алгебра (Р2,
)
называется булевой алгеброй
переключательных функций.
Импликантой переключательной функции Y=F(x1,..., xn) называется функция y=f(x1,..., xn), которая обращается в 1 на некотором подмножестве единичных наборов функции Y.
Пример.
|
х1 |
х2 |
х3 |
|
|
0 |
0 |
0 |
1 |
|
0 |
0 |
1 |
1 |
|
0 |
1 |
0 |
0 |
|
0 |
1 |
1 |
0 |
|
1 |
0 |
0 |
1 |
|
1 |
0 |
1 |
1 |
|
1 |
1 |
0 |
0 |
|
1 |
1 |
1 |
0 |
Импликанты данной функции:
,
- элементарные конъюнкции.
Также импликантами являются конъюнкции, полученные в результате склеивания (формулы расщепления) или поглощения одних конъюнкций другими.
Пример.
.
Простой (первичной) импликантой (минималью) функции Y=F(x1,...,xn) называется импликанта, которая не склеивается с никакой другой и не поглощается никакой другой импликантой данной функции Y.
Пример.
- импликанта функции Y,
- простая импликанта функции Y,
т.к. она поглощает импликанту y1:
Сокращенная ДНФ (СкДНФ) - это ДНФ функции в виде дизъюнкции всех ее простых импликант. СкДНФ в общем случае избыточна, некоторые из составляющих ее простых импликант могут быть исключены при сохранении эквивалентности формул.
Тупиковая ДНФ (ТДНФ) - это ДНФ, из которой нельзя исключить ни одной простой импликанты без потери эквивалентности формулы.
Минимальная ДНФ (МДНФ) - это ТДНФ, содержащая минимальное число символов среди возможных ТДНФ функции.
Метод Квайна – Мак-Класки состоит из двух этапов:
1. Получение всех простых импликант ПФ (построение СкДНФ).
2. Поиск всех ТДНФ по импликантной таблице покрытий и выбор их них МДНФ.
Исходная функция должна быть представлена в СДНФ.
Каждая элементарная конъюнкция может быть представлена двоичным числом.
Каждой конъюнкции присваивается индекс – число единиц в двоичном представлении конъюнкции
|
х1 |
х2 |
х3 |
х4 |
число |
индекс |
|
0 |
0 |
0 |
0 |
0 |
0 |
|
0 |
0 |
0 |
1 |
1 |
I |
|
0 |
0 |
1 |
0 |
2 |
I |
|
0 |
0 |
1 |
1 |
3 |
II |
|
0 |
1 |
0 |
0 |
4 |
I |
|
0 |
1 |
0 |
1 |
5 |
II |
|
0 |
1 |
1 |
0 |
6 |
II |
|
0 |
1 |
1 |
1 |
7 |
III |
|
1 |
0 |
0 |
0 |
8 |
I |
|
1 |
0 |
0 |
1 |
9 |
II |
|
1 |
0 |
1 |
0 |
10 |
II |
|
1 |
0 |
1 |
1 |
11 |
III |
|
1 |
1 |
0 |
0 |
12 |
II |
|
1 |
1 |
0 |
1 |
13 |
III |
|
1 |
1 |
1 |
0 |
14 |
III |
|
1 |
1 |
1 |
1 |
15 |
IV |
Первый этап основан на последовательном применении операции склеивания (формула расщепления).
Для того чтобы два числа являлись номерами двух склеивающихся между собой конъюнкций, необходимо и достаточно, чтобы:
1) индексы данных чисел отличались на единицу;
2) сами числа отличались на 2i (i=0, 1, …);
3) число с бóльшим индексом было больше числа с меньшим индексом.
Одна и та же конъюнкция может быть склеена с другими несколько раз. При этом компонента, меняющая свое значение, заменяется «–».
Пример.
При склеивании 0011 и 0111 получаем 0–11.