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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

Операция замыкания . Основные замкнутые классы .
__________________________________________________________________________________________
84
ременные
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 ∨= построить СДНФ и
СКНФ .
Решение. Сначала строим нормальные формы:
z
y
z
x
y
x
D
∨
∨
=
,
(
)
(
)
.yxzxK
∨
∨
=
В первом слагаемом ДНФ недостает переменной
z
, во втором —
переменной
, в третьем —
x
. В соответствии с (4) запишем :
z
y
x
z
y
x
z
y
x
yz
x
z
y
x
z
y
x
D
∨
∨
∨
∨
∨
=
.
Убрав лишние слагаемые , находим СДНФ :
zyxyzxzyxzyxD
c
∨
∨
∨
=
.
В первом сомножителе КНФ не достает переменной
, во втором —
z
; поэтому в соответствии с (5) имеем СКНФ :
(
)
(
)
(
)
(
)
.zyxzyxzyxzyxK
c
∨
∨
∨
∨
∨
∨
∨
∨
=
ЗАДАЧИ И УПРАЖНЕНИЯ

Страницы