3 (1132839), страница 4
Текст из файла (страница 4)
Тогда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Введениеa01a0p...••v0•a1 •Σ0• aqaj •Σ00•v 00...•a001•a00sa)a01•a1 ••a001a0p...••v0aj1 •Σ0...aj2 •...• ajtv 00• aq••a00sb)Рис. 3.2: к доказательству леммы 3.1Введение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Введениеативности произведения матриц. Случай разделительностиКС Σ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̌)-КС Σ̌ в результате добавления но-Введение31•1•v0xi•vΣ̌•1•Σ̌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ВведениеЗаметим, что при этом разложение (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)Введение33xi••... ...••xi • ¬Ǔ•&•'zv1 v0∨•(vvxσi•... ...•Ǔ•vσ&•&•v(v•$wa)b)•xσi•... ...•Ǔvσ•∨•v(vc)Рис. 4.2: к моделированию операций присоединения контактов в классе СФЭ34Введениеа объединение Σ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 , . . . , f mL (Σ00 )6и для которой2L (Σ0 ).Метод каскадов позволяет по произвольной заданной системе функций алгебры логики F = (f1 , . . . , fm ), F ∈ P2m (n),строить (1, m)-КС ΣF , ΣF ∈ UK , и СФЭ UF , UF ∈ UC , которые реализуют F . Будем считать, что все ФАЛ f1 , f2 , . . . , fmсистемы F различны, отличны от констант, и для каждойБП xi , 1 6 i 6 n, среди них есть ФАЛ, существенно зависящая от xi .Разложим ФАЛ f1 , f2 , . .
. , fm сначала по БП x1 , потом поБП x2 и так далее. При этом построим последовательностиb i , состоящих из ФАЛ от БП xi , xi+1 , . . . , xn ,множеств Gi и Gгде i = 1, 2, . . . , n, такие, что1. Gi состоит из всех различных ФАЛ g (xi , . . . , xn ) видаg = fj (σ1 , .
. . , σi−1 , xi , xi+1 , . . . , xn ) ,где 1 6 j 6 m, (σ1 , . . . , σi−1 ) ∈ B i−1 ;b i состоит из всех различных функций g, g ∈ Gi , ко2. Gторые существенно зависят от xi .Легко видеть, чтоG1 = {f1 , . . . , fm } ,b n ⊆ {xn , xn } ,GВведение35b1 , . . . , Gb n не пусты и попарно не пересеа множества ФАЛ Gкаются.b i , где 1 6 i 6 n,Заметим, что любую ФАЛ g, g ∈ Gможно представить в виде (4.1)g = µ (xi , g0 , g1 ) = xi g0 ∨ xi g1 ,где gσ = g (σ, xi+1 , .
. . , xn ), и, следовательно, gσ ∈ Ǧi+1 ∪{0, 1} для всех σ, σ ∈ B. Если при этом для некоторогоσ, σ ∈ B, ФАЛ gσ равна 0, то вместо (4.1) будем использовать разложение (4.2)g = xσi gσ ,где gσ ∈ Ǧi+1 ∪ {1}.→−Построим КС Σ̌F , которая реализует систему ФАЛ G F ,b1 ∪ . . . ∪ Gb n с помощью операций присоединениягде GF = Gодного или двух противоположных контактов. При этом дляb i , реаликаждого i, i = n, (n−1), .
. . , 1, каждая ФАЛ g, g ∈ Gзуется согласно (4.1) ((4.2)) на выходе v, который при α =0, 1 (соответственно α = σ) соединен контактом вида xαi стем выходом vα , где реализуется ФАЛ gα = g (α, xi+1 , . . . , xn )так, как это показано на рис. 4.1a (соответственно рис. 4.1b).Заметим, что указанное присоединение одного или двухпротивоположенных контактов не изменяет ФАЛ, реализуемые в вершинах vα , α ∈ {0, 1}.Для получения искомой КС ΣF достаточно «снять» пометки с тех выходных вершин КС Σ̌F , в которых реализуются ФАЛ, отличные от f1 , .
. . , fm .Аналогичным образом по методу каскадов строится и→−СФЭ ǓF , реализующая систему ФАЛ G F , с той лишь разницей, что:1. сначала реализуются все ФАЛ вида xi , 1 6 i 6 n,которые встречаются в КС ΣF ;36Введение2. для всех i, i = (n − 1) , . . . , 1, разложение (4.1), гдеb i и g0 , g1 ∈ Ǧi+1 , реализуется так, как показаноg ∈Gна рис. 4.2a, а разложение (4.2), применяемое в случаеgσ = 0 (разложениеg = xσi ∨ gσ xσi = xσi ∨ gσ(4.4)в случае gσ = 1), — так, как показано на рис.
4.2b(соответственно 4.2c);3. каждая ФАЛ вида gσ xσi , используемая в предыдущемпункте при реализации разложений вида (4.1) или (4.2)для различных ФАЛ g, реализуется только один раз.Как и в случае КС, СФЭ UF , реализующая систему ФАЛ Fи построенная по методу каскадов, получается из СФЭ ǓFв результате «снятия» тех выходов, в которых реализуютсяФАЛ, отличные от ФАЛ из F .Пусть, например, F = (f1 , f2 ), гдеf1 = x1 x2 (x3 ⊕ x4 ) ∨ x1 (x2 ∨ x3 x4 ) ,f2 = x1 (x3 ⊕ x4 ) ∨ x1 x4 .Тогда:b 1 = G1 = {f1 , f2 } ;Gb 2 = {x2 (x3 ⊕ x4 ) , x2 ∨ x3 x4 } , G2 = Gb 2 ∪ {x3 ⊕ x4 , x4 } ;Gb 3 = {x3 ⊕ x4 , x3 x4 } ,b 3 ∪ {x4 } ;GG3 = Gb 4 = {x4 , x4 } .GНа рис. 4.3 показана построенная для данной системы ФАЛКС Σ̌F , вершины которой помечены сопоставленными имФАЛ, на рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
