Дискретная математика. Элементы теории, задачи и упражнения. Часть 2. Булгакова И.Н. - 28 стр.

UptoLike

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

28
Определение 5. Сокращенной ДНФ функции
f
называется дизъ-
юнкция всех простых импликантов функции
f
.
Сокращенная ДНФ определяется однозначно для функции
f
.
Метод построения сокращенной ДНФ функции
f
Шаг 1. Построить ДНФ для функции
f
.
Шаг 2. Производить операцию обобщенного склеивания
212121
KKKXXKKXXK
Ú
Ú
=
Ú
до тех пор, пока это возможно.
Шаг 3. Производить операцию поглощения
1211
KKKK
=
Ú
.
В результате приходим к сокращенной ДНФ, учитывая, что 0
11
=
KK
и
111
KKK
=
Ú
.
Пример 2. Построить сокращенную ДНФ для функции
(
)
(
)
zyxyxf
Ú
Ú
Ú
=
.
Решение. Раскрывая скобки по 1-му дистрибутивному закону, полу-
чаем ДНФ; затем применяем операцию поглощения:
(
)
(
)
( ) ( )
( )
xzyxzyzy
xzyzyyxyzxzyxyyx
yzxzyyxyyxxxzyxyxf
Ú=ÚÚ=
=ÚÚÚ=ÚÚÚÚ=
=
Ú
Ú
Ú
Ú
Ú
=
Ú
Ú
Ú
=
сокращенная ДНФ.
Определение 6. ДНФ функции
(
)
n
x,...,x,xf
21
называется совершен-
ной, если она составлена из попарно различных э.к. ранга
n
, т.е. формула
вида:
(
)
( )
(
)
n
n
n
,...,,f
n
x&...&x&xx,...,x,xf
s
ss
sss
21
21
21
1
21
=
Ú= ,
где дизъюнктивная сумма берется по всем наборам
(
)
n
,...,,
s
s
s
21
, на кото-
рых
(
)
1
21
=
n
,...,,f
s
s
s
. Ясно, что функция
(
)
n
x,...,x,xf
21
отлична от тож-
дественного нуля.
В следующем параграфе подробно рассматриваются совершенные
нормальные формы и их нахождение, имеющие важное значение в прило-
жениях.