ОК_Часть_3_2015_(320-328) (1132807), страница 4
Текст из файла (страница 4)
. . , fp соответственно, получается (1, 1)-КС, реализующая ФАЛ f10 f100 ∨· · ·∨fp0 fp00 , при правильном отождествлениивходов (выходов) КС в реализуемой ею матрице происходитпоразрядная дизъюнкция тех строк (соответственно столбцов), которые соответствуют отождествленным входам (соответственно выходам) и т. п.Легко видеть, что операция переименования входов (выходов) КС без отождествления, операция объединения КС,а также операция последовательного соединения (1, 1)-КСкорректны в любом случае.
В то же время параллельноесоединение (1, 1)-КС, при котором сначала отождествляются входы, а затем выходы соединяемых КС, не является,в общем случае, корректной операцией суперпозиции, хотяявляется при этом правильной суперпозицией, так как полученная КС реализует дизъюнкцию ФАЛ, реализуемых исходными КС. Заметим, что корректное дизъюнктированиевыходных ФАЛ можно осуществить с помощью стыковкиисходной КС с вентильной звездой (см. рис.
3.1c).Схема называется разделительной по входам (выходам),если ФАЛ проводимости между любыми ее различными входами (соответственно выходами) равна 0. Так (p, 1)-схемаΣ00 = Σ00 (y1 , . . . , yp ; z1 ), показанная на рисунке 3.1c, является разделительной по входам схемой, которая называетсявентильной звездой порядка p. Примером разделительнойпо выходам (входам) КС может служить (1, 2n ) (соответственно (2n , 1)) контактное дерево порядка n (см. рис.
1.1).§3. Некоторые модификации основных классов схем27Будем говорить, что КС Σ от БП x1 , . . . , xn разделительнана наборе α = (α1 , . . . , αn ) значений этих БП, если соответствующей разделительностью обладает сеть Σ|α . Следующее утверждение является обобщением известной леммыШеннона (см.
[32, 14]).Лемма 3.1. Пусть КС Σ является результатом стыковки вида Σ = Σ00 (Σ0 ), а F , F 0 и F 00 — матрицы, реализуемыеКС Σ, Σ0 и Σ00 соответственно. ТогдаF > F 0 · F 00 и F = F 0 · F 00 ,(3.2)если КС Σ00 разделительна по входам или КС Σ0 разделительна по выходам.Доказательство. Пусть КС Σ является сначала результатом бесповторной стыковки (p, q)-КС Σ0 и (q, s)-КС Σ00 от БПx1 , . .
. , xn . Пусть, кроме того, v 0 (v 00 ) — произвольная вершина КС Σ0 (соответственно Σ00 ), а ФАЛ fj0 (соответственно fj00 ),j ∈ [1, q], — ФАЛ проводимости от вершины v 0 к j-му выходу в КС Σ0 (соответственно от j-го входа к вершине v 00 вКС Σ00 ). Докажем, что для ФАЛ f — ФАЛ проводимости отвершины v 0 к вершине v 00 в КС Σ, – справедливо неравенствоf (x1 , . . . , xn ) > f10 · f100 ∨ · · · ∨ fq0 · fq00 ,(3.3)которое переходит в равенствоf (x1 , . . .
, xn ) = f10 · f100 ∨ · · · ∨ fq0 · fq00 ,(3.4)если КС Σ0 разделительна по выходам или КС Σ00 разделительна по входам.Действительно, пусть aj , j ∈ [1, q], — вершина КС Σ,которая получается в результате присоединения j-го входа КС Σ00 к j-му выходу КС Σ0 (см. рис. 3.2a). Справедливость неравенства (3.3) следует из того, что его правая28Глава 3. Синтез и сложность управляющих системa01a0p...••v0•a1 •Σ0• aqaj •Σ00•v 00...•a001•a00sa)a01•a1 ••a001a0p...••v0aj1 •Σ0...aj2 •...• ajtv 00• aq••a00sb)Рис.
3.2: к доказательству леммы 3.1§3. Некоторые модификации основных классов схем29часть описывает «суммарную» проводимость тех (v 0 − v 00 )цепей КС Σ, которые проходят через вершины a1 , . . . , aq ровно один раз (см. рис. 3.2a). Любая другая (v 0 − v 00 )-цепь КСΣ проходит через указанные вершины не меньше трех раз(см. рис. 3.2b) и в случае разделительности КС Σ0 по выходам или разделительности КС Σ00 по входам имеет нулевуюпроводимость.Из (3.3) и (3.4) непосредственно вытекает (3.2) с учетомтого, что при v 0 = a0i и v 00 = a00j , где i ∈ [1, p] и j ∈ [1, s], левая(правая) часть этих соотношений равна элементу матрицы F (соответственно F 0 · F 00 ), расположенному в i-й строкеи j-м столбце.Пусть теперь КС Σ получается из КС Σ00 в результатеприменения операции отождествления входов, то есть Σ эквивалентна бесповторной стыковке вида Σ00 (Σ0 ), где КС Σ0состоит из проводящей звезды и тождественных вершин.
Вэтом случае неравенство (3.2) имеет вид F > Fb00 , где матрица Fb00 получается из матрицы F 00 в результате поразрядной дизъюнкции строк, соответствующих отождествляемымвходам КС Σ00 , и по-прежнему переходит в равенство, еслиКС Σ00 разделительна по входам. В последнем случае, кроe 00 ,ме того, из аналогичного равенства, связанного с КС Σ00которая получается из КС Σ в результате объявления ееe 00 , следует развходов входами и, одновременно, выходами Σделительность КС Σ по входам.Заметим, наконец, что стыковка общего вида Σ = Σ00 (Σ0 )сводится к последовательномувыполнению отождествленияb 00 = Σ00 Σ̌00 и бесповторной стыковки видавходов вида Σb 00 (Σb 0 ), где КС Σ̌00 состоит из проводящей звезды и тожΣ=Σb 0 получается из КС Σ0 снятиемдественных вершин, а КС Σнекоторых выходов.
При этом неравенство (в случае разделительности КС Σ00 по входам равенство) (3.2) для КС Σ,Σ0 , Σ00 вытекает из установленных выше аналогичных соотb 00 , Σ̌00 , Σ00 и КС Σ, Σb 0, Σb 00 в силу ассоциношений для КС Σ30Глава 3. Синтез и сложность управляющих системативности произведения матриц.
Случай разделительностиКС Σ0 по выходам рассматривается аналогично.Лемма доказана.Следствие 1. В случае разделительности КС Σ00 по входам в каждой вершине КС Σ, Σ = Σ00 (Σ), которая соответствует выходу КС Σ0 , реализуется тот же самый столбецФАЛ, что и в КС Σ0 , то есть рассматриваемая суперпозиция является корректной.Действительно, полагая v 0 = a0i и v 00 = aj , где i ∈ [1, p],а j ∈ [1, q], из (3.4) получим требуемое равенство f = fj0 .Случай стыковки общего вида рассматривается аналогично.Следствие 2.
Равенство (3.2) выполняется на любом наборе значений БП, на котором КС Σ00 разделительна по входам или КС Σ0 разделительна по выходам.§4Каскадные контактные схемы и схемы из функциональных элементов. Метод каскадов и примеры его применения. Метод ШеннонаПриведенные в §1 простейшие методы синтеза позволяютстроить формулы и π-схемы, специфика которых не допускает многократного использования «промежуточных результатов». Метод каскадов [21] является достаточно простым ив то же время довольно эффективным методом синтеза какКС, так и СФЭ, который позволяет это делать.
Он связанс последовательным разложением заданных ФАЛ по БП ирекурсивным построением схемы, реализующей эти ФАЛ.Рассмотрим сначала специальный частный случай корректной суперпозиции КС — операцию присоединения к выходам одновходовой КС одного или двух противоположныхконтактов, которая заключается в следующем. Пусть (1, m)КС Σ получается из (1, m̌)-КС Σ̌ в результате добавления но-§4. Метод каскадов для КС и СФЭ•1•v0xi•vΣ̌•311•Σ̌xi•xσivσ•vv1a)b)Рис. 4.1: присоединение одного или двух противоположныхконтактоввой выходной вершины v, которая соединяется с выходнымивершинами v0 и v1 КС Σ̌ контактами xi и xi соответственно(см.
рис. 4.1a). Тогда в вершинах v0 и v1 КС Σ в силу нулевой проводимости между входами присоединяемой (2, 1)-КСреализуются те же самые ФАЛ g0 и g1 , что и в КС Σ̌, а ввершине v — ФАЛ g видаg = µ (xi , g0 , g1 ) = xi g0 ∨ xi g1 .(4.1)Аналогичные соотношения будут справедливы и тогда,когда вершина v КС Σ связана с вершиной vσ только однимконтактом вида xσi , σ ∈ {0, 1} (см. рис. 4.1b). В этом случаев вершине v КС Σ реализуется ФАЛg = xσi gσ ,(4.2)а в вершине vσ по-прежнему реализуется ФАЛ gσ .Описанные выше операции присоединения одного илидвух противоположенных контактов очевидным образом распространяются на случай КС с несколькими входами.
Крометого, они допускают моделирование в классе СФЭ в базисеБ0 . Так, переход от СФЭ Ǔ , Ǔ ∈ UC , которая реализует ввыходных вершинах v0 и v1 ФАЛ g0 и g1 соответственно, кСФЭ U, U ∈ UC , которая реализует ФАЛ g, удовлетворяющую (4.1) ((4.2)), показан на рис. 4.2a (соответственно 4.2b).32Глава 3. Синтез и сложность управляющих системЗаметим, что при этом разложение (4.1) в случае gσ ≡ 1 эквивалентно представлениюg = xσi ∨ gσ ,схемная реализация которого показана на рис.
4.2c.Определим, далее, каскадную КС как приведенную КСбез изолированных полюсов, которая может быть полученаиз системы тождественных вершин в результате ряда операций присоединения одного или двух противоположных контактов и операций переименования выходов.
Каскадная КС(ККС) считается полной, если она была построена без использования операции присоединения одного контакта. Так,например, к числу ККС относится контактное дерево, показанное на рис. 1.1, причем соответствующее ему (2n , 1)-КДявляется полной ККС.Заметим, далее, что, в силу отмеченных выше свойстврассматриваемых операций присоединения контактов, ККСимеет нулевые ФАЛ проводимости между своими входами.Отсюда следует, что в каждой вершине ККС реализуетсястолбец, в котором никакие две ФАЛ не обращаются в единицу одновременно, причем в случае полной ККС дизъюнкция всех ФАЛ этого столбца дает 1. Так, в частности, вкаждой вершине полной ККС с двумя входами реализуетсястолбец из двух противоположных ФАЛ.Вершина ККС, введенная в нее с помощью операцииприсоединения одного контакта, называется неполной вершиной этой ККС. Будем говорить, что ККС Σ00 являетсядополнением неполной ККС Σ0 , если она получается в результате соединения всех неполных вершин Σ0 отсутствующими в них контактами с новым входом, удаления всех«старых» входов и перехода к соответствующей приведенной КС.
При этом, очевидно,L Σ00 6 2L Σ0 ,(4.3)§4. Метод каскадов для КС и СФЭ33xi••... ...••xi • ¬Ǔ•&•'zv1 v0∨•(vvxσi•... ...•Ǔ•vσ&•&•v(v•$wa)b)•xσi•... ...•Ǔvσ•∨•v(vc)Рис. 4.2: к моделированию операций присоединения контактов в классе СФЭ34Глава 3. Синтез и сложность управляющих система объединение Σ0 и Σ00 является полной ККС. ДополнениеΣ00 к полной ККС Σ с 1 входом будем называть инверснойк Σ0 ККС.
Заметим, что ККС Σ00 , в силу отмеченных выше0свойств полных ККС, реализует систему ФАЛ F , если ККСΣ0 реализует систему ФАЛ F 0 . Таким образом, в силу (4.3)справедливо следующее утверждениеЛемма 4.1. Если (1, m)-ККС Σ0 реализует систему ФАЛ0 ), то существует (1, m)-ККС Σ00 , котораяF 0 = (f10 , . . . , fm000реализует систему ФАЛ F = f 1 , .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
