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

Метод Квайна – Мак-Класки представляет собой предыдущий метод, но без геометрического построения п – мерных кубов: кубы присутствуют, но абстрактно.

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

В итеративной процедуре минимизации попарное сравнение можно производить только между соседними группами.

Нахождение простых импликат на первом этапе:

1. Все исходные конъюнктивные термы записываются в виде их двоичных наборов.

2. Все наборы разбиваются на непересекающиеся группы по числу единиц. Условие образования r-куба – наличие расхождения в (r-1)-кубах только по одной координате в одном двоичном разряде и наличие общих независимых координат.

3. В i-группу включают все двоичные наборы, имеющие в своей записи i единиц.

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

Пример.

(Предыдущий пример)

Минимизировать булеву функцию

1 этап. Определение сокращенной ДНФ.

По двоичным наборам запишем 0-кубы:

К ⁰= {0011, 0100, 0101, 0111, 1001, 1011, 1100, 1101}.

Выполним их разбиение на подгруппы по количеству единиц:

Строим К ¹-кубы, сравнивая соседние подгруппы:

Выполним разбиение всех К ¹-кубов в зависимости от положения независимой координаты Х:

Выполним сравнение кубов внутри каждой подгруппы с целью построения К ²-кубов:

Поскольку они одинаковы, то

Записываем сокращенную ДНФ, в которую входят простые импликанты из К ¹ (не вошедшие в К ²) и К ²:

2 этап. Определение тупиковой ДНФ.

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

Простые импликанты	Исходные термы
	0011	0100	0101	0111	1001	1011	1100	1101
0 – 11	*			*
- 011	*					*
01 – 1			*	*
10 – 1					*	*
1 – 01					*			*
- 10 -		*	*				*	*

Определяя минимальное число строк, покрывающих все столбцы таблицы, находим тупиковую ДНФ:

Литература

1. Горбатов В.А. Основы дискретной математики. – М.: Высшая школа, 1986. – 311 с.

2. Коршунов Ю.М. Математические основы кибернетики. – М.: Энергоатомиздат, 1987. – 496 с.

3. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. – М.: Энергоатомиздат, 1988. – 480 с.

4. Сигорский В.П. Математический аппарат инженера. – М.: Техника, 1975. – 768 с.

5. Шапорев С.Д. Дискретная математика. – СПб., 2006. - 400 с.

6. Хаханов В.И., Чумаченко С.В. Дискретная математика. Конспект теоретического материала (электронная версия). ХНУРЭ, 2003.

7. Яблонский С.В. Введение в дискретную математику. – М.: Наука, 1979. – 272 с.

8. Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. – М.: ФИЗМАТЛИТ, 2005. – 416 с.