Statistical independence of the boolean function superposition. II.pdf Следуя [1], будем говорить, что булева функция f статистически не зависит отподмножества U своих аргументов, если для любой её подфункции f ' , полученнойфиксированием значений всех переменных в U, имеет место w ( f ' ) = w(f)/2|U|, гдеw ( f ) - вес функции f.В [2] доказано следующее утверждение.Утверждение 1. Пусть x, y, z - переменные со значениями в (Z2)n, (Z2 )m и ( Z 2 )соответственно и функция f (x,y) статистически не зависит от переменных в x. То-гда и функция h(x,y,z) = g (f ( x , y ) , z ) , где g - любая функция от l + 1 переменных,статистически не зависит от переменных в x.В общем случае это утверждение не допускает обобщения на случай несколькихвнутренних функций f. Получено следующее достаточное условие статистическойнезависимости от аргументов суперпозиции произвольной функции с двумя внутрен-ними функциями.Утверждение 2. Пусть x, y, z - переменные со значениями в (Z2)n, (Z2 )m и ( Z 2 )соответственно, функции f 1 ( x , y ) , f 2 ( x , y ) , u(x,y) = f 1 ( x , y ) ф f 2 ( x , y ) статистически независят от переменных в x. Тогда и функция h(x, y, z) = g (f1(x, y), f 2(x, y), z), где g -любая функция от l + 2 переменных, статистически не зависит от переменных в x.Доказательство. Для любых a G {0,1}n , i , j G {0,1} обозначим с", = |{y GG { 0 , 1 } m : f1(a, y) = i, f2(a, y) = j}|. В силу статистической независимости функций f 1,f 2 , u от переменных в x для любого a G { 0 , 1 } n выполняетсяс?0 + с?1 = w(f1)/2n, с"1 + с?1 = w(f2)/2n, с"1 + с?0 = w(u)/2n.Отсюда получаем с"1 = (w(u) - w ( f 1 ) + w ( f 2 ) ) / 2 n + 1 , с"0 = (w(u)+ w ( f 1 ) - w ( f 2 ) ) / 2 n + 1 ,c?1 = (w(f1) + w(f2) - w(u))/2n + 1 , ca0 = 2m - (w(u) + w(f1) + w(f2))/2n + 1 , т.е. с", независит от a для всех i, j G {0,1}. Тогда и вес подфункции функции h, полученнойфиксацией переменных в x набором значений a, не зависит от a, так как w(h(a, y, z)) == S cj w(g(i, j, z)). Следовательно, функция h статистически не зависит от пе-i j e { 0 ' 1 }ременных в x. Следующее утверждение характеризует условия статистической независимости отпеременных в x суммы двух функций в частном случае - когда одна из функций за-висит только от x.Утверждение 3. Пусть x, y - переменные со значениями в (Z2)n и (Z2 )m соответ-ственно и функция / ( x , y) статистически не зависит от переменных в x. Тогда функция/ ( x , y ) ф g(x), где g - любая функция от n переменных, статистически не зависит отпеременных в x, если и только если / уравновешена или g = const.Доказательство. По условию w(/(a,y)) = w ( / ) / 2 n для всех a Е {0,1}n ; сле-довательно, w(/(a,y) ф g(a)) не зависит от a, если и только если g = const илиw ( / ) / 2 n = 2m - w ( / ) / 2 n ; последнее равенство равносильно уравновешенности /.

Скачать электронную версию публикации