2 (1132838), страница 9
Текст из файла (страница 9)
Рассмотрим ориентированноеупорядоченное дерево D00 , получающееся из D0 введением (условной) ориентации всех его ребер по направлению ккорню и таким их упорядочением, при котором вершина a1становится первым листом D00 (см. §1).Заметим, что число ребер (вершин, листьев) дерева D00не больше, чем L (соответственно L + 1, L), и поэтому, всилу (1.4), число таких деревьев с учетом пометок их ребер символами x1 , . . . , xn , x1 , .
. . , xn не больше, чем (8n)L .Заметим также, что КС Σ может быть получена в результате присоединения каждого листа дерева D00 к одной из еговершин, отличной от a2 . Следовательно, K U (L, n) 6 UK (L, n) 6 (8nL)L .60ВведениеЛемма доказана.Рассмотрим, в заключение, особенности функционирования КС с несколькими входами.
Будем считать,что в каждой вершине (p, q)-КС Σ реализуется столбец, составленный из p ФАЛ проводимости от входовΣ к этой вершине, а сама КС Σ реализует матрицу,которая состоит из q столбцов, реализованных на еевыходах. Таким образом, функционированиеКС Σ =000000= Σ x1 , . . . , xn ; a1 , . .
. , ap ; a1 , . . . , aq представляет собойматрицу F = F (x1 , . . . , xn ) с p строками, q столбцами и элементами из P2 (n), для которой F hi, ji — ФАЛ, реализуемаямежду a0i и a00j , где i ∈ [1, p] и j ∈ [1, q], то есть при любом α, α ∈ B n , матрица F (α) является матрицей достижимости сети Σ|α . В частности, функционирование (1, q)-КСпредставляет собой набор (строку) из q ФАЛ проводимости от ее входа к выходам, а функционирование (p, 1)-КС —столбец из p ФАЛ проводимости от ее входов к выходу.Так, КС Σ (x1 , x2 , x3 ; a1h, v; a2i, a3 ), показанная на рисунке 6.3c реализует матрицу ll3 ll3 от БП X(3), а на рис.
6.4b3 3приведено (2n , 1)-КД порядка n от БП X (n), которое имеет вид D (x1 , . . . , xn ; a0 , . . . , a2n −1 ; a) и реализует столбец извсех ЭК множества Qn , упорядоченных сверху вниз по возрастанию их номеров.В соответствии с общими правилами из §1, функционирование КС Σ = Σ (x1 , . . . , xn ; a1 , . . .
, am ) снеразделенными полюсами определяется как функционирование КС с разделенными полюсами видаΣ (x1 , . . . , xn ; a1 , . . . , am ; a1 , . . . , am ). В этом случае матрица F является рефлексивной и транзитивной матрицей, аесли, кроме того, Σ — неориентированная сеть, то и — симметричной матрицей. Заметим также, что функционирование (1, 1)-КС из неориентированных контактов по существуне отличается от функционирования соответствующей двух-Введение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Введение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: основные тождества для КСВведениеa) bt4 :63x112∼x1b) bt5 :1x12∼11x1•x1x1•x12x12x1Рис. 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Введениеx1x1a) t7 :1b) t8 :11∼•x213x1•x1•∼121∼x12x1x1332e) t11 :x1m13x1x1x103x2x11x121x11x2•x1c) t9 :d) t10 :2x12x2x1∼2∼mx12x1x10x1Рис. 7.3: вспомогательные тождества для КС3Введение65x1Σ8 −→t41•2x2x2⇒•x1•x2t5x2•x11•x1•3x2Рис. 7.4: вывод t8x1Σ9 −→t7•x11−−→ Σ̌9(2)t6Рис.
7.5: вывод t91Σ10 −→2x1x1x1t7−→ Σ̌10t53Рис. 7.6: вывод t102x2x2x2−→ Σ̌8t3366Введение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, моделирующую ееВведениеa)(n)t267I: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Рис. 7.8: обобщенные тождества порядка n для КС68Введение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Введение69•xn(n)Σ4−−−−→(n−1)t4xn1xn••xnt4xnI 00n−22•⇒2t4xn−1xnxn−1⇒I100xn−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Введение(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).Лемма доказана.Введение§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}
