С.Н. Селезнёва, А.Б. Дайняк, М.С. Шуплецов - Булевы функции и полиномы (1123636), страница 2
Текст из файла (страница 2)
(n) =3(2.1)Доказательство. Сначала докажем, что для любой функции f ∈ P2 (n) выполнено неравенство2 nLп.п. (f ) 6·2 .(2.2)3Проведем доказательство индукцией по n .Если n = 1, то L(f ) = 1 6 23 · 21 .Пусть n > 1 , и Lп.п. (n) 6 23 · 2n . Пусть f (exn+1 ) — произвольная булева функция. Для σ ∈ E2обозначим fσ (x2 , . .
. , xn+1 ) = f (σ, x2 , . . . , xn+1 ). Запишем очевидные равенства:=f (x1 , . . . , xn+1 ) = x1 · f0 ⊕ x1 · f1= x1 (f0 ⊕ f1 ) ⊕ f1 == x1 (f0 ⊕ f1 ) ⊕ f0 .(2.3)Положим f 0 = f0 ⊕ f1 . По предположению индукции, найдется вектор δe0 такой, что2 n2e0l(Pfδ0 ) 6· 2 6 · 2n .33e0Для σ ∈ E2 положим Pσ0 = Pfδσ . Имеемf = x1 · P00 ⊕ x1 · P10 .(2.4)Пусть найдется ЭК, встречающаяся в обоих полиномах P00 и P10 — вынесем ее в качестве отдельногослагаемого в правой части равенства (2.4).
Например, пусть P00 = K ⊕ P000 и P10 = K ⊕ P100 . Тогдаf===x1 · (K ⊕ P000 ) ⊕ x1 · (K ⊕ P100 )x1 ·x1 ·P000P000⊕ x1 ·⊕ x1 ·P100P100⊕ x1 · K ⊕ x1 · K⊕ K.==2.2. СЛОЖНОСТЬ БУЛЕВЫХ ФУНКЦИЙ В КЛАССЕ ПОЛЯРИЗОВАННЫХ ПОЛИНОМОВ7Если в полиномах P000 и P100 найдутся одинаковые ЭК, снова вынесем их отдельно. Так будем действовать до тех пор, пока не получим для f представлениеf = x 1 · P0 ⊕ x 1 · P1 ⊕ P2 ,где в полиномах P0 , P1 и P2 уже не будет одинаковых слагаемых. Теперь заметим, чтоf 0 = P00 ⊕ P10 = P0 ⊕ P1 ,(2.5)то есть P0 ⊕P1 — это δe0 –поляризованный полином для f 0 . Вектор δe0 выбирался так, что l(P0 ⊕P1 ) 6 32 ·2n .Хотя бы один из полиномов P0 , P1 имеет длину, не превосходящую12n· l(P0 ⊕ P1 ) =.23Предположим для определенности, что l(P0 ) 6равенства P00 = P0 ⊕ P2 , получаем:2n3.
Возьмем δe = (0, δe0 ) . Из (2.3), (2.5), а также изf = x1 · (f0 ⊕ f1 ) ⊕ f0 = x1 · (P0 ⊕ P1 ) ⊕ P0 ⊕ P2 .Поскольку полиномы P0 , P1 и P2 содержат различные слагаемые, их суммарная длина не превосхоnдит 2n . Кроме того, l(P0 ) = 23 . Поэтому длина полинома, получающегося при раскрытии скобок ввыраженииx1 · (P0 ⊕ P1 ) ⊕ P0 ⊕ P2 ,не превосходит 31 · 2n + 2n = 23 · 2n+1 .
Нетрудно видеть, что этот полином является δe–поляризованнымполиномом,функцию f . Таким образом, индуктивный переход завершен и неравенство реализующимLп.п. (n) 6 23 · 2n доказано.Осталось доказать неравенство2 nLп.п. (n) >·2 .(2.6)3Рассмотрим функции fn , gn и hn , задаваемые рекурсивно следующим образом: Если n = 1, тоf1 = 1, g1 = x1 , h1 = x1 . Если n > 1 , тоfn+1 = xn+1 · fn ⊕ xn+1 · gn ,gn+1 = xn+1 · gn ⊕ xn+1 · hn ,hn+1 = xn+1 · hn ⊕ xn+1 · fn .(2.7)eeeПокажем, что для любого фиксированного вектора δe из чисел l(Pfδn ), l(Pgδn ), l(Phδn )n+1n+1два равны 2 3 −1 , и одно равно 2 3 +2 , когда n нечетно,n+1n+1два равны 2 3 +1 , и одно равно 2 3 −2 , если n четно (из этого сразу следует (2.6)).В случае, когда n = 1 и n = 2 это свойство проверяется, например, перебором. Пусть n > 2 , ипусть δe = (δe0 , δn+1 ) ∈ E2n+1 . По индукции легко доказать (и это предлагается проделать в качествеупражнения), что fn ⊕ gn ⊕ hn = 0, откуда fn ⊕ gn = hn .
Запишем цепочку равенствfn+1====xn+1 · fn ⊕ xn+1 · gn =xn+1 · fn ⊕ fn ⊕ xn+1 · gn =xn+1 · (fn ⊕ gn ) ⊕ fn =xn+1 · hn ⊕ fn .Аналогично можно доказать равенство fn+1 = xn+1 · hn ⊕ gn . Для функций gn+1 и hn+1 тем жеспособом получаются аналогичные представления. Окончательно имеем:fn+1 = xn+1 · hn ⊕ fn = xn+1 · hn ⊕ gn ,gn+1 = xn+1 · fn ⊕ gn = xn+1 · fn ⊕ hn ,hn+1 = xn+1 · gn ⊕ hn = xn+1 · gn ⊕ fn .8ГЛАВА 2. ПОЛИНОМЫ ЖЕГАЛКИНА И ПОЛЯРИЗОВАННЫЕ ПОЛИНОМЫОтсюда видно, что если δn+1 = 0, тоe0e0e0e0e0e0e0e0e0e0e0e0l(Pfδn+1 ) = l(Phδn ) + l(Pfδn ),el(Pgδn+1 ) = l(Pfδn ) + l(Pgδn ),el(Phδn+1 ) = l(Pgδn ) + l(Phδn ).eЕсли же δn+1 = 1, тоl(Pfδn+1 ) = l(Phδn ) + l(Pgδn ),el(Pgδn+1 ) = l(Pfδn ) + l(Phδn ),el(Phδn+1 ) = l(Pgδn ) + l(Pfδn ).eЭти равенства завершают (проверьте!) индуктивный переход, а значит и доказательство неравенства (2.6).Из (2.2) и (2.6) следует (2.1).
Теорема доказана.Примечание. Функции fn , gn , hn , определяемыеиз (2.7), являются единственными функциями,сложность которых в точности равняется 23 · 2n . Подумайте, как это можно доказать.Упражнение 6. Для функции h3 (ex3 ) , определяемой по формуле (2.7), запишите поляризованныйполином длины 5 .Глава 3Реализация булевых функцийобобщенными полиномами3.1Сложность булевых функций в классе обобщенных полиномовОбозначим через P(n) множество всех обобщенных полиномов от переменных из {x1 , . . .
, xn }. Как ив предыдущем параграфе, введем функции сложности:l(f ) = minPf l(Pf )Lо.п. (n) = maxf ∈P2 (n) l(f ) — функция Шеннона сложности в классе обобщенных полиномов.В данном параграфе приводятся лучшие известные на сегодняшний день (ноябрь 2006 г.) оценкидля функции Lо.п. (n) , причем верхняя оценка получена совсем недавно, а нижняя — почти 40 летназад. С доказательства нижней оценки мы и начнем этот параграф.Теорема 3.1 ([11]).Lо.п.
(n) >2n.n log2 3(3.1)Доказательство. Пусть Lо.п. (n) = L. Всего существует 3n ЭК от n переменных. Поэтому числополиномов длины не больше L от n переменных не превосходит (3n )L . Число булевых функций отnn переменных равно 22 . Очевидно, число полиномов не должно быть меньше числа функций, иначенайдется функция, которую реализовать полиномом длины 6 L не получится — вопреки определениюLо.п. (n).nПолучаем 3nL > 22 , откуда сразу следует утверждение теоремы.Упражнение 7. Покажите, что с помощью идеи из доказательства теоремы 3.1 порядок оценки(3.1) нельзя улучшить, даже оценивая число полиномов длины не больше L точно, как суммуL nX3ii=0.Теперь получим существенно менее тривиальную верхнюю оценку для Lо.п.
(n) . Для этого нампотребуется сначала дать несколько новых определений.Для всякого набора αe ∈ E2n определим его теньe = |es(eα) = {βe | βe 6 αe, |β|α| − 1}.910ГЛАВА 3. РЕАЛИЗАЦИЯ БУЛЕВЫХ ФУНКЦИЙ ОБОБЩЕННЫМИ ПОЛИНОМАМИДля множества наборов T тень определяется следующим образом:[s(eα).s(T ) =αe∈TМножество T ⊆ E2n назовем затеняющим, если s(T ) = E2n \ {e1} .Будем говорить, что монотонная элементарная конъюнкция K соответствует набору αe , еслиind(K) = ind(eα).Набор αe затеняет набор βe , если βe ∈ s(eα) .Пример 3.1. Множество T = {(111), (011), (110), (001)} является затеняющим в E23 .
Наборамэтого множества соответствуют ЭК x1 x2 x3 , x2 x3 , x1 x2 , и x3 .Упражнение 8. Найдите в E24 затеняющее множество мощности 7.Теорема 3.2 ([3]). Если в E2n найдется затеняющее множество мощности l , то для любой функцииот n переменных существует реализующий ее обобщенный полином длины не большей, чем (l + 1) .Доказательство. Пусть T = {eα(1) , αe(2) , . . . , αe(l) } ⊆ E2n — затеняющее множество. Будем считать, чтонаборы в T упорядочены по невозрастанию, то есть αe(1) = e1 , и при i < j наборы αe(i) и αe(j) либо(i)(j)(m)несравнимы, либо αe >αe .
Через Kбудем обозначать ЭК, соответствующую набору αe(m) .nПусть f (ex ) ∈ P2 (n) — произвольная функция. Пусть P0 — полином Жегалкина для функцииf (exn ) ⊕ K (1) ⊕ K (2) ⊕ . . . ⊕ K (l) . Приведем явный алгоритм преобразования полинома P0 в обобщенныйполином длины не больше (l + 1) для f . Алгоритм состоит из l шагов. Опишем шаг с номером m > 1 :b (m) = xσ1 · .
. . · xσrm , гдеПусть ind(K (m) ) = {i1 , . . . , irm } . Построим конъюнкцию Ki1i rmσs =0,1,если в Pm−1 найдется ЭК K такая, что K (m) = K · xrsиначе.b (m) ) — полином Жегалкина для Kb (m) . Результатом шага с номером m являетсяПусть P (Kполиномb (m) ⊕ K (m) ⊕ P (Kb (m) ).Pm = Pm−1 ⊕ KПосле l шагов алгоритма мы получаем полином Pl .
Он, очевидно, реализует функцию f , посколькуна каждом шаге m мы прибавляем к полиному Pm−1 некоторый полином, реализующий функциюK (m) . Начали мы с полинома P0 , реализующего f (exn ) ⊕ K (1) ⊕ K (2) ⊕ . . . ⊕ K (l) , значит в результатеполучим полином, реализующий f .Осталось показать, что длина Pl не превосходит (l + 1). Основная идея состоит в том, что на шагес номером m мы удаляем из полинома Pm−1 все монотонные ЭК ранга (r(K (m) ) − 1) такие, что соответствующие им наборы затеняются набором αe(m) . Правда, приходится платить за это добавлением(m)bЭК Kи некоторого числа слагаемых ранга не больше (r(K (m) ) − 2). Из определения затеняющегомножества следует, что для всякого k < n на каком-то шаге mk мы удалим все монотонные ЭК ранb (1) , .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
