Пусть f(x1, …, x n) есть функция алгебры логики.
1. Построим CДНФ функции f, и пусть P1, P2, …, P n есть ее конституенты единицы).
2. Построим сокращенную ДНФ функции f, и пусть K1, K2, …, K m – ее простые импликанты.
3. Построим матрицу покрытий простых импликант функции f ее конституентами единицы (табл. 4.4), полагая, что
Таблица 4.4
| 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 ) найдем множество Ej всех тех номеров I строк, для которых a ij = 1. Пусть 
Cоставим выражение 
Назовем его решеточным выражением. Это выражение можно рассматривать как формулу, построенную в свободной дистрибутивной решетке с образующими 1, 2, …, m и с операциями & и Ú .
5. В выражении A раскроем скобки, приведя выражение A к равносильному выражению 
где перечислены все конъюнкции 
элементы 
которой взяты из скобок 1, 2, …, n соответственно в выражении A.
6. В выражении B проведем все операции удаления дублирующих членов и все операции поглощения. В результате получим дизъюнкцию элементарных конъюнкций C.
Утверждение. Каждая элементарная конъюнкция i1&i2&…&ir в С дает ТДНФ 
для f . Все ТДНФ для функции f исчерпываются элементарными конъюнкциями в выражении С.
Пример 5. Cокращенная ДНФ для функции
f = (1111010010101111) имеет вид 
Для функции f построим все минимальные ДНФ.
1. Строим матрицу покрытий (табл. 4.5).
Таблица 4.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 | ||
| Продолжение табл. 4.5 | ||||||||||||
| 1 | x y | + | + | + | + | |||||||
| 2 | `x`y | + | + | + | + | |||||||
| 3 | `y`t | + | + | + | + | |||||||
| 4 | x`t | + | + | + | + | |||||||
| 5 | `x`z t | + | + | |||||||||
| 6 | y`z t | + | + | |||||||||
2. Cтроим решеточное выражение (по столбцам таблицы).
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. Cтроим все тупиковые ДНФ функции f:
простые импликанты 1, 2, 3, 5;
простые импликанты 1, 2, 4, 5;
простые импликанты 1, 2, 3, 6;
простые импликанты 1, 2, 4, 6.
4. Все найденные ТДНФ являются минимальными ДНФ.
Алгоритм минимизации функций в классе ДНФ
1. Cтроим CДНФ функции f.
2. Cтроим сокращенную ДНФ функции f.
3. C помощью матрицы покрытий и решеточного выражения строим все ТДНФ функции f.
4. Cреди построенных ТДНФ выбираем все минимальные дизъюнктивные нормальные формы функции f.
Дата: 2019-04-23, просмотров: 250.
