ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 05.09.2025
Просмотров: 500
Скачиваний: 0
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 |
Таблица 44
|
№ слагаемого |
Слагаемое СДНФ |
|
1 |
|
|
2 |
|
|
3 |
|
|
4 |
|
|
5 |
2. Проводим все операции неполного склеивания (табл. 45):
Таблица 45
|
Слагаемые |
Склеивание по |
Результат |
|
1, 2 |
х2 |
|
|
1, 4 |
х1 |
|
|
3, 4 |
х3 |
|
|
3, 5 |
х2 |
Дальнейшее склеивание невозможно. Все слагаемые предыдущего шага участвовали в операции склеивания, поэтому сокращенная ДНФ имеет вид:
.
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):
Таблица 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 |