Построение всех тупиковых днф

Все найденные ТДНФ являются минимальными ДНФ.

Пример 39.

Построить одну из МДНФ функции f=11100101.

Решение.

Сокращенная ДНФ для данной функции имеет вид

Строим матрицу покрытий (табл. 40):

Таблица 40

№	Простые импликанты			Конституенты единицы функции f
№	x1	x2	x3	000	001	010	101	111
1	0	0	-	+	+
2	0	-	0	+		+
3	1	-	1				+	+
4	-	0	1		+		+

Шаг 1. Выбираем слагаемое 3 (табл. 41):

Таблица 41

№	Простые импликанты			Конституенты единицы функции f
№	x1	x2	x3	000	001	010	101	111
1	0	0	-	+	+
2	0	-	0	+		+
3	1	-	1				+	+
4	-	0	1		+		+

Шаг 2. Выбираем слагаемое 2 (табл. 42):

Таблица 42

№	Простые импликанты			Конституенты единицы функции f
№	x1	x2	x3	000	001	010	101	111
1	0	0	-	+	+
2	0	-	0	+		+
3	1	-	1				+	+
4	-	0	1		+		+

Шаг 3. Выбираем слагаемое 1(табл. 43):

Таблица 43

№	Простые импликанты			Конституенты единицы функции f
№	x1	x2	x3	000	001	010	101	111
1	0	0	-	+	+
2	0	-	0	+		+
3	1	-	1				+	+
4	-	0	1		+		+

В результате получаем МДНФ:

Дискретная математика