Теормин (все билеты, кроме 12-14) (Мадорский) (1133375), страница 3
Текст из файла (страница 3)
Если UA — один из указанных классовсхем, то через UA (L, n) будем обозначать множество приведенных (1, 1)-схем Σиз UA от БП X (n), для которых L (Σ) 6 L.Лемма 4.2. При любых натуральных L и n выполняется неравенствоДок-во: часть 2, стр. 42kUπ (L, n)k 6 (12n)L .Лемма 4.3. При любыхнатуральных L и n выполняется неравенствоUK (L, n) 6 (8nL)L .Док-во: часть 2, стр. 42-43Любая симметрическая, транзитивная и рефлексивная матрица F , F ∈(P2 (n))m,m, реализуется КС Σ = Σ (x1, ... , xn; a1, ... , am), которая представляетсобой объединение всех КС Σij = Σij (x1, ...
, xn; ai, aj ), где 1 6 i < j 6 m, а КС Σijявляется π-схемой и построена по совершенной ДНФ ФАЛ F hi, ji и считаетсяканонической КС матрицы F .Пусть Σ — КС от БП X (n) и α = (α1 , . . . , αn ) — набор из B n . Определим сеть Σ|α как сеть, получающуюсяиз Σ в результате удаления всех ребер (дуг) с пометкамиxα1 1 , . . . , xαnn , то есть ребер, которые не проводят на наборе α, и снятия пометок с остальных ребер Σ. Для вершин v иu КС Σ введем функцию проводимости от вершины v квершине u как ФАЛ gv,u (x1, .
. . , xn), которая равна 1 нанаборе α = (α1 , . . . , αn ) ∈ B n тогда и только тогда, когдав сети Σ|α существует (v − u)-цепь, то есть тогда и только тогда, когда в Σ имеется цепь из проводящих на набореα контактов вида xα1 1 , . . . , xαnn , идущая из v в u. Будем говорить также, что ФАЛ gv,u является функцией достижимости вершины u из вершины v, или, иначе, реализуетсямежду вершинами v и u.1•x1x1••x2x2x2xn•••a0xn•••a1...x2ai••xσ1(1, 2n)-КС D (x1, . . .
, xn; 1; a0, . . . , a2n−1),которая называется (1, 2n)-контактным деревомпорядка n от БП X (n). Легко видеть, что в выходной вершине ai, i = 0, . . . 2n − 1, этогоконтактного дерева (КД) реализуется ЭКвида x1σ1 · · · xσnn , где ν (σ1, . . . , σn) = (i − 1), иx σ что ФАЛ про-водимости между любыми его•a•nn2n−2выходами равна 0. Таким об-разом, (1, 2n)-КДxnпорядка n является дешифратором порядка n,•a2nто есть схемой, реализующей систему Qn из−1всех ЭК ранга n от БП X (n).Схемы Σ ′ и Σ ′′ считаются, как обычно, изоморфными, если изоморфнысоответствующие им графы, и эквивалентными, если они реализуют равныесистемы ФАЛ.
Изоморфные КС, очевидно, эквивалентны.σσДля множества C, состоящего из контактов вида xi11 , . . . , xirr в КС Σ,определим его функцию проводимости K (C) и функцию отделимости J (C) какФАЛ вида xσi11 · · · xσirr и xσi11 ∨ . . . ∨ xσirr соответственно. При этом множествоC называется проводящим (отделимым), если K (C) 6= 0 (J (C) 6= 1), и нулевым(соответственно единичным) в противном случае.K C ′ > K (C) и J C ′ 6 J (C) , если C ′ ⊆ C.Простейшей π-схемой считается любая (1, 1)-КС, которая состоит из одногоконтакта, соединяющего полюса.
Если π-схемы Σ1 и Σ2 уже определены, то (1, 1)КС Σ ′ (Σ′′), которая получается в результате их параллельного (соответственнопоследовательного) соединения тоже является π-схемой.Лемма 4.1. Любой π-схеме Σ можно сопоставить эквивалентную ей формулуF из UΦс поднятыми отрицаниями такую, что R (F) = L (Σ) и обратно.Схема, моделируюшая совершенную ДНФ ФАЛ f, называется каноническойКС для этой ФАЛ.Будем называть (1, m)-КС приведенной, если все изолированные вершины Σявляются ее полюсами, а все контакты и остальные вершины Σ принадлежатпростым проводящим цепям, соединяющим ее вход и выходы. При этом КС bΣ,1xn...суперпозиции и её корректность для некоторых типов11Операциясхем. Каскадные и разделительные контактные схемы, лемма Шеннона.Рассмотрим структурные преобразования схем, которые обобщают операциюсуперпозиции функций и используются для построения сложных схем из болеепростых.
Базисом таких построений является обычно схема из однойизолированной вершины, являющейся ее входом. Указанная вершина называетсятождественной вершиной кратности k, k > 0, если она одновременно являетсяk-кратным выходом данной схемы. При этом кратность один, как правило, неуказывается, а тождественная вершины кратности 0 считается фиктивной.Простейшими видами суперпозиции схем являются: 1) операцияпереименования входов схемы с возможным их отождествлением; 2) операцияпереименования выходов схемы с возможным их дублированием или снятием;3) операция объединения схем, не имеющих общих вершин и общих вход-выходныхпометок, понимаемая, как обычное объединение соответствующих графов.Будем говорить, что схема Σ имеет вид Σ = Σ ′′(Σ′), то есть являетсясуперпозицией схем Σ ′′ и Σ ′ без общих вершин и вход-выходных пометок, если онаполучается в результате объединения этих схем и присоединения (части) входовсхемы Σ ′′ к (некоторым) выходам схемы Σ ′.
Указанная суперпозиция считаетсябесповторной, если различные входы Σ ′′ присоединяются к различным выходнымвершинам Σ ′. Суперпозиция вида Σ = Σ ′′(Σ′) называется стыковкой, если числовходов схемы Σ′′ равно числу выходов схемы Σ′ и каждый вход Σ′′ присоединяетсяк выходу Σ′ с тем же номером.Для суперпозиции схем вида Σ = Σ ′′(Σ′) характерно, как правило, то, чтосхема Σ реализует функции, получающиеся в результате соответствующейподстановки (всех или части) функций, реализованных схемой Σ′ вместо (всех иличасти) входных переменных схемы Σ ′′. Суперпозиция Σ = Σ ′′(Σ′) считаетсяправильной, если схема Σ обладает указанным свойством, и корректной, если,кроме того, в любой вершине Σ , которая соответствует выходной вершине Σ ′,реализуется та же самая функция, что и в Σ′.Каскадная КС - приведенная КС без изолированных полюсов, которая можетбыть получена из системы тождественных вершин в результате ряда операцийприсоединения одного или двух противоположных контактов и операцийпереименования выходов.
Каскадная КС (ККС) считается полной, если она былапостроена без использования операции присоединения одного контакта.Вершина ККС, введенная в нее с помощью операции присоединения одногоконтакта, называется неполной вершиной этой ККС. Будем говорить, что ККС Σ′′является дополнением неполной ККС Σ ′, если она получается в результатесоединения всех неполных вершин Σ ′ отсутствующими в них контактами с новымк соответствующей приведенвходом, удаления всех «старых» входов и перехода′′′ной КС.
При этом, очевидно, L Σ 6 2L Σ , а объединение Σ ′ и Σ ′′ являетсяполной ККС. Дополнение Σ ′′ к полной ККС Σ с 1 входом будем называтьинверсной к Σ ′ ККС. Заметим, что ККС Σ ′′, в силу отмеченных выше свойств′полных ККС, реализует систему ФАЛ F , если ККС Σ′ реализует систему ФАЛ F ′.Лемма 5.1. Если (1, m)-ККС Σ′ реализует систему ФАЛ′ ), то существует (1, m)-ККС Σ′′ , котораяF ′ = (f1′ , . . .
, fm′реализует систему ФАЛ F =′′f 1, . . . , f mи для которойy1y2... Рис. 5.5 c) z16В соответствии с общими правилами стыковка (суперпозиция) КС видаΣ = Σ′′ (Σ′) называется правильной, если для матриц F , F ′ и F ′′, реализуемыхКС Σ, Σ′ и Σ′′ соответственно, выполняется равенство F = F ′ · F ′′ .Указанная суперпозиция считается корректной, если, кроме того, в выходныхвершинах подсхемы Σ ′′ схемы Σ реализуются те же самые столбцы ФАЛ, что и всамой схеме Σ . Аналогичным образом определяется правильность и корректность суперпозиции КС на заданном наборе значений управляющих БП.Схема называется разделительной по входам (выходам), если ФАЛпроводимости между любыми ее различными входами (соответственновыходами) равна 0.
Так (p, 1)-схема Σ ′′ = Σ ′′ (y1, . . . , yp; z1), показанная нарисунке 5.5c, является разделительной по входам схемой, которая называетсявентильной звездой порядка p. Будем говорить, что КС Σ от БП x1, ..., xnразделительна на наборе α = (α1, ..., αn) значений этих БП, еслисоответствующей разделительностью обладает сеть Σ|a.Лемма 5.2. Пусть КС Σ является результатом стыковки вида Σ = Σ ′′ (Σ′), аF , F ′ и F ′′ — матрицы, реализуемые КС Σ, Σ′ и Σ′′ соответственно. ТогдаF > F ′ · F ′′ и F = F ′ · F ′′ , если КС Σ′′ разделительна по входам или КС Σ′ разДок-во: часть 2, стр.
55-57делительна по выходам.Следствие 1. В случае разделительности КС Σ ′′ по входам в каждой вершинеКС Σ, Σ = Σ′′ (Σ), которая соответствует выходу КС Σ′, реализуется тот жесамый столбец ФАЛ, что и в КС Σ ′, то есть рассматриваемая суперпозицияявляется корректной.Следствие 2. Равенство (5.5) выполняется на любом наборе значений БП, накотором КС Σ′′ разделительна по входам или КС Σ′ разделительна по выходам.L (Σ′′ )2L (Σ′ ).yp15 Задача синтеза. Простейшие методы синтеза схем и связанные с ними верхние оценкисложности функций.Будем считать, что функционал сложности Ψ обладаетсвойством монотонности, то есть Ψ (Σ) >Ψ (Σ′), если Σ, Σ′ ∈U, и Σ′ получается из Σ в результате удаления вершин илиребер. Все введенные в главе 2 функционалы сложностиэтим свойством обладают.
Определим сложность Ψ (F )системы ФАЛ F относительнофункционала Ψ в классе U как минимальное значение величины Ψ (Σ) на множестве тех схем Σ из U, которые реализуют F . При этом схема Σ, принадлежащая классу U, котораяреализует F и для которой Ψ (Σ) = Ψ (F ), называется минимальной схемой в классе U относительно функционала Ψ.Величину Ψ (F ), в том случае когда функционал Ψ совпадает с введенным в главе 2 функционалом L (D, R, и т.
д.),будем называть сложностью (соответственно глубиной, рангом, и т. д.) системы ФАЛ F . Введем функциюΨ (n) = max Ψ (f ) ,f ∈P2 (n)которая, обычно, называется функцией Шеннона для класса U относительно функционала сложности Ψ. В дальнейшем сложность системы ФАЛ F относительно функционаAла Ψ для любого из введенных классов вида UAБ (вида U )Aбудем обозначать через ΨAБ (F ) (соответственно Ψ (F )), афункцию Шеннона для этого класса относительно Ψ — через ΨБA (n) (соответственно ΨA (n)).CΦΨ′ (F ) 6 Ψ′′ (F ) , если U′ ⊇ U′′. В частности, ΨБ (F ) 6 ΨБ (F ) ,ΨK (F ) 6 Ψπ (F )Для сложности L (F ) системы ФАЛ F = (f1, . .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
