Lectionc3 (С.А. Ложкин - Лекции по основам кибернетики (2007)), страница 5

Базисом таких построений являетсяобычно схема из одной изолированной вершины, являющейся ее входом. Указанная вершина называется тождественной вершиной кратности k, k > 0, если она одновременноявляется k-кратным выходом данной схемы. При этом кратность один, как правило, не указывается, а тождественнаявершины кратности 0 считается фиктивной.Простейшими видами суперпозиции схем являются: 1)операция переименования входов схемы с возможным ихотождествлением; 2) операция переименования выходов схемыс возможным их дублированием или снятием; 3) операцияобъединения схем, не имеющих общих вершин и общих входвыходных пометок, понимаемая, как обычное объединениесоответствующих графов.Будем говорить, что схема Σ имеет вид Σ = Σ00 (Σ0 ), тоесть является суперпозицией схем Σ00 и Σ0 без общих вершини вход-выходных пометок, если она получается в результате объединения этих схем и присоединения (части) входовсхемы Σ00 к (некоторым) выходам схемы Σ0 .

Указанная суперпозиция считается бесповторной, если различные входыΣ00 присоединяются к различным выходным вершинам Σ0 .Суперпозиция вида Σ = Σ00 (Σ0 ) называется стыковкой, если число входов схемы Σ00 равно числу выходов схемы Σ0 икаждый вход Σ00 присоединяется к выходу Σ0 с тем же номером.Заметим, что операции объединения схем и переименования их входов (выходов) являются частными случаями32Глава 3. Синтез и сложность управляющих системвведенной операции суперпозиции. Действительно, для объединения схем это очевидно, а любое переименование выходов (входов) схемы Σ можно задать суперпозицией вида Σ002 (Σ001 (Σ)) (соответственно Σ(Σ01 (Σ02 ))), где схемы Σ0i иΣ00i , i = 1, 2, состоят из тождественных вершин различнойкратности.Заметим также, что суперпозиция общего вида Σ = Σ00 (Σ0 )b 00 (Σb 0 ), гдевсегда может быть сведена к стыковке вида Σ = Σ000000b и Σb получаются из схем Σ и Σ соответственсхемы Σно добавлением тождественных вершин и переименованиемвыходов.

Стыковка вида Σ = Σ00 (Σ0 ), в свою очередь, можетb 00 (Σb 0 ), гдебыть сведена к бесповторной стыковке вида Σ = Σ000000bbсхемы Σ и Σ получаются из схем Σ и Σ снятием выходови отождествлением входов соответственно.Для суперпозиции схем вида Σ = Σ00 (Σ0 ) характерно, какправило, то, что схема Σ реализует функции, получающиеся в результате соответствующей подстановки (всех или части) функций, реализованных схемой Σ0 вместо (всех иличасти) входных переменных схемы Σ00 .

В случае стыковки, например, это означает, что схема Σ реализует наборфункций вида F00 (F0 ), где F00 и F0 — наборы функций, реализованные схемами Σ00 и Σ0 соответственно. СуперпозицияΣ = Σ00 (Σ0 ) считается правильной, если схема Σ обладаетуказанным свойством, и корректной, если, кроме того, в любой вершине Σ, которая соответствует выходной вершине Σ0 ,реализуется та же самая функция, что и в Σ0 .

Заметим, чтоправильная суперпозиция вида Σ00 (Σ0 ) автоматически является корректной, если кратность любой выходной вершиныΣ0 больше числа присоединяемых к ней входов Σ00 . Заметимтакже, что с содержательной точки зрения корректность суперпозиции вида Σ00 (Σ0 ) позволяет одновременно использовать выходы Σ0 в других суперпозициях.Заметим также, что любая СФЭ может быть получена врезультате многократного применения операции суперпози-§4. Операция суперпозиции. Лемма Шеннонаx/1x2•/•/x1x2•&••w•'¬••z1 &Σ2x3--∨33•Σ22222...xq,,,,•Σ2z1a)b)Рис. 4.1: пример суперпозиции СФЭции, на каждом шаге которой происходит дублирование выхода или присоединение одного ФЭ, к СФЭ, первоначальносостоящей из тождественных вершин.На рис.

4.1a показана СФЭ Σ⊕2 , имеющая сложность 4 иреализующая ФАЛ x1 ⊕ x2 , а на рис. 4.1b — СФЭ Σ⊕q , q > 3,которая является результатом «последовательной» суперпозиции (q − 1) схем Σ⊕2 и реализует ФАЛ `q (x1 , . . . , xq ) сосложностью 4q − 4.Рассмотрим теперь вопросы, связанные с нахождениемфункционирования для суперпозиций сетей или КС. Из соображений удобства будем допускать наличие в КС вентилей и неориентированных ребер без пометок, которые проводят при любых значениях управляющих входных БП иназываются проводниками. Это позволяет считать, что сетиявляются частным случаем КС и реализуют свои матрицыдостижимости, состоящие из константных ФАЛ.34Глава 3.

Синтез и сложность управляющих системОперация суперпозиции КС и все ее частные случаи определяются обычным образом. При этом пометками входов ивыходов КС, в отличие от СФЭ, не обязательно являютсяпеременные, а БП, управляющие проводимостью контактовКС, никак не связаны с ее входами.Легко видеть, что перестановка входов(выходов) КС порождает в реализуемой ею матрице такую же перестановкусвязанных с ними строк (соответственно столбцов), а снятие(дублирование) выходов этой КС — удаление (соответственно добавление) связаных с ними столбцов. Заметим также,что КС Σ, которая является объединением КС Σ0 и Σ00 , реализующих матрицы F 0 и F 00 соответственно, реализует матрицу F вида1 :F0 0F =0 F 00Обратимся, далее, к особенностям функционирования КС,получающихся в результате применения операций суперпозиции общего вида. Напомним, что суперпозиция общего вида сводится к последовательному выполнению операций переименования выходов, добавления тождественных вершини стыковки.

При этом стыковка, в свою очередь, сводитсяк снятию выходов, отождествлению входов и бесповторнойстыковке.Заметим, что результат отождествления первых p входов КС Σ эквивалентен результату стыковки вида Σ (Σ0 ),а результат p-кратного дублирования первого выхода КСΣ — результату стыковки Σ00 (Σ), где КС Σ0 , Σ00 состоят из(1, p)-проводящей звезды (см. рис.

4.2a, a — вход) и тождеbственных вершин. Заметим также, что стыковка вида Σ(Σ),Предполагается, что номер любого входа (выхода) КС Σ0 меньшеномера любого входа (соответственно выхода) КС Σ00 в КС Σ, а внутренняя упорядоченность полюсов КС Σ0 и Σ00 в КС Σ сохраняется.В остальных случаях происходит необходимая перестановка входов ивыходов КС Σ.1§4. Операция суперпозиции.

Лемма Шеннона? ?????  . . . ?????  . . . ?'. . . ??'?? ''?? ' . . . ?? '' ??' a1aa1 a235apapa2aa)b)?'. . . ??'?? ''?? '?? '' ??'  y1ypy2z1c)Рис. 4.2: проводящие и вентильная звезды порядка pb состоит из (p, 1)-проводящей звезды (см.

рис. 4.2b,где КС Σa — выход) и тождественных вершин, соответствует отождествлению первых p выходов КС Σ.Схема называется разделительной по входам(выходам),если ФАЛ проводимости между любыми ее различными входами (соответственно выходами) равна 0. Так (p, 1)-схемаΣ00 = Σ00 (y1 , . . . , yp ; z1 ), показанная на рисунке 4.2c, является разделительной по входам схемой, которая называетсявентильной звездой порядка p. Примером разделительнойпо выходам (входам) КС может служить (1, 2n )- (соответственно (2n , 1)-) контактное дерево порядка n (см. рис. ??).Будем говорить, что КС Σ от БП x1 , .

. . , xn разделительнана наборе α = (α1 , . . . , αn ) значений этих БП, если соответствующей разделительностью обладает сеть Σ|α . Следу-36Глава 3. Синтез и сложность управляющих системющее утверждение является обобщением известной леммыШеннона (см. [32, 14]).Лемма 4.1.

Пусть КС Σ является результатом стыковки вида Σ = Σ00 (Σ0 ), а F , F 0 и F 00 — матрицы, реализуемыеКС Σ, Σ0 и Σ00 соответственно. ТогдаF > F 0 · F 00 и F = F 0 · F 00 ,(4.1)если КС Σ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 ,(4.2)которое переходит в равенствоf (x1 , . . . , xn ) = f10 · f100 ∨ · · · ∨ fq0 · fq00 ,(4.3)если КС Σ0 разделительна по выходам или КС Σ00 разделительна по входам.Действительно, пусть aj , j ∈ [1, q], — вершина КС Σ,которая получается в результате присоединения j-го входа КС Σ00 к j-му выходу КС Σ0 (см.

рис. 4.3a). Справедливость неравенства (4.2) следует из того, что его праваячасть описывает «суммарную» проводимость тех (v 0 − v 00 )цепей КС Σ, которые проходят через вершины a1 , . . . , aq ровно один раз (см. рис. 4.3a). Любая другая (v 0 − v 00 )-цепь КС§4. Операция суперпозиции. Лемма Шеннонаa01a0p...••v0•a1 •37Σ0• aqaj •Σ00•v 00...•a001•a00sa)a01•a1 ••a001a0p...••v0aj1 •Σ0...aj2 •...• ajtv 00• aq••a00sb)Рис. 4.3: к доказательству леммы 4.138Глава 3. Синтез и сложность управляющих системΣ проходит через указанные вершины не меньше трех раз(см. рис.

4.3b) и в случае разделительности КС Σ0 по выходам или разделительности КС Σ00 по входам имеет нулевуюпроводимость.Из 4.2 и 4.3 непосредственно вытекает 4.1 с учетом того, что при v 0 = a0i и v 00 = a00j , где i ∈ [1, p] и j ∈ [1, s], левая(правая) часть этих соотношений равна элементу матрицы F (соответственно F 0 · F 00 ), расположенному в i-й строкеи j-м столбце.Пусть теперь КС Σ получается из КС Σ00 в результатеприменения операции отождествления входов, то есть Σ эквивалентна бесповторной стыковке вида Σ00 (Σ0 ), где КС Σ0состоит из проводящей звезды и тождественных вершин. Вэтом случае неравенство 4.1 имеет вид F > Fb00 , где матрица Fb00 получается из матрицы F 00 в результате поразрядной дизъюнкции строк, соответствующих отождествляемымвходам КС Σ00 , и по-прежнему переходит в равенство, еслиКС Σ00 разделительна по входам.