Lectionc2 (1132951), страница 9
Текст из файла (страница 9)
д.С другой стороны, любая симметрическая, транзитивная и рефлексивная матрица F , F ∈ (P2 (n))m,m , реализуется КС Σ = Σ (x1 , . . . , xn ; a1 , . . . , am ), которая представляет собой объединение всех КС Σij = Σij (x1 , . . . , xn ; ai , aj ),где 1 6 i < j 6 m, а КС Σij построена по совершенной ДНФФАЛ F hi, ji (см. ??) и считается канонической КС матрицы F .§7Эквивалентные преобразования контактныхсхем.
Основные тождества, выводвспомогательных и обобщенных тождествРассмотрим вопросы ЭП для КС из UK с неразделенными(бесповторными) полюсами. В соответствии с §1, ?? главы 2 эквивалентность КС Σ0 = Σ0 (x1 , . . . , xn ; a1 , . . . , 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, . . ., соответственно, которые мы будем называть основными тождествами для ЭП КС.Определим подстановку для КС как переименование (свозможным отождествлением и инвертированием) БП, а также переименование (с возможным отождествлением и снятием) полюсов. Заметим, что применяя одну и ту же подстановку к двум эквивалентным КС, мы получим эквива-§7.
Эквивалентные преобразования контактных схемa) t1 :b) t2 :x1c) t3 :x11x1∼2x2∼ ∅∼2•1d) t4 :x2•1•11x2x1•6122O 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: основные тождества для КС262Глава 2. Основные классы управляющих системa) bt4 :b) bt5 :11x1x1x122∼∼O 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 , которые мы будем называть вспомогатель-§7. Эквивалентные преобразования контактных схем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: вспомогательные тождества для КС6364Глава 2. Основные классы управляющих систем•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: вывод t103§7. Эквивалентные преобразования контактных схем1O2 3OOO x1 oooOox1 Ooo x1oooo 0oo x1Σ11 −→t7x1oo 2651Ooooox13OOOx1 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 (см. ?? главы 2), и пусть(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 .66a)Глава 2. Основные классы управляющих систем(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∼xnIIexnI gg•gggg∼11O(n)3∼3(n)t11 :I01:h)i){{{ 2{{{ I:t921I1:g)xn2n1I13I4244 I 444 I44 444 3m 4404I 4I∼Рис.
7.8: обобщенные тождества порядка n для КС2n§7. Эквивалентные преобразования контактных схем(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)⇒ Σ̌3t36768Глава 2. Основные классы управляющих систем(n)Σ4O00OOOvv−−−−→ 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⇒t2§7. Эквивалентные преобразования контактных схем69no(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).Лемма доказана.70§8Глава 2. Основные классы управляющих системПолнота системы основных тождеств иотсутствие конечной полной системытождеств в классе контактных схемДокажем сначала полноту системы основных тождеств τ∞для ЭП КС. Для этого, как обычно, достаточно доказать,что с помощью ЭП на основе системы τ∞ произвольную КСиз 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.(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 , соединяющих полюс§8. Отсутствие КПСТ в классе КС71aj с полюсом 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)72Глава 2. Основные классы управляющих системдокажем индукцией по числу тех внутренних вершин КС Σ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 , .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
