Алгоритм минимизации функций в классе днф
Ъ
Ъ
Ъ
.
3. Строим матрицу покрытий (табл. 46).
Таблица 46
|
№ |
Простые импликанты |
Конституенты единицы функции f |
||||||
|
x1 |
x2 |
x3 |
001 |
011 |
100 |
101 |
110 |
|
|
1 |
0 |
- |
1 |
+ |
+ |
|||
|
2 |
- |
0 |
1 |
+ |
+ |
|||
|
3 |
1 |
0 |
- |
+ |
+ |
|||
|
4 |
1 |
- |
0 |
+ |
+ |
|||
Последовательно выбираем слагаемые: № 4, 1, 2 (табл. 47).
Таблица 47
|
№ |
Простые импликанты |
Конституенты единицы функции f |
||||||
|
x1 |
x2 |
x3 |
001 |
011 |
100 |
101 |
110 |
|
|
1 |
0 |
- |
1 |
+ |
+ |
|||
|
2 |
- |
0 |
1 |
+ |
+ |
|||
|
3 |
1 |
0 |
- |
+ |
+ |
|||
|
4 |
1 |
- |
0 |
+ |
+ |
|||
В результате МДНФ имеет вид: ЪЪ.
Пример 41.
Построить МДНФ функции f=11011011.
Решение.
Для построения сокращенной ДНФ используем минимизационную карту (табл. 48).
Шаг 1.
Таблица 48
|
№ |
x1 |
x2 |
x3 |
x1x2 |
x1x3 |
x2x3 |
x1x2x3 |
f(x1, x2, x3) |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
|
1 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
|
2 |
0 |
1 |
0 |
1 |
0 |
2 |
2 |
0 |
|
3 |
0 |
1 |
1 |
1 |
1 |
3 |
3 |
1 |
|
4 |
1 |
0 |
0 |
2 |
2 |
0 |
4 |
1 |
|
5 |
1 |
0 |
1 |
2 |
3 |
1 |
5 |
0 |
|
6 |
1 |
1 |
0 |
3 |
2 |
2 |
6 |
1 |
|
7 |
1 |
1 |
1 |
3 |
3 |
3 |
7 |
1 |
Шаг 2. Вычеркиваем строки, в которых функция обращается в нуль (табл. 49):
предыдущаяследующая