On almost balanced boolean functions.pdf Обозначим через En множество упорядоченных двоичных наборов (вершин) дли-ны n. Введём операцию [x,y] = (x1y1 , . . . , xnyn) для наборов x , y . En . Количествоединиц в наборе y . En называется весом набора и обозначается через wt(y). Множе-ство вершин чётного веса будем обозначать через E. (нечётного - через E . ) . Граньюразмерности (n - wt(y)) называется множество E . ( z ) = {x . En : [x,y] = [z,y]}.Пусть S С En ; через xS будем обозначать характеристическую функцию множе-ства S. Функция xS называется корреляционно-иммунной порядка (n - m), если длялюбой грани E . ( z ) размерности m пересечения E . ( z ) n S имеют одинаковую мощность.хРабота выполнена при поддержке РФФИ (проекты 11-01-997, 10-01-00616) и ФЦП «Науч-ные и научно-педагогические кадры инновационной России» на 2009-2013 гг. (гос. контракт№02.740.11.0362).Через cor(S) будем обозначать максимальный порядок корреляционной иммунности,cor(S) = max{n - m}. Корреляционно-иммунная функция XS называется уравновешен-ной, если |S| = 2n - 1 . Тогда множество S пересекается с гранями размерности m ровнопо половине вершин, т. е. |Eyn(z) ПS| = |Eyn(z)|/2. В [1] установлено, что неуравновешен-ная непостоянная булева функция XS удовлетворяет неравенству cor(S) ^ 2n/3 - 1. Яс-но, что непостоянная корреляционно-иммунная функция порядка n - 1 является счёт-чиком чётности или нечётности (хЕ° или xEn = XE° © 1). Корреляционно-иммунныефункции порядка n - const немногочисленны и описаны в [2]. Некоторые оценки числакорреляционно-иммунных функций меньших порядков имеются в [2 - 4].Ниже рассматривается класс почти уравновешенных функций, содержащий зна-чительное количество не эквивалентных булевых функций, максимально подобныхкорреляционно-иммунным функциям высокого порядка. Функцию XS будем назы-вать почти уравновешенной, если для любой грани E^(z) любой размерности пере-сечение Eyn(z) П S отличается от половины мощности грани не более чем на 1, т.е.- 1 ^ |Eyn(z) П S| - |Eyn(z)|/2 ^ 1.В соответствии с определением класс почти уравновешенных функций является на-следственным, т. е. все ретракты почти уравновешенных функций, полученные произ-вольной фиксацией произвольного набора переменных, являются почти уравновешен-ными. Одним из способов задания наследственного класса булевых функций являетсяперечисление минимальных запретов. Булева функция g размерности k называетсяминимальным запретом для наследственного класса P, если g Е P, но все её ретрак-ты содержатся в P. Поскольку P - наследственный класс, функции из класса P неимеют ретрактов, совпадающих с запретом g.Теорема 1. Множество почти уравновешенных булевых функций является на-следственным классом с бесконечным набором минимальных запретов.Будем обозначать через P(n) множество функций от n аргументов из класса P.Пусть f Е P(n), вершину x Е En будем называть свободной относительно f, еслинайдётся функция f' Е P(n), отличающаяся от f только на аргументе x.Утверждение 1. Пусть P - наследственный класс и для некоторого m любаяm - . 1 / (n\)функция f Е P(m) не имеет свободных вершин. Тогда |P(n)| ^ 2 k=0 .Далее рассмотрим множество трёхзначных функций f : En ^ { - 1, 0,1}, опре-делённыхна булевом кубе. Приведённые выше определения наследственного класса,минимального запрета и свободной вершины естественным образом распространяютсяна такие функции. Определим класс B трёхзначных уравновешенных функций сле-дующим образом: f Е B, если для любой грани 7 = Eyn(z) любой размерности суммазначений функции в ней не превышает по модулю единицы, т. е. f(x) Е {-1, 0, 1}.Через B0 будем обозначать подкласс класса B, удовлетворяющий дополнительнымусловиям f - 1 ( 1 ) С En и f - 1 (-1) С En. Ясно, что классы B и B0 являются наслед-ственными.Утверждение 2. Булева функция f является почти уравновешенной тогда и/ЕП 7-> - X Е B0.Преобразованием Мёбиуса функции h : En ^ R называется функцияM[h] : En ^ R, где M[h](y) = (-1)wt(y) Е h(x).i E E " ,[x,y]=xИз формулы включения-исключения и определения классов B и Bo получаемУтверждение 3.а) M[M[h]] = h для любой функции h : En ^ R.б) M [B] = B.в) M [ f ] . B0U(-Bo), если и только если f . B и 0 - свободная вершина функции f.Справедливость п. в следует из того, что вершина является свободной, только есливо всех гранях, содержащих вершину, сумма значений функции имеет одинаковыйзнак.В следующих утверждениях приведены несколько способов построения функцийиз классов B и B0.Утверждение 4.а) Пусть f . B (или f . B0), тогда f xY . B (или f xY . B0 ) для любой грани 7.б) Пусть f . B0(n), тогда (-1)xEn - f . B0(n).в) Пусть 71,72 - грани в En и 71 П Y2 = 0. Определим функцию f равенствомf (x1,... ,x.,xn+1) = xn+1XY1 (-1)xEn + (xn+1 0 1)х72(-1)xEn. Тогда f . B0(n + 1).Утверждение 5.а) Пусть f . B(n), g . B(m) и F(x,y) = f (x)g(y). Тогда F . B(n + m).б) Пусть f . B0(n), g . B0(m) и F(x,y) = f (x)g(y). Тогда F . B0 (n + m).Доказательства утверждений 4 и 5 легко получить непосредственной проверкой.Булев n-мерный куб En естественным образом наделяется структурой вектор-ного пространства над полем GF(2). Будем называть носителем вектора x . Enмножество позиций, на которых в векторе x находятся единицы. Рассмотрим наборвекторов z 1 , . . . , z k с попарно не пересекающимися носителями. Пусть V С En -подпространство, натянутое на векторы z1, . . . , z k , V = {ф a,z, : а . Ek } . Пустьf : Ek ^ { -1,0,1}. Определим функцию Gy [ f ] : En ^ { - 1, 0,1} равенствамиGV[ f ] ( x ) = f (а), если x = ф aгzг, и Gy [ f ] ( x ) = 0, если x . V.Теорема 2.а) Если f . B(k), то Gy[f] . B(n).б) Класс B(n) содержит не менее еСл,/п, c > 0, неэквивалентных функций.

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