Lectionc2 (1132951), страница 8
Текст из файла (страница 8)
На рис. 6.4a показана (1, 2n )-КС D (x1 , . . . , xn ; 1; a0 , . . . , a2n −1 ),которая называется (1, 2n )-контактным деревом порядка nот БП X (n). Легко видеть, что в выходной вершине ai , i =0, . . .. . . , 2n − 1, этого контактного дерева (КД) реализуется ЭКвида xσ1 1 · · · xσnn , где ν (σ1 , . .
. , σn ) = (i − 1), и что ФАЛ проводимости между любыми его выходами равна 0. Таким образом, (1, 2n )-КД порядка n является дешифратором порядка n, то есть схемой, реализующей систему Qn из всех ЭКранга n от БП X (n).Схемы Σ0 и Σ00 считаются, как обычно, изоморфными, если изоморфны соответствующие им графы, и эквивалентными, если они реализуют равные системы ФАЛ. Изоморфные КС, очевидно, эквивалентны.Для множества C, состоящего из контактов вида xσi11 , . .
. , xσirrв КС Σ, определим его функцию проводимости K (C) ифункцию отделимости J (C) как ФАЛ вида xσi11 · · · xσirr иxσi11 ∨. . .∨xσirr соответственно. При этом множество C называется проводящим (отделимым), если K (C) 6= 0 (J (C) 6= 1),и нулевым (соответственно единичным) в противном случае.
Заметим, что в результате приведения подобных (см.?? гл. ??) отличная от 0 ФАЛ K (C) и отличная от 1 ФАЛJ (C) могут быть преобразованы в ЭК и ЭД соответственно.Очевидно, также, чтоK C 0 > K (C)и J C 0 6 J (C) ,52Глава 2. Основные классы управляющих системss• a0sssKsK•sKKKxn KK•axnss•ssssOsx1 sss• OOOOsx2 OO•ss1 •sKKKKK xo2oooo•x1 KKo•KoKKKKx2 KKx2•1...ai•/ xσ1 .
. . xσnn1ss• a2n −2sssKsK•sKKKxn KK a n•xn2 −1a)a0 •KKK xnKKKKs•ssssa1 •ss xn•KKK xKK2KKo•KKK x1ooKKoox2oKKo•s• aOs• OO x2sOOO ssOs•ss x1ssssx2ss•a2n −2 •KKK xnKKKKs•ssssxnsa2n −1 •sb)Рис. 6.4: (1, 2n )- и (2n , 1)- контактные деревья порядка n§6. Контактные схемы и π-схемы, оценка их числа53если C 0 ⊆ C.Из введенных определений (см. также §1) следует, чтоФАЛ g, реализуемая КС Σ (x1 , . . . , xn ; a1 ; a2 ), обращается в 1(обращается в 0) на наборе α, α ∈ B n , тогда и только тогда,когда в Σ существует множество контактов C, образующеепростую проводящую (a1 − a2 )-цепь (соответственно тупиковое отделимое (a1 |a2 ))-сечение), для которого K (C) = 1(соответственно J (C) = 0) на наборе α.
Таким образом,g (x1 , . . . , xn ) = K (C1 ) ∨ . . . ∨ K (Ct ) == J (S1 ) & . . . &J (Sr ) , (6.1)где C1 , . . . , Ct и S1 , . . . , Sr — все простые проводящие (a1 − a2 )цепи и все тупиковые отделимые (a1 |a2 )-сечения КС Σ.Заметим, что первая из формул (6.1) может быть преобразована в ДНФ, а вторая — в КНФ, в результате приведения подобных (см. §4), если g 6≡ 0 и g 6≡ 1 соответственно.Так, в КС, показанной на рис. 6.3b, имеются три простыепроводящие цепи C1 , C2 и C3 , которые идут из a1 в a2 . ПриэтомK (C1 ) = x1 x2 x3 , K (C2 ) = x1 x2 x1 = x1 x2 , K (C3 ) = x1 x3и, следовательно,g (x1 , x2 , x3 ) = x1 x2 x3 ∨ x1 x2 ∨ x1 x3 == x1 x2 ∨ x2 x3 ∨ x3 x1 = H (x1 , x2 , x3 ) .Рассмотрим теперь параллельно-последовательные или,иначе, π-схемы, которые являются частным случаем КС.Простейшей π-схемой считается любая (1, 1)-КС, которая состоит из одного контакта, соединяющего полюса (см. рис.
6.6a).Если π-схемы Σ1 и Σ2 уже определены, то (1, 1)-КС Σ0 (Σ00 ),54Глава 2. Основные классы управляющих системa1 a2C1Cta)a1 •··· a2•SpS1b)Рис. 6.5: КС, моделирующие ДНФ и КНФкоторая получается в результате их параллельного (соответственно последовательного) соединения (см. рис. 6.6b и 6.6c)тоже является π-схемой. Заметим, что при этом вход (выход) Σ0 является результатом отождествления входов (соответственно выходов) Σ1 и Σ2 , тогда как входом Σ00 являетсявход Σ1 , выходом Σ00 — выход Σ2 , а выход Σ1 отождествляется с входом Σ2 и становится внутренней вершиной Σ00 .Легко видеть, что π-схема, показанная на рис.
6.6a, реализует ФАЛ xσi , а π-схемы Σ0 и Σ00 (см. рис. 6.6b и 6.6c) —ФАЛ f1 ∨ f2 и f1 &f2 соответственно, где f1 и f2 — ФАЛ,реализуемые π-схемами Σ1 и Σ2 соответственно.Лемма 6.1. Любой π-схеме Σ можно сопоставить эквивалентную ей формулу F из UΦ с поднятыми отрицаниямитакую, что R (F) = L (Σ) и обратно.Доказательство. Построим формулу F индукцией по строению π-схемы Σ. Если Σ — простейшая π-схема вида xσi , тоположим F = xσi . Если π-схемам Σ1 и Σ2 уже сопоставлены формулы F1 и F2 с поднятыми отрицаниями, то π-схеме§6. Контактные схемы и π-схемы, оценка их числаa1 xσi a2Σ0:a1 Σ155 a2Σ2a)b)Σ00 : a1 Σ1•Σ2 a2c)Рис.
6.6: к определению π-схемыΣ0 (Σ00 ), получающейся в результате параллельного (соответственно последовательного) соединения Σ1 и Σ2 , сопоставим формулу F0 = F1 ∨ F2 (соответственно F00 = F1 &F2 ).При этомR F0 = R F00 = R (F1 ) + R (F2 )и, следовательно, по индуктивному предположению,R F0 = R F00 = L (Σ1 ) + L (Σ2 ) = L (Σ) .Аналогичным образом, индукцией по строению формулы Fс поднятыми отрицаниями можно найти эквивалентную ейπ-схему Σ такую, что L (Σ) = R (F).Лемма доказана.На рис 6.7a показана π-схема, которая реализует ФАЛH (x1 , x2 , x3 ) и соответствует формуле:H (x1 , x2 , x3 ) = x1 (x2 ∨ x3 ) ∨ x2 x3 ,56Глава 2. Основные классы управляющих системt•ttx2tttttttx3tt aa1 JtJJtt 2JJ xttx3 ttJJ 2JJtJJtttJJ tt•tx1a)x2 oooo•oooR oRo•oRox1 ooRRRoox2 RR•a1 OoOoOx2 lll•OOlllx1 OOOllO• OOOOOx2 OOO•?xn oooo• ??o??oo??ooOO•OOOO??O??y0xn OOO• OOOOO ???OOO ??O ?y1 OOOO??OO? aoo o 2y2n −2ooooo ooo oooooy2n −1xn oooo•ooooOoO•OOOOxn OOO•b)Рис.
6.7: примеры π-схем§6. Контактные схемы и π-схемы, оценка их числа57а на рис. 6.7b — π-схема, которая построена на основе контактного дерева и реализует ФАЛ µn — мультиплексорнуюФАЛ порядка n, — в соответствии с формулойµn (x1 , . . . , xn , y0 , . . . , y2n −1 ) =! !___=xσ1 1 xσ2 2 · · ·xσnn yν(σ1 ,...,σn ) · · · .σ1 ∈Bσ2 ∈Bσn ∈BСхема, моделируюшая совершенную ДНФ ФАЛ f , называется канонической КС для этой ФАЛ.Будем называть (1, m)-КС приведенной, если все изолированные вершины Σ являются ее полюсами, а все контактыи остальные вершины Σ принадлежат простым проводящимb коцепям, соединяющим ее вход и выходы.
При этом КС Σ,торая получается из КС Σ удалением «лишних», то есть непринадлежащих цепям указанного вида, неполюсных вершин и контактов, является эквивалентной Σ приведеннойb 6 L (Σ). Заметим, что приведенная КСКС такой, что L(Σ)не содержит петель, а приведенная КС, не реализующая нулевых ФАЛ, является связным графом. Так, КС, показанная на рис. 6.3c, не является приведенной, а соответствующая ей приведенная КС получается из нее удалением вершины v.Рассмотрим теперь некоторые оценки числа контактныхсхем различных типов. Пусть UK и Uπ — множество всех КСиз неориентированных контактов и множество всех π-схемсоответственно. Если UA — один из указанных классов схем,то через UA (L, n) будем обозначать множество приведенных(1, 1)-схем Σ из UA от БП X (n), для которых L (Σ) 6 L.
Длялюбого множества схем U в соответствии с §1 через |U| и kUkбудем по-прежнему обозначать число попарно не изоморфных и попарно не эквивалентных схем в U соответственно.При этом для любого из введенных выше множеств схемнеравенство (1.7) будет выполняться.58Глава 2. Основные классы управляющих системЛемма 6.2. При любых натуральных L и n выполняетсянеравенствоkUπ (L, n)k 6 (16n)L .(6.2)Доказательство.
В силу леммы 6.1, достаточно доказать,что число попарно не эквивалентных формул F (x1 , . . . , xn )с поднятыми отрицаниями над базисом Б0 , для которыхR (F) 6 L, не превосходит (16n)L . Для этого сопоставимформуле F указанного вида формулу F0 из UΦ{&,∨} от БПx1 , . . . , x2n , которая получается из F заменой каждой ееподформулы xi , i ∈ ∈ [1, n], формулой xi+n и для которой,в силу замечания к лемме 2.1,L F0 = R (F) − 1 6 L − 1.При таком сопоставлении неэквивалентные формулы переходят в неэквивалентные, и поэтому число попарно не эквивалентныхформулрассматриваемого вида не больше, чем ΦU (L − 1, 2n), откуда, в силу (2.8), следует (6.2).Лемма доказана.Лемма 6.3.
При любых натуральных L и n выполняетсянеравенство KU (L, n) 6 (8nL)L .Доказательство. Для того, чтобы задать с точностью доизоморфизма произвольную связную КС Σ== Σ(x1 , . . . , xn ; a1 ; a2 ), Σ ∈ UK (L, n), достаточно выбрать соответствующую ей неориентированную связную (1, 1)-сетьΣ̂ с не более, чем L, ребрами, а затем сопоставить каждомуребру Σ̂ одну из пометок x1 , .
. . , xn , x1 , . . . , xn .Заметим, что число способов выбора сети Σ̂ в силу замечания и следствия из леммы 1.2 не больше, чем (4L)L , а число способов пометки ее ребер символами x1 , . . . , xn , x1 , . . . , xnне больше, чем (2n)L . Следовательно, K U (L, n) 6 UK (L, n) 6 (8nL)L .§6. Контактные схемы и π-схемы, оценка их числа59Лемма доказана.Рассмотрим, в заключение, особенности функционирования КС с несколькими входами. Будем считать, что в каждой вершине (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)-КС из неориентированныхконтактов по существу не отличается от функционированиясоответствующей двухполюсной КС с неразделенными по-60Глава 2.
Основные классы управляющих системлюсами.В частности, показанная на рис. 6.3c КС с неразделенны1 l3 l 3ми полюсами a1 , a2 , a3 реализует матрицу l3 1 0 , КС изl3 0 1тождественных вершин реализует единичную матрицу, если каждая ее вершина является входом и выходом с одними тем же номером и т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
