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

. . , δp ) — разбиение куба B n от БП x = (x1 , . . . , xn ). Определиммультиплексорную ФАЛ µ∆ , соответствующую разбиению ∆, равенствомµ∆ (x, u1 , . . . , up ) =p_i=1xδi(x)ui ,(7.1)38гдеГлава 1.xδi— характеристическая ФАЛ компоненты δi . Тогда стандартную мульти-плексорную ФАЛ порядка nµn (x, u0 , . . . , u2n −1 ) =_Kσ (x)uν(σ)σ=(σ1 ,...,σn(7.2))∈B nможно рассматривать как обобщённую мультиплексорную ФАЛ µ∆ с тривиальнымразбиением ∆ таким, что δν(σ) = {σ} для каждого σ, σ ∈ B n .Напомним, что БП x1 , .

. . , xn считаются адресными БП указанных выше мультиплексорных ФАЛ, а БП u1 , . . . , up и u0 , . . . , u2n −1 называются информационнымиБП ФАЛ µ∆ и µn соответственно. С содержательной точки зрения поведение мультиплексорной ФАЛ µ∆ определяется тем, что на любом наборе значений адресныхБП из компоненты δi , i ∈ [1, p], она совпадает с информационной БП ui .Заметим, что правые части равенств (7.1) и (7.2) представляют собой результат суперпозиции, внешней ФАЛ, которой является дизъюнкция вида y1 ∨ · · · ∨ yp иy0 ∨ · · · ∨ y2n −1 соответственно, а каждая внутренняя ФАЛ этой суперпозиции зависит от адресных БП и не более, чем от одной, из информационных БП.

Обобщимуказанные представления на тот случай, когда в качестве внешней ФАЛ используется, вообще говоря, произвольная ФАЛ от достаточно большого числа БП.Лемма 7.1. Для любой существенной ФАЛ ϕ(y1 , . . . , yp ) и любого разбиения ∆ == (δ1 , . . . , δp ) куба B n от БП x = (x1 , . . . , xn ) существуют ФАЛ gi (x, ui ), i =1, . . . , p, которые монотонно или антимонотонно зависят от БП u1 , . .

. , up , идля которыхµ∆ (x, y1 , . . . , yp ) = ϕ(g1 , . . . , gp ).(7.3)Доказательство. Существенность ФАЛ ϕ означает, что для любого i, i = 1, . . . , p,найдутся булевские константы αi,1 , . . . , αi,p такие, что (ср. с. (3.2))ϕ(αi,1 , . . . , αi,i−1 , yi , αi,i+1 , . . . , αi,p ) = yi ⊕ αi,i .Значит, определив ФАЛ gi так, что(αi,j ,если β ∈ δi при j 6= i;gj (β, uj ) =yj ⊕ αj,j , если β ∈ δj ;(7.4)для произвольного набора β, β ∈ δi , будем иметьϕ(g1 (β, y1 ), . . . , gi−1 (β, yi−1 ), gi (β, yi ), gi+1 (β, yi+1 ), . . .

, gp (β, yp )) == ϕ(αi,1 , . . . , αi,i−1 , yi ⊕ αi,i , αi,i+1 , . . . , αi,p ) = (yi ⊕ αi,i ) ⊕ αi,i = yi == µ∆ (β, y1 , . . . , yp ). (7.5)Из (7.4) следует, что каждая ФАЛ gj зависит от БП uj только на компоненте δj ,на которой gj = uj ⊕ αj,j . Следовательно, каждая ФАЛ gj либо монотонно, либоантимонотонно зависит от БП uj .Лемма доказана.§7. Мультиплексорные ФАЛ и обобщённое разложение39Замечание.

Лемма 7.1 остаётся справедливой и в том случае, когда число компонент разбиения ∆ равно t и t < p, если при этом формально считать все недостающие компоненты δt+1 , . . . , δp разбиения ∆ пустыми, а соответствующие им информационные БП ud+1 , . . . , up — фиктивными БП ФАЛ gt+1 , . . . , gp , µ∆ .В дальнейшем представление (7.3) мультиплексорной ФАЛ µ∆ будем называтьеё ϕ–разложением или, иначе, обобщенным разложением µ∆ с внешней ФАЛ ϕ.При этом ФАЛ системы (g1 , . . .

, gp ) будем считать внутренними ФАЛ указанногоразложения, а все различные ФАЛ вида gj (x, σ), где j ∈ [1, p], и σ ∈ B, — еговспомогательными ФАЛ. Так ФАЛ вида x (x) · ui , i ∈ [1, p], и Kσ (x) · uν(σ) , σ ∈ B n ,iявляются внутренними ФАЛ разложений (7.1) и (7.2) соответственно, а ФАЛ видаx (x), i ∈ [1, p], и 0 (вида Kσ (x), σ ∈ B n , и 0) — внутренними ФАЛ разложения (7.1)i(соответственно (7.2)).Заметим, что обобщённое разложение (7.3) стандартной мультиплексорнойФАЛ µn с внешней ФАЛ ϕ(y1 , . .

. , yp ), где p > 2n , можно использовать для соответствующего обобщённого разложения по БП x = (x1 , . . . , xn ) произвольнойФАЛ ψ(x, z), где z = (z1 , . . . , zm ), следующим образом:ψ(x, z) = ϕ(g0 (x, ψ(0̃, z)), . . . , g2n −1 (x, ψ(1̃, z)), g2n (x), . . . , gp−1 (x))Установим, далее, верхние оценки некоторых «мощностных» и «сложностных» характеристик внутренних и вспомогательных ФАЛ обобщённого разложения (7.3)в тех случаях, когда ФАЛ ϕ обладает определёнными свойствами и, в частности,когда она реализуется бесповторной формулой базиса Б.Отметим, сначала, что при n = m имеется явная связь между вспомогательными (внутренними) ФАЛ обобщённого разложения (7.3) и построенным в §3 наоснове разбиения ∆ «диагональным» ϕ–УМ G порядка m, которое имеет вид G =G(1) ∪ · · · ∪ G(p) .

Действительно, если и в том и в другом случае используется одини тот же набор констант αi,j — констант существенной зависимости ФАЛ ϕ отеё БП, — то в силу (3.2), (3.3), (7.3), (7.4) ФАЛ gj (x, 1) и gj (x, 0), где j ∈ [1, p],являются единственным максимальным и единственным минимальным элементами частично упорядоченного отношением «поразрядного» сравнения 6 множестваФАЛ G(j) соответственно.Аналогичное соответствие сохраняется и тогда, когда ϕ–УМ G порядка m строится для (произвольного) разбиения ∆ = (δ1 , . .

. , δp ) на базе селекторного разбиения ∆ БП ФАЛ ϕ(y1 , . . . , yp ) (см. доказательство леммы 3.1). При этом построениеуказанного множества G возможно и в тех случаях, когда условия леммы 3.1, связанные с чётностью мощностей компонент разбиения ∆, а также с совпадениеммощностей тех компонент ∆, которые соответствуют БП из одной и той же компоненты разбиения ∆, не выполняются.

С учётом вышесказанного из доказательствалеммы 3.1 вытекает справедливость следующего утверждения.40Глава 1.Лемма 7.2. Пусть в условиях леммы 7.1 ФАЛ ϕ имеет селекторное разбиение множества своих БП на d компонент. Тогда внутренние ФАЛ ϕ–разложения (7.3) ФАЛ µ∆ можно выбрать так, что число различных вспомогательных ФАЛ этого разложения будет не больше, чем 2d.Назовём альтернированием набора α, α = (α1 , . . .

, αn ), число изменений значений αi в нём, при их просмотре в порядке возрастания номера i, i = 1, . . . , n, иобозначим это число через alt (α). Другими словамиalt (α) =n−1X(αi ⊕ αi+1 ).i=1Альтернирование набора равно минимальному числу отрезков постоянства, на которые он распадается, уменьшенному на единицу. Определим альтернированиеФАЛ f как альтернированию столбца её значений и обозначим эту величину через alt (f ).

Назовём ФАЛ h ступенчатой, если alt (h) 6 1. Нетрудно видеть, чтоступечантая ФАЛ является либо монотонной, либо антимонотонной ФАЛ. Функцию hi , hi ∈ P2 (n), назовём i-ой ступенчатой ФАЛ (0 6 i 6 2n ), если для всякого β, β ∈ B n ,(0, при ν(β) < i;hi (β) =1, при ν(β) > i.Лемма 7.3. При n > 2 глубина в базисе Б0 любой ФАЛ g, g ∈ P2 (n), удовлетворяет неравенствуD(g) 6 2 dlog ne + dlog(alt (g) + 1)e .(7.6)Доказательство. Если alt (g) = 0, то есть ФАЛ g — константа, то неравенство (7.6)выполняется, поскольку любую константу можно реализовать одной из формулвида x1 ∨ x1 , x1 · x1 , которые имеют глубину 2.Индукцией по k, k > 1 докажем, что при любом n, n ∈ [2, 2k ] и любом i, i ∈[1, 2n ), выполняется неравенствоD(hi (x1 , . .

. , xn )) 6 2 dlog ne − 1.(7.7)Базис индукции составляет случай k = 1, в котором h1 (x1 , x2 ) = x1 ∨x2 , h2 (x1 , x2 ) =x1 , h3 (x1 , x2 ) = x1 · x2 , и, следовательно, неравенство (7.7) справедливо.Пусть для некоторого натурального k неравенство (7.7) выполняется при любом n0 , n0 ∈ (2k−1 , 2k ], и любом i0 , i ∈ [1, 2n ). Для обоснования индуктивного перехода достаточно доказать (7.7) для любого n, n ∈ (2k , 2k+1 ], то есть для любого n,удовлетворяющего соотношению dlog ne = k + 1, и любого i, i ∈ [1, 2n ).Рассмотрим ФАЛ hi , hi ∈ P2 (n), как ФАЛ, зависящую от всех 2k+1БП x1 , .

. . , x2k+1 (при n < 2k+1 от последних БП зависимость фиктивная), и обозначим x = (x1 , . . . , x2k ), x00 = (x2k +1 , . . . , x2k+1 ). Представим число i, 1 6 i 6 2n − 1 6k+122− 1, в видеki = 22 i0 + i00 ,§7. Мультиплексорные ФАЛ и обобщённое разложение41kгде 0 6 i0 , i00 6 22 − 1, причём i0 и i00 не равны нулю одновременно. Заметим, чтопри этомhi (x0 , x00 ) = hi+1 (x0 ) ∨ Ki+0 (x0 ) · hi00 (x00 ),(7.8)где K0+ ≡ 1 и Ki+0 (x0 ) — конъюнкция тех БП набора x0 , которым в наборе ν −1 (i0 )значений этих БП соответствуют единицы, если i0 > 0.kПусть i0 ∈ (0, 22 − 1), i00 6= 0 и пусть формулы Fi0 +1 (x0 ), Fi00 (x00 ) построены поиндуктивному предположению для ФАЛ hi0 +1 (x0 ), hi00 (x00 ) соответственно, а фор+ 00мула K+i0 (x ) реализует ЭК Ki0 (x ) на основе двоичного дерева глубины не больше,чем k, состоящего из ФЭ &.

Тогда в силу (7.8) формула00000Fi (x0 , x00 ) = Fi0 +1 (x0 ) ∨ K+i0 (x ) · Fi (x )реализует ФАЛ hi (x0 , x00 ) с глубинойD(Fi ) 6 max{2k − 1, max{k, 2k − 1} + 1} + 1 6 2(k + 1) − 1,удовлетворяющей (7.7).В остальных случаях, используя введённые выше обозначения, определим искомую формулу Fi , удовлетворяющую (7.7), следующим образом:000если i0 = 0;F1 (x ) ∨ Fi00 (x ),kFi = x1 · . . . · x2k · Fi00 (x00 ), если i0 = 22 − 1 и i00 > 0;Fi0 (x0 ),если i00 = 0.Неравенство (7.7), таким образом, полностью доказано.Заметим, что альтернирование 1 и 2 в P2 (n) имеют только ФАЛ вида hi , hi ,где i ∈ (0, 2n ), и ФАЛ вида hi ∨ hj , hi · hj , где 0 < i < j < 2n соответственно.Следовательно, в силу (7.7) для любой ФАЛ g, g ∈ P2 (n), такой, что 1 6 alt (g) 6 2,справедливо неравенствоD(g) 6 2 dlog ne + dlog(alt (g))e ,(7.9)из которого для указанной ФАЛ g вытекает (7.6).

Заметим также, что приведённыевыше ФАЛ hi ·hj и hi ∨hj являются характеристической ФАЛ отрезка [i, j) куба B nи её отрицанием соответственно.Пусть, далее, g — произвольная ФАЛ из P2 (n) и пусть alt (g) = g > 3. Из определений следует, что куб B n разбивается на последовательные отрезки «постоянства»ФАЛ g, то есть отрезки I0 , I1 , . .

. , Iq такие, что ФАЛ g равна g(0, . . . , 0) + i (mod 2)на отрезке Ii , i ∈ [0, q]. При этом ФАЛ g представляет собой дизъюнкцию характеристических ФАЛ t, t = b(q + 1)/2c > 2, «нечётных» отрезков её постоянства I1 , I3 , . . . , I2t−1 , если g(0, . . . , 0) = 0, и конъюнкцию отрицаний этих ФАЛ,если g(0, .

. . , 0) = 1.42Глава 1.Следовательно, формула Fg , которая реализует ФАЛ g, g(0, . . . , 0) = σ, с глубиной, удовлетворяющей (7.6), получается в результате подстановки t удовлетворяющих (7.9) формул для σ–степеней характеристических ФАЛ отрезков I1 , . . . , I2t−1вместо t БП бесповторной формулы, дерево которой представляет собой квазиполное двоичное дерево глубины dlog te из ФЭ &, если σ = 1, и ФЭ ∨, если σ = 0.Действительно,D(Fg ) 6 2 dlog ne + 1 + dlog te == 2 dlog ne + dlog(2 b(q + 1)/2c)e 6 2 dlog ne + dlog(q + 1)e .Лемма доказана.§8Задача синтеза схем для функций из специальных классов,примеры её решения и мощностные нижние оценки. Инвариантные классы С. В.

Яблонского, теорема о числе инвариантных классовДля множества ФАЛ Q, Q ⊆ P2 , и натуральногого n через Q(n) будем обозначатьмножество Q∩P2 (n). При этом, как само множество Q, так и связанную с ним последовательность Q(1), Q(2), . . . будем называть классом ФАЛ. Аналогичным образомпоследовательность Q(1), . . . , Q(n), . . . , где Q(n) ⊆ P2m (n) и m = mQ (n), а такжеих объединение называется классом операторов. Будем предполагать, что ни одноиз множеств Q(n), n = 1, 2, . . . , рассматриваемого класса ФАЛ или операторов Qне является пустым и, как правило, |Q(n)| > 3.Пусть заданы класс ФАЛ или операторов Q, класс схем U и функционал сложности L.