Дифференцирование и интегрирование булевых функций

Дифференцирование и интегрирование булевых функций f ( x1, x2 ,..., xn )  f ( x1, x2 ,..., xi 1,1,..., xn )  f ( x1, x2 ,..., xi 1,0,..., xn ) xi f ( x1, x2 , x3 )  x1x2  x1 x3 единичная остаточная функция нулевая остаточная функция f ( x1, x2 , x3 )  f (1, x2 , x3 )  f (0, x2 , x3 )  1 x2  1 x3   0  x2  0  x3   x2  x3 x1 (условие переключения) f ( x1, x2 , x3 ) изменит свое значение при изменении x1 при условии - x2  x3  1 f  x1  x1 x3   x1 x3  x11  x3   x1x3 x2 условие переключения f при переключении x2 f  x1x2  x1  x1 x2 x3 x1x3 =1 x1 x2 =1 условие переключения f при переключении x3 k  f ( x1, x2 ,..., xn )  Смешанная производная  xi1 xi2 ...xik xik   k 1 f ( x , x ,..., x )  1 2 n    xi xi ...xi   1 2 k 1  Производная k-го порядка  k f ( x1, x2 ,..., xn ) f 2 f       xi1 , xi2 ,..., xik  x  x  x iI i i, jI ,i  j i j i, j , sI ,   I  {i1, i2 ,...,ik } i  j ,i  s, s  j 3 f k f  ...  xi x j xs xi1 xi2 ...xik f  x2  x3 x1 f ( x1, x2 , x3 )  x1x2  x1 x3 f  x x f  x1x3 1 2 x2 x3 2 f   f   1  x   0  x   1  x    3 3 3  x3 x1x2 x2  x1  x1 0 0 0 0 1 1 1 1 x2 0 0 1 1 0 0 1 1 2 f  x2  x3    x1x3   x3  x3  x1x2  x1 x2 x3 0 1 0 1 0 1 0 1   x1, x2  11101011 условие переключения f при одновременном переключении x1 и x2 2 f f f 2 f     x1, x2  x1 x2 x1x2 x3  x1x2  x1 x2  1 f переключается при одновременном переключении x1, x2 с 00 на 11 и с 11 на 00 3 f f f f 2 f 2 f 2 f 3 f         x1, x2 , x3  x1 x2 x3 x1x2 x1x3 x2x3 x1x2x3 2 f   f     x2  x1x3 x3  x1  2 f   f     x1  x2x3 x3  x2  3 f    2 f   1   x1x2x3 x1  x2x3  3 f  x1 x 2 x3  x1x2 x3  x1x2 x3  x1 x 2 x3  x1 x 2 x3  x1x2 x3  x1, x2 , x3  f переключается при переключении входных переменных 100↔011, 110↔001, 111↔000 Интеграл  f ( X )dxi  {F j  X , xi }, F j  X , xi  xi f ( x1, x2 )  x1 & x2 X  ( x1, x2 ,...,xi 1, xi 1,...,xn )  f (X )  f ( x1, x2 )dx3  {F j  x1, x2 , x3 } F j  x1, x2 , x3  x3 {F j ( X , xi )}  2  f ( x1, x2 )  x1 & x2 F j  x1, x2 , x3   F j  x1, x2 ,0  F j  x1, x2 ,1  x1 & x2 x3 x1 & x2  1  x1  1,   x2  1  F j 1,1,0  F j 1,1,1  1 x1 & x2  0  x1  1,  F j 1,0,0  F j 1,0,1  0  x   2 24  16  F j 1,1,0   0,  F j 1,1,0   1, или    F j 1,1,1  1  F j 1,1,1  0 F j 1,0,0  F j 1,0,1  1 F j 1,0,0  F j 1,0,1  0 или  x1  0, F j 0,1,0  F j 0,1,1  1 или       F , 1 ,  F , 1 , 1  j j F j 0,1,0  F j 0,1,1  0  x2  1  x1  0,  F j 1,0,0  F j 1,0,1  0 F j 0,0,0  F j 0,0,1  1 или  F j 0,0,0  F j 0,0,1  0  x2  0 2 X x1  F j 1,1,0   0,  F j 1,1,0   1, или    F j 1,1,1  1  F j 1,1,1  0 x2 f ( x1, x2 ) x3 F j ( x1, x2 , x3 ) 1 1 1 1 1 F j 1,0,0  F j 1,0,1  1 или F j 1,0,0  F j 1,0,1  0 F j 0,1,0  F j 0,1,1  1 или F j 0,1,0  F j 0,1,1  0 … … … … … 1 1 1 1 1 1 1 1 1 1 1 1 1 … 1 … … 16 или F j 0,0,0  F j 0,0,1  0 F j 0,0,0  F j 0,0,1  1 Многомерное интегрирование  f ( X )dxi1 dxi2 ...dxik  F j X , xi1 , xi2 ,...,xik ,     k F j X , xi1 , xi2 ,..., xik  f (X )  xi1 , xi2 ,..., xik  F j X , xi1 , xi2 ,...,xik   2 k 2 X Разложение булевой функции в заданной точке Теорема. Любая булева функция f ( x1, x2 ,..., xn ) представима своим значением в точке 00…0 и значениями всех производных в этой точке:     n f   n 2  f   f ( x1, x2 ,..., xn )  f (0,0,...,0)   & xi1    & xi1 xi2   ...     x x x  i1 1 i1 00...0   i1,i2 1 i1 i2 00...0   i1 i2      k n n  f  f  ...   & x x ... x  ...  & x1x2 ...xn  i1 i2 ik  i ,i ,...,i 1 xi xi ...xi  x1x2 ...xn 1 2 k 00...0 00...0  i1 2i ...ki  1 2  k f ( x1, x2 , x3 )  x1x2  x1 x3 f  x1 x2 0,0,0  0 x3 3 f 1 x1x2x3 0,0,0 f  x2  x3 0,0,0  1 x1 2 f  x 3 0,0,0  0 x1x2 f  x1x3 0,0,0  0 x2 2 f  x1 0,0,0  0 x2x3 2 f  x 2 0,0,0  1 x1x3 f ( x1, x2 , x3 ) 0,0,0  x1  x1x3  x1x2 x3 f ( x1, x2 , x3 ) 0,0,0  f (0,0,0)  2 f  x1x2 f (0,0,0)  0 2 f & x1x2  x1x3 f f f & x1  & x2  & x3  x1 0,0,0 x2 0,0,0 x3 0,0,0 0,0,0 2 f & x1x3  x2x3 0,0,0 3 f & x2 x3  x1x2x3 & x1x2 x3 0,0,0 Разложение булевой функции в точке (1, 2 ,..., n ) (0,0,...,0) xi   i xi f ( x1, x2 , x3 )  x1x2  x1 x3 f (1,0,1)  1 f  x2  x3 1,1,0  1 x1 2 f  x 3 1,1,0  0 x1x2 f ( x1, x2 , x3 ) 1,1,0  f (1,1,0)  2 f  x1x2 1,1,0 3 f  x1x2x3 f  x1x3 1,1,0  0 x2 2 f  x 2 1,1,0  0 x1x3 (1,1,0) f  x1 x2 1,1,0  0 x3 2 f  x1 1,1,0  1 x2x3 3 f 1 x1x2x3 f f f &  x1  1  &  x2  1  &  x3  0   x1 1,1,0 x2 1,1,0 x3 1,1,0 2 f &  x1  1 x2  1  x1x3 1,1,0 2 f &  x1  1 x3  0   x2x3 &  x1  1 x2  1 x3  0   1  x1  x 2 x3  x1 x 2 x3 1,1,0 (1, 2 ,..., n ) &  x2  1 x3  0   1,1,0 Проблема порождения ложного значения функции - транспортное запаздывание значений переменных Трасса T(Xa,Xb) булевой функции f(X) – цепь интервала J(Xa,Xb): X i  J , X i  X a , X i  X b X a  X i  X b f  X a   f  X b , f  X i   f  X a  0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 x1 x2 x3 x4 f 0000000011 0000111100 0011001100 0101010101 1 11 0 01 0 00 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1111 0000-0100-0110-0111-1111 - трасса длины 4 0111 0011 1011 1101 1110 0101 0110 1001 1010 0001 0010 0100 1000 0000 0000-1000-1100 - трасса длины 2 0100-1100-1101 - трасса длины 2 1100 Чем больше трасс, тем больше возможность порождения ложной информации Вес производной – число конституент   k f ( x , x ,..., x )  1 2 n  P   xi , xi ,..., xi   1 2 k    Чем больше вес производной, тем сильнее функция зависит от переменных по которым она была продифференцирована Оптимальное разложение функции по k переменным   k f ( x , x ,..., x )  1 2 n  1) Находят max P   xi , xi ,..., xi  - определяют исключаемые переменные.  1 2 k    2) Для единичной и нулевой остаточных функций повторяют шаг 1), пока они не будут иметь простой вид Взаимно ортогональные функции f & f   0 Переключательные функции f ( x1 , x2 ,..., xn ) : {0,1,...,k1  1}  {0,1,...,k2  1}  ... {0,1,...,kn  1}  {0,1,...,k f  1} x1 {0,1,2}, x2 {0,1}, x3 {0,1}, f {0,1,2,3} x1 x2 x3 f ( x1, x2 , x3 ) Гиперкуб 210 1 0 110 3 3 3 001 000011112222 001100110011 010101010101 331023011103 211 111 101 1 1 010 201 011 1 2 200 100 3 000 k1  k2  ...  kn  k f  k k-значные переключательные функции x1 1 2 3  2  2  12 Таблица Вейча x2 x3 00 01 10 3 3 1 2 3 1 1 11 1 3 Отрицание x  x  1(mod k ) 1. Циклический сдвиг или отрицание Поста: 2. Зеркальное отображение или отрицание Лукашевича: Nx  k  1  x 1 при x  i, 3. Характеристическая функция: ji ( x)   i  0,1,...,k  1 при x  i  k  1 при x  i, i  0,1,...,k  1 4. Ii ( x)   при x  i  Свойства операций Конъюнкция x1x2 Дизъюнкция x1  x2 1. ассоциативность 5. min( x1, x2 ) 7. max( x1, x2 ) 2. коммутативность 3. дистрибутивность 6. x1  x2 (mod k ) 8. x1  x2 (mod k ) 4. Правила спуска символа I вглубь формулы k  1 при c   , I (c)   c,  0,1,...,k  1 при c     I 0 ( x)  ...  I 1( x)  I 1( x)  ...  I k 1( x) при   0,  I ( I ( x))  0 при 0    k  1,  I ( x) при   k  1  I ( x1x2 )  I ( x1)( I ( x2 )  ...  I k 1( x2 ))  I ( x2 )( I ( x1)  ...  I k 1( x1)) I ( x1  x2 )  I ( x1)( I0 ( x2 )  ...  I ( x2 ))  I ( x2 )( I 0 ( x1)  ...  I ( x1)) 5. Правило исключения «чистых» вхождений переменной x  1 I1( x)  2  I 2 ( x)  ...  (k  1) I k 1( x) 6. Правило введения переменной 7. Правила упрощений x1  x1( I 0 ( x2 )  ...  I k 1( x2 ))