С.Н. Селезнёва, А.Б. Дайняк, М.С. Шуплецов - Булевы функции и полиномы (1123636), страница 3
Текст из файла (страница 3)
. . , Kb (mk ) , и, возможно,га k , а все слагаемые ранга > k будут исчерпываться конъюнкциями Kконъюнкцией x1 x2 · . . . · xn ранга n (поскольку, если она была в полиноме P0 , избавиться от нее мыне сможем). На шаге l мы придем, таким образом, либо к полиномуb (1) ⊕ . . . ⊕ Kb (l) ,Pl = Kлибо к полиномуb (1) ⊕ . . . ⊕ Kb (l) .Pl = x 1 · . . .
· x n ⊕ KВ любом случае, в Pl будет не более (l + 1) слагаемых. Теорема доказана.3.1. СЛОЖНОСТЬ БУЛЕВЫХ ФУНКЦИЙ В КЛАССЕ ОБОБЩЕННЫХ ПОЛИНОМОВ11Пример 3.2. Приведем пример работы описанного в теореме 3.2 алгоритма.Пусть f (x1 , x2 , x3 ) = x1 x2 x3 ⊕ x1 x2 ⊕ x1 x3 ⊕ x1 ⊕ x3 ⊕ 1. Будем использовать затеняющее множествоиз примера 3.1. ИмеемP0 = x1 x2 x3 ⊕ x1 x2 ⊕ x1 x3 ⊕ x1 ⊕ x3 ⊕ 1 ⊕ x1 x2 x3 ⊕ x2 x3 ⊕ x1 x2 ⊕ x3 = x1 x3 ⊕ x2 x3 ⊕ x1 ⊕ 1Шаг 1.αe(1) = (111)K (1) = x1 x2 x3b (1) = x1 x2 x3Kb (1) ) = x1 x2 x3 ⊕ x1 x3 ⊕ x2 x3 ⊕ x3P (KP1 = x1 x3 ⊕ x2 x3 ⊕ x1 ⊕ 1 ⊕ x1 x2 x3 ⊕ x1 x2 x3 ⊕ x1 x2 x3 ⊕ x1 x3 ⊕ x2 x3 ⊕ x3 = x1 x2 x3 ⊕ x1 ⊕ x3 ⊕ 1Шаг 2.Шаг 3.Шаг 4.αe(2) = (011)K (2) = x2 x3b (2) = x2 x3Kb (2) ) = x2 x3 ⊕ x3P (KP2 = x1 x2 x3 ⊕ x1 ⊕ x3 ⊕ 1 ⊕ x2 x3 ⊕ x2 x3 ⊕ x2 x3 ⊕ x3 = x1 x2 x3 ⊕ x2 x3 ⊕ x1 ⊕ 1αe(3) = (110)K (3) = x1 x2b (3) = x1 x2Kb (3) ) = x1 x2 ⊕ x1P (KP3 = x1 x2 x3 ⊕ x2 x3 ⊕ x1 ⊕ 1 ⊕ x1 x2 ⊕ x1 x2 ⊕ x1 x2 ⊕ x1 = x1 x2 x3 ⊕ x2 x3 ⊕ x1 x2 ⊕ 1αe(4) = (001)K (4) = x3b (4) = x3Kb (4) ) = x3 ⊕ 1P (KP4 = x1 x2 x3 ⊕ x2 x3 ⊕ x1 x2 ⊕ 1 ⊕ x3 ⊕ x3 ⊕ x3 ⊕ 1 = x1 x2 x3 ⊕ x2 x3 ⊕ x1 x2 ⊕ x3Итак, f = x1 x2 x3 ⊕ x2 x3 ⊕ x1 x2 ⊕ x3 .
Заметим, что на самом деле l(f ) = 2, поскольку можноуказать, например, такой полином длины 2 для f : x1 x2 x3 ⊕x3 (а полиномом длины 6 1 функциюf реализовать невозможно).Теорема 3.2 позволяет получать оценки для функции Lо.п. (n) путем построения в E2n затеняющихмножеств “небольшой мощности”.Любое затеняющее множество T ⊆ E2n можно разбить на “слои” T1 , . . . , Tn . Слой Ti содержит всенаборы ранга i из T , и затеняет все наборы ранга (i − 1) из E2n .
Решать задачу поиска T можно,очевидно, по шагам, строя множества Ti последовательно. При этом выбор множества Ti никак независит от выбора других множеств Tj , j 6= i . Поэтому для решения задачи о нахождении множества Tнам достаточно уметь решать подзадачи такого вида: найти множество Ti наборов ранга i , затеняющеевсе наборы ранга i − 1. Воспользуемся для решения подзадач градиентным алгоритмом:(1)Шаг 1. Полагаем Ti= {eα}, где αe — произвольный набор ранга i.(k−1)Шаг k . Пусть результатом предыдущего шага является Ti. Если в E2n нет набора, который не за(k−1)(k−1)теняется множеством Ti, то полагаем Ti = Tiи алгоритм завершается.
В противном(k)(k−1)случае, полагаем Ti = Ti∪ {eα}, где αe — произвольный набор, затеняющий наибольшее(k−1)число наборов из множества E2n \ s(Ti).12ГЛАВА 3. РЕАЛИЗАЦИЯ БУЛЕВЫХ ФУНКЦИЙ ОБОБЩЕННЫМИ ПОЛИНОМАМИОписанный алгоритм, очевидно, строит множество Ti с нужными свойствами, и число шагов алгоритма не превосходит мощность множества наборов ранга (i − 1). Оценим мощность полученногомножества Ti . Введем обозначения:t = ni — мощность множества Ri всех наборов ранга i.nm = i−1— мощность множества Ri−1 всех наборов ранга (i − 1).p = n − i + 1 — число наборов ранга i, затеняющих фиксированный набор ранга (i − 1).Теорема 3.3. Если множество Ti построено градиентным алгоритмом, тоemptln(),pt|Ti | 6 1 +(3.2)где e = 2, 71828 .
. .Доказательство. Пусть δk — доля наборов из Ri−1 , остающихся незатененными после k –го шагаалгоритма. Будем считать по определению, что δ0 = 1 . Положим γ = pt . Среднее число наборов изk)Ri−1 \ s(Tik ) , затеняемых (t − k) наборами из Ti , оценивается снизу какδkmp.t−kГрадиентный алгоритм на (k + 1) –ом шаге выбирает набор, затеняющий максимальное, а значит, неmpменьшее, чем δk t−kчисло наборов из Ri−1 \ s(Tik ) . Поэтомуmδk − mδk+1 > δkmp.t−kОтсюдаp) 6 δk (1 − γ).(3.3)t−kИз (3.3) по индукции получаем, что δk 6 (1 − γ)k .
Поскольку на каждом шаге алгоритма в множество,полученное на предыдущем шаге, добавляется ровно один набор, то общее число шагов не превосходитвеличины (k + mδk ) , причем это верно для любого k . В результате получаем, чтоδk+1 6 δk (1 −|Ti | 6 k + mδk 6 k + m(1 − γ)k 6 k + me−γk .(3.4)В неравенстве в (3.4) мы воспользовалисьтем,m что 1 − x 6 e−x для любого действительного x .lПолагая в (3.4) число k равным γ1 ln(γm) , получаем (3.2).Следствие 3.1. При любом n > 1 в E2n существует затеняющее множество T мощности небольше2n2·(1 + ln n) − 1.nДоказательство. Пусть n > 5 . Построим множество T как объединение n множеств Ti , каждое изкоторых получено градиентным алгоритмом.
Имеем|T | =Pni=1|Ti | 6Pni=1 (1=Pn−1=Pn−1=Pni=0i=0+(ni)n−i+1(ni)(1 +i+1(1 +i+1i=1 (1+n+12n+16n+62n+1n (1(ni)ln(ne(i−1)(n−i+1)(ni)ne(i+1)(i+1)(ni))) =)) =ln(e(n − i))) =(n+1i )n+1ln((1 + ln(n − i + 1))) 6(1 + ln n) 6+ ln n) − 1.3.2. ПРИБЛИЖЕННАЯ РЕАЛИЗАЦИЯ БУЛЕВЫХ ФУНКЦИЙ13Ограничение n > 5 нам понадобилось только для обеспечения последнего неравенства в приведеннойвыше цепочке.Если n 6 4 , то достаточно воспользоваться результатами примера 3.1 и упражнения 8.Из теоремы 3.2 и следствия 3.1 многновенно вытекает следующее утверждение, дающее лучшую попорядку известную на сегодняшний день (декабрь 2006) верхнюю оценку для Lо.п. (n).Теорема 3.4.Lо.п. (n) 6 2 ·3.22n(1 + ln n).nПриближенная реализация булевых функцийВ этом параграфе мы займемся получением оценок для длины и ранга полиномов Жегалкина, приближенно реализующих булевы функции.
Уточним сначала, что мы будем понимать под приближеннойреализацией. Везде далее разделе рассматриваются только полиномы Жегалкина.Расстоянием между функциями f (exn ) и g(exn ) (обозначается d(f, g)) называется расстояние Хемeминга d(f , ge) между векторами-столбцами значений этих функций. Иными словами, d(f, g) — эточисло наборов, на которых значения функций f и g отличаются.Пусть δ ∈ [0, 1] — действительная константа. Будем говорить, что функция g(exn ) является δ –nприближением функции f (ex ), еслиd(f, g)6 δ,2nиначе говоря, доля наборов, на которых f и g совпадают, должна быть не меньше 1 − δ .Если полином P реализует какое-то δ –приближение функции f , то будем говорить, что P реализует f с точностью δ .Заметим, что, вообще говоря, один и тот же полином может приближенно реализовывать несколькофункций, и для одной функции может быть несколько δ –приближений. Любая функция является 1–приближением любой другой функции.
0–приближением всякой функции является только она сама.Введем функции сложностиrδ (f ) =min r(Pg )g – δ-пр. flδ (f )=rδ (n)=lδ (n)=ming – δ-пр. fl(Pg )max rδ (f )f ∈P2 (n)max lδ (f )f ∈P2 (n)В данном параграфе мы установим асимптотику функции rδ (n) и получим оценку сверху для lδ (n) .Вначале нам потребуется доказать некоторые оценки для биномиальных коэффициентов и их сумм.Лемма 1. При любых r и n таких, что 2r < n , выполнено неравенство n2n6.rn − 2r(3.5)Доказательство. При 2r < n имеемb(n−1)/2c Xi=0b(n−1)/2c >Xi=rnib(n−1)/2c >Xi=rni> nnn−1=·(− r + 1) >rr2> nr · ( n2 − r).(3.6)14ГЛАВА 3.
РЕАЛИЗАЦИЯ БУЛЕВЫХ ФУНКЦИЙ ОБОБЩЕННЫМИ ПОЛИНОМАМИС другой стороны, из равенствni=nn−iиn Xnii=0= 2nследует, чтоb(n−1)/2c niXi=06 2n−1 .(3.7)Из (3.6) и (3.7) следует (3.5).Лемма 2. Пусть 0 6 r <n2. Тогдаr Xni=0i6n−r· 2n .(n − 2r)2(3.8)Доказательство. Пусть r > 0 . Заметим, что для любого i < r nrr−innr(r − 1) · .
. . · (i + 1)6.·=·(n − r + 1)(n − r + 2) · . . . · (n − i)r(n − r + 1)r−iirОтсюдаr Xni=0i6nrr X·i=0rr−i=(n − r + 1)r−i∞ X·6nr=ni=0r·rn−ri Xrrin·6r(n − r + 1)ii=0 n1=·=r1 − n−rrn−rn−2r .Итак,r Xni=0i6 nn−r.·n − 2rr(3.9)Осталось воспользоваться неравенством (3.5).Мы действовали в предположении, что r > 0. Но если r = 0, то неравенство (3.8) также, очевидно,выполнено.nСледствие 3.2. Учитывая то, что ni = n−i, из леммы 2 следует, что при n2 < r 6 n выполненонеравенствоn Xnr6· 2n .2(2r−n)ii=rЛемма 3. Пусть δ ∈ (0, 21 ) — фиксированная константа.
Тогда существует такая константа < 1 ,что при всех достаточно больших n и всех r 6 δn выполнено неравенствоr Xn6 2n .ii=0rДоказательство. Случай r = 0 тривиален. Пусть r > 0 . Положим t = n−r. Учитывая то, что t < 1 ,имеемnrrXn i X n i−r X nt−r (1 + t)n = t−rt >t>.iiii=0i=0i=03.2. ПРИБЛИЖЕННАЯ РЕАЛИЗАЦИЯ БУЛЕВЫХ ФУНКЦИЙУчитывая, что t−r (1 + t)n =nnr r (n−r)n−r, получаем:r Xni=015i6rnn= 2n·H( n ) ,rn−rr (n − r)где функция H — функция двоичной энтропии, задаваемая при x ∈ [0, 1] равенством1H(x) = −x log2 x − (1 − x) log2 (1 − x).В качестве несложного упражнения, предоставляем читателю показать, что функция H(x) возрастает на интервале (0, 21 ) , и что H(x) < 1 при x ∈ (0, 12 ) .
Из этого непосредственно будет следоватьдоказываемое утверждение — в качестве искомого достаточно будет взять любое число из интервала[H(δ), 1).Теперь у нас есть все необходимые технические средства для доказательства следующей теоремы.Теорема 3.5 ([2, 6]). rδ (n) = 0 при δ >rδ (n) = n при δ = 0.rδ (n) ∼ 21 n при δ ∈ (0, 12 ) .12.Доказательство.
Доказательство в случае δ = 0 и δ > 21 предоставляется читателю.Пусть δ ∈ (0, 12 ). Получим сначала асимптотическое неравенство rδ (n) . n2 . Пусть f (exn ) — произвольная функция. Пусть r ∈ [1, n] — некоторое натуральное число. Пусть P — полином, получающийсяиз полинома Жегалкина для f отбрасыванием всех слагаемых, ранг которых больше r . Подберем rтак, чтобы полином P реализовывал f с точностью δ .
Заметим, что полином P реализует функцию,совпадающую с f на всех наборах ранга, не превосходящего r . Поэтому достаточно взять такое r , длякоторого число наборов ранга больше r составляет от числа всех наборов долю, не большую δ . Этомуусловию удовлетворяют такие значения r , при которыхn Xn6 δ · 2n .ii=rДля выполнения этого неравенства, в силу следствия 3.2, достаточно, чтобы r удовлетворяло неравенствам r > n2 иr6 δ.(3.10)(2r − n)2При r >n2неравенство (3.10) эквивалентно неравенствуn − r 6 δ(n − 2r)2 .Этому квадратичному неравенству удовлетворяет, например,√n 1 + 8δn + 1nr=+. .28δ2Отсюда rδ (n) .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
