Материалы для подготовки к экзамену прошлых лет, страница 8

, 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.5)Доказательство. Пусть π–схема Σ сложности L реализует ФАЛ f и состоит изконтактов K1 , . . . , KL , где Ki - контакт вида xσjii , i = 1, .

. . , L. Каждому наборуα = (α1 , . . . , αn ), α ∈ Nf , сопоставим цепь Cα из множества C(Σ), состоящую изконтактов вида 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 является единственным§5.

Теорема Храпченко35общим контактом цепи Cα и сечения Sβ . При этом пара (α, β) принадлежит соответствующему множеству Ri тогда и только тогда, когда наборы α и β являютсясоседними.Докажем теперь, что|Ri | 6 |Ni0 |и|Ri | 6 |Ni00 |(5.6)для всех i, i = 1, . . . , L. Для этого достаточно доказать, что для любых двух различных пар (α, β) и (γ, δ) из Ri выполнены соотношения: α 6= γ и β 6= δ. Действительно, наборы α и β, а также наборы γ и δ являются соседними по БП xji ипоэтому в случае α = γ или β = δ было бы выполнено равенство (α, β) = (γ, δ),которое противоречит выборц данных пар.Из определения и свойств введенных выше множеств, а также неравенств (5.6)и неравенства Коши-Буняковского!2mmX1 X2ai >|ai |mi=1i=1следует, что|N0 | · |N00 | = |Π| =LXi=1|Πi | =LX|Ni0 | · |Ni00 | >i=1LXi=11|Ri |2 >LLXi=1!|Ri |>1 2|R|LТаким образом,L>|R|2.|N0 | · |N00 |Теорема доказана.Теорема 5.2.

При n > 1 для линейной ФАЛ lnσ , σ ∈ {0, 1}, выполнены неравенстваn2 6 Lπ (lnσ ) 6 4n2Доказательство. Требуемая нижняя оценка вытекает из (5.5) при 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)36Глава 2. Синтез схем для индивидуальных функцийи¯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 .Теорема доказана.Напомним (см. [2, §3,4]), что любой π–схеме Σ можно сопоставить эквивалентную формулу F с поднятыми отрицаниями из класса UФ , для которой R(F) = L(Σ),и что при поднятии отрицаний ранг формулы не изменится. Следовательно,RФ (lnσ ) > n2и, в соответствии со следствием 3 из леммы 1.1 работы [2],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] Ложкин С.А. Лекции по основам кибернетики. М.: МГУ, 2004.[3] Лупанов О.Б. Асимптотические оценки сложности управляющих систем. М.:МГУ, 1984.[4] Нигматулин Р. Г. Сложность булевых функций. М.: Наука, 1991.[5] Яблонский С.В. Об алгоритмических трудностях синтеза минимальных контактных схем. Проблемы кибернетики, вып. 2. - М.:Физматгиз, 1959. С. 75-121(См. также Избранные труды С.В. Яблонского. М.: МАКС Пресс, 2004.).[6] Яблонский С.В. Надежность управляющих систем.

М.: Изд-во МГУ, 1991.[7] Андреев А.Е. О сложности реализации частичных булевых функций схемамииз функциональных элементов. Дискретная математика, т. 1 (1989), №4. С.36-45.[8] Кричевский Р.Е. О сложности параллельно-последовательных контактныхсхем, реализующих одну последовательность булевых функций. Проблемыкибернетики, вып. 12. М.: Наука, 1964. С. 45-55.[9] Ложкин С.А.

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

Математические вопросы кибернетики,вып. 6 М.: Наука, 1996. С. 189 - 214.[11] Ложкин С.А. О глубине функций алгебры логики в произвольном полномбазисе. Вестник МГУ. Математика. Механика, 1996, №2. С. 80-82.[12] Ложкин С.А, Кошкин М. А. О сложности реализации некоторых системфункций алгебры логики контактными многополюсниками.

ДАН СССР, т.298 (1988), №4. С. 807-811.3738Литература[13] Ложкин С.А. О минимальных -схемах для монотонных симметрическихфункций с порогом 2. Дискретная математика, т. 17 (2005), № 4, с. 108-110.[14] Ложкин С.А. О синтезе формул, сложность и глубина которых не превосходят асимптотически наилучших оценок высокой степени точности. Вестн.Моск.

ун-та. Сер. 1, математика, механика. 2007 № 3, с. 19-25.[15] Лупанов О.Б. Об одном подходе к синтезу управляющих систем -принципелокального кодирования. Проблемы кибернетики, вып. 14. М.: Наука, 1965.С. 31-110.[16] Марков А.А. Об инверсной сложности булевых функций. ДАН СССР, 1956,т. 111, №6. С. 1171 - 1174.[17] Мадатян Х.С. Полный тест для бесповторных контактных схем. Проблемыкибернетики, вып. 23. М.: Наука, 1970. С. 103-118.[18] Редькин Н.П. Надежность и диагностика схем.

М.: Изд-во МГУ, 1992.[19] Соловьев Н.А. Тесты (теория, построение, применение). Новосибирск: Наука,1978.[20] Шоломов Л.А. О реализации недоопределенных булевых функций схемамиих функциональных элементов. Проблемы кибернетики, вып. 21. М.: Наука,1969. С. 215 - 226..