Специальные представления ФАЛ

1. Специальные представления ФАЛ

Саровский физико-технический институт
Национального исследовательского ядерного университета МИФИ
Специальные представления
ФАЛ
Алексеев В.В.
Саров
2016
1

2. Разложение ФАЛ по переменным

• Пусть х – логическая переменная. Как
известно
x , если 1;
x
x , если 0.
Т.к. x 1тогда и только тогда, когда x
k
1 2
то x1 x2 xk 1 когда i | xi i .
2

3. Теорема (о разложении ФАЛ)

• Любая ФАЛ f ( x1 , x2 xn ) при любом k
( 1 k n ) может быть представлена в
виде
f ( x1 , xk , xk 1 , xn
x x x f ( , , x , x )
( 1 , k )
1
1
2
2
k
k
1
2
k
k 1
n
где дизъюнкция берется по всевозможным
наборам 1 , 2 , k значений аргументов
x1 , x2 , xk
3

4. Доказательство.

• Для доказательства достаточно доказать,
что для любого набора 1 , 2 , n
значений аргументов левая и правая
части выражения принимают одинаковые
k
1 2
значения. Т.к. 1 2 k 1 когда для
любого i i i, то
f ( , , ,
( 1 , k )
1
1
2
2
1
1
2
2
k
k
1
2
k
k 1
, n )
k
k
f ( 1 , 2 , k , k 1 , n )
f ( 1 , 2 , n ) , ч.т.д.
4

5. Полином Жегалкина

• Итак, как известно, для функции
«Исключающие ИЛИ» («Сложение по
модулю 2») справедливы свойства
-коммутативности x1 x2 x2 x1 ;
-ассоциативности x1 ( x2 x3 ) ( x1 x2 ) x3 ;
-дистрибутивности x1 ( x2 x3 ) x1 x2 x1x3 .
На основе свойства ассоциативности имеем
n
x x x x
i 1
i
1
2
n
5

6. Теорема Жегалкина

Любая ФАЛ может быть представлена
многочленом вида
f ( x1 , x2 , xn ) k0 k1 x1 k2 x2
,
x x x
kn 1 x1 x2 kn 2 x1 x3 kn m 1 2
n
где ki 0,1
6

7.

Доказательство.
• ПСНФ имеет вид:
f ( x1 x2 xn ) x x x
1
1
2
2
n
n
1
т.к.
x x x 1,
0
x x x 0,
1
то
x x
Подставив в исходное выражение вместо
i
xi равное ему выражение xi i
Получаем:
f ( x1 x2 xn ) ( x1 1 )( x2 2 ) ( xn n )
1
7

8.

• Раскрыв скобки обычным образом и
учитывая, что А А=0, получаем
представление ФАЛ в виде полинома
Жегалкина.
8

9. Производные от ФАЛ

f
f ( x1 , x2 , xi 1 ,1, xi 1 xn )
xi
f ( x1 , x2 , xi 1 ,0 , xi 1 xn )
Единичная
остаточная
функция
Нулевая
остаточная
функция
f
xi от ФАЛ
• Производная 1-го порядка
определяет условия, при которых эта
функция изменяет значения при
переключении переменной хi .
9

10.

k f
• Смешанной производной xi1 , xi2 , xik
от ФАЛ f ( x1 , x2 , xn ) называется
выражение вида
k 1
f
f
xi1 , xi2 , xik ik xi1 , xi2 , xik 1
k
Эту производную вычисляют, применяя
соотношение для вычисления 1-ой
производной k раз при фиксации
xi1 xi2 xik по порядку.
10

11.

• Производной k-того порядка от ФАЛ по
переменным xi1 xi2 xiназывается
k
выражение
k f
f
2 f
( xi1 xi2 xik )
i xi
i , j ,i j xi , x j
f
f
xi , x j , xl
xi1 , xi2 , xik
i , j ,l
3
k
i j , j l
i l
• Производная k-того порядка определяет
условия , при которых f ( x1 , x2 , xn )
изменяет значение при одновременном
11
x
x
x
изменении переменных i1 i2
ik