оки2 (С.А. Ложкин - Лекции по основам кибернетики (2014)), страница 8

Заметим, что ККС Σ00 , в силу отмеченных выше0свойств полных ККС, реализует систему ФАЛ F , если ККС§5. Некоторые модификации основных классов схемa0vaxi•5v0xi•)v10xi•va•510•5v01•)v1a11a)b)Рис. 5.4: к определению BDDΣ0 реализует систему ФАЛ F 0 . Таким образом, в силу (5.3)справедливо следующее утверждениеЛемма 5.1. Если (1, m)-ККС Σ0 реализует систему ФАЛ0 ), то существует (1, m)-ККС Σ00 , котораяF 0 = (f10 , .

. . , fm000реализует систему ФАЛ F = f 1 , . . . , f mL (Σ00 )6и для которой2L (Σ0 ).Рассмотрим далее вопросы, связанные с нахождениемфункционирования для суперпозиций сетей или КС общеговида. Из соображений удобства будем допускать наличие вКС ориентированных (неориентированных) ребер без пометок, которые проводят при любых значениях управляющихвходных БП в указанном (соответственно в любом) направлении и называются вентилями (соответственно проводниками).

Это позволяет считать, что сети являются частнымслучаем КС и реализуют свои матрицы достижимости, состоящие из константных ФАЛ.Легко видеть, что перестановка входов(выходов) КС порождает в реализуемой ею матрице такую же перестановкусвязанных с ними строк (соответственно столбцов), а снятие52Глава 2. Основные классы управляющих систем(дублирование) выходов этой КС — удаление (соответственно добавление) связаных с ними столбцов.

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

рис. 5.5a, a — вход) и тождеbственных вершин. Заметим также, что стыковка вида Σ(Σ),bгде КС Σ состоит из (p, 1)-проводящей звезды (см. рис. 5.5b,a — выход) и тождественных вершин, соответствует отождествлению первых p выходов КС Σ.В соответствии с общими правилами стыковка (суперпозиция) КС вида Σ = Σ00 (Σ0 ) называется2 правильной, еслиПредполагается, что номер любого входа (выхода) КС Σ0 меньшеномера любого входа (соответственно выхода) КС Σ00 в КС Σ, а внутренняя упорядоченность полюсов КС Σ0 и Σ00 в КС Σ сохраняется.В остальных случаях происходит необходимая перестановка входов ивыходов КС Σ.2Это определение соответствует «обычному» определению корректной суперпозиции в рамках модели так называемых преобразующихКС.1§5. Некоторые модификации основных классов схемa1aa2...53ap.........a1 a2apaa)b)y1y2...yp z1c)Рис. 5.5: проводящие и вентильная звезды порядка pдля матриц F , F 0 и F 00 , реализуемых КС Σ, Σ0 и Σ00 соответственно, выполняется равенствоF = F 0 · F 00 .(5.4)Указанная суперпозиция считается корректной, если, кроме того, в выходных вершинах подсхемы Σ00 схемы Σ реализуются те же самые столбцы ФАЛ, что и в самой схемеΣ.

Аналогичным образом определяется правильность и корректность суперпозиции КС на заданном наборе значенийуправляющих БП.Заметим, что при правильной стыковке (1, p)-КС и (p,1)КС, реализующихстроку и столбец из ФАЛ f10 , . . . , fp0 и0000f1 , . . . , fp соответственно, получается (1, 1)-КС, реализующая ФАЛ f10 f100 ∨· · ·∨fp0 fp00 , при правильном отождествлении54Глава 2.

Основные классы управляющих системвходов (выходов) КС в реализуемой ею матрице происходитпоразрядная дизъюнкция тех строк (соответственно столбцов), которые соответствуют отождествленным входам (соответственно выходам) и т. п.Легко видеть, что операция переименования входов (выходов) КС без отождествления, операция объединения КС,а также операция последовательного соединения (1, 1)-КС(см. §4) корректны в любом случае. В то же время параллельное соединение (1, 1)-КС, при котором сначала отождествляются входы, а затем выходы соединяемых КС, неявляется, в общем случае, корректной операцией суперпозиции, хотя является при этом правильной суперпозицией,так как полученная КС реализует дизъюнкцию ФАЛ, реализуемых исходными КС. Заметим, что корректное дизъюнктирование выходных ФАЛ можно осуществить с помощьюстыковки исходной КС с вентильной звездой (см. рис.

5.5c).Схема называется разделительной по входам (выходам),если ФАЛ проводимости между любыми ее различными входами (соответственно выходами) равна 0. Так (p, 1)-схемаΣ00 = Σ00 (y1 , . . . , yp ; z1 ), показанная на рисунке 5.5c, является разделительной по входам схемой, которая называетсявентильной звездой порядка p.

Примером разделительнойпо выходам (входам) КС может служить (1, 2n ) (соответственно (2n , 1)) контактное дерево порядка n (см. рис. 4.4).Будем говорить, что КС Σ от БП x1 , . . . , xn разделительнана наборе α = (α1 , . . . , αn ) значений этих БП, если соответствующей разделительностью обладает сеть Σ|α . Следующее утверждение является обобщением известной леммыШеннона (см. [31, 14]).Лемма 5.2. Пусть КС Σ является результатом стыковки вида Σ = Σ00 (Σ0 ), а F , F 0 и F 00 — матрицы, реализуемыеКС Σ, Σ0 и Σ00 соответственно. ТогдаF > F 0 · F 00 и F = F 0 · F 00 ,(5.5)§5.

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

рис. 5.6a). Справедливость неравенства (5.6) следует из того, что его праваячасть описывает «суммарную» проводимость тех (v 0 − v 00 )цепей КС Σ, которые проходят через вершины a1 , . . . , aq ровно один раз (см. рис. 5.6a). Любая другая (v 0 − v 00 )-цепь КСΣ проходит через указанные вершины не меньше трех раз(см. рис. 5.6b) и в случае разделительности КС Σ0 по выходам или разделительности КС Σ00 по входам имеет нулевуюпроводимость.Из (5.6) и (5.7) непосредственно вытекает (5.5) с учетом того, что при v 0 = a0i и v 00 = a00j , где i ∈ [1, p] иj ∈ [1, s], левая(правая) часть этих соотношений равна элементу матрицы F (соответственно F 0 · F 00 ), расположенномув i-й строке и j-м столбце.56Глава 2.

Основные классы управляющих системa01a0p...••v0•a1 •Σ0• aqaj •Σ00•v 00...•a001•a00sa)a01•a1 ••a001a0p...••v0aj1 •Σ0...aj2 •...• ajtv 00• aq••a00sb)Рис. 5.6: к доказательству леммы 5.2§5. Некоторые модификации основных классов схем57Пусть теперь КС Σ получается из КС Σ00 в результатеприменения операции отождествления входов, то есть Σ эквивалентна бесповторной стыковке вида Σ00 (Σ0 ), где КС Σ0состоит из проводящей звезды и тождественных вершин. Вэтом случае неравенство (5.5) имеет вид 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 по входам равенство) (5.5) для КС Σ,Σ0 , Σ00 вытекает из установленных выше аналогичных соотb 00 , Σ̌00 , Σ00 и КС Σ, Σb 0, Σb 00 в силу ассоциношений для КС Σативности произведения матриц. Случай разделительностиКС Σ0 по выходам рассматривается аналогично.Лемма доказана.Следствие 1. В случае разделительности КС Σ00 по входам в каждой вершине КС Σ, Σ = Σ00 (Σ), которая соответствует выходу КС Σ0 , реализуется тот же самый столбецФАЛ, что и в КС Σ0 , то есть рассматриваемая суперпозиция является корректной.Действительно, полагая v 0 = a0i и v 00 = aj , где i ∈ [1, p],а j ∈ [1, q], из (5.7) получим требуемое равенство f = fj0 .Случай стыковки общего вида рассматривается аналогично.58Глава 2.

Основные классы управляющих системСледствие 2. Равенство (5.5) выполняется на любом наборе значений БП, на котором КС Σ00 разделительна по входам или КС Σ0 разделительна по выходам.Литература[1] Алексеев В. Б. Введение в теорию сложности алгоритмов. М.: Издательский отдел ф-та ВМиК МГУ, 2002.[2] Алексеев В. Б., Вороненко А. А., Ложкин С.

А.,Романов Д. С., Сапоженко А. А., Селезнева С. Н.Задачи по курсу «Основы кибернетики». Издательский отдел ф-та ВМиК МГУ, 2002.[3] Алексеев В. Б., Ложкин С. А. Элементы теории графов, схем и автоматов. М.: Издательский отдел ф-таВМиК МГУ, 2000.[4] Боровков А. А. Курс теории вероятностей. М.: Наука,1976.[5] Гаврилов Г. П., Сапоженко А.

А. Задачи и упражнения по дискретной математике. 3-е изд., перераб.М.: ФИЗМАТЛИТ, 2004.[6] Дискретная математика и математические вопросы кибернетики, под редакцией С. В. Яблонского иО. Б. Лупанова. Т. 1. М.: Наука, 1974.[7] Евдокимов А. А. О максимальной длине цепи в единичном n-мерном кубе // Матем. заметки. 1969. 6.

№3.С. 309–319.[8] Емеличев В. А., Мельников О. И., Сарванов В. И.,Тышкевич Р. И. Лекции по теории графов. М.: Наука,1977.5960Литература[9] Журавлев Ю. И. Локальные алгоритмы вычисленияинформации // Кибернетика. №1. 1965. С. 12–19.[10] Журавлев Ю. И. Теоретико-множественные методы валгебре логики // Проблемы кибернетики.