Some decompositions for quadratic boolean threshold functions.pdf Полиномиальная булева пороговая функция f (x1,... , xn) определяется следующим образом [1]: f (xb ... ,Xn) = 0 ^ g(xb... ,Xn) ^ 0, (1) где g - действительный полином. Если degg = 2, то говорят о квадратичных булевых пороговых функциях (к.б.п.ф.). В последнем случае неравенство из (1) может быть преобразовано в эквивалентное w(x1,...,xn) ^ t, где w - квадратичная форма; t - свободный член многочлена g, взятый с противоположным знаком и называемый порогом. Пару (w,t) часто называют структурой квадратичной пороговой функции f. Если для некоторых m из {1,... , n - 1} и квадратичных форм u и v справедливо представление w(x1,..., xn) = u(x1,... , xm) + v(xm+1,... , xn), то этот факт для краткости будем обозначать w = u + v. Введём бинарное отношение ~ на множестве целочисленных матриц одного размера. Будем полагать, что A ~ B, если , i2, j1 , j2 (aii,ji < ai2,j2 ^^ 1 ,j1 < bi2,j2 & ail,j1 ai2,j2 ^^ bil,j1 bi2,j2 ). Очевидно, что отношение ~ является отношением эквивалентности, и множество всех матриц одного размера разбивается на классы эквивалентных матриц по введённому отношению. Пример 1. Построим класс матриц, эквивалентных единичной матрице E3: это любые целочисленные матрицы вида a b b\ b a b I , b b ay где a > b. Пусть Aw = {jw(x) : x Е {0,1}ra}} -мультимножество значений квадратичной формы w(x). Через {Aw} обозначим множество значений w(x); w* = (w0,w2,..., w*n-1) -упорядоченный по неубыванию набор элементов множества Aw. В [1] введены понятия нижнего |_ajw и верхнего |~a]w приближений действительного числа a в множестве значений w(x) : |_ajw = max{z Е {Aw} : z ^ a}, |~a]w = min{z Е {Aw} : z > a}. Заметим, что нижнее и верхнее приближения a существуют, если и только если a ^ w* и a < w*„_ 1 соответственно. В дальнейшем для удобства максимальный элемент последовательности w2 обозначим wmax. Кроме того, положим |_ajw = - то, если a < w0, и [a]w = то, если a ^ wmax; в этом случае будем говорить о бесконечных приближениях. По аналогии с таблицей Sfm) = ||, i = 0,..., 2m - 1, j = 0,..., 2n-m - 1, введённой в [1] для к.п.б.ф. f со структурой (u+v, t), элементы которой определяются следующим образом: Sij = 0 ^ u* + v* ^ t, Sij = 1 ^ u* + v* > t, введём таблицу qW™ = ||qij ||, i = 0,... , 2m - 1, j = 0,... , 2n-m - 1, для распавшейся квадратичной формы w = u + v, элементы которой определяются следующим образом: qij = u* + v*. Для таблицы QWm), как и для Sfm), справедливо свойство монотонности: если p ^ i, q ^ j, то qpq ^ qij. Свойство функциональной разделимости [1, определение 1] булевых функций с данным отношением связывает Утверждение 1. Пусть w, z - квадратичные формы от n переменных и к.б.п.ф. f со структурой (w,t) допускает простую декомпозицию с параметром m. Если QWm) ~ Qzm), то существует такое d, что к.б.п.ф. со структурой (z,d) также допускает простую декомпозицию с параметром m. (Как ив [1], для простоты полагаем, что перестановка переменных в простой декомпозиции для f тождественная.) Доказательство. Достаточно заметить, что в качестве d можно взять элемент qij, такой, что = |_tJw Тогда по свойству монотонности и из эквивалентности q|j = d ^ sgs = 1. ■ Следствие 1. К.п.б.ф. f со структурой (w,t) и g со структурой (z,d) из утверждения 1 эквивалентны относительно группы перестановок переменных. Замечание 1. Пусть w(x) = x2 +... + xn. Тогда к.п.б.ф. f со структурой (w,t) является функционально неразделимой для невырожденных значений порогов, так как f является линейной п.б.ф. со структурой (€, t), где € = x1 + ... + xn, и, следовательно, функционально неразделимой для невырожденных значений порогов [2]. В некоторых случаях матрица QWm) может быть разбита на группы смежных строк и столбцов так, что подматрицы, лежащие на пересечении строк из какой-либо группы строк и столбцов из какой-либо группы столбцов, состоят из одинаковых элементов а. Такие подматрицы будем называть блоками и обозначать через [a]rxs или arxs, где r х s - размер блока. В очевидных случаях указание на размер блока может опускаться. Например, для квадратичной формы w(x) = x2 +... + xn матрица QWm) распадается на m +1 групп строк и n - m +1 групп столбцов и приобретает блочный вид / 0 1 ... n - m \ 1 2 ... n - m +1 \m m +1 ... n у где блок [i + j] имеет размер х ^n . . Блочную матрицу (2) будем обозначать [QWm)]. Очевидным является Утверждение 2. Если матрицы QWm) и Q(m) для квадратичных форм w и z эк- (т) (т) (т) (т) вивалентны, т.е. Qw ~ QZ , то [Qw ] ~ [QZ ]. Обратное, вообще говоря, неверно, однако в утверждении 1 можно перейти к более общей формулировке. Утверждение 3. Пусть w,z - квадратичные формы от необязательно одного и того же числа переменных и к.б.п.ф. f со структурой (w,t) допускает простую декомпозицию с параметром m. Если для некоторого натурального r выполняется [QWm)] ~ [QZr)], то существует такое число d, что к.б.п.ф. со структурой (z,d) также допускает простую декомпозицию с параметром m. Утверждение 3 представляет собой переформулировку утверждения 1 из [3], которое основано на отношении частичного порядка на множестве квадратичных форм. Дальнейшее обобщение утверждения 3 может быть связано с рассмотрением полиномиальных пороговых функций, что показывает следующий пример. Пример 2. Пусть £(я) = x1 + ... + xn и w(x) = (x1 + ... + xn)k. Тогда [Q(m)] ~ - [QWm)]. Следующая теорема даёт полное описание нетривиальных простых декомпозиций для к.б.п.ф. с распавшейся на два константных блока квадратичной формой. Доказательство проводится путём непосредственного применения критерия функциональной разделимости для квадратичных булевых пороговых функций [1, теорема 4]. Теорема 1. Пусть квадратичная форма em задана матрицей 1m, квадратичная форма w = em + aen-m, a Е n, - распавшаяся, к.б.п.ф. f, заданная структурой (w,t), существенно зависит от всех своих переменных. Тогда f допускает нетривиальную простую декомпозицию с параметром m тогда и только тогда, когда выполняется любое из условий: 1) t < m2 и существует j Е {1,..., n - m}, что |_tje + a(j - 1)2 ^ t < |~t]e; 2) t > m2 и существуют i Е {1,..., m}, j Е {1,..., n - m}, такие, что max{(i - 1)2 + a(n - m)2,m2 + a(j - 1)2} ^ t < i2 + aj2; 3) t > m2 и существуют i Е {1,..., m}, j, l Е {1,..., n - m}, такие, что j < l и max{(i - 1)2 + a(l - 1)2, m2 + a(j - 1)2} ^ t < min{al2, i2 + aj2}.

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