OK_metodichka_part_3 (1132798), страница 2
Текст из файла (страница 2)
(1.6)nДоказательство. В классе UC построим схемный дешифратор порядка n, удовлетворяющий первому неравенству (??),следующим образом:§1. Задача синтеза111. разобьем набор БП 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 является(1, 2n )-контактное дерево, показанное на рисунке 6.4a §6 главы 2, а искомым контактным мультиплексором порядка n —π-схема, приведенная там же на рис.
6.6b. Заметим, чтосложность схем, показанных на рис. 6.4a и 6.6b, равна 2n+1 −2 и 3 · 2n − 2 соответственно, то есть удовлетворяет неравенствам (??) и (1.5), причем число размыкающих контактов вкаждой из них равно 2n − 1.В результате моделирования π-схемы, показанной на ??b,можно построить бесповторную по информационным БПформулу (см. ??,?? главы 2)Fn (x1 , . . .
, xn , y0 , . . . , y2n −1 ) =! !___=xσ1 1 xσ2 2 · · ·xσnn yν(σ1 ,...,σn ) · · · ,σ1 ∈Bσ2 ∈Bσn ∈Bкоторая удовлетворяет второму неравенству (1.5), так какреализует ФАЛ µn , имеет сложность 4 · 2n − 3 и альтернирование 2n − 1.Неравенства (1.6) при n = 1, очевидно, выполняются.Искомой СФЭ, реализующей линейную ФАЛ `n , n > 2, сосложностью (1.6), является СФЭ Σ⊕n , показанная на рис. ??12Глава 3. Синтез и сложность управляющих системглавы 2. Аналогичная СФЭ для ФАЛ `n получается в результате замены ФЭ & на ФЭ ∨ и ФЭ ∨ на ФЭ & в первой⊕подсхеме вида Σ⊕2 схемы Σn (см. рис. ??b главы 2).Лемма доказана.Рассмотрим, далее, некоторые нижние оценки сложности ФАЛ и примеры минимальных схем.Лемма 1.4. Если ФАЛ f (x1 , . .
. , xn ) существенно зависитот всех своих БП, тоLC (f ) > n − 1,LK (f ) > n.(1.7)Если при этом ФАЛ f не является монотонной ФАЛ (каждая БП xi , i ∈ [1, k], не является ни монотонной, ни инмонотонной БП ФАЛ f ), тоLC (f ) > n(соответственно LK (f ) > n + k).(1.8)Доказательство. Пусть Σf — минимальная по сложностиСФЭ из UC , реализующая ФАЛ f . Из существенной зависимости ФАЛ f от БП x1 , . . . , xn следует, что R (Σf ) > n, ипоэтому, в силу соотношений ?? главы 2,LC (f ) > L&, ∨ (Σf ) > n − 1.Если же, кроме того, ФАЛ f не является монотоннойФАЛ, то схема Σf должна содержать хотя бы один ФЭ ¬ и,следовательно, в указанном случаеLC (f ) = L (Σf ) > n.Таким образом, первые из неравенств (1.7) и (1.8) доказаны.Пусть теперь Σf — минимальная по сложности (1, 1)-КС,реализующая ФАЛ f . Из существенной зависимости ФАЛ f§1.
Задача синтеза13от БП 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.Лемма 1.5.
Для системы F = (f1 , . . . , fm ), состоящей изпопарно различных ФАЛ отличных от констант (от переменных), справедливо неравенствоLK (F ) > m(соответственно LCБ (F ) > m).(1.9)Доказательство. Второе из неравенств (1.9) вытекает изтого, что все ФАЛ fi , i = 1, . . . , m, реализуются на попарно различных выходах СФЭ, отличных от ее входов.Пусть теперь ΣF — приведенная (1, m)-КС, реализующая систему ФАЛ F . Из приведенности ΣF и условий леммы вытекает, что ΣF — связный граф с не менее чем (m + 1)вершиной, и поэтому, в силу неравенства ??главы 2,L (ΣF ) > |V (ΣF )| − 1 > m.Лемма доказана.14Глава 3. Синтез и сложность управляющих системСледствие.−→ L Q n > 2n ,−→ LC J n > 2n ,−→nLCP(n)> 22 − n,2БC−→ Q n > 2n ,L−→ LK J n > 2n ,−→nLK P 2 (n) > 22 − 2.KПусть вершина w СФЭ Σ не достижима из ее вершины v,а СФЭ Σ0 получается из СФЭ Σ в результате удаления вершины v, объявления вершины w начальной вершиной всехисходивших из v дуг и переноса в вершину w всех выходных БП, приписанных вершине v.
Тогда СФЭ Σ0 считаетсярезультатом применения к СФЭ Σ операции присоединениявершины v к вершине w. Заметим, что для любых двух вершин схемы одну из них всегда можно присоединить к другой. Две вершины СФЭ называются эквивалентными, еслив них реализуются равные ФАЛ. Применяя к СФЭ Σ операцию присоединения одной из двух эквивалентных вершинк другой, мы получим СФЭ Σ0 , которая, очевидно, эквивалентна Σ.Приведенная схема называется строго приведенной, если в ней нет эквивалентных вершин. Из любой СФЭ можнополучить эквивалентную ей строго приведенную СФЭ с помощью операции присоединения эквивалентных вершин иоперации удаления висячих вершин.Аналогичным образом определяется операция присоединения вершин в КС, с той лишь разницей, что на нее не накладываются какие-либо ограничения, связанные с достижимостью вершин.Лемма 1.6.
Для каждого натурального n в UCБ существует универсальная СФЭ Un порядка n, сложность которойnравна 22 − n.§2. Метод каскадов для КС и СФЭ15Доказательство. В силу полноты базиса, в UCБ существует система формул Σ от БП x1 , . . . , xn , которая реализу→−ет систему ФАЛ P 2 (n).
Искомая СФЭ Un является строго приведенной СФЭ, которая эквивалентна Σ и получаетсяиз нее в результате применения операций присоединения эквивалентных вершин, а также операций удаления висячихвершин (см. ?? главы 2). Действительно, из построения следует, что число всех вершин СФЭ Un , включая n ее входов,nравно 22 и поэтомуnL (Un ) = 22 − n.Лемма доказана.Замечание. В силу следствия из леммы 1.5, построенная схема Un является минимальной по сложности универсальнойСФЭ порядка n, и поэтому, в частности,−→nLCP(n)= 22 − n.2Б§2Метод каскадов для контактных схем исхем из функциональных элементов.Метод ШеннонаПриведенные в §1 простейшие методы синтеза позволяютстроить формулы и π-схемы, специфика которых не допускает многократного использования «промежуточных результатов».
Метод каскадов [20] является достаточно простым ив то же время довольно эффективным методом синтеза какКС, так и СФЭ, который позволяет это делать. Он связанс последовательным разложением заданных ФАЛ по БП ирекурсивным построением схемы, реализующей эти ФАЛ.Для построения соответствующей контактной схемы используется специальный частный случай корректной суперпозиции КС (см. §9 главы 2) — операции присоединения16Глава 3. Синтез и сложность управляющих системqqqqq •QvQ0qqQQQxiqQQQqqq1 •qMMMM Σ̌mmm• vmMMMmm ximmMMM •MM v1qqqqqqqqxσiqqq1 •MqMMM Σ̌ • vσMMMMMMMMa)•vb)Рис.
2.1: присоединение одного или двух противоположныхконтактоводного или двух противоположных контактов, которая заключается в следующем. Пусть (1, m)-КС Σ получается из(1, m̌)-КС Σ̌ в результате добавления новой выходной вершины v, которая соединяется с выходными вершинами v0 иv1 КС Σ̌ контактами xi и xi соответственно (см. рис.
2.1a).Тогда в вершинах v0 и v1 КС Σ в силу разделительности повходам присоединяемой (2, 1)-КС реализуются те же самыеФАЛ g0 и g1 , что и в КС Σ̌, а в вершине v — ФАЛ g видаg = µ (xi , g0 , g1 ) = xi g0 ∨ xi g1 .(2.1)Аналогичные соотношения будут справедливы и тогда,когда вершина v КС Σ связана с КС Σ̌ только одним контактом вида xσi , σ ∈ {0, 1}, соединяющим ее с вершиной vσ(см. рис. 2.1b). В этом случае в вершине v КС Σ реализуетсяФАЛg = xσi gσ .(2.2)Переход от СФЭ Ǔ , Ǔ ∈ UC , которая реализует в выходных вершинах v0 и v1 ФАЛ g0 и g1 соответственно, к СФЭU, U ∈ UC , которая реализует ФАЛ g, удовлетворяющую(2.1) ((2.2)), показан на рис. 2.2a (соответственно 2.2b).Определим сначала каскадную КС как приведенную КСбез изолированных полюсов, которая может быть полученаиз системы тождественных вершин в результате ряда опера-§2.
Метод каскадов для КС и СФЭ17xi••... ...••xi • ¬Ǔ•&v1 v0' QQ•zQQxσi•... ...•Ǔ•vσ&•&•(vvl•w$QQQ∨ lllll(•vlva)b)•xσi•... ...•Ǔvσ•∨•(vvc)Рис. 2.2: к описанию метода каскадов для СФЭ18Глава 3. Синтез и сложность управляющих системций присоединения одного или двух противоположных контактов и операций переименования выходов. Каскадная КС(ККС) считается полной, если она была построена без использования операции присоединения одного контакта. Так,например, КС, показанная на рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
