Лекция 8

ТЕМА: МИНИМИЗАЦИЯ В КЛАССЕ ДИЗЪЮНКТИВНЫХ НОРМАЛЬНЫХ ФОРМ.

ПЛАН:

1. Формула номера набора в таблице истинности.

2. Понятие минимальной ДНФ. Метод минимизирующих карт.

3. Метод Квайна.

4. Метод Карно.

5. Постановка задачи минимизации в геометрической форме.

6. Сокращенная ДНФ.

7. Тупиковая ДНФ. ДНФ Квайна.

Главная

1. Формула номера набора в таблице истинности.

Для удобства задания булевой функции введем формулу, связывающую номер набора в таблице истинности со значениями переменных в наборе: , n – количество переменных в функции, i – порядковый номер единицы или нуля в наборе. Рассмотрим пример: f(00101011) или f(3,5,6,7)=1. Найдем наборы при которых функция равна 1, тогда на остальных наборах функция равна 0: функция от трех переменных, значит, n =3,

3=2¹+2⁰=2^3-2+2^3-3 : (011);

5=2²+2⁰=2 ^3-1+2^3-3 : (101);

7=2²+2¹+2⁰ = 2 ^3-1+2 ^3-2 + 2 ^3-3 :(111);

Для N =8 : (000).

Заметим, что предпоследний набор состоит из единиц, последний - из нулей.