С.А. Ложкин - Элементы теории синтеза дискретных управляющих систем (1160764), страница 5
Текст из файла (страница 5)
. . , xji,t,(5.10)где gi,r ∈ G(r) , m + 1 6 ji,r 6 q и τi,r ∈ B при всех r, r = 1, . . . , t, причём τi,1 = . . . = τi,t = 1,если δi — «хорошая» компонента.Полагая, как и раньше, x00 = (xq+1 , . . . , xn ), разложим реализуемую ФАЛ f (x0 , x00 ) следующим образомf (x0 , x00 ) =q−m2_i=1x (x0 )i_Kσ00 (x00 ) · fσ00 ,i (x0 ) ,(5.11)σ 00 ∈B n−qгде x (x0 ) — характеристическая ФАЛ компоненты δi , i = 1, . . . , 2t , а ФАЛ fσ00 ,i (x0 ), σ 00 ∈ B n−q ,iимеет вид правой части равенства (5.10) для ФАЛ fσ00 (x0 ) = f (x0 , σ 00 ).−b и Ǩ, реализует систему ФАЛ →G наПусть (1, λ)-КС ΣG , построенная из контактов Kоснове совершенных ДНФ входящих в неё ФАЛ с использованием контактного дерева отБП (x, .
. . , xm ) со сложностьюb + Ľ · 2m .L ΣG 6 L(5.12)Пусть, далее, для каждого i, i = 1, . . . , 2q−m , (1, 2n−q )-КС Σ0i содержит КС ΣG в качестве своей подсхемы и реализует каждую ФАЛ fσ00 ,i , σ 00 ∈ B n−q , на одном из своих выходовb t , если δi — «хорошая» компов соответствии с (5.10). Для этого используется либо КС Fb t заменой части контактов Kb контактами Ǩ, внента, либо КС, которая получается из Fостальных случаях. Заметим, что указанные схемы являются разделительными по входамна компоненте δi , что обеспечивает корректность применяемых операций суперпозиции наней.
Определим (1, 2n−m )-КС Σ0 как КС, которая получается отождествлением входов у всехКС Σ0i , i = 1, . . . , 2q−m , и реализует на своих 2n−m выходах все ФАЛ вида fσ00 ,i (x0 ).e которая получается из (2q , 1)-КД от БП x0 отождествРассмотрим теперь (2q−m , 1)-КС Σ,лением для каждого i, i = 1, . . . , 2q−m , тех его листьев, которые соответствуют конъюнкциямσвида xσ1 1 · . . . · xq q , где (σ1 , . . . , σq ) ∈ δi . Построим, наконец, (2n−m , 1)-КС Σ00 , которая получаe выхода (корня) (2n−q , 1)-контактногоется в результате присоединения к каждому входу КС Σдерева от БП x00 .
Заметим, что все операции суперпозиции, использованные при построении КС Σ00 , являются корректными и поэтому Σ00 разделительна по входам, а система ФАЛ20Глава 1.проводимости между её входами и выходом состоит из всех ФАЛ видаx (x0 ) · Kσ00(x00 ),iгде i ∈ [1, 2q−m ] и σ 00 ∈ B n−q .Искомая КС Σf содержит КС Σ0 в качестве подсхемы и представляет собой результатсуперпозиции вида Σf = Σ00 (Σ0 ), при выполнении которой входы Σ00 присоединяются квыходам Σ0 в соответствии с (5.11). В силу разделительности КС Σ00 по входам указаннаясуперпозиция является корректной и поэтому КС Σf действительно реализует ФАЛ f .Из (5.7)–(5.9) и (5.12) с учётом того, что число контактов в контактном дереве от d БПравно 2d+1 − 2, вытекает неравенство (ср.
с (5.5))b · 2n−m · t + O 2q + 2n−m 1 + t · λ .L Σf 6 L2aОценка (5.6) получается из последнего неравенства при следующих значениях параметров√ 3log n ,s = n − 3a n ,a = blog nc ,m=2при которых, начиная с достаточно большого n, выполнены все необходимые соотношенияи, в частности, неравенства (5.9).Теорема доказана.Следствие. Из (5.6) с учётом нижней оценки §3 вытекает соотношениеLКБ (n) ∼ πБ2n.nЛитература[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.2122Литература[13] Ложкин С. А. О глубине функций алгебры логики в произвольном полном базисе.Вестник МГУ. Математика. Механика, 1996, №2. С. 80-82.[14] Ложкин С. А., Кошкин М. А. О сложности реализации некоторых систем функцийалгебры логики контактными многополюсниками. ДАН СССР, т. 298 (1988), №4. С.807-811.[15] Шоломов Л.
А. О реализации недоопределенных булевых функций схемами их функциональных элементов. Проблемы кибернетики, вып. 21. М.: Наука, 1969. С. 215 226.[16] Shannon C. E. The synthesis of two-terminal switching circuits // Bell System TechnicalJournal. — Vol. 28, No.
1. — 1949. — P. 59–98. (Русский перевод: Шеннон К. Синтез двухполюсных переключательных схем // Работы по теории информации и кибернетике. —М: ИЛ, 1963. — С. 59–105.).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
