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

Будем считать,что в каждой вершине (p, q)-КС Σ реализуется столбец, составленный из p ФАЛ проводимости от входовΣ к этой вершине, а сама КС Σ реализует матрицу,которая состоит из q столбцов, реализованных на еевыходах. Таким образом, функционированиеКС Σ =000000= Σ x1 , . . . , xn ; a1 , . . . , ap ; a1 , . . . , aq представляет собойматрицу F = F (x1 , . . .

, xn ) с p строками, q столбцами и элементами из P2 (n), для которой F hi, ji — ФАЛ, реализуемаямежду a0i и a00j , где i ∈ [1, p] и j ∈ [1, q], то есть при любом α, α ∈ B n , матрица F (α) является матрицей достижимости сети Σ|α . В частности, функционирование (1, q)-КСпредставляет собой набор (строку) из q ФАЛ проводимости от ее входа к выходам, а функционирование (p, 1)-КС —столбец из p ФАЛ проводимости от ее входов к выходу.Так, КС Σ (x1 , x2 , x3 ; a1h, v; a2i, a3 ), показанная на рисунке 4.3c реализует матрицу ll3 ll3 от БП X(3), а на рис. 4.4b3 3приведено (2n , 1)-КД порядка n от БП X (n), которое имеет вид D (x1 , . . .

, xn ; a0 , . . . , a2n −1 ; a) и реализует столбец извсех ЭК множества Qn , упорядоченных сверху вниз по возрастанию их номеров.В соответствии с общими правилами из §1, функционирование КС Σ = Σ (x1 , . . . , xn ; a1 , . . . , am ) с44Глава 2. Основные классы управляющих системнеразделенными полюсами определяется как функционирование КС с разделенными полюсами видаΣ (x1 , . .

. , xn ; a1 , . . . , am ; a1 , . . . , am ). В этом случае матрица F является рефлексивной и транзитивной матрицей, аесли, кроме того, Σ — неориентированная сеть, то и — симметричной матрицей. Заметим также, что функционирование (1, 1)-КС из неориентированных контактов по существуне отличается от функционирования соответствующей двухполюсной КС с неразделенными полюсами.В частности, показанная на рис. 4.3c КС с неразделенны1 l3 l 3ми полюсами a1 , a2 , a3 реализует матрицу l3 1 0 , КС изl3 0 1тождественных вершин реализует единичную матрицу, если каждая ее вершина является входом и выходом с одними тем же номером и т. д.С другой стороны, любая симметрическая, транзитивная и рефлексивная матрица F , F ∈ (P2 (n))m,m , реализуется КС Σ = Σ (x1 , .

. . , xn ; a1 , . . . , am ), которая представляетсобой объединение всех КС Σij = Σij (x1 , . . . , xn ; ai , aj ), где1 6 i < j 6 m, а КС Σij является π-схемой и построена посовершенной ДНФ ФАЛ F hi, ji и считается каноническойКС матрицы F .§5Операция суперпозиции и её корректностьдля некоторых типов схем. Каскадные иразделительные контактные схемы, леммаШеннона.Рассмотрим структурные преобразования схем, которыеобобщают операцию суперпозиции функций и используются для построения сложных схем из более простых. Базисом таких построений является обычно схема из однойизолированной вершины, являющейся ее входом.

Указаннаявершина называется тождественной вершиной кратности§5. Некоторые модификации основных классов схем45k, k > 0, если она одновременно является k-кратным выходом данной схемы. При этом кратность один, как правило,не указывается, а тождественная вершины кратности 0 считается фиктивной.Простейшими видами суперпозиции схем являются: 1)операция переименования входов схемы с возможным ихотождествлением; 2) операция переименования выходовсхемы с возможным их дублированием или снятием; 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 ), где схемы Σb0 и Σb 00 получаются из схем Σ0 и Σ00 соΣответственно добавлением тождественных вершин и пере-46Глава 2.

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

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

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

Некоторые модификации основных классов схемx1x2•x1x2••47•Σ⊕2x3•&•w•'¬∨Σ⊕2••z1 &...xq•Σ⊕2z1a)b)Рис. 5.1: пример суперпозиции СФЭдов и выходов КС, в отличие от СФЭ, не обязательно являются переменные, а БП, управляющие проводимостью контактов КС, никак не связаны с ее входами.Рассмотрим сначала специальный частный случай корректной суперпозиции КС — операцию присоединения к выходам одновходовой КС одного или двух противоположныхконтактов, которая заключается в следующем. Пусть (1, m)КС Σ получается из (1, m̌)-КС Σ̌ в результате добавления новой выходной вершины v, которая соединяется с выходнымивершинами v0 и v1 КС Σ̌ контактами xi и xi соответственно(см. рис.

5.2a). Тогда в вершинах v0 и v1 КС Σ в силу нулевой проводимости между входами присоединяемой (2, 1)-КСреализуются те же самые ФАЛ g0 и g1 , что и в КС Σ̌, а ввершине v — ФАЛ g видаg = µ (xi , g0 , g1 ) = xi g0 ∨ xi g1 .(5.1)Аналогичные соотношения будут справедливы и тогда,48Глава 2. Основные классы управляющих систем•1•v0xi•vΣ̌•1•Σ̌xi•xσivσ•vv1a)b)Рис. 5.2: присоединение одного или двух противоположныхконтактовкогда вершина v КС Σ связана с вершиной vσ только однимконтактом вида xσi , σ ∈ {0, 1} (см.

рис. 5.2b). В этом случаев вершине v КС Σ реализуется ФАЛg = xσi gσ ,(5.2)а в вершине vσ по-прежнему реализуется ФАЛ gσ .Описанные выше операции присоединения одного илидвух противоположенных контактов очевидным образомраспространяются на случай КС с несколькими входами.Кроме того, они допускают моделирование в классе СФЭв базисе Б0 . Так, переход от СФЭ Ǔ , Ǔ ∈ UC , которая реализует в выходных вершинах v0 и v1 ФАЛ g0 и g1 соответственно, к СФЭ U, U ∈ UC , которая реализует ФАЛ g,удовлетворяющую (5.1) ((5.2)), показан на рис.

5.3a (соответственно 5.3b). Заметим, что при этом разложение (5.1) вслучае gσ ≡ 1 эквивалентно представлениюg = xσi ∨ gσ ,схемная реализация которого показана на рис. 5.3c.Определим, далее, каскадную КС как приведенную КСбез изолированных полюсов, которая может быть получена§5. Некоторые модификации основных классов схемxi••... ...••xi • ¬Ǔ•&•'zv1 v0∨•(vvxσi•...

...49•Ǔ•vσ&•&•v(v•$wa)b)•xσi•... ...•Ǔvσ•∨•v(vc)Рис. 5.3: к моделированию операций присоединения контактов в классе СФЭ50Глава 2. Основные классы управляющих системиз системы тождественных вершин в результате ряда операций присоединения одного или двух противоположных контактов и операций переименования выходов. Каскадная КС(ККС) считается полной, если она была построена без использования операции присоединения одного контакта.

Так,например, КС, показанная на рис. 4.3c, является полнойККС, если её входами считать вершины a1 и v, а выходами — вершины a2 и a3 , или наоборот. К числу ККС относятся также контактные деревья, показанные на рис. 4.4,причем (2n , 1)-КД является полной ККС.Заметим, далее, что, в силу отмеченных выше свойстврассматриваемых операций присоединения контактов, ККСимеет нулевые ФАЛ проводимости между своими входами.Отсюда следует, что в каждой вершине ККС реализуетсястолбец, в котором никакие две ФАЛ не обращаются в единицу одновременно, причем в случае полной ККС дизъюнкция всех ФАЛ этого столбца дает 1. Так, в частности, вкаждой вершине полной ККС с двумя входами реализуетсястолбец из двух противоположных ФАЛ.Вершина ККС, введенная в нее с помощью операцииприсоединения одного контакта, называется неполной вершиной этой ККС.

Будем говорить, что ККС Σ00 являетсядополнением неполной ККС Σ0 , если она получается в результате соединения всех неполных вершин Σ0 отсутствующими в них контактами с новым входом, удаления всех«старых» входов и перехода к соответствующей приведенной КС. При этом, очевидно,L Σ00 6 2L Σ0 ,(5.3)а объединение Σ0 и Σ00 является полной ККС. ДополнениеΣ00 к полной ККС Σ с 1 входом будем называть инверснойк Σ0 ККС.