2 (1132838), страница 8
Текст из файла (страница 8)
6.2aи 6.2b), а аналогичный ориентированный контакт — какМОП-транзистор соответствующего типа с диодом Шоттки [17, 23]. Кроме того, ориентированный контакт вида xσi ,идущий из вершины v в вершину u (см. рис. 6.1c), часторассматривают как команду условного перехода из v в u,который выполняется, если xi = σ.Сеть Σ с входами a01 , . . . , a0p и выходами a001 , . . . , a00q , в которой все ребра (дуги) помечены переменными x1 , . . . , xn илиих отрицаниями x1 , . . . , xn , называется (p, q)-контактнойсхемой (КС) от БП x1 , . . .
, xn и обозначается Σ == Σ (x1 , . . . , xn ) или Σ = Σ x1 , . . . , xn ; a01 , . . . , a0p ; a001 , . . . , a00q .При этом число контактов называется сложностью КС Σи обозначается через L (Σ). На рис. 6.3a–c показаны некоторые конкретные КС от БП x1 , x2 , x3 с входом a1 и выходамиa2 , a3 .Пусть Σ — КС от БП X (n) и α = (α1 , . . . , αn ) — набор из B n . Определим сеть Σ|α как сеть, получающуюсяиз Σ в результате удаления всех ребер (дуг) с пометкамиxα1 1 , . . . , xαnn , то есть ребер, которые не проводят на наборе α, и снятия пометок с остальных ребер Σ. Для вершинv и u КС Σ введем функцию проводимости от вершины vк вершине u как ФАЛ gv,u (x1 , .
. . , xn ), которая равна 1 нанаборе α = (α1 , . . . , αn ) ∈ B n тогда и только тогда, когдав сети Σ|α существует (v − u)-цепь, то есть тогда и только тогда, когда в Σ имеется цепь из проводящих на набореα контактов вида xα1 1 , . . . , xαnn , идущая из v в u. Будем говорить также, что ФАЛ gv,u является функцией достижимости вершины u из вершины v, или, иначе, реализуетсямежду вершинами v и u. Из определения следует, что длянахождения ФАЛ gv,u (x1 , . . . , xn ) достаточно просмотретьвсе наборы α, α ∈ B n , и для каждого из них выяснить наличие или отсутствие в Σ цепи, состоящей из проводящихВведение51vs3sx1s v1v2 sa2a1x1x1x1s v1x2 v2x2a1x1x2v4sx3sa)C2C1sa2C3b)a1 svsx1x1sx2sx3s a3x1x2x3x1x2x3sx2sx3sa2c)Рис.
6.3: некоторые КС от БП x1 , x2 , x3на наборе α контактов, которая идет из v в u. Так, просматривая все наборы значений БП x1 , x2 , можно убедиться втом, что ФАЛ проводимости gv1 ,v2 (x1 , x2 ) в КС Σ, показанной на рис. 6.3a, равна x1 ⊕ x2 , а ФАЛ проводимости gv3 ,v4равна 0.Будем считать, что в каждой вершине (1, m)-КСΣ(x1 , . .
. , xn ; a1 ; a2 , . . . , am+1 ) реализуется ФАЛ проводимости от входа a1 к этой вершине и что Σ реализует систему ФАЛ F = (f1 , . . . , fm ), где fj — ФАЛ проводимости от a1 к выходу с пометкой aj+1 , j ∈ [1, m].52ВведениеПри этом, очевидно, в вершине a1 реализуется ФАЛ 1,которую в дальнейшем по умолчанию будем использовать в качестве пометки единственного входа (1, m)-КС.Так, КС, изображенные на рис. 6.3a, 6.3b и 6.3c, реализуют ФАЛ x1 ⊕ x2 , H (x1 , x2 , x3 ) и набор ФАЛ(x1 ⊕ x2 ⊕ x3 , x1 ⊕ x2 ⊕ x3 ⊕ 1) соответственно. На рис. 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), и нулевым (соответственно единичным) в противном случае. Заметим, что в результате приведения подобных (см. §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Введение53xn• a0xn• a1•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Введение(обращается в 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) тоже является π-схемой. Заметим,Введение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Введение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 — мультиплексорнуюВведение57•x2x1x3a1x2a2x3•a)xn•xn••x1•x2x2••x2•y0•a1x1x2y1a2y2n −2•xn•xn••b)Рис. 6.7: примеры π-схемy2n −158ВведениеФАЛ порядка 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) будет выполняться.Введение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).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
