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

. . , y1 и учитывая, что получившаяся в результате соответствующих подстановок констант ФАЛ существенно зависит от БП x1 , . . . , xn , y0 .Следствие 2. Из (2.9) в силу леммы 4.1 главы 2 вытекеает неравенствоD(µn ) > n + 1.Замечание. В силу следствия 1 формула x1 y0 ∨x1 y1 являетсяминимальной СФЭ, раеализующей ФАЛ µ1 и LC (µ1 ) = 4.§3Разложение ФАЛ и операция суперпозициисхем. Корректность суперпозиции для некоторых типов схем, разделительные контактные схемы и лемма Шеннона.Рассмотрим структурные преобразования схем, которые обобщают операцию суперпозиции функций и используются дляпостроения сложных схем из более простых. Базисом такихпостроений является обычно схема из одной изолированнойвершины, являющейся ее входом. Указанная вершина называется тождественной вершиной кратности k, k > 0,если она одновременно является k-кратным выходом данной схемы.

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

Указанная суперпозиция считается бесповторной, если различные входыΣ00 присоединяются к различным выходным вершинам Σ0 .Суперпозиция вида Σ = Σ00 (Σ0 ) называется стыковкой, если число входов схемы Σ00 равно числу выходов схемы Σ0 икаждый вход Σ00 присоединяется к выходу Σ0 с тем же номером.Заметим, что операции объединения схем и переименования их входов (выходов) являются частными случаямивведенной операции суперпозиции.

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

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

Заметим, чтоправильная суперпозиция вида Σ00 (Σ0 ) автоматически является корректной, если кратность любой выходной вершиныΣ0 больше числа присоединяемых к ней входов Σ00 . Заметимтакже, что с содержательной точки зрения корректность суперпозиции вида Σ00 (Σ0 ) позволяет одновременно использовать выходы Σ0 в других суперпозициях.Легко видеть, что любая СФЭ может быть получена врезультате многократного применения операции суперпозиции, на каждом шаге которой происходит дублирование выхода или присоединение одного ФЭ к выходам СФЭ, первоначально состоящей из тождественных вершин.Так, на рис. 2.2a показана СФЭ Σ⊕2 , имеющая сложность4 и реализующая ФАЛ x1 ⊕x2 , а на рис.

2.2b — СФЭ Σ⊕n, n >3, которая является результатом «последовательной» суперпозиции (n − 1) схем Σ⊕2 и реализует ФАЛ `n (x1 , . . . , xn ) сосложностью 4n − 4.Операция суперпозиции КС и все ее частные случаи определяются обычным образом. При этом пометками входов ивыходов КС, в отличие от СФЭ, не обязательно являютсяпеременные, а БП, управляющие проводимостью контактовКС, никак не связаны с ее входами.Рассмотрим вопросы, связанные с нахождением функционирования для суперпозиций сетей или КС. Из соображений удобства будем допускать наличие в КС ориентированных (неориентированных) ребер без пометок, которые про-24Введениеводят при любых значениях управляющих входных БП вуказанном (соответственно в любом) направлении и называются вентилями (соответственно проводниками). Это позволяет считать, что сети являются частным случаем КС иреализуют свои матрицы достижимости, состоящие из константных ФАЛ.Легко видеть, что перестановка входов(выходов) КС порождает в реализуемой ею матрице такую же перестановкусвязанных с ними строк (соответственно столбцов), а снятие(дублирование) выходов этой КС — удаление (соответственно добавление) связаных с ними столбцов.

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

3.1: проводящие и вентильная звезды порядка p(1, p)-проводящей звезды (см. рис. 3.1a, a — вход) и тождеbственных вершин. Заметим также, что стыковка вида Σ(Σ),bгде КС Σ состоит из (p, 1)-проводящей звезды (см. рис. 3.1b,a — выход) и тождественных вершин, соответствует отождествлению первых p выходов КС Σ.В соответствии с общими правилами стыковка (суперпозиция) КС вида Σ = Σ00 (Σ0 ) называется2 правильной, еслидля матриц F , F 0 и F 00 , реализуемых КС Σ, Σ0 и Σ00 соответственно, выполняется равенствоF = F 0 · F 00 .2(3.1)Это определение соответствует «обычному» определению корректной суперпозиции в рамках модели так называемых преобразующихКС.26ВведениеУказанная суперпозиция считается корректной, если, кроме того, в выходных вершинах подсхемы Σ00 схемы Σ реализуются те же самые столбцы ФАЛ, что и в самой схемеΣ. Аналогичным образом определяется правильность и корректность суперпозиции КС на заданном наборе значенийуправляющих БП.Заметим, что при правильной стыковке (1, p)-КС и (p,1)КС, реализующихстроку и столбец из ФАЛ f10 , .

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

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

, αn ) значений этих БП, если соответствующей разделительностью обладает сеть Σ|α . Следующее утверждение является обобщением известной леммыШеннона (см. [32, 14]).Лемма 3.1. Пусть КС Σ является результатом стыковки вида Σ = Σ00 (Σ0 ), а F , F 0 и F 00 — матрицы, реализуемыеКС Σ, Σ0 и Σ00 соответственно.