Алгоритм куайна построения сокращенной днф
1. Получить СДНФ функции.
2. Провести все операции неполного склеивания.
3. Провести все операции поглощения.
Пример 35.
Минимизировать функцию f=1111010010101111.
Решение.
1. Строим таблицу значения для данной функции (табл. 20). Строим СДНФ функции. При этом слагаемые нумеруем и записываем в столбец (табл. 21).
Таблица 20
|
№ |
x1 |
x2 |
x3 |
x4 |
f(x1, x2, x3, х4) |
|
0 |
0 |
0 |
0 |
0 |
1 |
|
1 |
0 |
0 |
0 |
1 |
1 |
|
2 |
0 |
0 |
1 |
0 |
1 |
|
3 |
0 |
0 |
1 |
1 |
1 |
|
4 |
0 |
1 |
0 |
0 |
0 |
|
5 |
0 |
1 |
0 |
1 |
1 |
|
6 |
0 |
1 |
1 |
0 |
0 |
|
7 |
0 |
1 |
1 |
1 |
0 |
|
8 |
1 |
0 |
0 |
0 |
1 |
|
9 |
1 |
0 |
0 |
1 |
0 |
|
10 |
1 |
0 |
1 |
0 |
1 |
|
11 |
1 |
0 |
1 |
1 |
0 |
|
12 |
1 |
1 |
0 |
0 |
1 |
|
13 |
1 |
1 |
0 |
1 |
1 |
|
14 |
1 |
1 |
1 |
0 |
1 |
|
15 |
1 |
1 |
1 |
1 |
1 |
СДНФ (1): № 0, 1, 2, 3, 5, 8, 10, 12, 13, 14, 15.
Таблица 21
|
№ слагаемого |
слагаемое |
|
1 |
|
|
2 |
|
|
3 |
|
|
4 |
|
|
5 |
|
|
6 |
|
|
7 |
|
|
8 |
|
|
9 |
|
|
10 |
|
|
11 |
|
2. Проводим все операции неполного склеивания.
предыдущаяследующая