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

Пусть 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

a. N	P1 P2 … Pj …Pn
K1 K2 Ki Km	a11 a12 … a1j …a1n a21 a22 … a2j … a2n ai1 ai2 … aij … ain am1 am2… 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
b. 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. Все найденные ТДНФ являются минимальными ДНФ.

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

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

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

3. С помощью матрицы покрытий и решеточного выражения строим все ТДНФ функции f.

4. Среди построенных ТДНФ выбираем все минимальные дизъюнктивные нормальные формы функции f.

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

Чтобы построить все минимальные КНФ (МКНФ) функции f, следует построить все МДНФ функции `f и взять от каждой из них отрицание, для чего заменить знаки & на Ú , а Ú на & ( сохранив первоначальное распределение скобок) и над каждой буквой поставить знак отрицания. Полученные КНФ для функции f будут минимальными. В самом деле, если бы для f существовала КНФ с меньшим числом букв, то ее отрицание дало бы для `f ДНФ с меньшим числом букв, чем в любой из минимальных ДНФ для `f. Противоречие с их минимальностью.