OK_metodichka_part_2 (1132797), страница 8
Текст из файла (страница 8)
. . , 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 ),§6. Контактные схемы и π-схемы, оценка их числаa1 53 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 с поднятыми отрицаниями, то π-схеме54Глава 2. Основные классы управляющих системa1 xσi a2Σ0:a1 Σ1 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 ,§6.
Контактные схемы и π-схемы, оценка их числа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: примеры π-схем5556Глава 2. Основные классы управляющих система на рис. 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) будет выполняться.§6. Контактные схемы и π-схемы, оценка их числа57Лемма 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.9), следует (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 .Заметим, что число способов выбора сети Σ̂ в силу замечания и следствия из леммы ?? не больше, чем (4L)L , а число способов пометки ее ребер символами x1 , . . . , xn , x1 , . . . , xnне больше, чем (2n)L . Следовательно, K U (L, n) 6 UK (L, n) 6 (8nL)L .58Глава 2. Основные классы управляющих системЛемма доказана.Рассмотрим, в заключение, особенности функционирования КС с несколькими входами.
Будем считать, что в каждой вершине (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)-КС из неориентированныхконтактов по существу не отличается от функционированиясоответствующей двухполюсной КС с неразделенными по-§7. Эквивалентные преобразования контактных схем59люсами.В частности, показанная на рис.
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, ?? главы 2 эквивалентность КС Σ0 = Σ0 (x1 , . . . , xn ; a1 , . .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
