Теормин (билеты 8 - 11) (2014) (спасибо Денису) (1133373), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

Каскадная КС (ККС) считается полной, если она была построена без использования операции присоединения одного контакта. Вершина ККС, введенная в нее с помощью операции присоединения одного контакта, называется неполной вершиной этой ККС. ДОБОЛЯЮЯЯВ ЯОБОЛЯОЙ )ДхС ККС Х" является дополнением неполной ККС Х', если она получается в результате соединения всех неполных вершин Х' отсутствующими в них контактами с новым входом, удаления всех «старых» входов и перехода к соответствующей приведенной КС. При этом ЦХ") < 2ЦХ'), а объединение Х' и Х" является полной ККС. КЯВеРОЯБВ )хКт".

Дополнение Х" к полной ККС Х с 1 входом называется инверсной к Х' ККС. Лемма Если (1, гп)-ККС Х' реализует систему ФАЛ Е' = (Д, ..., ~' ), то существует (1, гп)-ККС Х", которая реализует систему ФАЛ Р' = (Д, ...,~' ) и для которой ЦХ") < 2Е(Х'). Ъ ождественная верщйна Базисом является обычно схема из одной изолированной вершины, являющейся ее входом. Указанная вершина называется тождественной вершиной кратности )с, )с > О, если она одновременно является йкратным выходом данной схемы.

При этом кратность 1, как правило, не указывается, а тождественная вершины кратности О считается фиктивной. ЙростейзБме Виды суперпознцин схем 1. Операция переименования входов схемы с возможным их отождествлением; 2. Операция переименования выходов схемы с возможным их дублированием или снятием; 3.

Операция объединения схем, не имеющих общих вершин и общих вход-выходных пометок, понимаемая как обычное объединение соответствующих графов. Суперпозиция обтцего вида Будем говорить, что схема Х имеет вид Х = Х" (Х'), то есть является суперпозицией схем без общих вершин и вход-выходных пометок, если она получается в результате объединения этих схем и присоединения (части) входов схемы Х" к ~некоторым) выходам схемы Х'.

Беспожгорная супертгоэнцня Суперпозиция вида Х = Х" (Х') считается бесповторной, если различные входы Х" присоединяются к различным выходным вершинам Х'. Стыковка Суперпозиция вида Х = Х" (Х') называется стыковкой, если число входов схемы Х" равно числу выходов схемы Х', и каждый вход Х" присоединяется к выходу Х' с тем же номером. йравяльная суперпоэяцня Если схема Х = Х" (Х') реализует функции, получающиеся в результате соответствующей подстановки (всех или части) функций, реализованных схемой Х' вместо (всех или части) входных переменных схемы Х", то такая суперпозиция называется правильной.

Корреь сная суперпозиция Правильная суперпозиция называется корректной, если, кроме того, в любой вершине Х, которая соответствует выходной вершине Х', реализуется та же самая функция, что и в Х'. РВВделээтельязя Б О ЦхОЛВм ~ны~Одйзт) скемн Схема называется разделительной по входам (выходам ), если ФАЛ проводимости между любыми ее различными входами (соответственно выходами) равна О. РйздйлктОлыэйя яй 836Оде КЕ, Будем говорить, что КС Х от БП хт„..., х„разделительная на наборе а = (ат, ..., а„) значений этих БП, если соответствующей разделительностью обладает сеть Х(„.

Леммй(ЦОБЯОЯВ Пусть КС Х является результатом стыковки вида Х = Х" (Х'), а Е, Г', Е" — матрицы, реализуемые соответствующими КС. Тогда Р ) Е' Е" и Р = Р' Е"„ если КС Х" разделительна по входам или если КС Х' разделительна по выходам. Следствие 1 В случае разделительности КС Х" по входам в каждой вершине КС Х = Х" (Х), которая соответствует выходу КС Х', реализуется тот же самый столбец ФАЛ, что и в КС Х', то есть рассматриваемая суперпозиция является корректной.

Следствие 2 Равенство г" = г"' с" выполняется на любом наборе значений БП, на котором КСХ" разделительна по входам или если КС Х' разделительна по выходам. .

Характеристики

Список файлов ответов (шпаргалок)