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

. . , p. Заметим, что в случае ϕ(y1 , . . . , yp ) = y1 ∨ · · · ∨ ypпонятие ϕ–УМ совпадает с понятием ДУМ ранга p.Так же, как и ДУМ (см. [3]), будем строить ϕ–УМ порядка m на основе разбиения ∆ = (δ1 , . . . , δp ) единичного куба B m . Для каждого i, i = 1, . . . , p, в силусущественной зависимости ФАЛ ϕ от БП yi найдётся набор двоичных константαi,1 , . . . , αi,p такой, чтоϕ(αi,1 , . .

. , αi,i−1 , yi , αi,i+1 , . . . , αi,p ) = yi ⊕ αi,i .(3.2)§3. Универсальные системы ФАЛ19Обозначим через G(j) , j = 1, . . . , p, множество всех тех ФАЛ из P2 (m), которыепри любом i, 1 6 i 6 p и j 6= i, равны αi,j на множестве наборов δi , и пустьG = G(1) ∪ · · · ∪ G(p) .(3.3)Нетрудно убедиться в том, что равенство (3.1) имеет место для любой функции g,g ∈ P2 (m), если gi , i = 1, . . .

, p, — ФАЛ из G(i) , совпадающая на δi с ФАЛ g ⊕ αi,i .Действительно, для любого i, i = 1, . . . , p, и любого набора β, β ∈ δi , в силу (3.2),получим:ϕ(g1 (β), . . . , gp (β)) = ϕ(αi,1 , . . . , αi,i−1 , g(β) ⊕ αi,i , αi,i+1 , . . . , αi,p ) = g(β).Следовательно, множество G представляет собой ϕ–УМ порядка m, которое будемназывать стандартным ϕ–УМ, связанным с разбиением ∆.Приведём пример стандартного ϕ–УМ для функции ϕ(y1 , . . . , yp ) = y1 yt+1 ∨∨ y2 yt+2 ∨ · · · ∨ yt y2t , где p = 2t, связанного с разбиением куба B m на последовательные отрезки δ1 , .

. . , δp длины s1 , . . . , sp соответственно, где s1 + · · · + sp = 2m . Еслипри этом константы в (3.2) выбрать так, что αi,j = 1 только тогда, когда |i − j| = t,e порядка m будет иметь вид (3.3), гдето соответствующее стандартное ϕ–УМ G(j)G состоит из таких ФАЛ g, g ∈ P2 (m), для которых g(α) = 1 при α ∈ δi , если |i − j| = t, и g(α) = 0 на остальных отрезках δi , за исключением δj . Заметим,e имеет мощность t(2s0 + 2s00 ), если |s1 | = · · · = |st | = s0 ичто полученное ϕ–УМ Gst+1 = · · · = |s2t | = s00 , где t(s0 + s00 ) = 2m .Заметим также, что в указанном случае можно построить и более компактноеϕ–УМ порядка m для рассматриваемой функции ϕ.

Введём множество Ǧ, Ǧ ⊂00P2 (m), которое состоит из 2s функций, равных единице на множестве δ1 ∪ · · · ∪ δt ипринимающих одинаковые значения на наборах с одинаковыми номерами внутрикомпонент δt+1 , . . . , δ2t . Из определения множеств G(1) , . . .

, G(t) и того факта, чтопри 1 6 i 6 t выполнены тождестваϕ(0, . . . , 0, yi , 0, . . . , 0, 1, . . . , 1) ≡ yi ;| {z }tϕ(0, . . . , 0, 1, 0, . . . , 0, yt+1 , . . . , y2t ) ≡ yt+i ,| {z }ib = G(1) ∪· · ·∪G(t) ∪ Ǧ является ϕ–УМ мощности t·2s0 +2s00следует, что множество Gи что любые две ФАЛ из различных множеств G(i) , i = 1, .

. . , t, ортогональны.Определение. Разбиение D = (Y1 , . . . , Yd ) множества Y = {y1 , . . . , yp } называетсяселекторным разбиением БП функции ϕ(y1 , . . . , yp ) тогда и только тогда, когдадля всякого i, i = 1, . . . , d, и для любой переменной y ∈ Yi найдутся константыα1 , . . . , αd такие, что при подстановке α1 , . . . , αi−1 , αi+1 , . . . , αd вместо переменныхиз Y1 , . . . , Yi−1 , Yi+1 , . . . , Yd соответственно, выполняется равенство ϕ = y ⊕ αi .20Глава 1.Отметим, что если ϕ(y1 , .

. . , yp ) существенно зависит от всех своих БП, то тривиальное разбиение D, при котором Yi = {yi }, i = 1, . . . , p, является селекторным.Заметим также, что если функция ϕ симметрична по переменным yi , yj , то они немогут входить в одну и ту же компоненту селекторного разбиения. Отсюда следует,что у функции ϕ(y1 , . . . , yp ) = y1 ∨ · · · ∨ yp нет нетривиальных селекторных разбиений БП.

В то же время функция ϕ(y1 , . . . , yp ) = y1 yt+1 ∨ y2 yt+2 ∨ · · · ∨ yt y2t имеет селекторное разбиение с компонентами Y1 = {y1 }, . . . , Yt = {yt }, Yt+1 = {yt+1 , . . . , y2t }.Лемма 3.1. Пусть D = (Y1 , . . . , Yd ) селекторное разбиение множества переменных Y = {y1 , . . . , yp } ФАЛ ϕ(y1 , . . .

, yp ), где |Yi | = pi , i = 1, . . . , p, и пустьs1 , . . . , sd — чётные числа, удовлетворяющие условию s1 p1 + · · · + sd pd > 2m . Тогдасуществует ϕ–УМ G порядка m такое, что|G| 6 2s1 + · · · + 2sd ,~ 6 eA |G| + O(d · 2L (G)Am+s/2(3.4)),(3.5)где A ∈ {К, C}, s = max16i6d si и eК = 2, eC = 4.Доказательство. Будем считать, что для каждого j, j = 1, . . . , d, множество номеров БП из Yj составляет отрезок Ij = [aj , aj+1 ), где a1 = 1, ad+1 = p + 1 и|Ij | = aj+1 − aj = pj при любом j, j ∈ [1, d].

Данное предположение не ограничивает, очевидно, общность проводимых рассуждений. Рассмотрим сначала случай,когдаp1 s1 + · · · + pd sd = 2m .Пусть ∆ = (δ1 , . . . , δp ) — разбиение куба B m на последовательные отрезки длины s1 , . . . , s1 , . . . , sd , . . . , sd соответственно и пусть i–й отрезок ∆, i = 1, . . . , p,| {z }| {z }p1pdсвязан с БП yi ФАЛ ϕ. При этом для каждого j, j = 1, . . . , d, отрезки длиныsj с номерами из Ij будут соответствовать БП из Yj .

Из селекторности разбиения D следует, что для каждого j, j = 1, . . . , d, и каждого i, i ∈ Ij , существуютконстанты αi,1 , . . . , αi,j−1 , αi,j+1 , . . . , αi,d при подстановке которых вместо БП изY1 , . . . , Yj−1 , Yj+1 , . . . , Yd соответственно ФАЛ ϕ переходит в ФАЛ вида yi ⊕ βi , гдеβi ∈ B.Определим (см. рис. 3.1) для каждого j, j = 1, .

. . , d, множество G(j) как множество всех тех ФАЛ из P2 (m), которые:1) принимают на любом отрезке δi , i ∈ ([1, p] \ Ij ), значение αi,j ;2) принимают одинаковые значения на любых двух наборах с одинаковыми«внутренними» номерами из различных отрезков ∆, соответствующих БПиз Yj .Заметим, что у любой ФАЛ из G(i) , i ∈ [1, d], те части столбца её значений которые соответствуют отрезкам разбиения ∆ с номерами из Ii и рассматриваются§3. Универсальные системы ФАЛ21Рис.

3.1: Таблица ФАЛ из ϕ–УМ Gкак наборы «высоты» si , совпадают между собой и что в качестве указанных наборов у различныхиз G(i) встречаются все 2si различных наборов. Отсюда (i) ФАЛsiследует, что G= 2 , так как на остальных отрезках разбиения ∆ все ФАЛ из(i)G ведут себя одинаково.Из построения следует, что множество (ср. с (3.3))G = G(1) ∪ · · · ∪ G(d)является ϕ–УМ порядка m. Действительно, для любой ФАЛ g, g ∈ P2 (m), справедливо представлениеg = ϕ(g1 , . .

. , gp ),где для каждого i, i = 1, . . . , d, и каждого j, j ∈ Ii , в качестве ФАЛ gj берётся таФАЛ из G(i) , которая совпадает с ФАЛ g ⊕ βj на отрезке δj . Кроме того, множествоG удовлетворяет (3.4), так как|G| 6dX|G(i) | 6 2s1 + · · · + 2sd .i=1Убедимся в том, что множество G удовлетворяет (3.5), то есть является искомым ϕ–УМ порядка m. Для каждого i, i = 1, . .

. , d, и каждого σ, σ ∈ B, рассмотрим22Глава 1.(i)(i)множество ФАЛ Gσ , Gσ ⊆ P2 (m − 1), которые состоят из всех различных ФАЛ,получающихся из ФАЛ множества G(i) в результате подстановки константы σ вме(i)(i)сто БП xm . При этом из чётности чисел s1 , . . . , si вытекает, что G0 = G1 и что (i) (i) G = G 6 2si /2 . Следовательно, для каждого A, A ∈ {C, К}, и каждого i,01→−(A)i ∈ [1, d], сложность схемы Σi из UA , построенной для системы ФАЛ G (i) по методу каскадов (см. [3]) с разложением реализуемых ФАЛ по БП xm , xm−1 , . .

. , x1удовлетворяет неравенству(A)L(Σi ) 6 eA · G(i) + O(2m+si /2 ).Суммируя данные неравенства для всех i, i = 1, . . . , d, получим (3.5).Осталось рассмотреть случай, когдаh = p1 s1 + · · · + pd sd > 2m .Положим q = dlog he и рассмотрим в кубе B q от набора БП xb = (u1 , . . . , ut , x1 , . . . , xm ),где t = q − m > 0, отрезок I, состоящий из первых h наборов этого куба.

Построиммножество ФАЛ G, G ⊆ P2 (bx), так же, как строилось множество G в предыдущемслучае, полагая, что все рассматриваемые ФАЛ от БП xb равны 0 вне отрезка I.При этом множество G будет обладать свойством ϕ–универсальности на отрезкеI, то есть любая ФАЛ g, g ∈ P2 (bx), будет совпадать на I с некоторыой ФАЛ видаϕ(g1 , . . . , gp ), где gj ∈ G при всех j, j ∈ [1, p]. Следовательно, множество G, котоb при подстановке константы 0 вместо БП u1 , . . . , ut ,рое получается из множества Gявляется ϕ–УМ порядка m и удовлетворяет (3.4), (3.5).Лемма доказана.Замечание 1. В условии леммы 3.1 допустимо равенство si = 0, которое означает,что построенное при доказательстве множество Ii пусто, а множество G(i) состоитиз одной ФАЛ, принимающей на каждой из непустых полос δj , 1 6 j 6 p, постоянные значения.Замечание 2.

Построенное в начале §3 для ФАЛ ϕ(y1 , . . . , y2t ) = y1 yt+1 ∨ · · · ∨b является частным случаем ϕ–УМ G = G(1) ∪ · · · ∪yt y2t «компактное» ϕ-УМ G,G(t+1) , полученного по лемме 3.1 для этой же ФАЛ на основе указанного ранееселекторного разбиения D = ({y1 }, . . . , {yt }, {yt+1 , . . . , y2t }) её БП, гдеs1 = · · · = st = s0 ,st+1 = s00 ,G(t+1) = Ǧ и t(s0 + s00 ) > 2m .Определение. Энтропией разбиения D, D = (Y1 , . . .