оки4 (1155747), страница 4
Текст из файла (страница 4)
Тождество t10 называют иногда тождеством замыкания по транзитивности, а тождество t11 — «леммой» озвезде.(1)(2)Лемма 3.1. Имеет место выводимость {t1 − t5 , t6 , t6 } |⇒{t7 − −t11 }.(1)Доказательство. Заметим, что выводимость {t5 , t6 } ⇒ t7(1)доказывается применением тождества t6 к правой частитождества bt5 (см. рис. 3.2a) для удаления из нее «висячего» цикла длины 1. Выводимость тождеств t8 –t11 из основ(1) (2)ных тождеств {t1 − t5 , t6 , t6 } показана на рис. 3.4–3.7 соответственно, где Σi и Σ̌i — левая и правая части тождестваti , i ∈ [8, 11].Обобщим тождества t1 –t11 на случай КС от БП X (n),где n > 2.
Для каждого i, i ∈ [1, 2n ], сопоставим ЭК ви-§3. Эквивалентные преобразования контактных схемx1x1a) t7 :1b) t8 :1∼21∼•x213x1•x1•∼121∼x12x1x1332e) t11 :x1m13x1x1x103x2x11x121x11x2•x1c) t9 :d) t10 :2x12x2x125∼mx12x1x10x1Рис. 3.3: вспомогательные тождества для КС326Глава 4. Эквивалентные преобразования управляющих системx1Σ8 −→t41•2x2x2⇒•x1•x2t5x2•x11•x1•3x2Рис. 3.4: вывод t8x1Σ9 −→t7•x11−−→ Σ̌9(2)t6Рис.
3.5: вывод t91Σ10 −→2x1x1x1t7−→ Σ̌10t53Рис. 3.6: вывод t102x2x2x2−→ Σ̌8t33§3. Эквивалентные преобразования контактных схем21x1x1Σ11 −→t7m1x1x1x1t5mx1x10x13x1m22x1t5x1x11−→0x1−→3x1x1270−→t53⇒ Σ̌11t5Рис. 3.7: вывод t11да xσ1 1 · · · xσnn , где ν (σ1 , . . . , σn ) = i − 1, моделирующую ее(n)цепочку Ii (см. ??), и пусть(n)Ii(n−1)Ii(n−2)Iii ∈ [1, 2n ] ,= Ii0 , i ∈ 1, 2n−1 ,= Ii00 , i ∈ 1, 2n−2 ,= Ii ,I = I2n ;I 0 = I20 n−1 ;I 00 = I200n−2 .no(n)(n)(n)(n)Систему тождеств τ (n) = t1 , . .
. , t11 , где t1 = t1 , t6 —(n)соответствующее основное тождество (см. рис. 3.1f), t2 —система, состоящая из тождеств, показанных на рис. 3.8a,где Ie — произвольная перестановка цепочки I, а остальныетождества приведены на рис. 3.8b—3.8i, будем называть системойn обобщенных тождествo порядка n. При этом система(1)(n)τn = t1 , . . . , t5 , t6 , . . . , t6считается системой основныхтождеств порядка n, а система всех основных тождеств обозначается через τ∞ .28Глава 4.
Эквивалентные преобразования управляющих системa)(n)t2I:1∼2Ie12•I2nI1b)(n)t3I2:1∼2n21•xnc)(n)t4xn:1∼2I10•1xnI20xn(n)t5I:1∼22I 0 n−1•d)2n22I1I2I33Ie)f)(n)t7(n)t8(n)I:1I:∼•1xn3It9h)t10 :∼I112I0•I0•∼2II3i):mII0I13I3I3(n)t112xn12Ixn1I12I•1(n)12xn0:g)∼2∼m2III03IРис.
3.8: обобщенные тождества порядка n для КС§3. Эквивалентные преобразования контактных схем2(n)Σ8→I 00•1xn−1•• xn−→t8xnI 001•3•⇒t2I 001•⇒t2•xn32xn−1• xnxn2xnxn−1xn−1(n)⇒(n−1)t8,t2xn−1Σ̌83(n)Рис. 3.9: вывод t8•I10(n)Σ3⇒(n)xn•t81−−−−→(n−1)t3xn12••2xn−−−−→xn2n − 12xnI 0 n−1xn(n−1)t32nxn•xn2n2n − 1(n)Рис. 3.10: вывод t329(n)⇒ Σ̌3t330Глава 4. Эквивалентные преобразования управляющих систем•xn(n)Σ4−−−−→(n−1)t4xn1xn••xnt4xnI 00n−22•⇒2t4xn−1xnxn−1⇒I100xn−1••I100••(n)⇒ Σ̌4(n−1)I 00n−2t82xn−1(n)Рис.
3.11: вывод t41(n)Σ5I0•→2xn•xn1I0xn−→t5I0I031I03•I0⇒t2xnxn••2(n)−−−−→ Σ̌5(n−1)t53(n)Рис. 3.12: вывод t5xn•2⇒t2§4. Отсутствие КПСТ в классе КС31Лемма 3.2. При n>2 имеет место выводимость τn ⇒τ (n) .Доказательство. Отметим сначала следующие очевидныевыводимости:(n){t2 } ⇒ t2 ,(n){t9 } ⇒ t9 .(n)Выводимость τn ⇒ ti , i = 8, 3, 4, 5, докажем индукциейпо n, n > ni , где n3 = n5 = 1 и n8 = n4 = 2. Базис этой(n )индукции составляет тождество ti = ti i , i = 8, 3, 4, 5, аобоснование индуктивного перехода дает выводимость пра(n)(n)вой части Σ̌i тождества ti , n > ni , из его левой части(n)Σi , показанная на рис.
3.9–3.12.Легко видеть, что выводимостиnonono(n) (n)(n)(n) (n)(n) (n)t2 , t5⇒ t7 ,t7 , t5⇒ t10 , t11при n > 2 доказываются аналогично тому, как это делалосьдля случая n = 1 (см. рис. 3.6, 3.7).Лемма доказана.§4Полнота системы основных тождеств иотсутствие конечной полной системытождеств в классе контактных схемДокажем сначала полноту системы основных тождеств τ∞для ЭП КС. Для этого, как обычно, достаточно доказать,что с помощью ЭП на основе системы τ∞ произвольную КСиз UK можно привести к каноническому виду. Напомнимb 1 , . . .
, xn ; a1 , . . . , am ), или,(см. ??), что каноническая КС Σ(xиначе, каноническая КС порядка n, представляет собой объb ij (x1 , . . . , xn ; ai , aj ),единение канонических (1, 1)-КС вида Σпостроенных на основе совершенных ДНФ ФАЛ проводимости от ai к aj для всех i и j таких, что 1 6 i < j 6 m.32Глава 4. Эквивалентные преобразования управляющих систем(n)Любую цепь Ii (см. §3), где i ∈ [1, 2n ], а также любую(n)цепь, которая получается из Ii перестановкой контактов,будем называть канонической цепью порядка n. Заметим,b (x1 , .
. . , xn ; a1 , . . . , am ) является канонической КСчто КС Σпорядка n тогда и только тогда, когда она обладает следующими свойствами:b принадлежит некоторой канониче1. любой контакт Σbской цепи порядка n, являющейся подсхемой схемы Σ,причем полюсами этой подсхемы служат только концевые вершины данной цепи;b является внутренней2. любая внутренняя вершина Σвершиной некоторой цепи из пункта 1;b отсутствуют «висячие циклы» (см.
тождество3. в КС Σ(n)t6 ) и «параллельные» цепи, то есть канонические цепи порядка n из пункта 1, которые соединяют одни ите же полюса и реализуют равные ЭК;b нет существенных транзитных проводимостей,4. в КС Σ(n)то есть наличие цепей вида Ii , соединяющих полюсaj с полюсом ak и полюс ak с полюсом at (см. рис. 4.1a),влечет наличие цепи такого же вида, соединяющей полюс aj с полюсом at (см. рис. 4.1b).Лемма 4.1. Для любой КС Σ, где Σ ∈ UK и Σ == Σ (x1 , . . . , xn ; a1 , . . . , am ), и любой эквивалентной Σ КСb (x1 , . .
. , xn ; a1 , . . . , am ) канонического вида существуетΣbЭП Σ ⇒ Σ.τnДоказательство. Построим ЭП видаbΣ ⇒ Σ1 ⇒ Σ2 ⇒ Σ3 ⇒ Σ4 = Σ,τnτnτnτn§4. Отсутствие КПСТ в классе КС33akakbΣbΣ(n)(n)IiIi(n)Iiaj(n)Iiajat(n)Ii=⇒ata)b)Рис. 4.1: к свойству 4 КС канонического видагде КС Σi , i = 1, 2, 3, 4, обладает отмеченными выше свойствами 1, .
. . , i, отличающими канонические КС. Первое изэтих ЭП имеет видΣ ⇒ Σ1(n)t4и связано с применением к каждому контакту тождества(n)t4 .Существование ЭПΣ1nΣ2⇒(n)(n)(n)(n)(n)t6 , t11 , t9 , t3 , t1(4.1)oдокажем индукцией по числу тех внутренних вершин КС Σ1 ,которые не являются внутренними вершинами ее канонических цепей. Базис индукции составляют схемы Σ1 , которыене имеют указанных вершин и для которых, следовательно,Σ2 = Σ1 . Пусть теперь КС Σ1 имеет хотя бы одну вершинууказанного вида и пусть v — одна из таких вершин. Уда(n)лим с помощью тождества t6 все присоединенные к v «висячие» циклы и рассмотрим все остальные цепи C1 , . . . , Cq ,концевой вершиной которых она является (см. рис.
4.2a).Не ограничивая общности рассуждений, будем считать, чтодля некоторых натуральных чиселa1 = 1 < a2 < · · · < ap < ap+1 = q + 134Глава 4. Эквивалентные преобразования управляющих системи любого j, j ∈ [1, p], цепи Caj , . . . , Caj+1 −1 являются цепя(n)ми типа Iij = Iij , где i1 , . . . , ip — различные числа отрезка[1, 2n ]. Применяя к каждой из этих p групп цепей одного ти(n)па тождество t11 , получим КС Σ01 , в которой из вершиныv выходит по одной цепи каждого типа Iij , j ∈ [1, p] (см.рис.
4.2b). Пусть, далее, КС Σ001 получается из КС Σ01 присо(n)единением к вершине v с помощью тождества t9 «висячих»цепей Cp+1 , . . . , C2n всех отсутствующих среди Ii1 , . . . , Iip ти00пов (см. рис. 4.2c), а КС Σ0001 получается из КС Σ1 в результа(n)те удаления с помощью тождества t3 вершины v вместе совсеми «инцидентными» ей цепями и устранения с помощьютождества t1 образовавшихся при этом изолированных вершин — концевых вершин цепей Cp+1 , .
. . , C2n (см. рис. 4.2d).По индуктивному предположению для КС Σ000 существуетЭП видаΣ000 n⇒Σo 2(n)(n)(n)(n)(n)t6 , t11 , t9 , t3 , t1и, следовательно, для КС Σ1 существует ЭП (4.1).Переход от КС Σ2 к КС Σ3 осуществляется с помощью(n)(n)тождеств t6 и t7 , а от КС Σ2 к КС Σ3 — с помощью тож(n)деств t10 .Лемма доказана.Теорема 4.1. Для любых двух эквивалентных КС Σ0 и Σ00от БП x1 , . . . , xn существует ЭП вида Σ0 ⇒ Σ00 .τnb0 и Σb 00 — канонические КС от БПДоказательство.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
