Составители:
Пример минимизации по Квайну
−
Мак Класки. Исходная функция че-
тырех переменных:
∨∨∨∨=
4
3
2143
2
14
32
143
21
xxxxxxxxxxxxxxxxY
.
43
2
14
32
143
21
4
321
4321
xxxxxxxxxxxxxxxxxxxx ∨∨∨∨∨
(1.46)
Выпишем в столбик в виде двоичных чисел импликанты, входящие в вы-
ражение (1.46), как рекомендовано в п.1, и произведем разбиение на группы:
0 0 0 1
∨ 0 0 0 1∨ 0 − 0 1∨ − − 0 1
0 1 0 0
∨ 0 1 0 0∨ − 0 0 1∨ 0 1 − −
0 1 0 1
∨ 1 0 0 0∨ 0 1 0 −∨ − 1 0 −
0 1 1 0
∨ -------- 0 1 − 0∨ 1 − 0 −
0 1 1 1
∨ 0 1 0 1∨ − 1 0 0∨
1 0 0 0
∨ 0 1 1 0∨ 1 0 0 −∨
1 0 0 1
∨ 1 0 0 1∨ 1 − 0 0∨
1 1 0 0
∨ 1 1 0 0∨ ---------
1 1 0 1
∨ --------- 0 1 − 1∨
0 1 1 1
∨ − 1 0 1∨
1 1 0 1
∨ 0 1 1 −∨
1
− 0 1∨
1 1 0
−∨
Последний, самый короткий столбик, позволяет получить сокращенную
ДНФ функции в виде:
.
3
1
3
2
2143
xxxxxxxxY ∨∨∨=
(1.47)
Таблица импликантов, соответствующая (1.47), представлена в табл. 1. 6.
Таблица 1. 6
Простые Члены канонической суммы
импликанты 0001 0100 0101 0110 0111 1000 1001 1100 1101
− − 0 1 *
+ + + +
0 1
− − *
+ + + +
− 1 0 −
+ + + +
1
− 0 − *
+ + + +
В табл. 1. 6 отмечены звездочками те простые импликанты, которые обя-
зательно должны войти в любую тупиковую форму (столбцы с единственным
крестиком) – это существенные простые импликанты. Не отмеченный звез-
дочкой простой импликант не является существенным и не должен входить в
минимальную тупиковую форму, т. е. он – лишний. Минимальная тупиковая
форма, полученная из таблицы импликант, представлена в виде (1.48):
.
3
1
2143
xxxxxxY ∨∨=
(1.48)
22
Страницы
- « первая
- ‹ предыдущая
- …
- 20
- 21
- 22
- 23
- 24
- …
- следующая ›
- последняя »
