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

UptoLike

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

33
вующих этим наборам элементарных дизъюнкций является СКНФ задан-
ной функции:
(
)
(
)
(
)
(
)
.zyxzyxzyxzyxK
c
Ú
Ú
Ú
Ú
Ú
Ú
Ú
Ú
=
Рассмотренные примеры являются иллюстрацией к первому способу
построения СКНФ и СДНФ, основанному на представлениях (1) и (2).
Применяется он, как правило, для функций, заданных таблицей истинно-
сти или набором значений. Если же функция задана аналитически, т.е. при
помощи формулы, то для нее нужно сначала построить таблицу истинно-
сти, а затем применять описанный метод.
Второй способ построения СДНФ и СКНФ состоит в эквивалентном
преобразовании формулы, реализующей функцию, к виду (1) или (2). Как
уже отмечалось, совершенные дизъюнктивная или конъюнктивная нор-
мальные формы функции
(
)
n
x...,,xf
1
отличаются от обычных тем, что
каждое слагаемое СДНФ и каждый сомножитель СКНФ содержит все пе-
ременные
n
x...,,x
1
в некоторых «степенях». Это свойство дает возмож-
ность сформулировать следующие правила.
1. Для получения СДНФ реализуемой формулой функции
(
)
0
1
¹
n
x...,,xf нужно построить ДНФ этой функции (см. п. 5.2). Затем,
если какая-нибудь конъюнкция ДНФ не содержит переменной
l
x , заме-
нить ее парой конъюнкций
j
K
ljlj
xKxK
Ú
. (4)
Замену производить до тех пор, пока каждое слагаемое ДНФ не будет со-
держать всех переменных
n
x...,,x
1
(их отрицаний или их самих).
2. Для получения СКНФ реализуемой формулой функции
(
)
1
1
¹
n
x...,,xf нужно построить КНФ этой функции. Затем, если какая-
нибудь дизъюнкция
j
D КНФ не содержит переменной
l
x , заменить ее па-
рой дизъюнкций
(
)
(
)
ljlj
xDxD
Ú
Ú
. (5)
Замены (4) и (5) являются эквивалентными, так как в силу первого
дистрибутивного закона
(
)
jjlljljlj
KKxxKxKxK
=
×
=
Ú
=
Ú
1 ,
а в силу второго дистрибутивного закона
(
)
(
)
jjlljljlj
DDxxDxDxD
=
Ú
=
Ú
=
Ú
Ú
0 .
Пример 3. Для функции
(
)
xy~zxz,y,xf Ú= построить СДНФ и
СКНФ.
Решение. Сначала строим нормальные формы:
y
x
y
x
D
Ú
Ú
=
,
(
)
(
)
.yxzxK
Ú
Ú
=