OK_metodichka_part_2 (1132797), страница 11
Текст из файла (страница 11)
ТогдаF > F 0 · F 00 и F = F 0 · F 00 ,(9.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 ,(9.2)которое переходит в равенствоf (x1 , . . . , xn ) = f10 · f100 ∨ · · · ∨ fq0 · fq00 ,(9.3)§9. Операция суперпозиции. Лемма Шеннонаa01a0p...••v0•a1 •81Σ0• aqaj •Σ00•v 00...•a001•a00sa)a01•a1 ••a001a0p...••v0aj1 •Σ0...aj2 •...• ajtv 00• aq••a00sb)Рис. 9.3: к доказательству леммы 9.182Глава 2. Основные классы управляющих системесли КС Σ0 разделительна по выходам или КС Σ00 разделительна по входам.Действительно, пусть aj , j ∈ [1, q], — вершина КС Σ,которая получается в результате присоединения j-го входа КС Σ00 к j-му выходу КС Σ0 (см. рис.
9.3a). Справедливость неравенства (9.2) следует из того, что его праваячасть описывает «суммарную» проводимость тех (v 0 − v 00 )цепей КС Σ, которые проходят через вершины a1 , . . . , aq ровно один раз (см. рис. 9.3a). Любая другая (v 0 − v 00 )-цепь КСΣ проходит через указанные вершины не меньше трех раз(см. рис. 9.3b) и в случае разделительности КС Σ0 по выходам или разделительности КС Σ00 по входам имеет нулевуюпроводимость.Из (9.2) и (9.3) непосредственно вытекает (9.1) с учетом того, что при v 0 = a0i и v 00 = a00j , где i ∈ [1, p] и j ∈[1, s], левая(правая) часть этих соотношений равна элементу матрицы F (соответственно F 0 · F 00 ), расположенному вi-й строке и j-м столбце.Пусть теперь КС Σ получается из КС Σ00 в результатеприменения операции отождествления входов, то есть Σ эквивалентна бесповторной стыковке вида Σ00 (Σ0 ), где КС Σ0состоит из проводящей звезды и тождественных вершин.
Вэтом случае неравенство (9.1) имеет вид F > Fb00 , где матрица Fb00 получается из матрицы F 00 в результате поразрядной дизъюнкции строк, соответствующих отождествляемымвходам КС Σ00 , и по-прежнему переходит в равенство, еслиКС Σ00 разделительна по входам. В последнем случае, кроe 00 ,ме того, из аналогичного равенства, связанного с КС Σ00которая получается из КС Σ в результате объявления ееe 00 , следует развходов входами и, одновременно, выходами Σделительность КС Σ по входам.Заметим, наконец, что стыковка общего вида Σ = Σ00 (Σ0 )сводится к последовательномувыполнению отождествленияb 00 = Σ00 Σ̌00 и бесповторной стыковки видавходов вида Σ§9.
Операция суперпозиции. Лемма Шеннона83b 00 (Σb 0 ), где КС Σ̌00 состоит из проводящей звезды и тожΣ=Σb 0 получается из КС Σ0 снятиемдественных вершин, а КС Σнекоторых выходов. При этом неравенство (в случае разделительности КС Σ00 по входам равенство) (9.1) для КС Σ,Σ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], из (9.3) получим требуемое равенство f = fj0 .Случай стыковки общего вида рассматривается аналогично.Следствие 2.
Равенство (9.1) выполняется на любом наборе значений БП, на котором КС Σ00 разделительна по входам или КС Σ0 разделительна по выходам.Стыковка (суперпозиция) КС вида Σ = Σ00 (Σ)0 называется правильной, если она удовлетворяет равенству (9.1), исчитается корректной, если она, кроме того, удовлетворяеттребованиям следствия 1 из леммы 9.11 Аналогичным образом определяется правильность и корректность суперпозиции КС на заданном наборе значений управляющих БП.Заметим, что при правильной стыковке (1, p)-КСи (p,1)КС, реализующих строку и столбец из ФАЛ f10 , .
. . , fp0 и1Эти определения соответствуют определениям корректной суперпозиции в рамках модели так называемых преобразующих КС.Требования следствия 1 леммы 9.1 не распространяются, как правило, на тождественные вершины КС Σ0 , добавленные для согласованиячисла ее выходов с числом входов КС Σ00 .84Глава 2. Основные классы управляющих систем 00f1 , . . . , fp00 соответственно, получается (1, 1)-КС, реализующая ФАЛ f10 f100 ∨· · ·∨fp0 fp00 , при правильном отождествлениивходов (выходов) КС в реализуемой ею матрице происходитпоразрядная дизъюнкция тех строк (соответственно столбцов), которые соответствуют отождествленным входам (соответственно выходам) и т. п.Легко видеть, что операции переименования входов безотождествления, переименования выходов и объединения корректны в любом случае.
Из леммы ?? и ее следствий вытекает, что для разделительной по входам КС Σ00 любая суперпозиция вида Σ00 (Σ0 ) является корректной. Это относится, в частности, к последовательному соединению (1, 1)-КС(см. §6). В то же время параллельное соединение (1, 1)-КС,при котором сначала отождествляются входы, а затем выходы соединяемых КС, не является корректной операциейсуперпозиции, так как не удовлетворяет требованиям следствия 1 из леммы 9.1. Заметим, что параллельное соединение КС является при этом правильной суперпозицией, таккак полученная КС реализует дизъюнкцию ФАЛ, реализуемых исходными КС, и что корректное дизъюнктированиевыходных ФАЛ можно осуществить с помощью стыковкиисходной КС с вентильной звездой (см.
рис. 9.2c).В общем случае операции отождествления входов, а также операции стыковки не всегда являются правильными.Литература[1] Алексеев В. Б. Введение в теорию сложности алгоритмов. М.: Издательский отдел ф-та ВМиК МГУ, 2002.[2] Алексеев В. Б., Вороненко А. А., Ложкин С. А.,Романов Д.
С., Сапоженко А. А., Селезнева С. Н.Задачи по курсу «Основы кибернетики». Издательский отдел ф-та ВМиК МГУ, 2002.[3] Алексеев В. Б., Ложкин С. А. Элементы теории графов, схем и автоматов. М.: Издательский отдел ф-таВМиК МГУ, 2000.[4] Боровков А. А. Курс теории вероятностей. М.: Наука,1976.[5] Гаврилов Г. П., Сапоженко А. А. Задачи и упражнения по дискретной математике. 3-е изд., перераб.М.: ФИЗМАТЛИТ, 2004.[6] Дискретная математика и математические вопросы кибернетики, под редакцией С. В. Яблонского иО. Б. Лупанова.
Т. 1. М.: Наука, 1974.[7] Евдокимов А. А. О максимальной длине цепи в единичном n-мерном кубе // Матем. заметки. 1969. 6. №3.С. 309–319.[8] Емеличев В. А., Мельников О. И., Сарванов В. И.,Тышкевич Р. И. Лекции по теории графов. М.: Наука,1977.8586Литература[9] Журавлев Ю. И. Локальные алгоритмы вычисленияинформации // Кибернетика. №1. 1965. С. 12–19.[10] Журавлев Ю.
И. Теоретико-множественные методы валгебре логики // Проблемы кибернетики. Вып. 8.М.: Физматгиз, 1962. С. 5-44.[11] Кузьмин В. А. Оценки сложности реализации функций алгебры логики простейшими видами бинарныхпрограмм // Сб. «Методы дискретного анализа втеории кодов и схем». Новосибирск, 1976. Вып. 29.С.
11–39[12] Ложкин С. А. Оценки высокой степени точности длясложности управляющих систем из некоторых классов // Математические вопросы кибернетики. Вып. 6.М.: Наука, 1996. С. 189–214.[13] Ложкин С. А. Структурное моделирование и декомпозиция для некоторых классов схем.
М.: Издательский отдел ф-та ВМиК МГУ, 2001.[14] Лупанов О. Б. Асимптотические оценки сложностиуправляющих систем. М.: Изд-во МГУ, 1984.[15] Лупанов О. Б. О сложности реализации функцийалгебры логики релейно-контактными схемами //Проблемы кибернетики.
Вып. 11. М.: Наука, 1964.С. 25–48.[16] Лупанов О. Б. О сложности реализации функций алгебры логики формулами // Проблемы кибернетики.Вып. 3. М.: Физматгиз, 1960. С. 61–80.[17] Мурога С. Системы проектирования сверхбольшихинтегральных схем. М.: Мир, 1985.Литература87[18] Нечипорук Э. И. О топологических принципах самокорректирования // Проблемы кибернетики. Вып. 21.М.: Наука, 1969.
С. 5–102.[19] Нигматуллин Р. Г. Сложность булевых функций.М.: Наука, 1991.[20] Поваров Г. Н. Метод синтеза вычислительных и управляющих контактных схем // Автоматика и телемеханика. 1957. Т. 18. №2. С. 145–162.[21] Сапоженко А. А. Дизъюнктивные нормальные формы. М.: Изд-во МГУ, 1975.[22] Сапоженко А. А.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
