№2 произвольного набора в t-й стандартной антицепи равна 1 Ct свойство вероятности: ρn(Ak)=1. k=0 19 n · (n+1). <...> Ясно, что вероятность стандартной антицепи с номером t равна ρn(At)= 1 n Лемма 1. <...> Дляпроизвольной антицепи A = { α1,. , αs} над булевым кубом Bn Рассмотрим произвольную антицепь в булевом кубе Bn i=1 s C| αi| 1 n 1. <...> Дляпроизвольной антицепи A над булевым кубом Bn ρn(A) 1 n+1 . <...> Посмотрим, что происходит с вероятностью множества единиц функции при отбрасывании несущественных переменных. <...> Тогда ρn(Nn(f)) = ρs(Ns(fn−s)), где fn−s — функцияот s переменных, получаемаяиз f отбрасыванием ее n − s несущественных переменных. <...> Достаточно доказать утверждение для случая s = n−1, тогда для любого s n−1 последовательно выведем ρn(Nn(f)) = ρn−1(Nn−1(f1)) = . = ρs(Ns(fn−s)). функцию f1 от n−1 переменной. <...> В нашем распределении Аналогично В случае s = n − 1 отбросим у функции f(x1,. ,xn) несущественную переменную xn. <...> Частичной функцией f (x1,x2,. ,xn) называется функция, определенная на подмно2 . <...> Множество жестве A единичного булева куба, f : A → Bn всех таких функций обозначается Pn наборах из множества A, называется сужением функции f на множество A и обозначается через f|A. <...> Нижние оценки для линейной функции, для функции голосования и для почти всех Определение. <...> Докажем общее утверждение о нижней оценке сложности схемы, реализующей произвольную функцию от n переменных в базисе AC, и выведем из этого утверждения нижние оценки порядка √n для линейной функции, для функции голосования и для почти всех булевых функций от n переменных. <...> Для всякой функции f(x1,. ,xn) рассмотрим σr(f)—минимальное число, такое, что для любого подмножества переменных T мощности p r этим переменным можно присвоить такие значения ai1,. ,aip где p <...>