A condition for uniqueness of linear decomposition of a boolean function into disjunctive sum of indecomposable function.pdf Пусть Fn = {f : Vn ^ GF(2)} -множество двоичных функций от n переменных, n ^ 1, Vn = GF(2)n рассматривается как векторное пространство над полем GF(2), Hn - группа сдвигов пространства V^. Для каждого целого s ^ 0 определим подпространство Us = {f : deg f ^ s} пространства функций Fn, имеющих ограниченную степень нелинейности (не больше s). Заметим, что U0 = {0,1}. При s < 0 положим Us = {0} -нулевое подпространство. Обозначим (Hn)fs) множество таких сдвигов x Е Hn, что выполнено сравнение n x ф а у f (x ф а) = f (x) (mod Us), x Е К. Пусть 0 ^ t ^ n - 1, 1 ^ k ^ n. Будем говорить, что переменные x&+1,...,x. функции f (x1,..., xn) являются несущественными по модулю Us, если найдётся функция h(x1,... , xk), такая, что f ф h Е Us. Нетрудно видеть, что переменное xn является несущественным для функции f по модулю Us, если и только если x ) Е (Н„Г1) x ф enу при en = (0,..., 0,1). Будем говорить, что функция f Е Fn линейно разложима в бесповторную сумму по модулю Us, если при некотором линейном преобразовании A пространства V^ и 1 ^ k < n найдутся функции f1 и f2, для которых выполнено сравнение f (xA) = f1 (x1, . . . ,xfc) ф f2(xfc+1, ...,!„) (mod Us). Заметим, что разложение двоичной функции в бесповторное произведение нелинейных неприводимых сомножителей изучалось в работе [1]. Случай, когда s ^ 0 и k = 1 (k = n - 1), рассмотрен в [2]. В этом случае пространство размерности n - 1 однозначно определено в том и только в том случае, когда у функции f2 (f1) все переменные существенны по модулю U1. Для s ^ 1 и слагаемых второй степени ни о каком однозначном разложении в принципе не может быть и речи, так как таким функциям соответствуют квадратичные формы, которые имеют неприводимые группы инерции, в качестве которых выступают классические линейные группы. В то же время для s ^ 2 и слагаемых степени три и выше при ограничениях на число существенных переменных по модулю Us уже можно показать однозначность для разложения, имеющего максимальное число слагаемых. Теорема 1. Если при s ^ 2 функция f = f (x1,... ,xn) имеет тривиальную группу инерции (Hn)/s 1) и линейно разложима в бесповторную сумму по модулю Us, то для этой функции найдётся линейное разложение по модулю Us в бесповторную сумму линейно неразложимых (в бесповторную сумму) слагаемых, однозначно определённое в том смысле, что любое другое такое разложение соответствует тому же самому разложению пространства в прямую сумму подпространств, а соответствующие функции линейно эквивалентны по модулю Us. Метод доказательства аналогичен тому, который применён в работе [3]. В качестве следствия получаем описание группы инерции таких функций в полной аффинной группе. Следствие 1. Если в условиях теоремы 1 функция f представлена в виде суммы линейно неразложимых в бесповторную сумму по модулю Us функций f = f1 ф-.-ф fm (mod Us), причём множество функций {f1,... , fm} разбивается на t классов аффинной эквивалентности по модулю Us: f,... f} С , ... , f,... , f Vq} С Fnt, то для группы инерции бесповторной суммы этих функций справедлив изоморфизм AGL (n, 2/ф„/ = [AGL (nb /]SP x ■ ■ ■ x [AGL (nt, /]Sff. Здесь через G/s) обозначена группа инерции функции f по модулю Us в группе G, а [G]Sp - операция экспоненцирования группы G с помощью симметрической группы Sp степени p. Аналогичное описание справедливо для полной линейной группы GL (n, 2).

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