Минимизация булевых функций в классе КНФ (Конъюнктивная нормальная форма).

Операция склеивания (А*Х_i) È(А* Х _i)=А

Операция поглощения (А) È(А*Х_k)=А

Х1	Х2	Х3	Х4	f

Выделим наборы, на которых функция принимает нулевые значения.

Если произошла операция склеивания, то записываем набор только в склеенном виде. Если набор не участвовал в склеивании, то оставляем его в несклеенном виде.

	0 1 1 1 1 0 1 1	*	*
2	0 0 1 1 1 1 0 0	*	*		*
	0 1 0 0 1 0 0 0				* *	*	*
	0 0 0 0					*	*

Булевы функции после склеивания:

0 — 1 1

— 0 1 1

— 1 0 0

1 — 0 0

0 — 0 0

— 0 0 0

Прочерк на первом месте:

1	—0 1 1
	—1 0 0		*
	—0 0 0		*

После склеивания получим:

— 0 1 1

Прочерк на втором месте:

	1 — 0 0	*		*
2	0 — 1 1
	0 — 0 0	*		*

После склеивания получим:

0 — 1 1

— — 0 0

Имеем три набора после вторичной операции склеивания:

— — 0 0

0 — 1 1

— 0 1 1

Таблица реализации:

Исходные наборы дизъюнкции	Имплиценты
(X2 È X3 È X4)	(X1 È X3 È X4)	(X3 È X4)
(X1 ÈX2 È X3 È X4)
(X1 ÈX2 È X3 È X4)
(X1 ÈX2 È X3 È X4)

Получаем:

f=(X2 È X3 È X4)*(X1 È X3 È X4)*(X3 È X4)

Дата добавления: 2015-08-21