Лекция № 5. Геометрическая интерпретация булевых функций.

Определение 1.

Конъюнкция называется элементарной, если любая переменная встречается не более одного раза.

Определение 2.

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

Будем считать набор аргументов точками n-мерного пространства. Тогда функцией будет n-мерный куб.

Определение 3.

Интервалом k-ого ранга будем называть подмножество вершин n-мерного куба, соответствующей конъюнкции k-ого ранга.

Интервал большего ранга покрывает интервал меньшего ранга.

Пример.

Определение 4.

Интервал I называется максимальным, если не существует и , где – множество наборов значений аргументов, на которых функция равна 1.

Определение 5.

ДНФ, полученная покрытием множества максимальными интервалами, называется сокращенной ДНФ (СокДНФ).

Метод минимизации Куайн-Мак-Класки.

1. Нахождение первичных импликант. Все неотмеченные (не склеенные) мини термы называются первичными импликантами.

2. Построение таблицы и её разметка.

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

4. Вычеркивание лишних столбцов. Если 2 столбца имеют галочки в одних строках, то 1 их них можно вычеркнуть.

5. Вычеркивание лишних строк, если есть пустые строки.

Пример.

Смотри лабораторную работу.

Модификация Мак-Класки.

Мак-Класки решил вместо x писать двоичный код и разбивать на группы по числу единиц.

Лекция № 6.

МЕТОД БЛЕКА-ПОРЕЦКОГО.

Лемма 1.

Пусть , где . Тогда .



Если

Если 

Пример.

После получения первичных импликант применяем метод Мак-Класки со второго шага (таблица).

Метод минимизации в базисе .

Лемма 2.

–выражение, описывающее n-местную над n операндами.

Если , то эквивалентно , т. е.

–произвольный терм.





21|Страница