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

UptoLike

ВУЗ: 

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

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

Рубрика: 

25
()(()) ( )
(( )) ( ( ))( )
()() ( )
()
() .
ху x y xz x y z yz хy xy xxz
xyz yzxyxyx yzyz
xy xy x yz y z xy xy x y yyz x z yz
xy xyy xyyz xyz xyz xy xyz y x x z
yx z xy yz
∨∨ ∨∨=∨∨⋅
⋅∨⋅=∨ ∨∨ ∨=
=∨ ∨ ∨=∨ ∨ ∨ ∨ =
=∨∨ ∨∨=∨=∨ =
=∨=∨
Всякую ДНФ можно привести к СДНФ расщеплением конъюнк-
ций, которые содержат не все переменные. Получим СДНФ для пре-
дыдущего примера:
()()
.
хy уz хy z z x x yz xyz xyz xyz xyz
xyz xyz xyz
∨= ∨∨∨ = ∨ ∨ ∨ =
=∨∨
Получение тупиковой ДНФ состоит в нахождении простых импликантов с
помощью алгоритма Блейка, суть которого заключается в следующем.
1. Формула обобщенного расщепления (21), записанная в виде:
,
Хz Yz Xz Yz XY∨=∨∨
(22)
где z – буква, X, Y – элементарные конъюнкции, позволяет вводить в
ДНФ новый член. После применения соотношения (22) несколько раз к
исходной формуле F (пока получаются новые члены), ее можно привес-
ти к формуле F1, которая будет содержать все простые импликанты
представляемой ею булевой функции f.
2. Формулу F1 необходимо освободить от всех членов, не являющи-
мися простыми импликантами, используя операцию поглощения (17), и
прийти к сокращенной ДНФ, представляемой формулой F2.
3. Если некоторый член в формуле F2 может быть получен с помощью
применения соотношения (22), возможно, неоднократного из остальных
членов, то его можно исключить как лишний. В результате процесса ис-
ключения лишних членов придем к некоторой тупиковой ДНФ F3.
4. Для получения всех тупиковых ДНФ, описанный способ исключе-
ния следует применить несколько раз, изменяя порядок исключения раз-
ных членов. Нахождение минимальных ДНФ требует громоздкой рабо-
ты по перебору всех тупиковых ДНФ. Поэтому на практике ограничи-
ваются нахождением какой-нибудь одной тупиковой ДНФ, принимая ее
за МДНФ.
Пример. Покажем процесс минимизации ДНФ, заданной формулой:
.
F хyz xу xyz
=∨∨

Страницы