2.3.1.3. Таблица Квайна и ее покрытия

Таблица Квайна есть булева матрица, строки которой сопоставлены конъюнкциям сокращенной ДНФ, а столбцы – конъюнкциям совершенной ДНФ. Строки и столбцы могут отмечаться как конъюнкциями, так и представляющими их векторами. Элемент (i, j) матрицы равен 1, если конъюнкция i-й строки поглощает конъюнкцию j-го столбца. Иначе элемент матрицы принимает значение 0. Договоримся нули в матрицу не записывать для удобства ее просмотра. Для нашего примера таблица Квайна представляется в виде

	0001	0011	0100	0101	1001	1111	1010	1100
1010							1		4	A
1111						1			4	B
00–1	1	1							3	C
0–01	1			1					3	D
–001	1				1				3	E
010–			1	1					3	F
–100			1					1	3	G

Рис. 2.2. Таблица Квайна

Здесь конъюнкции, сопоставляемые строкам и столбцам, представлены векторами.

Назовем покрытием столбцов матрицы подмножество ее строк, удовлетворяющее условию: в каждом столбце подмножества содержится хотя бы одна единица.

Заметим, что все множество строк таблицы Квайна является покрытием. В нашем примере можно указать несколько подмножеств строк, являющихся покрытиями. Подмножества будем задавать перечислением номеров строк, образующих покрытие: {1, 2, 3, 4, 5, 7}, {1, 2, 3, 5, 6, 7}.

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

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

Назовем длиной покрытия число его строк.

Определение. Безызбыточное покрытие минимальной длины называется кратчайшим покрытием.

Припишем строкам таблицы Квайна веса, равные рангам сопоставляемых конъюнкций.

Определение. Безызбыточное покрытие с минимальной суммой весов его строк называется минимальным покрытием.

Безызбыточному покрытию сопоставляется безызбыточная, или тупиковая, ДНФ функции f( ,…, ).

Кратчайшему покрытию сопоставляется кратчайшая ДНФ функции f( ,…, ).

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

Минимальному покрытию сопоставляется минимальная ДНФ функции f( ,…, ).

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

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

Итак, задача построения минимальных и кратчайших ДНФ булевой функции f( ,…, ) сводится к построению минимальных и кратчайших покрытий столбцов таблицы Квайна.

В нашем примере приведенные выше покрытия являются одновременно кратчайшими и минимальными. В общем случае минимальное покрытие может не быть кратчайшим.