Основы дискретной математики. Щипцов В.В - 29 стр.

UptoLike

ВУЗ: 

СЗТУ | Санкт-Петербург

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

Рубрика: 

29
В качестве универсального метода решения этой задачи приведем
изложение метода Петрика.
Пусть совершенная ДНФ функция f имеет k конституент, а ее
сокращенная ДНФ имеет m простых импликант.
1. Обозначим каждую простую импликанту функции f через p
i
, т.е. имеем
p
1
,p
2
, ... , p
m
.
2. Выделим те простые импликанты сокращенной ДНФ функции f,
которые поглощают каждую из конституент единицы исходной ДНФ. Из
простых импликант, поглощающих первую конституенту, образуем
дизъюнкцию d
1
; из простых импликант, поглощающих вторую конституенту,
образуем дизъюнкцию d
2
и так далее, вплоть до k-ой конституенты. В итоге
получим набор дизъюнкций d
1
,d
2
,...,d
k
.
3. Из дизъюнкций d
i
, полученных в пункт 2, образуем конъюнкцию
F(p
1
,p
2
, ... , p
m
)= d
1
⋅ d
2
⋅... ⋅ d
k
.
4. Раскроем скобки в правой части (15) и произведем все возможные
поглощения (в правой части (15) каждая из дизъюнкций d
i
выражена через
соответствующие импликанты p
i
). Обозначим число элементарных
конъюнкций в полученном выражении через S. Каждой такой элементарной
конъюнкции соответствует одна тупиковая форма функции f, которая
получится, если в элементарной конъюнкции символы импликант p
i
заменить их значениями, а знаки конъюнкций заменить знаками
дизъюнкций. Таким образом, получим S тупиковых ДНФ функций f. Для
нахождения искомой минимальной ДНФ остается выбрать те из них,
которые имеют наименьшую сумму рангов.
Пример 8.
Для булевой функции примера 7 построить тупиковые и
минимальную ДНФ.
Решение.
В предыдущем примере была получена сокращенная ДНФ (14)
заданной функции. Выпишем ее простые импликанты
p
1
=xz, p
2
=yz, p
3
=xz, p
4
=xy. (16)
Выясним, какими импликантами поглощается каждая из конституент
единицы исходной ДНФ (13) и образуем из них соответствующие дизъюнкции.
xyz поглощается импликантами p
1
, p
2
; образуем
d
1
=p
1
∨p
2
,
xyz
»
p
1
;
»
d
2
=p
1
,
xyz
»
p
3
;
»
d
3
=p
3
,
xyz
»
p
3
, p
4
;
»
d
4
=p
3
∨p
4
,
xyz
»
p
2
, p
4
;
»
d
5
=p
2
∨p
4
.
Из дизъюнкций d
i
образуем конъюнкцию F
F = d
1
⋅ d
2
⋅ d
3
⋅ d
4
⋅ d
5
= (p
1
∨p
2
) ⋅ p
1
⋅ p
3
⋅ (p
3
∨p
4
) ⋅ (p
2
∨p
4
).
В полученном выражении раскроем скобки и преобразуем его, используя
соотношение х
⋅ х=х.
F= (p
1
⋅ p
1
⋅ p
3
∨p
2
⋅ p
1
⋅ p
3
) ⋅ (p
3
⋅ p
2
∨p
4
⋅ p
2
∨p
3
⋅ p
4
∨p
4
⋅ p
4
)
F= (p
1
⋅ p
3
∨p
1
p
3
p
2
)(p
2
p
3
∨p
2
p
4
∨p
3
p
4
∨p
4
)

Страницы