Метод импликантных матриц

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

 

			…		…
…
				+
…

 

Для каждой находим набор такой, что .

Клетку импликантной матрицы, образованную пересечением i-строки и j-столбца отметим крестиком.

Чтобы получить минимальную ДНФ заданной функции, достаточно найти минимальное число , которое совместно накрывают крестиками все столбцы импликантной матрицы.

Пример 6 Найти минимальные ДНФ для функции

.

Из предыдущего примера следует, что сокращенная ДНФ для данной функции . Очевидно, что

.

Строим импликантную матрицу в виде таблицы

 

	(0,0,1)	(0,1,0)	(0,1,1)	(1,0,0)	(1,0,1)	(1,1,0)
				+	+
				+		+
		+	+
		+				+
	+		+
	+				+

 

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

; .

 

Вопросы для самоконтроля

1 Какая ДНФ называется минимальной?

2 Чему равно число всех ДНФ от переменных?

3 Сформулируйте тривиальный алгоритм построения МДНФ?

4 Что такое элементарная конъюнкция?

5 Что такое ранг элементарной конъюнкции?

6 Что называется интервалом элементарной конъюнкции?

7 Какой интервал называется максимальным?

8 Что называется областью истинности булевой функции?

9 Сформулируйте теорему об области истинности булевой функции.

10 Что называется покрытием области истинности булевой функции?

11 Какое число элементов содержится в интервале?

12 Какая ДНФ называется сокращенной?

13 В чем состоит геометрическая интерпретация задачи минимизации булевой функции?

14 Сформулируйте геометрический метод построения сокращенной ДНФ.

15 Сформулируйте метод Нельсона построения сокращенной ДНФ.

16 Сформулируйте метод Блейка построения сокращенной ДНФ.

17 Сформулируйте метод карт Карно построения сокращенной ДНФ.

18 Какая связь между МДНФ и сокращенной ДНФ?

19 Какое покрытие области истинности булевой функции называется неприводимым?

20 Какая ДНФ называется тупиковой?

21 Какая связь между МДНФ и тупиковой ДНФ?

22 Сформулируйте алгоритм построения всех тупиковых ДНФ.

23 Как строится импликантная матрица?

24 Сформулируйте алгоритм нахождения МДНФ методом импликантных матриц.