2.2.2.1. Алгоритм Куайна построения сокращенной ДНФ
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.
Проводим все операции неполного склеивания.Первый этап склеивания (табл. 22):
Таблица 22
| Слагаемые | Склеивание по | Результат | Новые слагаемые |
| 1, 2 | x4 |  | 1 |
| 1, 3 | x3 |  | 2 |
| 1, 6 | x1 |  | 3 |
| 2, 4 | x3 |  | 4 |
| 2, 5 | x2 |  | 5 |
| 3, 4 | x4 |  | 6 |
| 3, 7 | x1 |  | 7 |
| 5, 9 | x1 |  | 8 |
| 6, 7 | x3 |  | 9 |
| 6, 8 | x2 |  | 10 |
| 7, 10 | x2 |  | 11 |
| 8, 9 | x4 |  | 12 |
| 8, 10 | x3 |  | 13 |
| 9, 11 | x3 |  | 14 |
| 10, 11 | x4 |  | 15 |
В первом этапе склеивания участвовали все слагаемые СДНФ, значит, ни одно из исходных слагаемых не войдут в сокращенную ДНФ. После первого этапа склеивания (и возможных поглощений) получаем, что
Пронумеруем дизъюнктивные члены в полученной ДНФ в порядке их следования от 1 до 15 (табл.
23).Второй этап склеивания:
Таблица 23
| Слагаемые | Склеивание по | Результат |
| 1, 6 | x3 |  |
| 2, 4 | x4 | |
| 2, 9 | x1 |  |
| 3, 7 | x3 | |
| 9, 13 | x2 |  |
| 10, 11 | x3 | |
| 12, 15 | x3 |  |
| 13, 14 | x4 | |
В процедуре склеивания на втором этапе не принимали участие слагаемые № 5, 8 с предыдущего шага, поэтому после второго этапа склеивания и последующих поглощений получаем, что
Поскольку дальнейшее склеивания невозможны, то это и будет сокращенная ДНФ исходной функции.