OK_metodichka_part_2 (1132797), страница 9
Текст из файла (страница 9)
. , am ) иΣ00 = Σ00 (x1 , . . . , xn ; a1 , . . . , am ), то есть возможность тождества t : Σ0 ∼ Σ00 означает, что для любых i и j из отрезка[1, m] ФАЛ проводимости от ai к aj в КС Σ0 равна ФАЛ проводимости от ai к aj в КС Σ00 . На рис. 7.1a–7.1e и 7.1f приведены пары эквивалентных КС, образующие тождества t1 –t5(m)и t6 , m = 1, 2, . . ., соответственно, которые мы будем называть основными тождествами для ЭП КС.Определим подстановку для КС как переименование (свозможным отождествлением и инвертированием) БП, а также переименование (с возможным отождествлением и снятием) полюсов.
Заметим, что применяя одну и ту же подстановку к двум эквивалентным КС, мы получим эквива-60Глава 2. Основные классы управляющих системa) t1 :b) t2 :x1c) t3 :x11x1∼2x2∼ ∅∼2•1d) t4 :x2•1•11x2x1•22O xx2 oooo• OOOO1∼2OOOooOoOooOOo1 x OOO ooox o 2Ooo 12•e) t5 :ooo 2oooo x1x11∼3(m)f) t63r•LLLL xLL2LLLx1 rrr:rr,rr1 ,,,,,xm,,x1OOOO1 x OOO1•∼ 1•Рис. 7.1: основные тождества для КС2§7. Эквивалентные преобразования контактных схемa) bt4 :b) bt5 :11x1x1x122∼∼61O xx1 oooo• OOOOO1OOoooOoOo1 xOOOOO oooxoo 2O•oo 111x12x1Рис. 7.2: подстановки для основных тождествлентные КС. Действительно, для переименования БП и переименования без отождествления полюсов это очевидно, ав случае отождествления полюсов эквивалентность получаемых КС вытекает из того, что матрица достижимости КС,являющейся результатом отждествления, однозначно определяется матрицей достижимости исходной КС.
На рис. 7.2a(7.2b) показана подстановка bt4 тождества t4 (соответственно bt5 тождества t5 ), связанная с переименованием БП x2 вx1 (соответственно полюсов 1 = 3 в 1).Понятие подсхемы для КС из рассматриваемого классаопределяется однозначным образом (см.
§5) с учетом неразделенности полюсов. Это означает, что для подсхемы Σ0 КСΣ имеет место включение V (Σ0 ) ⊂ V (Σ) и E(Σ0 ) ∈ E(Σ), аполюсами Σ0 являются все принадлежащие ей полюса КСΣи все те ее вершины, которые инцидентны в Σ ребрам изE(Σ) \ E(Σ0 ), и, возможно, некоторые другие вершины. Притаком определении подсхемы для рассматриваемого классаКС будет выполняться принцип эквивалентной замены.Рассмотрим примеры ЭП контактных схем с помощьюсистемы основных тождеств. На рис. 7.3a–7.3e приведенытождества t7 –t11 , которые мы будем называть вспомогатель-62Глава 2. Основные классы управляющих системa) t7 :x11b) t8 :12tt 2ttttJ•JJJJx2 J∼∼3x1 oooo•ooo∼oc) t9 :11x1d) t10 :1Oe) t11 :m 2 x12 ∼33OOO x1 x1 oooOOO ooox1ooo 0ooooo x11x1x1tJtJt1 x JJJJ1•x2 2 31x177 21 777x1 77 x17 14∼2x2x1 ttt•x2x13x1 4x1 44x1444m 4404x1 44424444x14 3Рис.
7.3: вспомогательные тождества для КС§7. Эквивалентные преобразования контактных схем•2Jx1 yyyx1 ttt• JJJx2 x2 ttytJytJJ ttyt⇒ EyEEΣ8 −→ JtJJt•tJJt4 1JJ tttt JJJJ1EEt5x1 Jtt x2 x2 x1 EE••32yyyyyyEy x2•E−→ Σ̌8EEx2t3EEEx2x2Рис. 7.4: вывод t8Σ9 −→t7x1•x11−−→ Σ̌9(2)t6Рис. 7.5: вывод t91Σ10 −→t72x1 −→ Σ̌10 xt51x13Рис. 7.6: вывод t1063364Глава 2. Основные классы управляющих систем1O2 3OOO x1 oooOox1 Ooo x1oooo 0oo x1Σ11 −→t7x1oo 21Ooooox13OOOx1 oooOox1 Ooo−→ot5oxoo 0oo1x1−→t5mm2oo OOOxO1OooO 31OooOOOx1 oooOox1 Ooo⇒ Σ̌11oooo 0t5oo x1x1−→t5mРис. 7.7: вывод t11(1)ными. Заметим, что выводимость {t5 , t6 } ⇒ t7 доказывает(1)ся применением тождества t6 к правой части тождества bt5(см. рис.
7.2a) для удаления из нее «висячего» цикла длины 1. Выводимость тождеств t8 –t11 из основных тождеств(1) (2){t1 − t5 , t6 , t6 } показана на рис. 7.4–7.7 соответственно,где Σi и Σ̌i — левая и правая части тождества ti , i ∈ [8, 11].Тождество t10 называют иногда тождеством замыкания потранзитивности, а тождество t11 — «леммой» о звезде.Обобщим тождества t1 –t11 на случай КС от БП X (n),где n > 2. Для каждого i, i ∈ [1, 2n ], сопоставим ЭК вида xσ1 1 · · · xσnn , где ν (σ1 , . . . , σn ) = i − 1, моделирующую ее(n)цепочку Ii (см.
§6), и пусть(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 .§7. Эквивалентные преобразования контактных схемa)(n)t2:I12r•LLrrr LLLIL2Lnrr I2LLrrr∼I1b)c)d)e)f)(n)t3(n)t4(n)t5(n)t7(n)t8(n):12:1:t10 :I2pp 2ppNNN•pNNxn ∼ 2 I2 212•RRR I 0l•[[[R[R[R1RRR[[[[R8lxlnI20 mmm1 8882mmxn 8 mmm0mm I n−1•∼2C1 CCCCICI3I1∼2Ippp•NpNp1 0NNNxn•I∼13xn 2 3 2? I?1 ????I2I013OOO I I oooOoOooIoo 0oooo Im∼xnIIe1xnI gg•gggg∼11O(n)3∼3(n)t11 :I01:h)i){{{ 2{{{ I:t921I1:g)xn2n65I13I4244 I 444 I44 444 3m 4404I 4I∼Рис. 7.8: обобщенные тождества порядка n для КС2n66Глава 2.
Основные классы управляющих систем(n)Σ8→1I 002xn−1 xn9••999xn 9xn 2• xn−1I 00 •99−→ ⇒9t8 1t2xn−1 99•xn3xn−1•00Ix9 n•9⇒ 91t2xn 99•xn−132(n)⇒(n−1)t8,t2Σ̌83(n)Рис. 7.9: вывод t8D 0zz• DDDI2n−1zDDzz•,z•2xn ,,, xn xn 222xn I10(n)Σ3⇒(n)t81−−−−→(n−1)t32n − 12•2 222xn xn12−−−−→(n−1)t32n•2 222xn xn2n2n − 1(n)Рис.
7.10: вывод t3(n)⇒ Σ̌3t3§7. Эквивалентные преобразования контактных схем(n)Σ467O00OOOvv−−−−→ vHHHo ⇒(n−1)1 x HHH ooo00oo 2 t4t4n•oo I2n−2I1xn vvv• OOOO•II•RRIIIxn−1xn RRRIRIIRRI00 xnxn−1 •UUUUIU1 UU(n)⇒ /?/? xnii ⇒ Σ̌4iii?// ?? xn−1(n−1)t4eii 00eeeeeeuu• I2n−2 t8xn // •e uuu// uuxn−1u•u(n)Рис. 7.11: вывод t41(n)Σ5→21vvvvv x−→v•v nvt5vv0vv II0•I0xn31⇒t2I0•22xn22I0 2vv•vxvvv n3(n)(n−1)t53(n)Рис.
7.12: вывод t5xn2xn 22vv•vv0vv I2−−−−→ Σ̌5•222⇒t268Глава 2. Основные классы управляющих системno(n)(n)(n)(n)Систему тождеств τ (n) = t1 , . . . , t11 , где t1 = t1 , t6 —(n)соответствующее основное тождество (см. рис. 7.1f), t2 —система, состоящая из тождеств, показанных на рис. 7.8a,где Ie — произвольная перестановка цепочки I, а остальныетождества приведены на рис. 7.8b—7.8i, будем называть системойn обобщенных тождествo порядка n. При этом система(1)(n)τn = t1 , . . . , t 5 , t 6 , . . . , t 6считается системой основныхтождеств порядка n, а система всех основных тождеств обозначается через τ∞ .Лемма 7.1. При 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 , показанная на рис. 7.9–7.12.Легко видеть, что выводимостиno(n) (n)(n)t2 , t 5⇒ t7 ,nono(n) (n)(n) (n)t7 , t 5⇒ t10 , t11при n > 2 доказываются аналогично тому, как это делалосьдля случая n = 1 (см. рис. 7.6, 7.7).Лемма доказана.§8. Отсутствие КПСТ в классе КС§869Полнота системы основных тождеств иотсутствие конечной полной системытождеств в классе контактных схемДокажем сначала полноту системы основных тождеств τ∞для ЭП КС.
Для этого, как обычно, достаточно доказать,что с помощью ЭП на основе системы τ∞ произвольную КСиз UK можно привести к каноническому виду. Напомнимb 1 , . . . , xn ; a1 , . . . , am ), или,(см. §6), что каноническая КС Σ(xиначе, каноническая КС порядка n, представляет собой объb ij (x1 , . .
. , xn ; ai , aj ),единение канонических (1, 1)-КС вида Σпостроенных на основе совершенных ДНФ ФАЛ проводимости от ai к aj для всех i и j таких, что 1 6 i < j 6 m.(n)Любую цепь Ii (см. §7), где 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 , соединяющих полюс70Глава 2.
Основные классы управляющих системaj с полюсом ak и полюс ak с полюсом at (см. рис. 8.1a),влечет наличие цепи такого же вида, соединяющей полюс aj с полюсом at (см. рис. 8.1b).akpppp -(n)Ii ppp-- (n)ppp-I- ipppp-pajbΣakpppp -(n)Ii ppp-- (n)ppp-I- ip=⇒ppp(n)p\\\\\\\\Ii\\\\\\\\\-ajbΣata)atb)Рис. 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)§8. Отсутствие КПСТ в классе КС71докажем индукцией по числу тех внутренних вершин КС Σ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 существуетЭП видаΣ000nΣ2⇒(n)(n)(n)(n)(n)t6 , t11 , t9 , t3 , t1oи, следовательно, для КС Σ1 существует ЭП (8.1).72Глава 2. Основные классы управляющих систем UU ZZUZUZUZUCZU1UU v iCiqidididididiZZZUZU iZ....ddddidiUZIi1UZZZZddddidi" U d. ididididiiii "" UUUUZUZUZUZU.i Ca −1 "Cap "2 "Ca2 "" C " a3 −1 . . . "Σ1| {z }Ii2a)vv2n p+1222Cp+1C2n 2222 Ii1 2v Iip\\\\\\ v⇒ v1p(n)t9Ii2 v2Iip⇒v1(n)t11vv\\\Ii\p\\pIi2 v2 Ii1v2n b)−−→ v1 (n)t3c)⇒(n)t9vp+1 vp ⇒ Σ0001(n)v2t1d)Рис. 8.2: к доказательству леммы 8.1Переход от КС Σ2 к КС Σ3 осуществляется с помощью(n)(n)тождеств t6 и t7 , а от КС Σ2 к КС Σ3 — с помощью тож(n)деств t10 .Лемма доказана.Теорема 8.1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
