Дискретная математика. Элементы теории задачи и упражнения. Часть 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
∨
∨
∨
∨
∨
∨
∨
∨
=
ЗАДАЧИ И УПРАЖНЕНИЯ 
                                            84
Операция замыкания. Основные замкнутые классы.
__________________________________________________________________________________________
ременные x1 , ..., x n в некоторых «степенях». Это свойство дает возмож-
ность сформулировать следующие правила.
1. Для получения СДНФ реализуемой формулой функции f ( x1 , ..., x n ) ≠0
   нужно построить ДНФ этой функции (см. п.5.2). Затем, если какая-
   нибудь конъюнкция ДНФ не содержит переменной x l , заменить ее па-
   рой конъюнкций K j
                                   K j x l ∨ K j xl .                                 (4)
   Замену производить до тех пор, пока каждое слагаемое ДНФ не будет
   содержать всех переменных x1 , ..., x n (их отрицаний или их самих).
2. Для получения СКНФ реализуемой формулой функции f ( x1 , ..., x n ) ≠1
   нужно построить КНФ этой функции. Затем, если какая-нибудь дизъ-
   юнкция D j КНФ не содержит переменной x l , заменить ее парой дизъ-
   юнкций
                           (D j ∨ x l )(D j ∨ x l ).                    (5)
     Замены (4) и (5) являются эквивалентными, так как в силу первого
дистрибутивного закона
                 K j x l ∨ K j x l =K j ( x l ∨ x l ) =K j ⋅1 =K j ,
а в силу второго дистрибутивного закона
                (D j ∨ xl )(D j ∨ xl ) =D j ∨ x l xl =D j ∨ 0 =D j .
       Пример 3. Для функции f ( x , y , z ) = x ∨ z ~ xy построить СДНФ и
СКНФ.
       Решение. Сначала строим нормальные формы:
                     D =xy ∨ xz ∨ yz , K =( x ∨ z )( x ∨ y ).
       В первом слагаемом ДНФ недостает переменной z , во втором —
переменной y , в третьем — x . В соответствии с (4) запишем:
                   D =xyz ∨ xyz ∨ xyz ∨ x yz ∨ xyz ∨ x yz .
Убрав лишние слагаемые, находим СДНФ:
                         Dc = xyz ∨ xyz ∨ x yz ∨ x yz .
       В первом сомножителе КНФ не достает переменной y , во втором —
z ; поэтому в соответствии с (5) имеем СКНФ:
               K c =( x ∨ y ∨ z )( x ∨ y ∨ z )( x ∨ y ∨ z )( x ∨ y ∨ z ).



                           ЗАДАЧИ И УПРАЖНЕНИЯ

Страницы