Дискретная математика

Глава 5

Метод Квайна - Мак-Класки минимизации булевых функций

5.1Склейка соседних наборов

Определение 5.1. Два набора σe1 и σe2 называются соседними, если они отличаются ровно в одной координате:

σe1 = (σi1 , σi2 , . . . , σik−1 , 0, σik+1 , . . . , σis ); σe2 = (σi1 , σi2 , . . . , σik−1 , 1, σik+1 , . . . , σis ).

У соседних наборов число координат, равных единице, различается на 1.

Геометрически на булевом кубе соседние наборы образуют ребра куба.

Для соседних наборов σe1 и σe2 определяют операцию склейки, поставив этим наборам в соответствие набор

σe = (σi1 , σi2 , . . . , σik−1 , −, σik+1 , . . . , σis ).

Символ "−" заменяет координату, значение которой на этих наборах различно.

71

Пусть наборам σ1 и σ2 соответствуют элементарные конъюнкции

В геометрической форме склейка означает объединение двух соседних вершин в интервал - ребро.

5.2Алгоритм Квайна - Мак-Класки

Алгоритм рассмотрим на конкретном примере.

Пример 5.1. Найти сокращенную, ядровую, все тупиковые и все минимальные ДНФ для булевой функции fe= (0101 0111) методом Квайна - Мак-Класки.

Решение.

1.Находим носитель функции Nf = {σe Bn|f(σe) = 1}.

В нашем примере Nf = { (001), (011), (101), (110), (111) }.

2.Размещаем наборы носителя по классам по количеству единиц в наборе. Для функции n переменных таких классов n + 1 :

72

3.Каждый набор из класса Si пытаемся склеить с каждым набором из соседнего класса Si+1. Наборы, помещенные не в соседние классы, склейке не подлежат, так как различаются более чем в одной координате (количество единиц у этих наборов различается более, чем на 1).

S1 (001) - соседние наборы

S2 (011)

(0-1) - результат склейки S1 (001) - соседние наборы S2 (101)

(-01) - результат склейки

Не все наборы из соседних классов являются соседними и склеиваются между собой.

S1 (001) - соседними не являются

S2 (110) и не склеиваются

Продолжаем склейку, пока есть пары соседних наборов.

Результат склейки соседних наборов из классов Si и Si+1 записываем во второй столбец. Количество единиц в нем равно i, поэтому склейку помещаем в строку, соответствующую классу Si.

После склейки всех соседних классов класс Sn оказывается пустым.

Все наборы, участвующие в склейке, помечаем каким-либо символом, например, " ".

В нашем примере таблица принимает вид

73

Заметим, что в первом столбце все наборы помечены " ".

4.Склеиваем наборы из соседних классов, расположенные во 2 столбце. В дальнейшей склейке участвуют наборы, имеющие прочерк на одинаковых местах.

( 0 − 1 )

Например, наборы - соседние,

( 1 − 1 )

результат их склейки - (− − 1 ),

Результат повторной склейки размещаем в правый столбец в строку, соответствующую количеству единиц в наборе. Соседние наборы опять помечаем " ".

Так продолжаем до тех пор, пока есть наборы, которые могут быть склеены.

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

В заданном примере таблица содержит 3 столбца.

74

Заметим, что после повторной склейки всегда появляются пары одинаковых наборов, в нашем случае (- -1). Геометрически повторная склейка соответствует объединению 4 ребер в одну грань. Одну из одинаковых склеек можно вычеркнуть.

5.Выписываем множество всех наборов из всех столбцов, которые не участвовали в склейке. Эти наборы не помечены " ". Такие наборы образуют максимальные интервалы, им соответствуют простые импликанты. Импликанты задаются так же, как и в геометрическом методе.

В нашем примере таких наборов два (они выделены в таблице):

(11-) и (- -1).

(11−) ↔ K1 = x1x2 (− − 1) ↔ K2 = x3

6.Находим сокращенную ДНФ.

Для нашей задачи ДНФсокр(f) = K1 K2 = x1x2 x3.

7.Составляем таблицу покрытия. Количество строк в таблице равно числу простых импликант, а количество столбцов равно количеству наборов в носителе. Если j−я вершина покрыта i−тым интервалом (то есть, значения несклеенных переменных в импликанте совпадают с соответствующими координатами набора), элемент, находящийся на пересечении i−той строки и j−го столбца, помечаем каким-либо символом, например,"1". Так как каждая склейка соответствует двум наборам, то количество меток в строке равно 2k, где k - количество склеенных переменных.

Каждая строка и каждый столбец таблицы покрытия должны содержать хотя бы 1 метку.

75

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

юнкция" , получаем ядро функции.

В рассматриваемом примере отмеченных столбцов 4, находятся метки в строках, соответствующих ядровым импликантам K1 и

K2.

ДНФядр(f) = ДНФсокр(f) = K1 K2 = x1x2 x3;

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

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

P = (K2)(K2)(K2)(K1)((K1 K2) = K1 · K2 · (K1 K2) = K1 · K2.

76

При упрощении функции Патрика, как обычно, применялись логические тождества:

A · A = A

A(A B) = A.

В результате преобразований получили, что P = K1·K2 - функция Патрика состоит из одного слагаемого K1K2. Ему соответствует одна тупиковая ДНФ. Так как все скобки сократились, то ядровая ДНФ совпадает с тупиковой (мы подтвердили результат, полученный на предыдущем шаге алгоритма). Эта же ДНФ является и минимальной.

ДНФмин(f) = ДНФтуп(f) = ДНФядр(f) = K1 K2 = x1x2 x3;

r(ДНФмин(f)) = 3.

Заметим, что находить ядровую ДНФ дважды не обязательно. Пункт 8 алгоритма можно пропускать.

Пример 5.2. Найти сокращенную, ядровую, все тупиковые и все минимальные ДНФ для булевой функции fe = (1101 0001 1000 1111) методом Квайна.

Решение.

1.Построим таблицу истинности булевой функции. Так как длина вектора значений равна 16 = 24, то функция зависит от 4 переменных.

77

Носитель функции

Nf = { (0000), (0001), (0011), (0111),

(1000), (1100), (1101), (1110), (1111) }.

2.Разобьем носитель по классам S0, S1, S2, S3, S4 по количеству единиц в наборе.

S0 (0000)

S1 (0001) (1000)

S2 (0011) (1100)

(0111) S3 (1101)

(1110)

S4 (1111)

3.Применим операцию склейки к наборам из соседних классов. Результат помещаем во 2 столбец. Все наборы, которые участвуют в склейке, помечаем " ".

78

Обратим внимание, что набор, состоящий из всех нулей (он расположен в классе S0), склеивается со всеми наборами из класса S1, а набор из всех единиц - со всеми наборами из класса S3.

4.Применим операцию склейки к наборам из второго столбца, также помечая соседние наборы. Результат записываем в 3 столбец.

Убедимся, что в третьем столбце появилась пара одинаковых склеенных наборов. Вычеркиваем один из них. Больше нет наборов, к которым можно было бы применить операцию склейки. Все наборы, не участвовавшие в склейке, дважды подчеркиваем.

5.Находим простые импликанты, соответствующие дважды подчеркнутым наборам. Выписываем сокращенную ДНФ.

79

ДНФсокр(f) = K1 K2 K3 K4 K5 K6 K7 =

=x1x2x3 x2x3x4 x1x2x4 x1x3x4 x1x3x4 x2x3x4 x1x2

6.Составим таблицу покрытия.

Для самопроверки заметим, что в каждой строчке, соответствующей наборам, участвовавшим в одной склейке (один " - " в наборе), стоят по 2 метки " 1 " , а в дважды склеивавшемся наборе - 4 метки.

7.Найдем ядровую ДНФ. Столбцы, содержащие по одной метке, соответствуют наборам (1101) и (1110). Обведем эти метки.

80