ОК_Часть_3_2015_(320-328) (1132807), страница 3
Текст из файла (страница 3)
Если для ФАЛ f , f ∈ P2 (n), и для любого σ,σ ∈ B, ФАЛ fσ (x1 , . . . , xn−1 , σ) 6≡ 0, 1, тоCCLC&,∨ (f ) > min{L&,∨ (f0 ), L&,∨ (f1 )} + 2.(2.8)20Глава 3. Синтез и сложность управляющих системДоказательство. Пусть Σ — минимальная по числу ФЭ &и ∨ СФЭ из класса UC , которая реализует ФАЛ f и котораяне содержит цепочек из двух последовательно соединенныхФЭ ¬.
Из условия леммы следует, что выход ФЭ ¬, присоединённого к входу xn СФЭ Σ не может быть её выходом.Пусть цепь C соединяет вход xn СФЭ Σ с её выходом z1и пусть константа σ, σ ∈ B, равна 0 тогда и только тогда,когда БП xn подается в C либо на вход ФЭ &, либо на входФЭ ¬, к выходу которого в C присоединён ФЭ ∨.b которая реализует ФАЛ fσ , fσ 6≡ 0, 1,Рассмотрим СФЭ Σ,и получена из СФЭ Σ в результате подстановки xn = σ, атакже последующего ЭП на основе тождеств τ ПК (см. §5гл. 2) вплоть до устранения всех вхождений констант. Убедимся в том, что при указанном ЭП будут удалены по крайней мере два ФЭ типа & или ∨.Действительно, в случае σ = 0 из СФЭ Σ будет удаленФЭ E0 , являющийся первым ФЭ типа & или ∨ цепи C.
Заметим, что выход ФЭ E0 не может быть выходом схемы и неможет быть входом ФЭ ¬, выход которого является выходомсхемы, так как при этом ФАЛ fσ была бы равна константе.Следовательно, на цепи C СФЭ Σ имеется ФЭ E00 типа &или ∨, на вход которого поступает либо выход E0 , либо выход ФЭ ¬, присоединенного к выходу E0 . Легко видеть, чтоb и, следоваФЭ E00 тоже будет удален при переходе от Σ к Σтельно, справедливы неравенстваb + 2 > L&,∨ (fσ ) + 2,L&,∨ (f ) = L&,∨ (Σ) > L&,∨ (Σ)из которых вытекает (2.8).Случай σ = 1, когда БП xn подаётся в C либо на входФЭ ∨, либо на вход ФЭ ¬, к выходу которого присоединёнФЭ типа &, рассматривается аналогично.Лемма доказана.§3. Некоторые модификации основных классов схем21Следствие 1.LC (µn ) > 2n+1 + n − 1.(2.9)Действительно, (2.9) получается в результате применения леммы 2.5 последовательно ко всем информационнымБП y2n −1 , .
. . , y1 и учитывая, что получившаяся в результате соответствующих подстановок констант ФАЛ существенно зависит от БП x1 , . . . , xn , y0 .Следствие 2. Из (2.9) в силу леммы 4.1 главы 2 вытекеает неравенствоD(µn ) > n + 1.Замечание. В силу следствия 1 формула x1 y0 ∨x1 y1 являетсяминимальной СФЭ, раеализующей ФАЛ µ1 и LC (µ1 ) = 4.§3Разложение ФАЛ и операция суперпозициисхем. Корректность суперпозиции для некоторых типов схем, разделительные контактные схемы и лемма Шеннона.Рассмотрим структурные преобразования схем, которые обобщают операцию суперпозиции функций и используются дляпостроения сложных схем из более простых.
Базисом такихпостроений является обычно схема из одной изолированнойвершины, являющейся ее входом. Указанная вершина называется тождественной вершиной кратности k, k > 0,если она одновременно является k-кратным выходом данной схемы. При этом кратность один, как правило, не указывается, а тождественная вершины кратности 0 считаетсяфиктивной.Простейшими видами суперпозиции схем являются: 1)операция переименования входов схемы с возможным ихотождествлением; 2) операция переименования выходов схемы22Глава 3.
Синтез и сложность управляющих системс возможным их дублированием или снятием; 3) операцияобъединения схем, не имеющих общих вершин и общих входвыходных пометок, понимаемая, как обычное объединениесоответствующих графов.Будем говорить, что схема Σ имеет вид Σ = Σ00 (Σ0 ), тоесть является суперпозицией схем Σ00 и Σ0 без общих вершини вход-выходных пометок, если она получается в результате объединения этих схем и присоединения (части) входовсхемы Σ00 к (некоторым) выходам схемы Σ0 . Указанная суперпозиция считается бесповторной, если различные входыΣ00 присоединяются к различным выходным вершинам Σ0 .Суперпозиция вида Σ = Σ00 (Σ0 ) называется стыковкой, если число входов схемы Σ00 равно числу выходов схемы Σ0 икаждый вход Σ00 присоединяется к выходу Σ0 с тем же номером.Заметим, что операции объединения схем и переименования их входов (выходов) являются частными случаямивведенной операции суперпозиции.
Действительно, для объединения схем это очевидно, а любое переименование выходов (входов) схемы Σ можно задать суперпозицией вида Σ002 (Σ001 (Σ)) (соответственно Σ(Σ01 (Σ02 ))), где схемы Σ0i иΣ00i , i = 1, 2, состоят из тождественных вершин различнойкратности.Заметим также, что суперпозиция общего вида Σ = Σ00 (Σ0 )b 00 (Σb 0 ), гдевсегда может быть сведена к стыковке вида Σ = Σ000000bbсхемы Σ и Σ получаются из схем Σ и Σ соответственно добавлением тождественных вершин и переименованиемвыходов. Стыковка вида Σ = Σ00 (Σ0 ), в свою очередь, можетb 00 (Σb 0 ), гдебыть сведена к бесповторной стыковке вида Σ = Σb0 и Σb 00 получаются из схем Σ0 и Σ00 снятием выходовсхемы Σи отождествлением входов соответственно.Для суперпозиции схем вида Σ = Σ00 (Σ0 ) характерно, какправило, то, что схема Σ реализует функции, получающиеся в результате соответствующей подстановки (всех или ча-§3. Некоторые модификации основных классов схем23сти) функций, реализованных схемой Σ0 вместо (всех иличасти) входных переменных схемы Σ00 .
В случае стыковки, например, это означает, что схема Σ реализует наборфункций вида F00 (F0 ), где F00 и F0 — наборы функций, реализованные схемами Σ00 и Σ0 соответственно. СуперпозицияΣ = Σ00 (Σ0 ) считается правильной, если схема Σ обладаетуказанным свойством, и корректной, если, кроме того, в любой вершине Σ, которая соответствует выходной вершине Σ0 ,реализуется та же самая функция, что и в Σ0 . Заметим, чтоправильная суперпозиция вида Σ00 (Σ0 ) автоматически является корректной, если кратность любой выходной вершиныΣ0 больше числа присоединяемых к ней входов Σ00 .
Заметимтакже, что с содержательной точки зрения корректность суперпозиции вида Σ00 (Σ0 ) позволяет одновременно использовать выходы Σ0 в других суперпозициях.Легко видеть, что любая СФЭ может быть получена врезультате многократного применения операции суперпозиции, на каждом шаге которой происходит дублирование выхода или присоединение одного ФЭ к выходам СФЭ, первоначально состоящей из тождественных вершин.Так, на рис. 2.2a показана СФЭ Σ⊕2 , имеющая сложность4 и реализующая ФАЛ x1 ⊕x2 , а на рис.
2.2b — СФЭ Σ⊕n, n >3, которая является результатом «последовательной» суперпозиции (n − 1) схем Σ⊕2 и реализует ФАЛ `n (x1 , . . . , xn ) сосложностью 4n − 4.Операция суперпозиции КС и все ее частные случаи определяются обычным образом. При этом пометками входов ивыходов КС, в отличие от СФЭ, не обязательно являютсяпеременные, а БП, управляющие проводимостью контактовКС, никак не связаны с ее входами.Рассмотрим вопросы, связанные с нахождением функционирования для суперпозиций сетей или КС. Из соображений удобства будем допускать наличие в КС ориентированных (неориентированных) ребер без пометок, которые про-24Глава 3. Синтез и сложность управляющих системводят при любых значениях управляющих входных БП вуказанном (соответственно в любом) направлении и называются вентилями (соответственно проводниками).
Это позволяет считать, что сети являются частным случаем КС иреализуют свои матрицы достижимости, состоящие из константных ФАЛ.Легко видеть, что перестановка входов(выходов) КС порождает в реализуемой ею матрице такую же перестановкусвязанных с ними строк (соответственно столбцов), а снятие(дублирование) выходов этой КС — удаление (соответственно добавление) связаных с ними столбцов. Заметим также,что КС Σ, которая является объединением КС Σ0 и Σ00 , реализующих матрицы F 0 и F 00 соответственно, реализует матрицу F вида1 :F0 0F =0 F 00Обратимся, далее, к особенностям функционирования КС,получающихся в результате применения операций суперпозиции общего вида. Напомним, что суперпозиция общего вида сводится к последовательному выполнению операций переименования выходов, добавления тождественных вершини стыковки.
При этом стыковка, в свою очередь, сводитсяк снятию выходов, отождествлению входов и бесповторнойстыковке.Заметим, что результат отождествления первых p входов КС Σ эквивалентен результату стыковки вида Σ (Σ0 ),а результат p-кратного дублирования первого выхода КСΣ — результату стыковки Σ00 (Σ), где КС Σ0 , Σ00 состоят изПредполагается, что номер любого входа (выхода) КС Σ0 меньшеномера любого входа (соответственно выхода) КС Σ00 в КС Σ, а внутренняя упорядоченность полюсов КС Σ0 и Σ00 в КС Σ сохраняется.В остальных случаях происходит необходимая перестановка входов ивыходов КС Σ.1§3. Некоторые модификации основных классов схемa1aa2...25ap.........a1 a2apaa)b)y1y2...yp z1c)Рис.
3.1: проводящие и вентильная звезды порядка p(1, p)-проводящей звезды (см. рис. 3.1a, a — вход) и тождеbственных вершин. Заметим также, что стыковка вида Σ(Σ),bгде КС Σ состоит из (p, 1)-проводящей звезды (см. рис. 3.1b,a — выход) и тождественных вершин, соответствует отождествлению первых p выходов КС Σ.В соответствии с общими правилами стыковка (суперпозиция) КС вида Σ = Σ00 (Σ0 ) называется2 правильной, еслидля матриц F , F 0 и F 00 , реализуемых КС Σ, Σ0 и Σ00 соответственно, выполняется равенствоF = F 0 · F 00 .2(3.1)Это определение соответствует «обычному» определению корректной суперпозиции в рамках модели так называемых преобразующихКС.26Глава 3. Синтез и сложность управляющих системУказанная суперпозиция считается корректной, если, кроме того, в выходных вершинах подсхемы Σ00 схемы Σ реализуются те же самые столбцы ФАЛ, что и в самой схемеΣ.
Аналогичным образом определяется правильность и корректность суперпозиции КС на заданном наборе значенийуправляющих БП.Заметим, что при правильной стыковке (1, p)-КС и (p,1)КС, реализующихстроку и столбец из ФАЛ f10 , . . . , fp0 и0000f1 , .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
