Составители:
162
Доказательство. Свойство является следствием определения О2.1,
примененного к булевой функции типа ЧПС первого порядка от ис-
ходной БФ по той же переменной. ■
Определение 2.4 (О2.4). Производная m-го порядка
()
()
im2i1i
m
xxx
xf
Κ∂
∂
от булевой функции
()
(
)
n21
x,,x,xfxf
Κ
=
по кортежу переменных
()
im2i1i
xxx Κ определяет условия, при которых функция
()
xf изменяет
свое значение при
одновременном изменении значений переменных
кортежа
. □
Для вычисления введенной с помощью
О2.4 производной восполь-
зуемся теоремой Д. Бохманна, доказательство которой можно найти в
[9].
Теорема Д. Бохманна. (Теорема Т.2.1).
Производная
()
()
im2i1i
m
xxx
xf
Κ∂
∂
по кортежу
(
)
im2i1i
xxx
Κ
от скалярной
булевой функции
() ( )
n21
x,,x,xfxf
Κ
=
представима суммой по модулю
два всех ее переменных порядка k от 1 до n
:
()
()
⊕
∂∂
∂
⊕
∂
∂
=
∂
∂
∑∑
≠
=
νµ
νµ
µ
µ
ji
j,i
ji
2
m
1
iim2i1i
m
xx
f
x
f
xxx
xf
Κ
.
xxx
f
xxx
f
im2i1i
m
lji
l,j,i
lji
3
∂∂∂
∂
⊕⊕
∂∂∂
∂
⊕
∑
≠≠
Κ
Κ
ρνµ
ρνµ
■ (2.86)
Сформулированную задачу решим в нескольких постановках. В
первой постановке контроль корректности булевых описаний с помо-
щью аппарата частных производных Селлерса 1-го порядка осущест-
вим инвариантным относительно его конкретного использования спо-
собом с помощью веса ЧПС на всех наборах переменных. В этой по-
становке задача решается использованием следующих определений и
утверждений
.
Определение 2.5 (О2.5). Весом
()
⎭
⎬
⎫
⎩
⎨
⎧
∂
∂
xf
x
P
i
частной производной
()
xf
x
i
∂
∂
Селлерса 1-го порядка от булевой функции
(
)
xf
по перемен-
ной
i
x
называется сумма значений БФ
()
xf
x
i
∂
∂
на всех
n
2 наборах
{}
x булевых переменных
{
}
n,1i,xrowx
i
== :
() ()
{}
∑
=
≡
∂
∂
=
⎭
⎬
⎫
⎩
⎨
⎧
∂
∂
n
1
x
ii
xf
x
xf
x
P
λ
λ
. □ (2.87)
Страницы
- « первая
- ‹ предыдущая
- …
- 157
- 158
- 159
- 160
- 161
- …
- следующая ›
- последняя »
