Построение всех тупиковых ДНФ

Пусть f (x ₁, …, x_n) есть функция алгебры логики.

1. Построим СДНФ функции f, и пусть P ₁, P ₂, …, P_n есть ее коституенты единицы).

2. Построим сокращенную ДНФ функции, f и пусть K ₁, K ₂, …, K_m – ее простые импликанты.

3. Построим матрицу покрытий простых импликант функции f ее конституентами единицы (табл. 3.4), полагая, что

+, если каждый множитель в K_i является множителем в P_j; (P_j есть a_ij = часть для K_i);

Æ в противном случае.

 

Таблица 3.4

N	P 1 P 2 … Pj … Pn
K 1 K 2 Ki Km	a 11 a 12 … a 1 j …a 1 n a 21 a 22 … a 2 j … a 2 n ai 1 ai 2 … aij … ain am 1 am 2 … amj … amn

 

4. Для каждого столбца j (1 £ j £ n) найдем множество E_j всех тех номеров I строк, для которых a_ij = 1. Пусть Составим выражение Назовем его решеточным выражением. Это выражение можно рассматривать как формулу, построенную в свободной дистрибутивной решетке с образующими 1, 2, …, m и с операциями & и Ú.

5. В выражении A раскроем скобки, приведя выражение A к равносильному выражению где перечислены все конъюнкции элементы которой взяты из скобок 1, 2, …, n соответственно в выражении A.

6. В выражении B проведем все операции удаления дублирующих членов и все операции поглощения. В результате получим дизъюнкцию элементарных конъюнкций C.

Утверждение. Каждая элементарная конъюнкция i ₁& i ₂& …& i_r в С дает ТДНФ для f. Все ТДНФ для функции f исчерпываются элементарными конъюнкциями в выражении С.

Пример 5. Сокращенная ДНФ для функции f = (1111010010101111) имеет вид

Для функции f построим все минимальные ДНФ.

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

Таблица 3.5

		Конституенты единицы функции f
N	ПИ	x ` x ` x ` x ` x x x x x x x y ` y ` y ` y y ` y ` y y y y y z ` z z z ` z ` z z ` z ` z z z t t ` t t t ` t ` t ` t t t t
	x y ` x ` y ` y ` t x ` t ` x ` z t y ` z t	+ + + + + + + + + + + + + + + + + + + +

 

2. Строим решеточное выражение (по столбцам таблицы).

E = (2Ú 3)(2Ú 5)(2Ú 3)2(5Ú 6)(3Ú 4)(3Ú 4)(1Ú 4)(1Ú 6)(1Ú 4)(1) = (2Ú 3)(2Ú 5)(5Ú 6)(3Ú 4)(1Ú 4)(1Ú 6)12 = (5Ú 6)(3Ú 4)(1)(2) = 1235Ú 1245Ú 1236Ú 1246.

3. Строим все тупиковые ДНФ функции f:

простые импликанты 1, 2, 3, 5;

простые импликанты 1, 2, 4, 5;

простые импликанты 1, 2, 3, 6;

простые импликанты 1, 2, 4, 6.

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