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

Сложность линейной функции в классеπ–схемПод контактной схемой (КС) в данном параграфе будем понимать (1, 1)–КС изнеориентированных контактов. Для множества C, состоящего из t контактов видаxσj11 , . . . , xσjtt , положимK(C) = xσj11 · . . . · xσjtt ,J(C) = xσj11 ∨ . . . ∨ xσjtt .Для КС Σ, реализующей ФАЛ f из P2 (n), через C(Σ) будем обозначать множество проводящих простых цепей Σ, соединяющих её полюса, а через S(Σ) —множество отделимых тупиковых сечений Σ, разделяющих её полюса (см.

[3,§5 гл. 2]). При этом каждому набору α = (α1 , . . . , αn ) из Nf соответствует цепь C,C ∈ C(Σ), состоящая из проводящих на наборе α контактов вида xα1 1 , . . . , xαnn , анабору β = (β1 , . . . , βn ) из N f = B n \ Nf — сечение S, S ∈ S(Σ), состоящее из разоββмкнутых на наборе β контактов вида x1 1 , . . . , xnn . Заметим, что множество S ∩ C,то есть множество общих для S и C контактов не пусто и состоит из контактоввида xαi i , где αi = βi .72Глава 2.Результат последовательного (параллельного) соединения КС Σ1 и Σ2 будемобозначать через Σ1 · Σ2 (соответственно Σ1 k Σ2 ). Назовём простейшей π–схемойлюбую КС, состоящую из одного контакта, а затем индукцией по сложности определим π–схему Σ как КС вида Σ1 · Σ2 или Σ1 k Σ2 , где Σ1 , Σ2 — π–схемы.Лемма 5.1.

Для π–схемы Σ любая цепь C, C ∈ C(Σ), и любое сечение S, S ∈ S(Σ)имеют ровно один общий контакт.Доказательство. Проведём индукцию по стороению π–схемы Σ. В случае, когда Σ — простейшая π–схема, состоящая из одного контакта, утверждение леммы,очевидно, выполняется. Докажем справедливость индуктивного перехода.Отметим, сначала, что для произвольных КС Σ1 и Σ2 выполняются равенства:C(Σ1 · Σ2 ) = { C | C = C1 · C2 , где K(C) 6= 0 и Ci ∈ C(Σi ), i = 1, 2 },S(Σ1 · Σ2 ) = S(Σ1 ) ∪ S(Σ2 ),C(Σ1 k Σ2 ) = C(Σ1 ) ∪ C(Σ2 )S(Σ1 k Σ2 ) = { S | S = S1 ∪ S2 , где J(S) 6= 1 и Si ∈ S(Σi ), i = 1, 2 }.(5.1)(5.2)Действительно, любая цепь C из C(Σ1 · Σ2 ) имеет вид C = C1 · C2 , где Ci ∈ C(Σi ),i = 1, 2, и K(C1 ) · K(C2 ) 6= 0, а любое сечение S из S(Σ1 · Σ2 ) совпадает либо снекоторым сечением S1 из S(Σ1 ), либо с некоторым сечением S2 из S(Σ2 ).Заметим, что при этомC ∩ S = Ci ∩ Si ,где S = Si , и, следовательно, если КС Σ1 , Σ2 являются π–схемами, удовлетворяющими условиям леммы, то π–схема Σ1 · Σ2 тоже будет им удовлетворять.

Аналогичным образом доказываются равенства (5.1), (5.2), и устанавливается справедливость индуктивного перехода в случае π–схемы вида Σ1 k Σ2 .Лемма доказана.Для пересекающихся подмножеств N0 и N00 множества B n обозначим через R(N0 , N00 ) множество всех пар (α, β), состоящих из соседних по какой-либоБП x1 , . . .

, xn наборов α и β куба B n таких, что α ∈ N0 и β ∈ N00 . Пусть, какобычно, Uπ — класс π–схем и, в соответствии с общими правилами §1, Lπ (f ) —сложность реализации ФАЛ f в классе Uπ .Теорема 5.1. Для любой ФАЛ f из P2 (n) и любых множеств N0 , N00 таких,что N0 ⊆ Nf и N00 ⊆ N f , справедливо неравенство:Lπ (f ) >|R(N0 , N00 )|2|N0 | · |N00 |(5.3)Доказательство. Пусть π–схема Σ сложности L реализует ФАЛ f и состоит изконтактов K1 , . . . , KL , где Ki — контакт вида xσjii , i = 1, . .

. , L. Каждому набору α = (α1 , . . . , αn ), α ∈ Nf , сопоставим цепь Cα из множества C(Σ), состоящую из§5. Теорема Храпченко73контактов вида xα1 1 , . . . , xαnn , а каждому набору β = (β1 , . . . , βn ), β ∈ N f , — сечение Sβ из множества S(Σ), состоящее из контактов вида xβ1 1 , . . . , xβnn . При этом всоответствии с леммой 5.1 множество Cα ∩ Sβ состоит из одного контакта вида xαs s ,где αs 6= βs . Рассмотрим следующие множества:Π = N0 × N00 ,R = R(N0 , N00 ),Ni0 = { α ∈ N0 | Sα 3 Ki },Ni00 = { β ∈ N00 | Sβ 3 Ki },Πi = Ni0 × Ni00 ,Ri = R ∩ Πi ,где i = 1, . . .

, L. Заметим, что при i 6= j множества Πi и Πj (Ri и Rj ) не пересекаются, а объединение всех таких множеств равно множеству Π (соответственно R).Действительно, любая пара (α, β) из Π принадлежит тому и только тому из множеств Ni0 × Ni00 , 1 6 i 6 L, для которого контакт Ki является единственным общимконтактом цепи Cα и сечения Sβ . При этом пара (α, β) принадлежит соответствующему множеству Ri тогда и только тогда, когда наборы α и β являются соседними.Докажем теперь, что|Ri | 6 |Ni0 | и |Ri | 6 |Ni00 |(5.4)для всех i, i = 1, . .

. , L. Для этого достаточно доказать, что для любых двух различных пар (α, β) и (γ, δ) из Ri выполнены соотношения: α 6= γ и β 6= δ. Действительно, наборы α и β, а также наборы γ и δ являются соседними по БП xji ипоэтому в случае α = γ или β = δ было бы выполнено равенство (α, β) = (γ, δ),которое противоречит выборц данных пар.Из определения и свойств введённых выше множеств, а также неравенств (5.4)и неравенства Коши-Буняковскогоm2mX1 X2ai >|ai |mi=1i=1следует, что000|N | · |N | = |Π| =LXi=1|Πi | =LX|Ni0 |i=1·|Ni00 |>LXi=1 L1 X1|Ri | > |R|2 .|Ri | >LL2i=1Таким образом,L>|R|2.|N0 | · |N00 |Теорема доказана.Теорема 5.2.

При n > 1 для линейной ФАЛ lnσ , σ ∈ {0, 1}, выполнены неравенстваn2 6 Lπ (lnσ ) 6 4n274Глава 2.Доказательство. Требуемая нижняя оценка вытекает из (5.3) при f = lnσ и N0 =Nf , N00 = N f так как в данном случае|N0 | = |N00 | = 2n−1 ,|R(N0 , N00 )| = n · 2n−1и поэтому Lπ (f ) > n2 .При получении верхней оценки рассмотрим случай n = 2k , k = 1, 2, . .

. . Дляn = 2 искомые π–схемы Σ02 и Σ002 реализующие со сложностью 4 ФАЛ l2 и l2 соответственно, строятся на основе совершенных ДНФ. Пусть для n = 2k искомыеπ–схемы Σ0n и Σ00n , реализующие со солжностью n2 ФАЛ ln и ln уже построены. Тогда π–схемы Σ02n и Σ002n , реализующие со сложностью 4n2 ФАЛ l2n и l2n могут бытьпостроены на основе разложений:l2n (x, y) = ln (x) · ln (y) ∨ ln (x) · ln (y) и l2n (x, y) = ln (x) · ln (y) ∨ ln (x) · ln (y),где x = (x1 , . . . , xn ) и y = (xn+1 , . . . , x2n ).

Таким образом,Lπ (lnσ ) 6 n2 ,если n = 2k , k = 1, 2, . . . . В общем случае, когда 2k−1 < n 6 2k , для построенияπ–схем Σ0n и Σ00n , реализующих со сложностью не более, чем 4n2 , ФАЛ ln и lnсоответственно, достаточно взять построенные выше π–схемы Σ02k и Σ002k , а затемподставить константу 0 вместо всех БП xn+1 , . . .

, x2k .Теорема доказана.Напомним (см. [?, § 3, 4]), что любой π–схеме Σ можно сопоставить эквивалентную формулу F с поднятыми отрицаниями из класса UФ , для которой R(F) = L(Σ),и что при поднятии отрицаний ранг формулы не изменится. Следовательно,RФ (lnσ ) > n2и, в соответствии со следствием 3 из леммы 1.1 работы [?],T (lnσ ) = D(lnσ ) > ]2 log n[С другой стороны, формулы Fn0 и Fn00 с поднятыми отрицаниями, которые соответствуют π–схемам Σ0n и Σ00n , построенными при доказательстве теоремы 5.2,имеют глубину не более, чем (2 log n + 3), и потомуT (lnσ ) 6 2 log n + 3.Литература[1] Алексеев В. Б., Ложкин С.

А. Элементы теории графов, схем и автоматов.М.: Издательский отдел ф-та ВМиК МГУ, 2000.[2] Андреев А. Е. О сложности реализации частичных булевых функций схемами из функциональных элементов. Дискретная математика, т. 1 (1989), №4.С. 36-45.[3] Ложкин С. А.

Лекции по основам кибернетики. М.: МГУ, 2004[4] Лупанов О. Б. О сложности реализации функций алгебры логики релейноконтактными схемами // Проблемы кибернетики. Вып. 11. М.: Наука, 1964.С. 25–48.[5] Лупанов О. Б. Об одном подходе к синтезу управляющих систем — принципе локального кодирования. // Проблемы кибернетики. Вып. 14. М.: Наука,1965.

С. 31–110.[6] Лупанов О. Б. Асимптотические оценки сложности управляющих систем. М.:МГУ, 1984.[7] Нигматулин Р. Г. Сложность булевых функций. М.: Наука, 1991.[8] Яблонский С. В. Об алгоритмических трудностях синтеза минимальных контактных схем. Проблемы кибернетики, вып. 2. - М.:Физматгиз, 1959. С. 75-121(См. также Избранные труды С.В. Яблонского. М.: МАКС Пресс, 2004.).[9] Яблонский С.

В. Надежность управляющих систем. М.: Изд-во МГУ, 1991.[10] Кричевский Р. Е. О сложности параллельно-последовательных контактныхсхем, реализующих одну последовательность булевых функций. Проблемыкибернетики, вып. 12. М.: Наука, 1964. С. 45-55.[11] Ложкин С. А. Об одном методе получения нижних оценок сложности контактных схем и о некоторых минимальных схемах для линейных функций.Сб.

трудов семинара по дискретной математике и ее приложениям. М.: Издво механико-математического ф-та МГУ, 1997. С. 113-115.[12] Ложкин С. А. Оценки высокой степени точности для сложности управляющих систем из некоторых классов. Математические вопросы кибернетики,вып. 6 М.: Наука, 1996. С. 189 - 214.7576Литература[13] Ложкин С. А. О глубине функций алгебры логики в произвольном полномбазисе.

Вестник МГУ. Математика. Механика, 1996, №2. С. 80-82.[14] Ложкин С. А., Кошкин М. А. О сложности реализации некоторых системфункций алгебры логики контактными многополюсниками. ДАН СССР, т.298 (1988), №4. С. 807-811.[15] Шоломов Л. А. О реализации недоопределенных булевых функций схемамиих функциональных элементов. Проблемы кибернетики, вып. 21.

М.: Наука,1969. С. 215 - 226..