Составители:
8
мальной ценой. При этом для получения МДНФ используется единичное
покрытие, а для получения МКНФ – нулевое.
Ценой покрытия
S
a
называется сумма цен кубов, образующих покры-
тие. Цена k-куба (S
k
) определяется количеством зависимых (не Х-ых) коор-
динат в его записи и определяется в виде: S
k
= n – k (n – число аргументов
минимизируемой булевой функции). Ценой покрытия S
b
называется сум-
ма цены S
a
и количества кубов, входящих в покрытие. Цены покрытия S
a
и S
b
при соблюдении определенных условий являются нижней и верхней
границами цены схемы по Квайну, т.е. S
a
≤ S
Q
≤ S
b
.
Обычно задача нахождения аналитических форм булевых функций,
обеспечивающих минимум цены схемы, решается в два этапа. На первом
этапе определяется МДНФ и/или МКНФ функции. На втором этапе прово-
дится их упрощение путем решения задач факторизации и, возможно, де-
композиции.
В задачах минимизации булевых функций используется понятие про-
стой импликанты. Некоторый
куб z ∈ K(f) называется простой импликан-
той, если он не содержится ни в одном кубе комплекса K(f), т.е. является
максимальным [2, 3]. Совокупность всех таких кубов образует множество
Z(f) простых импликант данной функции. Любой куб минимального по-
крытия C
min
(f) является простой импликантой, следовательно, C
min
(f)
⊆
Z(f).
Замечания.
1. Используемое в учебном пособии понятие простой импликанты как
максимального куба из покрытия булевой функции является упрощенным.
В классической булевой алгебре [1, 4] под импликантой понимается булева
функция, причем понятие импликанты определяет отношение покрытия
(включения) между двумя булевыми функциями: g(x) является импликан-
той f(x), если g(x)⊆ f(x). В соответствии с этим под простой (
первичной)
импликантой булевой функции понимается конъюнктивный терм, который
сам по себе является импликантой этой функции, но никакая его собствен-
ная часть уже не является импликантой.
В рамках кубического представления булевых функций простая им-
пликанта как конъюнктивный терм составляется для каждого максималь-
ного куба минимального покрытия и дизъюнкция простых импликант
представляет собой
МДНФ булевой функции.
2. Понятие импликанты и простой импликанты связаны с минимиза-
цией булевой функции по единичному покрытию. При нахождении мини-
мального нулевого покрытия и, соответственно, МКНФ используется по-
нятие имплиценты. В упрощенном представлении (в рамках курсовой ра-
боты) под простой имплицентой понимается максимальный куб нулевого
покрытия булевой функции. В
классическом представлении простая им-
плицента является дизъюнктивным термом, соответствующем некоторому
максимальному кубу нулевого покрытия булевой функции. Таким образом,
Страницы
- « первая
- ‹ предыдущая
- …
- 6
- 7
- 8
- 9
- 10
- …
- следующая ›
- последняя »
