ОК_Часть_3_2015_(320-328) (1132807), страница 2
Текст из файла (страница 2)
Так как при удалении вершиныудаляются и все инцидентные ей контакты, тоL (Σf ) 6 2 (2n − 1) − (2n − |Nf |) = 2n + |Nf | − 2.Формула Ff получается в результате моделирования построенной π-схемы Σf в классе формул с поднятыми отрицаниями (см. §2 гл. 2), и поэтомуR (Ff ) = L (Σf ) ,L (Ff ) = R (Ff ) + L− (Σf ) − 1,где L− (Σf ) — число размыкающих контактов в схеме Σ.Следовательно,L (Ff ) 6 L (Σf ) + 2n − 2 6 2n+1 + |Nf | − 4,так как число размыкающих контактов в КД порядка n равно 2n − 1.Лемма доказана.Следствие.Lπ (n) 6 2n+1 − 2,(1.2)LΦ (n) 6 3 · 2n − 4.(1.3)К схемам, полученным на основе простейших методовсинтеза, полезно применять с целью уменьшения их сложности эквивалентные преобразования и, в частности, следующие операции приведения.Пусть вершина w СФЭ Σ не достижима из ее вершины v,а СФЭ Σ0 получается из СФЭ Σ в результате удаления вершины v, объявления вершины w начальной вершиной всехисходивших из v дуг и переноса в вершину w всех выходных БП, приписанных вершине v.
Тогда СФЭ Σ0 считаетсярезультатом применения к СФЭ Σ операции присоединения12Глава 3. Синтез и сложность управляющих системвершины v к вершине w. Заметим, что для любых двух вершин схемы одну из них всегда можно присоединить к другой. Две вершины СФЭ называются эквивалентными, еслив них реализуются равные ФАЛ. Применяя к СФЭ Σ операцию присоединения одной из двух эквивалентных вершинк другой, мы получим СФЭ Σ0 , которая, очевидно, эквивалентна Σ.Приведенная схема называется строго приведенной, если в ней нет эквивалентных вершин. Из любой СФЭ можнополучить эквивалентную ей строго приведенную СФЭ с помощью операции присоединения эквивалентных вершин иоперации удаления висячих вершин.Аналогичным образом определяется операция присоединения вершин в КС, с той лишь разницей, что на нее не накладываются какие-либо ограничения, связанные с достижимостью вершин.→−Для множества ФАЛ G, G ⊆ P2 (n), через G будем обозначать систему, состоящую из всех различных ФАЛ множества G, упорядоченных в соответствии с номерами их столб→−цов значений.
При этом систему ФАЛ P 2 (n) будем называть универсальной системой порядка n.Довольно часто задачу синтеза приходится решать дляследующих ФАЛ и систем ФАЛ:1. линейной ФАЛ порядка n, то есть ФАЛ `n или ФАЛ `n ;2. мультиплексорной ФАЛ µn порядка n;→−→−3. дешифратора Q n (дизъюнктивного дешифратора J n )порядка n;→−4. универсальной системы P 2 (n) порядка n.Лемма 1.3. Для каждого натурального n в UCБ существу→−ет СФЭ Un , которая реализует систему ФАЛ P 2 (n) иnсложность которой равна 22 − n.§2. Нижние оценки13Доказательство. В силу полноты базиса, в UCБ существует система формул Σ от БП x1 , .
. . , xn , которая реализу→−ет систему ФАЛ P 2 (n). Искомая СФЭ Un является строго приведенной СФЭ, которая эквивалентна Σ и получаетсяиз нее в результате применения операций присоединения эквивалентных вершин, а также операций удаления висячихвершин (см. §4 главы 2). Действительно, из построения следует, что число всех вершин СФЭ Un , включая n ее входов,nравно 22 и поэтомуnL (Un ) = 22 − n.Лемма доказана.Следствие.§2→−nLCP(n)6 22 − n.2БНижние оценки сложности ФАЛ, реализация некоторых ФАЛ и минимальность некоторых схем.Рассмотрим сначала простейшие нижние оценки сложностиФАЛ и связанные с ними примеры минимальных схем.Лемма 2.1.
Если ФАЛ f (x1 , . . . , xn ) существенно зависитот всех своих БП, тоLC (f ) > n − 1,LK (f ) > n.(2.1)Если при этом ФАЛ f не является монотонной ФАЛ (каждая БП xi , i ∈ [1, k], не является ни монотонной, ни инмонотонной БП ФАЛ f ), тоLC (f ) > n(соответственно LK (f ) > n + k).(2.2)14Глава 3. Синтез и сложность управляющих системДоказательство.
Пусть Σf — минимальная по сложностиСФЭ из UC , реализующая ФАЛ f . Из существенной зависимости ФАЛ f от БП x1 , . . . , xn следует, что R (Σf ) > n, ипоэтому, в силу соотношений (2.6) главы 2,LC (f ) > L&, ∨ (Σf ) > n − 1.Если же, кроме того, ФАЛ f не является монотоннойФАЛ, то схема Σf должна содержать хотя бы один ФЭ ¬ и,следовательно, в указанном случаеLC (f ) = L (Σf ) > n.Таким образом, первые из неравенств (2.1) и (2.2) доказаны.Пусть теперь Σf — минимальная по сложности (1, 1)-КС,реализующая ФАЛ f .
Из существенной зависимости ФАЛ fот БП xi , i ∈ [1, n], следует, что либо контакт вида xi , либоконтакт вида xi встречается в КС Σf , и поэтомуLK (f ) = L (Σf ) > n.Если же, кроме того, БП xi , i ∈ [1, k], не является ни монотонной, ни инмонотонной БП ФАЛ f , то как контакт видаxi , так и контакт вида xi входят в Σf , и, следовательно, вданном случаеLK (f ) = L (Σf ) > n + k.Лемма доказана.Следствие.LC (`n ) > n,LK (`n ) > 2n,LC (µn ) > 2n + n,LK (µn ) > 2n + 2n.§2. Нижние оценки15[0,n−1]Замечание. Нижние оценки сложности ФАЛ f = sn,вытекающие из леммы 2.1, доказывают минимальность πсхемы, моделирующей ЭД x1 ∨ · · · ∨ xn = f , в классе КС иминиальность формулы (x1 .
. . xn ) = f в классе СФЭ, чтоустанавливает равенства LK (f ) = n и LC (f ) = n.Лемма 2.2. Для системы F = (f1 , . . . , fm ), состоящей изпопарно различных ФАЛ отличных от констант (от переменных), справедливо неравенствоLK (F ) > m(соответственно LCБ (F ) > m).(2.3)Доказательство. Второе из неравенств (2.3) вытекает изтого, что все ФАЛ fi , i = 1, . . . , m, реализуются на попарно различных выходах СФЭ, отличных от ее входов.Пусть теперь ΣF — приведенная (1, m)-КС, реализующая систему ФАЛ F . Из приведенности ΣF и условий леммы вытекает, что ΣF — связный граф с не менее чем (m + 1)вершиной, и поэтому, в силу неравенства (1.2) главы 2,L (ΣF ) > |V (ΣF )| − 1 > m.Лемма доказана.Следствие.→− LC Q n > 2 n ,→− LC J n > 2 n ,→−nLCP(n)> 22 − n,2Б→− L K Q n > 2n ,→− L K J n > 2n ,→−nLK P 2 (n) > 22 − 2.Замечание. В силу следствия универсальная СФЭ Un , построенная в лемме 1.3, является минимальной по сложностиСФЭ в классе UCБ.16Глава 3.
Синтез и сложность управляющих системРассмотрим некоторые схемные реализации и соответствующие им верхние оценки сложности для некоторых ФАЛи систем ФАЛ. Будем, как обычно, называть (схемным) мультиплексором, дешифратором, дизъюнктивным дешифратором и универсальным многополюсником любую схему, которая реализует соответствующую систему ФАЛ.Лемма 2.3. Для любого натурального n выполняются неравенства:nn→−→−LC ( Q n ) 6 2n + O(n · 2 2 ), LC ( J n ) 6 2n + O(n · 2 2 ); (2.4)→−LK ( Q n ) 6 2n+1 − 2;(2.5)Lπ (µn ) 6 3 · 2n − 2,LC (`n ) 6 4n − 4,LΦ (µn ) 6 2n+2 − 3;(2.6) 1LC (`n ) 6 4n − 4 +. (2.7)nДоказательство.
В классе UC построим схемный дешифратор порядка n, удовлетворяющий первому неравенству (2.4),следующим образом:1. разобьем набор БП X(n) на группы x0 == (x1 , . . . , xq ), x00 = (xq+1 , . . . , xn ), где q = dn/2e;2. возьмем дешифраторы Σ0 и Σ00 от БП x0 и x00 порядкаq и (n − q) соответственно, реализующие каждую своюЭК по лемме 1.1;3. объединим СФЭ Σ0 и Σ00 , после чего конъюнктируемкаждый выход Σ0 с каждым выходом Σ00 , а выходы всехиспользованных для этого 2n ФЭ & (и только их) объявим выходами искомого дешифратора.Аналогичным образом строится дизъюнктивный схемный дешифратор порядка n, удовлетворяющий второму неравенству (2.4).§2.
Нижние оценки17xn•xn••x1•x2x2••x2••a1x1x2y0y1a2y2n −2•xn•xn•y2n −1•Рис. 2.1: π-схема для ФАЛ µnИскомым контактным дешифратором порядка n является (1, 2n )-контактное дерево, показанное на рис. 1.1, а искомым контактным мультиплексором порядка n являетсяπ-схема, приведенная на рис. 2.1.
Заметим, что сложностьсхем, показанных на рис. 1.1 и 2.1, равна 2n+1 − 2 и 3 · 2n − 2соответственно, то есть удовлетворяет неравенствам (2.5) и(2.6), причем число размыкающих контактов в каждой изних равно 2n − 1.В результате моделирования указанной π-схемы можнопостроить бесповторную по информационным БП формулуFn (x1 , . . . , xn , y0 , . . . , y2n −1 ) =! !___=xσ1 1 xσ2 2 · · ·xσnn yν(σ1 ,...,σn ) · · · ,σ1 ∈Bσ2 ∈Bσn ∈Bкоторая удовлетворяет второму неравенству (2.6), так как18Глава 3.
Синтез и сложность управляющих системx1x2•x1x2•••Σ⊕2x3•&•w•'¬∨Σ⊕2•...•z1 &xn•Σ⊕2z1a)b)Рис. 2.2: СФЭ для ФАЛ `2 и `nреализует ФАЛ µn и имеет сложность 4 · 2n − 3.Неравенства (2.7) при n = 1, очевидно, выполняются.Искомой СФЭ, реализующей линейную ФАЛ `n , n > 2,со сложностью (2.7), является СФЭ Σ⊕n , показанная нарис. 2.2a,b. Аналогичная СФЭ для ФАЛ `n получается в результате замены ФЭ & на ФЭ ∨ и ФЭ ∨ на ФЭ & в первой⊕подсхеме вида Σ⊕2 схемы Σn (см. рис. 2.2a).Лемма доказана.Следствие.→−→−LС ( Q n ) ∼ LС ( J n ) ∼ 2n .Лемма 2.4.
Если система ФАЛ F = (f1 , . . . , fm ) состоит из попарно различных ФАЛ от БП X(n), отличных§2. Нижние оценки19от 0 и 1, тоKL (F ) > 21−nmXNf .jj=1Доказательство. Возьмем приведенную (1, m)-КС Σ, реализующую систему ФАЛ F , и заметим, что при любом α, α ∈B n , в сети Σ|α имеется связная компонента, которая содержит вход Σ и те ее выходы, где реализуемые ФАЛ обращаются в 1 на наборе α.
Из неравенства (1.2) главы 2 следует,что при этом|E (Σ|α )| > f1 (α) + · · · + fm (α).Суммируя полученное неравенство по всем наборам α, α ∈B n , придем к неравенству2n−1 L(Σ) >mXNf ,jj=1из которого вытекает неравенство леммы.Лемма доказана.Следствие.LK (Jn ) > 2n+1 − 2.Замечание. В силу следствия (1, 4)-КС с входом a, котораясостоит из двух непересекающихся по внутренним вершинам(a − a)-цепей (циклов) длины 3 с ЭК проводимости x1 x2 x1и x1 x2 x1 , является минимальным дизъюнктивным контактным дешифратором порядка 2.Лемма 2.5.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
