Файл: Булевы функции.doc

№	Простые импликанты				Конституенты единицы функции f
№	x₁	x₂	x₃	x₄	0000	0001	0010	0011	0101	1000	1010	1100	1101	1110	1111
1	1	1	-	-								+	+	+	+
2	0	0	-	-	+	+	+	+
3	-	0	-	0	+		+			+	+
4	1	-	-	0						+	+	+		+
5	0	-	0	1		+			+
6	-	1	0	1					+				+

Шаг 4. Выбираем слагаемое 5 (табл. 39):

Таблица 39

№	Простые импликанты				Конституенты единицы функции f
№	x₁	x₂	x₃	x₄	0000	0001	0010	0011	0101	1000	1010	1100	1101	1110	1111
1	1	1	-	-								+	+	+	+
2	0	0	-	-	+	+	+	+
3	-	0	-	0	+		+			+	+
4	1	-	-	0						+	+	+		+
5	0	-	0	1		+			+
6	-	1	0	1					+				+

Поскольку все конституенты единицы покрыты, то одна из ТДНФ имеет вид

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

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

Пример 39.

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

Решение.

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

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

Таблица 40

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

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

Таблица 41

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

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

Таблица 42

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

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

Таблица 43

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

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

2.2.2.4. Алгоритм минимизации функций в классе ДНФ

1. Строим СДНФ функции f.

2. Строим сокращенную ДНФ функции f.