ОК_Часть_2_2015_(320-328)_v03-09 (1132806), страница 8
Текст из файла (страница 8)
Изоморфные КС, очевидно, эквивалентны.Для множества 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), и нулевым (соответственно единичным) в противном случае. Заметим, что в результате приведения подобных (см. §4) отличная от 0 ФАЛ K (C) и отличная от 1 ФАЛ J (C) могут быть преобразованы в ЭК иЭД соответственно.
Очевидно, также, чтоK C 0 > K (C) и J C 0 6 J (C) ,если C 0 ⊆ C.Из введенных определений (см. также §1) следует, чтоФАЛ g, реализуемая КС Σ (x1 , . . . , xn ; a1 ; a2 ), обращается в 1§6. Контактные схемы и π-схемы, оценка их числаxn• a0xn• a153•x1•x2x2••x2••1•x1x2...ai•/ xσ1 . . . xσnn1•xn• a2n −2•xn• a2n −1a)a0 •xn•a1 •a2n −2 •xn•x2••x2x2•xn•x1•x1•ax2•a2n −1 •xnb)Рис. 6.4: (1, 2n )- и (2n , 1)- контактные деревья порядка n54Глава 2. Основные классы управляющих систем(обращается в 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) может быть преобразована в ДНФ, а вторая — в КНФ, в результате приведения подобных (см. §3), если 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.6b и 6.6c) тоже является π-схемой. Заметим,§6. Контактные схемы и π-схемы, оценка их числа55C1a1a2Cta)a1•···S1a2•Spb)Рис. 6.5: КС, моделирующие ДНФ и КНФчто при этом вход (выход) Σ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 с поднятыми отрицаниями, то π-схемеΣ0 (Σ00 ), получающейся в результате параллельного (соответственно последовательного) соединения Σ1 и Σ2 , сопоставим формулу F0 = F1 ∨ F2 (соответственно F00 = F1 &F2 ).56Глава 2. Основные классы управляющих системa1xσiΣ1a2Σ0:a1a2Σ2a)b)Σ00 : a1Σ1•Σ2a2c)Рис. 6.6: к определению π-схемыПри этом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.7b — π-схема, которая построена на основе контактного дерева и реализует ФАЛ µn — мультиплексорную§6. Контактные схемы и π-схемы, оценка их числа•x2x1x3a1x257a2x3•a)xn•xn••x1•x2x2••x2•y0•a1x1x2y1a2y2n −2•xn•xn••b)Рис. 6.7: примеры π-схемy2n −158Глава 2. Основные классы управляющих системФАЛ порядка 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. Контактные схемы и π-схемы, оценка их числа59Лемма 6.2. При любых натуральных L и n выполняетсянеравенствоkUπ (L, n)k 6 (12n)L .(6.2)Доказательство. В силу леммы 6.1, достаточно доказать,что число попарно не эквивалентных формул F (x1 , . . . , xn )с поднятыми отрицаниями над базисом Б0 , для которыхR (F) 6 L, не превосходит (12n)L .
Требуемая оценка вытекает из следствия к лемме 4.2.Лемма доказана.Лемма 6.3. При любых натуральных L и n выполняетсянеравенство KU (L, n) 6 (8nL)L .Доказательство. Возьмем произвольную КС Σ=K= Σ(x1 , . . . , xn ; a1 ; a2 ), Σ ∈ U (L, n), и выделим в нейостовное дерево D с корнем a2 так, чтобы в D вошли всеинцидентные a2 контакты Σ, а вершина a1 была листом D.Пусть, далее, D0 — связанное с D остовное наддерево КСΣ, которое получается путем присоединения каждого изне вошедших в D ребер Σ к одной из своих концевых вершин, отличной от a1 (см. §1).
Рассмотрим ориентированноеупорядоченное дерево 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Глава 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 , .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
