85990 (Математическая логика), страница 5

Представим функцию в виде СДНФ:

Запишем конъюнктивные термы в виде двоичных наборов:

.

Построим единичный 4 – мерный куб и выделим вершины, соответствующие двоичным наборам, входящим в заданную булеву функцию (рис. 10):

Рис. 10

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

Применим закон склеивания для отмеченных вершин (для двоичных наборов) куба, соединенных ребром:

Прочерк означает, что переменная в этом месте отсутствует.

Для некоторых простых импликант склеивание можно продолжить:

По закону идемпотентности:

Дизъюнкция полученных простых импликант является сокращенной ДНФ:

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

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

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

Недостатком метода является само построение п – мерного куба, т.к. при числе переменных это построение затруднительно.

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

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

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

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

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

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

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

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

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

Пример.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Литература

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

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

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

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

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

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

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

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