2.2.2.4. Алгоритм минимизации функций в классе ДНФ
1. Строим СДНФ функции f.
2. Строим сокращенную ДНФ функции f.
3. С помощью матрицы покрытий и решеточного выражения строим все ТДНФ функции f.
4. Среди построенных ТДНФ выбираем все минимальные дизъюнктивные нормальные формы функции f.
Пример 40.
В классе нормальных форм минимизировать функцию f=01011110.
Решение.
Для построения сокращенной ДНФ используем алгоритм Куайна. Строим СДНФ для функции f. Таблица значений имеет вид (табл. 43):
Таблица 43
| № | x1 | x2 | x3 | f |
| 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 1 | 1 |
| 2 | 0 | 1 | 0 | 0 |
| 3 | 0 | 1 | 1 | 1 |
| 4 | 1 | 0 | 0 | 1 |
| 5 | 1 | 0 | 1 | 1 |
| 6 | 1 | 1 | 0 | 1 |
| 7 | 1 | 1 | 1 | 0 |
СДНФ (1): № 1, 3, 4, 5, 6 (табл.44):
Таблица 44
| № слагаемого | Слагаемое СДНФ |
| 1 |  |
| 2 |  |
| 3 |  |
| 4 |  |
| 5 |  |
2. Проводим все операции неполного склеивания (табл. 45):
Таблица 45
| Слагаемые | Склеивание по | Результат |
| 1, 2 | х2 |  |
| 1, 4 | х1 |  |
| 3, 4 | х3 |  |
| 3, 5 | х2 |  |
Дальнейшее склеивание невозможно.
Все слагаемые предыдущего шага участвовали в операции склеивания, поэтому сокращенная ДНФ имеет вид:
UUU.
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 | + | + | |||
В результате МДНФ имеет вид: UU.
Пример 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):
Таблица 49
| № | 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 |
Шаг 3. В каждом столбце из сохранившихся чисел вычеркиваем те, равные которым уже вычеркнуты в этом столбце на предыдущем шаге (табл.
50):Таблица 50
| № | 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 |
Шаг 4. В сохранившихся строках выбираем «значения» наименьших по числу множителей конъюнкций (включая и конъюнкции с одним множителем – переменные) и обводим их (табл. 51):
Таблица 51
| № | 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 |
Шаг 5.
Если в одном столбце обведено несколько одинаковых чисел, то вычеркиваем все, кроме одного (табл. 52):Таблица 52
| № | 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 |
Шаг 6. Сокращенная ДНФ имеет вид: 
Строим матрицу покрытий (табл. 53).
Таблица 53
| № | Простые импликанты | Конституенты единицы функции f | |||||||
| x1 | x2 | x3 | 000 | 001 | 011 | 100 | 110 | 111 | |
| 1 | 0 | 0 | - | + | + | ||||
| 2 | 1 | 1 | - | + | + | ||||
| 3 | 0 | - | 1 | + | + | ||||
| 4 | 1 | - | 0 | + | + | ||||
| 5 | - | 0 | 0 | + | + | ||||
| 6 | - | 1 | 1 | + | + | ||||
Последовательно выбираем слагаемые: № 1, 2, 5, 6 (табл.
54).Таблица 54
| № | Простые импликанты | Конституенты единицы функции f | |||||||
| x1 | x2 | x3 | 000 | 001 | 011 | 100 | 110 | 111 | |
| 1 | 0 | 0 | - | + | + | ||||
| 2 | 1 | 1 | - | + | + | ||||
| 3 | 0 | - | 1 | + | + | ||||
| 4 | 1 | - | 0 | + | + | ||||
| 5 | - | 0 | 0 | + | + | ||||
| 6 | - | 1 | 1 | + | + | ||||
В результате МДНФ имеет вид: 