Алгоритм минимизации функций в классе днф
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 |
|
Дальнейшее склеивание невозможно. Все слагаемые предыдущего шага участвовали в операции склеивания, поэтому сокращенная ДНФ имеет вид:
предыдущаяследующая