Дискретная математика. Прокушев Л.А. - 24 стр.

UptoLike

ВУЗ: 

СПб ГУАП | Санкт-Петербург

Составители: 

Рубрика: 

22
Упрощение булевых формул состоит в уменьшении количества вхо-
дящих в них букв. Как известно, любую булеву функцию, отличную от
0, можно представить ее СДНФ. Элементарную конъюнкцию можно
представить выражением:
1
1
,
r
i
ir
i
U
xx
σσ
= …
где
01
{0,1}, ,
jjjj
j
xxx
x
σ∈ = =
,
и все
(1,2,,
)
ij
xj
r
= …
различны. Число r называется рангом конъюнк-
ции. Константа 1 считается конъюнкцией нулевого ранга.
Минимальной ДНФ (МДНФ) функции f(x
1
, x
2
, . . . , x
n
) называется ДНФ
1
,
k
NU U
=∨∨
…
содержащая наименьшее число букв по сравнению с
другими ДНФ, представляющими эту функцию.
Минимизация булевой формулы состоит в том, чтобы для всякой буле-
вой функции найти представление в виде МДНФ. Все методы минимиза-
ции в классе ДНФ основываются на понятии простого импликанта.
Импликантом функции f(x
1
, x
2
, . . . , x
n
) называется элементарная конъ-
юнкция если выполнено соотношение:
1
(, , )1,
n
U
fx x
→≡
…
где
{}
1
,, , 1,,.
ij n
xxxj r
∈=
……
Переменные, не вошедшие в конъюнкцию, являются несуществен-
ными для данного импликанта.
Импликант можно представить как булеву функцию g = U, которая
обращается в 1 на тех наборах значений переменных, на которых равна
1 функция f. Дизъюнкция импликантов
m
∨∨
, накрывающая в
совокупности все 1 функции f, совпадает с функцией f. При уменьше-
нии ранга (длины) элементарной конъюнкции за счет отбрасывания не-
существенных переменных количество накрываемых импликантом 1 уве-
личивается. Конституента 1 (длины n) обращается в 1 лишь в одной
точке, а элементарная конъюнкция длины n – k – в 2
k
точках. Выгодно
поэтому накрывать функцию f элементарными конъюнкциями мини-
мальной длины.
Простым импликантом функции f(x
1
, . . . , x
n
) называется импликант,
если элементарная конъюнкция, получающаяся из него удалением лю-
бой буквы, не является импликантом функции.
Сокращенной ДНФ функции f(x
1
, . . . , x
n
) называется дизъюнкция
всех простых импликантов функции.
Теорема 5. Сокращенная ДНФ функции f(x
1
, . . . , x
n
) представляет
эту функцию.

Страницы