2 (1132838), страница 10
Текст из файла (страница 10)
в КС Σ(n)то есть наличие цепей вида Ii , соединяющих полюс72Введениеaj с полюсом ak и полюс ak с полюсом at (см. рис. 8.1a),влечет наличие цепи такого же вида, соединяющей полюс aj с полюсом at (см. рис. 8.1b).akakbΣbΣ(n)(n)IiIi(n)Iiaj(n)Iiajat(n)Ii=⇒ata)b)Рис. 8.1: к свойству 4 КС канонического видаЛемма 8.1. Для любой КС Σ, где Σ ∈ UK и Σ == Σ (x1 , . . .
, xn ; a1 , . . . , am ), и любой эквивалентной Σ КСb (x1 , . . . , xn ; a1 , . . . , am ) канонического вида существуетΣbЭП Σ ⇒ Σ.τnДоказательство. Построим ЭП видаbΣ ⇒ Σ1 ⇒ Σ2 ⇒ Σ3 ⇒ Σ4 = Σ,τnτnτnτnгде КС Σi , i = 1, 2, 3, 4, обладает отмеченными выше свойствами 1, . . . , i, отличающими канонические КС. Первое изэтих ЭП имеет видΣ ⇒ Σ1(n)t4и связано с применением к каждому контакту тождества(n)t4 .Существование ЭПΣ1nΣ2⇒(n)(n)(n)(n)(n)t6 , t11 , t9 , t3 , t1o(8.1)Введение73докажем индукцией по числу тех внутренних вершин КС Σ1 ,которые не являются внутренними вершинами ее канонических цепей. Базис индукции составляют схемы Σ1 , которыене имеют указанных вершин и для которых, следовательно,Σ2 = Σ1 . Пусть теперь КС Σ1 имеет хотя бы одну вершинууказанного вида и пусть v — одна из таких вершин.
Уда(n)лим с помощью тождества t6 все присоединенные к v «висячие» циклы и рассмотрим все остальные цепи C1 , . . . , Cq ,концевой вершиной которых она является (см. рис. 8.2a).Не ограничивая общности рассуждений, будем считать, чтодля некоторых натуральных чиселa1 = 1 < a2 < · · · < ap < ap+1 = q + 1и любого j, j ∈ [1, p], цепи Caj , .
. . , Caj+1 −1 являются цепя(n)ми типа Iij = Iij , где i1 , . . . , ip — различные числа отрезка[1, 2n ]. Применяя к каждой из этих p групп цепей одного ти(n)па тождество t11 , получим КС Σ01 , в которой из вершиныv выходит по одной цепи каждого типа Iij , j ∈ [1, p] (см.рис. 8.2b). Пусть, далее, КС Σ001 получается из КС Σ01 присо(n)единением к вершине v с помощью тождества t9 «висячих»цепей Cp+1 , . . .
, C2n всех отсутствующих среди Ii1 , . . . , Iip ти00пов (см. рис. 8.2c), а КС Σ0001 получается из КС Σ1 в результа(n)те удаления с помощью тождества t3 вершины v вместе совсеми «инцидентными» ей цепями и устранения с помощьютождества t1 образовавшихся при этом изолированных вершин — концевых вершин цепей Cp+1 , . . . , C2n (см. рис. 8.2d).По индуктивному предположению для КС Σ000 существуетЭП видаΣ000⇒Σ2no(n) (n) (n) (n) (n)t6 , t11 , t9 , t3 , t1и, следовательно, для КС Σ1 существует ЭП (8.1).74Ii1ВведениеC1.. .CqvCa2 −1CapCa2Ii1vIipvp⇒(n)(n)t11t9Ii2v2b)vp+1C2n(n)t9v1⇒Ca3 −1v2nv1..
Iip. ...| {z }Ii2a)Σ1⇒vp+1v2 nCp+1vIi1Ii2Iipvp000vp ⇒ Σ 1−−→ v1(n)(n)t3t1v2v2c)d)Рис. 8.2: к доказательству леммы 8.1Переход от КС Σ2 к КС Σ3 осуществляется с помощью(n)(n)тождеств t6 и t7 , а от КС Σ2 к КС Σ3 — с помощью тож(n)деств t10 .Лемма доказана.Теорема 8.1.
Для любых двух эквивалентных КС Σ0 и Σ00от БП x1 , . . . , xn существует ЭП вида Σ0 ⇒ Σ00 .τnb0 и Σb 00 — канонические КС от БПДоказательство. Пусть Σx1 , . . . , xn , эквивалентные КС Σ0 и Σ00 соответственно. Изb0 ⇒ Σb 00 , и поэтому, в силу лемопределений следует, что Σ(n)t2Введение75мы 8.1, существует ЭП видаb0 ⇒ Σb 00 ⇒ Σ00 .Σ0 ⇒ Στn(n)t2τnТеорема доказана.Следствие 1. Система τn является КПСТ для ЭП КС изUK от БП x1 , . . . , xn .Следствие 2. Система τ∞ является ПСТ для ЭП КС изUK .Докажем теперь отсутствие КПСТ в классе UK .
Для КС Σот БП x1 , . . . , xn и набора α, α ∈ B n , определим величинуΘ (Σ, α) = |E (Σ|α )| − |V (Σ|α )| + |c (Σ|α )| ,которая (см. §1) задает цикломатическое число графа Σ|α .Положим, далее,XΘ (Σ) =Θ (Σ, α) .α∈B nЛемма 8.2. Если Σ0 (x1 , . . . , xn )⇒Σ00 (x1 , . . . , xn ), то{t1 −t5 }Θ (Σ0 ) = Θ (Σ00 ), а если Σ0 ⇒ Σ00 , где k < n, то Θ (Σ0 )−Θ (Σ00 )τkделится на 2n−k .Доказательство. Докажем, что Θ(Σ0 )=Θ(Σ00 ), если Σ0 −→Σ00tiдля любого i из отрезка [1, 5]. Действительно, пусть КС Σ00b 0 , которая имеполучается из КС Σ0 заменой ее подсхемы Σiет вид левой части тождества ti , на соответствующую ейb 00 этого тождества.
Нетрудно проверить, чтоправую часть Σiдля любого i, i ∈ [1, 5], число линейно независимых циклов графов Σ|α0 и Σ|α00 одинаково при всех α, α ∈ B n , и,следовательно, Θ (Σ0 ) = Θ (Σ00 ).76ВведениеПусть теперь Σ0 ⇒ Σ00 , причем k < n. Если КС Σ0 соτkдержит в качестве подсхемы цикл из k контактов с однимполюсом, то КС Σ00 содержит вместо него один лишь полюс. Рассмотрим цикломатическое число сети Σ0 |α для различных α, α ∈ B n .
Если цикл указанного вида в КС Σ0содержит контакты, помеченные различными буквами одной и той же БП, то, очевидно, для любого α, α ∈ B n ,Θ (Σ0 )−Θ (Σ00 ) = 0. В противном случае, пусть xj1 , . . . , xjm —все различные БП, встречающиеся среди пометок указанного цикла, причем m 6 k. Заметим, что если цикл проводитна наборе α, α ∈ B n , то он проводит и на всех 2n−m наборах, в которых значения переменных с индексами j1 , . . . , jmсовпадают со значениями соответствующих переменных набора α. Таким образом, разностьXΘ Σ0 − Θ Σ00 =Θ Σ0 |α − Θ Σ00 |αα=(α1 ,...,αn )делится на 2n−m и, следовательно, делится на 2n−kЛемма доказана.Теорема 8.2.
В классе UK не существует конечной полнойсистемы тождеств.Доказательство. Проведем доказательство от противного:пусть τ — КПСТ для ЭП КС UK , и пусть n — максимальное число БП, встречающихся в тождествах системыτ . Тогда τn ⇒ τ и τn — КПСТ для UK . Докажем, что(n+1)τn 6⇒ t6. Для этого рассмотрим КС Σ0 , состоящую изпростого цикла длины (n + 1), содержащего контакты с пометками xi , i ∈ [1, n + 1], и имеющую единственный полюс с пометкой 1, которая является левой частью тождества(n+1)t6. Очевидно, что ей эквивалентна КС Σ00 , содержащаяизолированный полюс 1, которая является правой частьюВведение77(n+1)тождества t6(n+1).
Если τn ⇒ t6, то Σ0 ⇒ Σ00 . Согласноτnданным выше определениям, Θ (Σ0 ) = 1, Θ (Σ00 ) = 0 и разность Θ (Σ0 ) − Θ (Σ00 ) = 1 не делится на 2, что противоречит(n+1)утверждению леммы 8.2. Таким образом, тождество t6не выводится из системы τn , а значит, и из системы τ . Отсюда следует, что τ не может являться КПСТ для ЭП КСиз класса UK .Теорема доказана.Литература[1] Алексеев В.
Б. Введение в теорию сложности алгоритмов. М.: Издательский отдел ф-та ВМиК МГУ, 2002.[2] Алексеев В. Б., Вороненко А. А., Ложкин С. А.,Романов Д. С., Сапоженко А. А., Селезнева С. Н.Задачи по курсу «Основы кибернетики». Издательский отдел ф-та ВМиК МГУ, 2002.[3] Алексеев В. Б., Ложкин С. А.
Элементы теории графов, схем и автоматов. М.: Издательский отдел ф-таВМиК МГУ, 2000.[4] Боровков А. А. Курс теории вероятностей. М.: Наука,1976.[5] Гаврилов Г. П., Сапоженко А. А. Задачи и упражнения по дискретной математике. 3-е изд., перераб.М.: ФИЗМАТЛИТ, 2004.[6] Дискретная математика и математические вопросы кибернетики, под редакцией С.
В. Яблонского иО. Б. Лупанова. Т. 1. М.: Наука, 1974.[7] Евдокимов А. А. О максимальной длине цепи в единичном n-мерном кубе // Матем. заметки. 1969. 6. №3.С. 309–319.[8] Емеличев В. А., Мельников О. И., Сарванов В. И.,Тышкевич Р. И. Лекции по теории графов. М.: Наука,1977.78Введение79[9] Журавлев Ю. И. Локальные алгоритмы вычисленияинформации // Кибернетика. №1. 1965. С. 12–19.[10] Журавлев Ю. И. Теоретико-множественные методы валгебре логики // Проблемы кибернетики.
Вып. 8.М.: Физматгиз, 1962. С. 5-44.[11] Кузьмин В. А. Оценки сложности реализации функций алгебры логики простейшими видами бинарныхпрограмм // Сб. «Методы дискретного анализа втеории кодов и схем». Новосибирск, 1976. Вып. 29.С. 11–39[12] Ложкин С. А. Оценки высокой степени точности длясложности управляющих систем из некоторых классов // Математические вопросы кибернетики. Вып.
6.М.: Наука, 1996. С. 189–214.[13] Ложкин С. А. Структурное моделирование и декомпозиция для некоторых классов схем. М.: Издательский отдел ф-та ВМиК МГУ, 2001.[14] Лупанов О. Б. Асимптотические оценки сложностиуправляющих систем. М.: Изд-во МГУ, 1984.[15] Лупанов О. Б. О сложности реализации функцийалгебры логики релейно-контактными схемами //Проблемы кибернетики. Вып. 11. М.: Наука, 1964.С. 25–48.[16] Лупанов О. Б. О сложности реализации функций алгебры логики формулами // Проблемы кибернетики.Вып. 3.
М.: Физматгиз, 1960. С. 61–80.[17] Мурога С. Системы проектирования сверхбольшихинтегральных схем. М.: Мир, 1985.80Введение[18] Нечипорук Э. И. О топологических принципах самокорректирования // Проблемы кибернетики. Вып. 21.М.: Наука, 1969. С. 5–102.[19] Нигматуллин Р.
Г. Сложность булевых функций.М.: Наука, 1991.[20] Поваров Г. Н. Метод синтеза вычислительных и управляющих контактных схем // Автоматика и телемеханика. 1957. Т. 18. №2. С. 145–162.[21] Сапоженко А. А. Дизъюнктивные нормальные формы. М.: Изд-во МГУ, 1975.[22] Сапоженко А. А. Некоторые вопросы сложности алгоритмов. Издательский отдел ф-та ВМиК МГУ, 2001.[23] Сапоженко А. А., Ложкин С. А.
Методы логического проектирования и оценки сложности схем на дополняющих МОП-транзисторах // Микроэлектроника. 1983. Т. 12. №1. С. 42–47.[24] Фихтенгольц Г. М. Основы математического анализа,том 1. М.: Наука, 1968.[25] Фихтенгольц Г. М. Основы математического анализа,том 2. М.: Наука, 1964.[26] Чегис И. А., Яблонский С.
В. Логические способыконтроля работы электрических схем // Труды МИАН СССР. Т. 51. М.: Изд-во АН СССР, 1958. С. 270–360.[27] Яблонский С. В. Введение в дискретную математику.2-е изд., перераб. и доп. М.: Наука, 1986.[28] Яблонский С. В. Надежность управляющих систем.М.: Изд-во МГУ, 1991.Введение81[29] Яблонский С. В.
Некоторые вопросы надежности иконтроля управляющих систем // Математические вопросы кибернетики. Вып. 1. М.: Наука, 1988. С. 5–25.[30] Яблонский С. В. Эквивалентные преобразования управляющих систем. М.: Изд-во МГУ, 1986.[31] Cardot C. Quelques resultats sur l’application de l’algèbrede Boole à la synthèse des circuits a relais //Ann. Telecommunications. 1952. V.7. №2. P. 75–84.[32] Shannon C. E. The syntesis of two-terminal switchingcircuits // Bell Syst. Techn.
J. 1949. V. 28. №1.P. 59–98 (Русский перевод: Шеннон К. Работы потеории информации и кибернетике. М.: ИЛ, 1963.С. 59–101).[33] Wegener I. Branching programs and binary decisiondiagrams. SIAM Publishers, 2000..
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
