Материалы для подготовки к экзамену (2012-2013 учебный год), страница 3

Аналогичным образом вводится «частичная» сложность LБ0 (Σ) и «частичная» глубина DБ0 (Σ) дляСФЭ Σ.Напомним (см. [3]), что СФЭ называется приведённой, если выход любого еёФЭ, не являющийся выходом схемы, поступает на вход другого ФЭ этой схемы.Приведённая СФЭ (системы формул) считается строго приведённой, если в нейнет эквивалентных вершин, то есть вершин, в которых реализуются равные ФАЛ(соответственно нет эквивалентных вершин, лежащих на одно цепи).

Заметим, чтодля любой СФЭ (системы формул) Σ существует эквивалентная ей строго приведённая СФЭ (соответственно система формул) Σ0 , для которойLБ0 (Σ0 ) 6 LБ0 (Σ) и TБ0 (Σ0 ) 6 TБ0 (Σ)при любом Б0 ⊆ Б. Легко видеть также, что в строго приведённой формуле илиСФЭ нет трёх или более последовательно соединённых одновходовых ФЭ.b = { Ei | ki > 2 } и заметим, что множество БbДля базиса Б = {Ei }bi=1 положим Бb определим его приведённыйне пусто в силу полноты базиса Б.

Для ФЭ Ei , Ei ∈ Б,вес ρi и приведённую задержку τi следующим образом:ρi =Li,ki − 1τi =Ti.log kiВведём, далее, величиныρБ = min ρibEi ∈Би τБ = min τi ,bEi ∈Бкоторые назовём приведённым весом и приведённой задержкой базиса Б соответственно. Для стандартного базиса Б0 = {&, ∨, ¬}, очевидно,b 0 = {&, ∨},БρБ0 = τБ0 = 1.14Глава 1.bДля функционала сложности ψ типа L, L, D, T через ψ(Σ)будем обозначать величину ψБb (Σ).УС и UФ множество СФЭ над базисом Б,Следуя [3] обозначим через UCБ , UББмножество усилительных СФЭ над Б и множество формул над Б соответственно.При этом для каждого A, A ∈ {C, УС, Ф} определим размер LAБ (F ) ФАЛ илисистемы ФАЛ F в классе UAиеёзадержкуT(F)обычнымобразом,а через LAББ (n)Би TБ (n) обозначим соответствующие функции Шеннона.Лемма 2.1. Для любой формулы F, F ∈ UФБ , выполняются неравенстваR(F) 61 bL(F) + 1,ρБR(F) 6 2b(F)TτБ.(2.1)Доказательство.

Пусть для каждого i, i = 1, . . . , b, формула F содержит si ФЭ Ei .При этом для числа ребер квазидерева F будут выполняться равенства|E(F)| =bXsi · ki = R(F) +i=1bXsi − 1.i=1Следовательно,R(F) =bXsi (ki − 1) + 1 =i=1X ki − 11 X1 b· Li s i + 1 6Li s i + 1 =L(F) + 1LiρБρБki >2ki >2и первое неравенство (2.1) доказано.Второе неравенство (2.1) доказывается индукцией по D(F). Действительно,при D(F) = 0, когда F = xj , оно, очевидно, выполняется. Пусть теперь второе неравенство (2.1) верно для любой формулы глубины меньше, чем d, и пустьF = ϕi (F1 , . . . , Fki ), где D(F) = d и D(Fj ) < d, Tb(Fj ) = tj при всех j = 1, .

. . , ki .ТогдаkiXtR(F) =R(Fj ) 6 ki · 2 τБ ,j=1где t = max16j6ki tj . Следовательно, при ki = 1 формула F удовлетворяет второмунеравенству (2.1), так как в этом случае Tb(F) = t. При ki > 2 в соответствии сопределением τБ выполняется неравенствоTiki 6 2 τБ ,используя которое и учитывая, что в данном случае Tb(F) = t + Ti , получимtR(F) 6 ki · 2 τБ 6 2Лемма доказана.t+TiτБ=2b(F)TτБ.§2.15Замечание. Аналогично первому неравенству (2.1) доказывается, что число рёбердерева, соответствующего формуле F, в которой нет трёх и более последовательносоединённых одновходовых ФЭ, удовлетворяет неравенству|E(F)| 6 6(R(F) − 1).(2.2)Действительно, если F содержит si ФЭ Ei , i = 1, .

. . , b, тоR(F) =bXbsi (ki − 1) + 1 > L(F)+ 1,i=1b|E(F)| 6 3 R(F) + L(F)− 1 6 3(2R(F) − 2) = 6(R(F) − 1).Неравенство (2.2) выполняется, в частности, для строго приведённой формулы F.Для приведённой одновыходной СФЭ Σ на базисом Б её остовом будем называть такую формулу F(x1 ) над Б, дерево которой получается в результате применения к каждой вершине Σ операций отсоединения всех исходящих дуг, кромеодной, и объявления начальных вершин этих дуг листьями указанного дерева.ФФПусть для A ∈ {C, УС} UAБ hL, ni (UБ hL, ni, UБ {T, n}) — множество всех строгоприведённых схем из функциональных элементов вида Σ(x1 , .

. . , xn ; z1 ) из UAБ (соответственно формул F(x1 , . . . , xn )) из UФ,длякоторыхL(Σ)6L(соответственноБL(F) 6 L, T (F) 6 T ).Лемма 2.2. Для любых L > 0, T > 0 и любого натурального n справедливынеравенства1 :1 CUБ hL, ni 6 (c1 (L + n)) ρБ L+1 ,1 ФUБ hL, ni 6 (c2 n) ρБ L+1 ,T ФUБ {T, n} 6 (c2 n)2 τБ .(2.3)(2.4)(2.5)Доказательство. Пусть Σ ∈ UC hL, ni, a F̌ — остов Σ. В силу леммы 2.1 и замечания к ней число рёбер в дереве формулы F̌ не больше, чем bc1 L, где bc1 = ρ6Б , аL/ρчисло таких попарно не изоморфных формул не превосходит c2 Б , где c2 6 46 .Любая формула F (СФЭ Σ) из UC hL, ni может быть получена в результате присоединения каждого из R(F̌) 6 ρ1Б L(F̌) + 1 (в силу леммы 2.1) листьев дереваформулы F̌, являющейся её остовом, к входам x1 , . . .

, xn (соответственно к входамx1 , . . . , xn и внутренним вершинам F̌), которое можно осуществить не более, чемnR(F̌) (соответственно (bc1 · L + n)R(F̌) ) способами. Перемножая полученные оценкии учитывая (2.1) приходим к (2.3) с константой c1 = c2 max{bc1 , 1} и (2.4).1Буквой c с различными индексами будем обозначать константы, зависящие только от базиса Б16Глава 1.В случае Σ = F ∈ UФБ {T, n}, рассуждая аналогично, приходим к (2.5) с учётомтого, что число рёбер в формуле F̌ не больше, чем 6 · 2T /τБ , число таких формулT /τне превосходит (c2 )2 Б , а их ранг ограничен сверху в силу (2.1) числом 2T /τБ .Лемма доказана.Лемма 2.3.

Для любого L > 0 и любого натурального n выполняется неравенство УСUБ hL, ni 6c3 (L + n)log(L + n)1 b(L+n)+1ρБ.(2.6)Доказательство. На основе рассуждений из доказательства леммы 2.2 и с учетомb(2.1)–(2.3) можно показать, что число СФЭ Σ, Σ ∈ UУСБ hL, ni, для которых L(Σ) =b не больше, чем= L,LρБc21b +n(L − L)c4bL+1ρБ Lb +1b + n ρБ ,L−L6 cL5где c4 — минимальный «вес» одновходовых ФЭ базиса Б.

Отсюда следует, чтоbL УСb + n) ρБ +1 .UБ hL, ni 6 cLmax(L−L6bL∈[0,L]Находя максимум правой части полученного неравенства как функции параметb принимающего значения из действительного отрезка [0, L], с помощью лемра L,мы 1.2, гдеm=1(L + n) + 1,ρБy=1b + n),(L − LρБa = m,τ = 1,α = 0,получим (2.6).Лемма доказана.Из лемм 2.2, 2.3 с помощью мощностного метода (см. (1.20) и (1.14’)) выводитсяследующая теорема.Теорема 2.1. Для натуральных n = 1, 2, . . . выполняются неравенства2nlog n − O(n)LC(n)>ρ1+,ББnn2n2 log n − O(1)УС1+,LБ (n) > ρБnn2n1LФ(n)>ρ1−O,ББlog nlog nTБ (n) > τБ (n − log log n) − O(1).(2.7)(2.8)(2.9)(2.10)§2.17Для базиса Б00 = {x1 · x2 , ¬x1 }, в котором L& = L¬ = 1 и T& = T¬ = 1, оценкилемм 2.2, 2.3 можно уточнить следующим образом.Лемма 2.4.

Для любого L > 0 и любого натурального n выполняются неравенства e n L+2 Ф4U(L,n),(2.11) Б006log n e (L + n) L+n+2 УС5.(2.12)UБ00 (L, n) 6log2 (L + n)Доказательство. Пусть F(x1 ) — остов какой-либо СФЭ (формулы) Σ, Σ ∈ UУС,иБ00пустьp = L1 (Σ) + 1,R(F) = R 6 −p + 2,а M , M 6 L − p + 2 (соответственно M 6 n), — число тех вершин Σ, от которыхпри переходе от Σ к F были отсоединены исходящие дуги. Разобьём множестволистьев дерева F на p групп, включив в i-ую группу, i = 1, . . . , p, все те ti , ti > 0,листьев, которые связаны цепочкой из ФЭ & с i-м ФЭ ¬, если i < p, и связаныаналогичным образом с выходом Σ, если i = p.Заметим, что число способов выбора остова F схемы (формулы) Σ не больше,чем 42L , и что выбор формулы F однозначно определяет описанное выше разбиениелистьев дерева F на группы.

Заметим также, что число тех попарно не эквивалентных схем (формул) Σ указанного вида, которые можно получить из одного и тогоже остова в результате соответствующего присоединения его листьев, не больше,чемnott1maxCM· . . . · CMp 616t1 +···+tp 6R(L−p+2 )3M t13M tp3M p6max.6 max· ... ·16t1 +···+tp 6R16p6L+2 L − p + 2t1tpСледовательно, в силу леммы 1.2, где a = 3n, τ = 1, α = 0, m = L + 2 и y = p,получим неравенствоL−p+2 3npe4 n L+2 FLmax6,UБ00 (L, n) 6 1616p6L+2 L − p + 2log nа при a = 3, τ = 2, α = 0, m = L + n + 2, y = n + p и с учётом числа способов выборатех вершин остова, от которых отсоединялись исходящие дуги, — неравенство3(n + p) · p L−p+2e5 (L + n) L+n+2 УСLmax6.UБ00 (L, n) 6 3216p6L+2L−p+2log2 (L + n)Лемма доказана.18Глава 1.Из леммы 2.4 на основе мощностных соображений выводится следующая теорема.Теорема 2.2.

Для натуральных n = 1, 2, . . . выполняются неравенства2nlog log n − O(1)ФLБ0 (n) > ρБ1+,0log nlog n3 log n − O(1)2n1+.LУС(n)>ρ0ББ0nn(2.13)(2.14)Замечание. Аналогичным образом, с учётом теоремы 2.1 для произвольного базиса Б устанавливаются следующие мощностные нижние оценки2næБ log log n − O(1)ФLБ (n) > ρБ1+,log nlog n2n(2 + æБ ) log n − O(1)УСLБ (n) > ρБ1+,nnгде æБ ∈ {0, 1} и æБ = 1 тогда и только тогда, когда все ФЭ Ei ∈ Б, для которыхρi = ρБ , реализуют либо только монотонные ЭК, либо только монотонные ЭД,либо только линейные ФАЛ.§3Универсальные системы ФАЛ и их построение на основе селекторных разбиений БПНапомним (см. [3]), что множество ФАЛ G называется дизъюнктивно-универсальным множеством (ДУМ) ФАЛ порядка m и ранга p, тогда и только тогда, когдаG ⊆ P2 (m) и для любой ФАЛ g, g ∈ P2 (m), найдутся функции g1 , .

. . , gp из G длякоторых g = g1 ∨ · · · ∨ gp .Обобщим понятие ДУМ ФАЛ следующим образом. Пусть ϕ(y1 , . . . , yp ) — существенная ФАЛ, то есть ФАЛ, существенно зависящая от всех своих БП. МножествоФАЛ G, G ∈ P2 (m), называется ϕ–универсальным множеством (ϕ–УМ) порядкаm, если любая ФАЛ g, g ∈ P2 (m), может быть представлена в видеg = ϕ(g1 , . . . , gp ),(3.1)где gi ∈ G при всех i, i = 1, .