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

UptoLike

ВУЗ: 

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

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

Рубрика: 

26
d
f
=ν
2
+ν
3
, (9)
где
ν
2
- число конъюнкций в ДНФ;
ν
3
- число дизъюнкций в ДНФ.
Пусть количество конъюнктивных членов в ДНФ равно к. Тогда легко
заметить, что
ν
2
= r(
i=1
k
∑
i
- 1) , ν
3
= k-1.
Подставляя эти выражения в формулу (9), получим
d
f
= r(
i=1
k
∑
i
- 1) + k-1 = ν
2
= r
i=1
k
∑
i
- 1 + k - 1 = r
i=1
k
∑
i=1
k
∑
i
- 1.
Таким образом вес d
f
НДФ функции f в базисе (8) вычисляется по формуле
d
f
= r
i=1
k
∑
i
- 1.
Так, все пять конъюнктивных членов ДНФ примера 6 имеют один и тот
же ранг, равный трем. Вес этой ДНФ d
f
в базисе (8) на основании полученной
формулы равен d
f
=3 х 5 - 1 = 14.
Из полученного соотношения следует, что, если для некоторой ДНФ
сумма рангов, образующих ее элементарных конъюнкций, будет наименьшей
по сравнению со всеми другими ДНФ данной функции, то рассматриваемая
форма будет минимальной
.
Аналогичные утверждения справедливы для суммы рангов
дизъюнктивных членов нормальной конъюнктивной формы (ДНФ) булевой
функции f.
Нахождение минимальной ДНФ произвольной булевой функции f
производится в два этапа.
Первый этап состоит в отыскании сокращенной
ДНФ.
Второй этап состоит в отыскании так называемых тупиковых
, а затем
минимальных ДНФ.
Нахождение сокращенной ДНФ.
Рассмотрим процедуру построения сокращенной ДНФ методом Квайна.
Этот метод основан на преобразовании ДНФ с помощью операций полного
и
неполного склеивания
и операции поглощение.
Полное склеивание.
Пусть х-булева переменная, а
β - элементарная конъюнкция. Тогда имеет
место соотношение
х
β∨хβ=β . (10)
Для доказательства этого соотношения преобразуем его левую часть,
используя свойство дистрибутивности конъюнкции относительно дизъюнкции
и равенства х
∨х=1, 1⋅ х=х.
х
β∨хβ = ( х∨х) ⋅ β = 1 ⋅ β = β .

Страницы