Математическая логика
На втором этапе строится таблица покрытий.В строках этой таблицы указываются найденные простые импликанты, а в столбцах – термы исходного выражения функции. Клетки таблицы отмечаются, если простая импликанта входит в состав какого-либо терма. В итоге минимизация булевой функции сводится к тому, чтобы найти такое минимальное количество простых импликант, которые покрывают все столбцы. В результате получают тупиковую ДНФ.
Недостаток метода–необходимость попарного сравнении всех конъюнктивных термов на первом этапе при нахождении простых импликант. С ростом числа исходных термов увеличивается количество попарных сравнений, что усложняет решение задачи минимизации.
5.2 Метод Квайна с применением п-мерных кубов
Данный метод устраняет недостаток предыдущего метода, т.е. устраняет необходимость попарного сравнения всех термов на первом этапе при нахождении простых импликант. Для этого строится п-мерный куб, по которому визуально можно определить те конъюнктивные термы, склеивание которых порождают простые импликанты.
При решении задачи минимизации булевой функции удобно вместо конъюнктивных термов использовать, соответствующие им, двоичные наборы.
Пример.
Минимизировать булеву функцию
.
Здесь в скобках стоят десятичные эквиваленты соответствующих двоичных наборов.
Представим функцию в виде СДНФ:
![]()
Запишем конъюнктивные термы в виде двоичных наборов:
.
Построим единичный 4 – мерный куб и выделим вершины, соответствующие двоичным наборам, входящим в заданную булеву функцию (рис. 10):

Рис. 10
1 этап. Определение сокращенной ДНФ.
Применим закон склеивания для отмеченных вершин (для двоичных наборов) куба, соединенных ребром:

Прочерк означает, что переменная в этом месте отсутствует.
Для некоторых простых импликант склеивание можно продолжить:
![]()
По закону
идемпотентности:
![]()
Дизъюнкция полученных простых импликант является сокращенной ДНФ:
![]()
2 этап. Определение тупиковой ДНФ.
Для определения тупиковой ДНФ построим таблицу покрытий, в которую следует включать и двоичные наборы, не участвовавшие в склеивании:
| Простые импликанты | Исходные термы | |||||||
| 0011 | 0100 | 0101 | 0111 | 1001 | 1011 | 1100 | 1101 | |
| 0 – 11 | * | * |
|
||||||
|
|
* | * | |||||||
|
|
* | * | |||||||
| 10 – 1 | * | * | |||||||
| 1 – 01 | * | * | |||||||
|
|
* | * | * |
Определяя минимальное число строк, покрывающих все столбцы таблицы, находим тупиковую ДНФ:
![]()
Недостатком
метода
является
само построение
п –
мерного куба,
т.к. при числе
переменных
это построение
затруднительно.
5.3 Метод Квайна – Мак-Класки
Метод Квайна – Мак-Класки представляет собой предыдущий метод, но без геометрического построения п – мерных кубов: кубы присутствуют, но абстрактно.
Метод основан на кубическом представлении конъюнктивных термов ДНФ с предварительным разбиением кубов на подгруппы, определяемые одинаковым числом единиц. Разбиение дает возможность сравнивать кубы только соседних по числу единиц групп для уменьшения количества переборов.
В итеративной процедуре минимизации попарное сравнение можно производить только между соседними группами.
Нахождение простых импликат на первом этапе:
1. Все исходные конъюнктивные термы записываются в виде их двоичных наборов.
2. Все наборы разбиваются на непересекающиеся группы по числу единиц. Условие образования r-куба – наличие расхождения в (r-1)-кубах только по одной координате в одном двоичном разряде и наличие общих независимых координат.
3. В i-группу включают все двоичные наборы, имеющие в своей записи i единиц.
4. Попарное сравнение производится только между соседними по номеру группами. Группы, которые различаются в двух разрядах и более, не имеет смысла сравнивать.
Пример.
(Предыдущий пример)
Минимизировать булеву функцию
![]()
1 этап. Определение сокращенной ДНФ.
По двоичным наборам запишем 0-кубы:
К 0 = {0011, 0100, 0101, 0111, 1001, 1011, 1100, 1101}.
Выполним их разбиение на подгруппы по количеству единиц:

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

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

Выполним сравнение кубов внутри каждой подгруппы с целью построения К 2-кубов:
![]()
Поскольку
они одинаковы,
то
![]()
Записываем сокращенную ДНФ, в которую входят простые импликанты из К 1 (не вошедшие в К 2) и К 2:
![]()
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 с.