Двоичные динамические системы дискретной автоматики. Мельников А.А - 160 стр.

UptoLike

ВУЗ: 

Университет ИТМО | Санкт-Петербург

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

Рубрика: 

163
Введенное определение позволяет на основе свойств частной про-
изводной Селлерса (ЧПС) 1-го порядка сформулировать следующее
утверждение.
Утверждение 2.6 (У2.6). Если вес ЧПС
()
xf
x
i
∂
∂
на всех
n
2
набо-
рах
{
}
n,1i,xrowx
i
== равен нулю так, что
()
0xf
x
P
i
=
⎭
⎬
⎫
⎩
⎨
⎧
∂
∂
, (2.88)
то в дизъюнктивной форме представления булевой функции
()
xf про-
исходит полное «склеивание» по переменной
i
x . □
Доказательство утверждения строится на том, что
()
0xf
x
P
i
=
⎭
⎬
⎫
⎩
⎨
⎧
∂
∂
означает, что
(
)
0
x
xf
i
=
∂
∂
на всех наборах переменных,
в том числе и на тех
µ
наборах, где
(
)
xf принимает единичное значе-
ние так, что для этих наборов становится в силу (2.67) справедлива за-
пись:
()
(
)
1x,x,,x,xf;1x,x,,x,xf
ni21ni21
=
=
Κ
Κ
ΚΚ . (2.89)
Тогда (2.89) позволяет для дизъюнктивной нормальной формы БФ
()
xf записать
() ()
jj
j
n
ij
1j
1l
iij
n
ij
1j
1l
xxxxxf
&&
α
µ
α
µ
≠
=
=
≠
=
=
∨∨
=∨
⎟
⎟
⎟
⎠
⎞
⎜
⎜
⎜
⎝
⎛
=
, (2.90)
где
jj
xx
j
=
α
при 0=
α
и
jj
xx
j
=
α
при 1
=
α
. ■
Утверждение 2.7 (У2.7). Если вес ЧПС
(
)
i
x
xf
∂
∂
на всех
n
2 наборах
переменных
{
}
n,1i,xrowx
i
== равен
n
2 так, что
()
n
i
2xf
x
P =
⎭
⎬
⎫
⎩
⎨
⎧
∂
∂
, (2.91)
то при конструировании множества пар наборов булевых переменных
полной мощности равной
1n
2
−
, на которых эта БФ меняет свое значе-
ние, не найдется такой пары, на которой эта БФ сохраняет свое зна-
чение
. □
Доказательство утверждения содержит в себе определение ЧПС
()
i
x
xf
∂
∂
, которое фиксирует изменение значения БФ
(
)
xf
при измене-
нии переменной
x
i
на ее инверсию
i
x
, что соответствует своей паре на-
боров булевых переменных. ■

Страницы