Лекция 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).

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

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

Любую булеву функцию моно представить в виде ДНФ или КНФ. Равносильными преобразованиями можно представить формулу с меньшим количеством переменных. Например:

первое преобразование не выводит формулу из класса ДНФ, а последнее – выводит. Будем минимизировать формулы только в классе ДНФ.

ДНФ формулы А называется минимальной. Если она содержит наименьшее число вхождений переменных по сравнению с остальными ДНФ этой формулы.

Значит, минимальную ДНФ можно найти, перебрав все ДНФ. Но при большом количестве переменных этот способ практически не применим. Существуют эффективные способы нахождения минимальной ДНФ. Рассмотрим некоторые из них.

Первый из способов, на котором мы остановимся называется методом минимизирующих карт. Он может показаться громоздким, но преимущество этого способа в его простоте и возможности реализации на компьютере.

Булева функция должна быть задана таблицей истинности или какой –либо совершенной нормальной формой. Составляют карту, которая имеет вид:

далее используют утверждение:

если какая- либо конъюнкция, содержащая все переменные и принадлежащая j – той строке карты, не входит в СДНФ, выражающую функцию , то любая конъюнкция этой строки не входит ни в какую ДНФ, выражающую исходную функцию.

Опираясь на данное утверждение, получаем алгоритм построения минимальной ДНФ.

1. Отметим в карте строки, в которых конъюнкция (в последнем столбце) не принадлежит СДНФ формулы;

2. Вычеркнем все конъюнкции в этих строках и во всех остальных строках карты;

3. В каждой строке выберем из оставшихся конъюнкций конъюнкции с наименьшим числом переменных, остальные вычеркнем;

4. В каждой строке выберем по одному оставшемуся элементу и составим из них ДНФ;

5. Из всех составленных ДНФ выберем минимальную.

Пример: Составим карту:

x	y	z	x y	xz	yz	xyz	-
x	y		xy	x	y	xy	+
x		z	x	xz	z	x z	+
	y	z	y	z	yz	yz	-
	y		y		y	y	-
		z		z	z	z	+
х			x	x		x	+
							-

Вычеркнем конъюнкции, отсутствующие в формуле и соответствующие строки. Вычеркнутые конъюнкции вычеркнуть и в остальных строках.

Составим всевозможные ДНФА, выбирая из каждой строки по одной оставшейся конъюнкции:

ДНФ₂А является минимальной.