ОК_Часть_2_2015_(320-328)_v03-09 (1132806), страница 9
Текст из файла (страница 9)
. . , xn ; a0 , . . . , a2n −1 ; a) и реализует столбец извсех ЭК множества Qn , упорядоченных сверху вниз по возрастанию их номеров.В соответствии с общими правилами из §1, функционирование КС Σ = Σ (x1 , . . . , xn ; a1 , . . . , am ) снеразделенными полюсами определяется как функционирование КС с разделенными полюсами видаΣ (x1 , . . . , xn ; a1 , . . . , am ; a1 , .
. . , am ). В этом случае матрица F является рефлексивной и транзитивной матрицей, аесли, кроме того, Σ — неориентированная сеть, то и — симметричной матрицей. Заметим также, что функционирование (1, 1)-КС из неориентированных контактов по существуне отличается от функционирования соответствующей двух-§7.
Эквивалентные преобразования контактных схем61полюсной КС с неразделенными полюсами.В частности, показанная на рис. 6.3c КС с неразделенны1 l3 l 3ми полюсами a1 , a2 , a3 реализует матрицу l3 1 0 , КС изl3 0 1тождественных вершин реализует единичную матрицу, если каждая ее вершина является входом и выходом с одними тем же номером и т. д.С другой стороны, любая симметрическая, транзитивная и рефлексивная матрица 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 эквивалентность КС Σ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, . . ., соответственно, которые мы будем называть основными тождествами для ЭП КС.Определим подстановку для КС как переименование (свозможным отождествлением и инвертированием) БП, атакже переименование (с возможным отождествлением иснятием) полюсов.
Заметим, что применяя одну и ту же подстановку к двум эквивалентным КС, мы получим эквива-62Глава 2. Основные классы управляющих системa) t1 :•x1b) t2 :x1c) t3 :x2•11∼2x1•∼2x2d) t4 :1∼2x1e) t5 :1∼2x1∼ ∅x2111f)(m)t6:12x2•x1x2•x11•x2∼22x13•xm2x13x1x1•1•Рис. 7.1: основные тождества для КС§7. Эквивалентные преобразования контактных схемa) bt4 :x112∼x1b) bt5 :1x12∼11x1•x1x1•x1632x12x1Рис. 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 , которые мы будем называть вспомога-64Глава 2. Основные классы управляющих системx1x1a) t7 :1b) t8 :11∼•x213x1•x1•∼121∼x12x1x1332e) t11 :x1m13x1x1x103x2x11x121x11x2•x1c) t9 :d) t10 :2x12x2x1∼2∼mx12x1x10x1Рис. 7.3: вспомогательные тождества для КС3§7. Эквивалентные преобразования контактных схемx1Σ8 −→t41•2x2x2⇒•x1•x2t5x2•x11x1•3x2Рис. 7.4: вывод t8x1Σ9 −→t7•x11−−→ Σ̌9(2)t6Рис. 7.5: вывод t91Σ10 −→2x1x1x1t7−→ Σ̌10t53Рис. 7.6: вывод t102x2•65x2x2−→ Σ̌8t3366Глава 2. Основные классы управляющих систем21x1x1Σ11 −→t7m1x1x1x1t5mx1x10x1x1m22x1t5x1x11−→0x1−→3x1x103−→t53⇒ Σ̌11t5Рис. 7.7: вывод t11тельными.
Тождество t10 называют иногда тождеством замыкания по транзитивности, а тождество t11 — «леммой» озвезде.(1)(2)Лемма 7.1. Имеет место выводимость {t1 − t5 , t6 , t6 } |⇒{t7 − −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].Обобщим тождества t1 –t11 на случай КС от БП X (n),где n > 2. Для каждого i, i ∈ [1, 2n ], сопоставим ЭК вида xσ1 1 · · · xσnn , где ν (σ1 , . . .
, σn ) = i − 1, моделирующую ее§7. Эквивалентные преобразования контактных схемa)(n)t2I:1∼267Ie12•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Рис. 7.8: обобщенные тождества порядка n для КС68Глава 2.
Основные классы управляющих систем2(n)Σ8→I 00•1xn−1•• xn−→t8xnI 001•xn−1xn−13•⇒t2I 001•⇒t2•xn32xn−1• xnxn2xn(n)⇒(n−1)t8,t2xn−1Σ̌83(n)Рис. 7.9: вывод t8•I10(n)Σ3⇒(n)xn•t81−−−−→(n−1)t3xn12xn••2xn−−−−→xn2n − 12xnI 0 n−1(n−1)t32nxn•xn2n2n − 1(n)Рис. 7.10: вывод t3(n)⇒ Σ̌3t3§7. Эквивалентные преобразования контактных схем•xn(n)Σ4−−−−→(n−1)t4xn1xn••xnt4xnI100I 00n−22•⇒2t4xn−1xnxn−1⇒69xn−1••I100••(n)⇒ Σ̌4(n−1)I 00n−2t82xn−1(n)Рис. 7.11: вывод t41(n)Σ5I0•→2xn•xn1I0xn−→t5I0I031I03•I0⇒t2xnxn••2(n)−−−−→ Σ̌5(n−1)t53(n)Рис. 7.12: вывод t5xn•2⇒t270Глава 2. Основные классы управляющих систем(n)цепочку Ii(см.
§6), и пусть(n)i ∈ [1, 2n ] ,I = I2n ;(n−1)Ii= Ii0 , i ∈ 1, 2n−1 ,I 0 = I20 n−1 ;(n−2)Ii= Ii00 , i ∈ 1, 2n−2 ,I 00 = I200n−2 .no(n)(n)(n)(n)Систему тождеств τ (n) = t1 , . . . , t11 , где t1 = t1 , t6 —Ii= Ii ,(n)соответствующее основное тождество (см. рис. 7.1f), t2 —система, состоящая из тождеств, показанных на рис. 7.8a,где Ie — произвольная перестановка цепочки I, а остальныетождества приведены на рис.
7.8b—7.8i, будем называть системойn обобщенных тождествo порядка n. При этом система(1)(n)τn = t1 , . . . , t5 , t6 , . . . , t6считается системой основныхтождеств порядка n, а система всех основных тождеств обозначается через τ∞ .Лемма 7.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 , показанная на рис.
7.9–7.12.Легко видеть, что выводимостиnonono(n) (n)(n)(n) (n)(n) (n)t2 , t5⇒ t7 ,t7 , t5⇒ t10 , t11при n > 2 доказываются аналогично тому, как это делалосьдля случая n = 1 (см. рис. 7.6, 7.7).Лемма доказана.§8. Отсутствие КПСТ в классе КС§871Полнота системы основных тождеств иотсутствие конечной полной системытождеств в классе контактных схемДокажем сначала полноту системы основных тождеств τ∞для ЭП КС.
Для этого, как обычно, достаточно доказать,что с помощью ЭП на основе системы τ∞ произвольную КСиз 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.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
