Построение всех тупиковых ДНФПусть f (x 1, …, xn) есть функция алгебры логики. 1. Построим СДНФ функции f, и пусть P 1, P 2, …, Pn есть ее коституенты единицы). 2. Построим сокращенную ДНФ функции, f и пусть K 1, K 2, …, Km – ее простые импликанты. 3. Построим матрицу покрытий простых импликант функции f ее конституентами единицы (табл. 3.4), полагая, что +, если каждый множитель в Ki является множителем в Pj; (Pj есть aij = часть для Ki); Æ в противном случае.
Таблица 3.4
4. Для каждого столбца j (1 £ j £ n) найдем множество Ej всех тех номеров I строк, для которых aij = 1. Пусть 5. В выражении A раскроем скобки, приведя выражение A к равносильному выражению 6. В выражении B проведем все операции удаления дублирующих членов и все операции поглощения. В результате получим дизъюнкцию элементарных конъюнкций C. Утверждение. Каждая элементарная конъюнкция i 1& i 2& …& ir в С дает ТДНФ Пример 5. Сокращенная ДНФ для функции f = (1111010010101111) имеет вид Для функции f построим все минимальные ДНФ. 1. Строим матрицу покрытий (таблица 3.5). Таблица 3.5
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:
4. Все найденные ТДНФ являются минимальными ДНФ.
|
Составим выражение 
Назовем его решеточным выражением. Это выражение можно рассматривать как формулу, построенную в свободной дистрибутивной решетке с образующими 1, 2, …, m и с операциями & и Ú.
где перечислены все конъюнкции 
элементы 
которой взяты из скобок 1, 2, …, n соответственно в выражении A.
для f. Все ТДНФ для функции f исчерпываются элементарными конъюнкциями в выражении С.
простые импликанты 1, 2, 3, 5;
простые импликанты 1, 2, 4, 5;
простые импликанты 1, 2, 3, 6;
простые импликанты 1, 2, 4, 6.
