![]() КАТЕГОРИИ:
АстрономияБиологияГеографияДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРиторикаСоциологияСпортСтроительствоТехнологияФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
|
Построение всех тупиковых ДНФ.Пусть f(x1, …, xn) есть функция алгебры логики. 1. Построим СДНФ функции f, и пусть P1, P2, …,Pn есть ее коституенты единицы). 2. Построим сокращенную ДНФ функции, f и пусть K1, K2, …, 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. Утверждение.Каждая элементарная конъюнкция i1&i2&…&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. Все найденные ТДНФ являются минимальными ДНФ.
|