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

4.3: некоторые КС от БП x1 , x2 , x3мости вершины u из вершины v, или, иначе, реализуетсямежду вершинами v и u. Из определения следует, что длянахождения ФАЛ gv,u (x1 , . . . , xn ) достаточно просмотретьвсе наборы α, α ∈ B n , и для каждого из них выяснить наличие или отсутствие в Σ цепи, состоящей из проводящихна наборе α контактов, которая идет из v в u.

Так, просматривая все наборы значений БП x1 , x2 , можно убедиться втом, что ФАЛ проводимости gv1 ,v2 (x1 , x2 ) в КС Σ, показанной на рис. 4.3a, равна x1 ⊕ x2 , а ФАЛ проводимости gv3 ,v4равна 0.§4. Контактные схемы и π-схемы, оценка их числа35Будем считать, что в каждой вершине (1, m)-КСΣ(x1 , . . . , xn ; a1 ; a2 , . . . , am+1 ) реализуется ФАЛ проводимости от входа a1 к этой вершине и что Σ реализует систему ФАЛ F = (f1 , . . .

, fm ), где fj — ФАЛ проводимости от a1 к выходу с пометкой aj+1 , j ∈ [1, m].При этом, очевидно, в вершине a1 реализуется ФАЛ 1,которую в дальнейшем по умолчанию будем использовать в качестве пометки единственного входа (1, m)-КС.Так, КС, изображенные на рис.

4.3a, 4.3b и 4.3c, реализуют ФАЛ x1 ⊕ x2 , H (x1 , x2 , x3 ) и набор ФАЛ(x1 ⊕ x2 ⊕ x3 , x1 ⊕ x2 ⊕ x3 ⊕ 1) соответственно. На рис. 4.4aпоказана (1, 2n )-КС D (x1 , . . . , xn ; 1; a0 , . . . , a2n −1 ), котораяназывается (1, 2n )-контактным деревом порядка n от БПX (n). Легко видеть, что в выходной вершине ai , i =0, . . . 2n − 1, этого контактного дерева (КД) реализуется ЭКвида xσ1 1 · · · xσnn , где ν (σ1 , .

. . , σn ) = (i − 1), и что ФАЛ проводимости между любыми его выходами равна 0. Таким образом, (1, 2n )-КД порядка n является дешифратором порядка n, то есть схемой, реализующей систему Qn из всех ЭКранга n от БП X (n).Схемы Σ0 и Σ00 считаются, как обычно, изоморфными, если изоморфны соответствующие им графы, и эквивалентными, если они реализуют равные системы ФАЛ.

Изоморфные КС, очевидно, эквивалентны.Для множества C, состоящего из контактов видав КС Σ, определим его функцию проводимости K (C) и функцию отделимости J (C) как ФАЛ вида xσi11 · · · xσirr и xσi11 ∨ . . . ∨ xσirr соответственно. При этоммножество C называется проводящим (отделимым), еслиK (C) 6= 0 (J (C) 6= 1), и нулевым (соответственно единичным) в противном случае. Заметим, что в результате приведения подобных (см. §3) отличная от 0 ФАЛ K (C) и отличная от 1 ФАЛ J (C) могут быть преобразованы в ЭК иxσi11 , . .

. , xσirr36Глава 2. Основные классы управляющих системxn• a0xn• a1•x1•x2x2••x2••1•x1x2...ai•/ xσ1 . . . xσnn1•xn• a2n −2•xn• a2n −1a)a0 •xn•a1 •a2n −2 •xn•x2••x2x2•xn•x1•x1•ax2•a2n −1 •xnb)Рис. 4.4: (1, 2n )- и (2n , 1)- контактные деревья порядка n§4. Контактные схемы и π-схемы, оценка их числа37ЭД соответственно. Очевидно, также, чтоK C 0 > K (C) и J C 0 6 J (C) ,если C 0 ⊆ C.Из введенных определений (см. также §1) следует, чтоФАЛ g, реализуемая КС Σ (x1 , . .

. , xn ; a1 ; a2 ), обращается в 1(обращается в 0) на наборе α, α ∈ B n , тогда и только тогда,когда в Σ существует множество контактов C, образующеепростую проводящую (a1 − a2 )-цепь (соответственно тупиковое отделимое (a1 |a2 ))-сечение), для которого K (C) = 1(соответственно J (C) = 0) на наборе α.

Таким образом,g (x1 , . . . , xn ) = K (C1 ) ∨ . . . ∨ K (Ct ) == J (S1 ) & . . . &J (Sr ) , (4.1)где C1 , . . . , Ct и S1 , . . . , Sr — все простые проводящие(a1 − a2 )-цепи и все тупиковые отделимые (a1 |a2 )-сеченияКС Σ.Заметим, что первая из формул (4.1) может быть преобразована в ДНФ, а вторая — в КНФ, в результате приведения подобных (см.

§3), если g 6≡ 0 и g 6≡ 1 соответственно.Так, в КС, показанной на рис. 4.3b, имеются три простыепроводящие цепи C1 , C2 и C3 , которые идут из a1 в a2 . ПриэтомK (C1 ) = x1 x2 x3 , K (C2 ) = x1 x2 x1 = x1 x2 , K (C3 ) = x1 x3и, следовательно,g (x1 , x2 , x3 ) = x1 x2 x3 ∨ x1 x2 ∨ x1 x3 == x1 x2 ∨ x2 x3 ∨ x3 x1 = H (x1 , x2 , x3 ) .Рассмотрим теперь параллельно-последовательные или,иначе, π-схемы, которые являются частным случаем КС.38Глава 2. Основные классы управляющих системC1a1a2Cta)a1•···S1a2•Spb)Рис. 4.5: КС, моделирующие ДНФ и КНФПростейшей π-схемой считается любая (1, 1)-КС, которая состоит из одного контакта, соединяющего полюса(см.

рис. 4.6a). Если π-схемы Σ1 и Σ2 уже определены, то(1, 1)-КС Σ0 (Σ00 ), которая получается в результате их параллельного (соответственно последовательного) соединения (см. рис. 4.6b и 4.6c) тоже является π-схемой. Заметим,что при этом вход (выход) Σ0 является результатом отождествления входов (соответственно выходов) Σ1 и Σ2 , тогда как входом Σ00 является вход Σ1 , выходом Σ00 — выходΣ2 , а выход Σ1 отождествляется с входом Σ2 и становитсявнутренней вершиной Σ00 . Легко видеть, что π-схема, показанная на рис. 4.6a, реализует ФАЛ xσi , а π-схемы Σ0 и Σ00(см.

рис. 4.6b и 4.6c) — ФАЛ f1 ∨ f2 и f1 &f2 соответственно,где f1 и f2 — ФАЛ, реализуемые π-схемами Σ1 и Σ2 соответственно.Лемма 4.1. Любой π-схеме Σ можно сопоставить эквивалентную ей формулу F из UΦ с поднятыми отрицаниямитакую, что R (F) = L (Σ) и обратно.Доказательство. Построим формулу F индукцией по стро-§4. Контактные схемы и π-схемы, оценка их числаa1xσi39Σ1a2Σ0:a1a2Σ2a)b)Σ00 : a1Σ1•Σ2a2c)Рис.

4.6: к определению π-схемыению π-схемы Σ. Если Σ — простейшая π-схема вида xσi , тоположим F = xσi . Если π-схемам Σ1 и Σ2 уже сопоставлены формулы F1 и F2 с поднятыми отрицаниями, то π-схемеΣ0 (Σ00 ), получающейся в результате параллельного (соответственно последовательного) соединения Σ1 и Σ2 , сопоставим формулу F0 = F1 ∨ F2 (соответственно F00 = F1 &F2 ).При этомR F0 = R F00 = R (F1 ) + R (F2 )и, следовательно, по индуктивному предположению,R F0 = R F00 = L (Σ1 ) + L (Σ2 ) = L (Σ) .Аналогичным образом, индукцией по строению формулы Fс поднятыми отрицаниями можно найти эквивалентную ейπ-схему Σ такую, что L (Σ) = R (F).Лемма доказана.40Глава 2.

Основные классы управляющих систем•x2x1x3a1x2a2x3•a)xn•xn••x1•x2x2••x2•y0•a1x1x2y1a2y2n −2•xn•xn••b)Рис. 4.7: примеры π-схемy2n −1§4. Контактные схемы и π-схемы, оценка их числа41На рис 4.7a показана π-схема, которая реализует ФАЛH (x1 , x2 , x3 ) и соответствует формуле:H (x1 , x2 , x3 ) = x1 (x2 ∨ x3 ) ∨ x2 x3 ,а на рис.

4.7b — π-схема, которая построена на основе контактного дерева и реализует ФАЛ µn — мультиплексорнуюФАЛ порядка n, — в соответствии с формулойµn (x1 , . . . , xn , y0 , . . . , y2n −1 ) =! !___=xσ1 1 xσ2 2 · · ·xσnn yν(σ1 ,...,σn ) · · ·  .σ1 ∈Bσ2 ∈Bσn ∈BСхема, моделируюшая совершенную ДНФ ФАЛ f ,называется канонической КС для этой ФАЛ.Будем называть (1, m)-КС приведенной, если все изолированные вершины Σ являются ее полюсами, а все контактыи остальные вершины Σ принадлежат простым проводящимb коцепям, соединяющим ее вход и выходы.

При этом КС Σ,торая получается из КС Σ удалением «лишних», то есть непринадлежащих цепям указанного вида, неполюсных вершин и контактов, является эквивалентной Σ приведеннойb 6 L (Σ). Заметим, что приведенная КСКС такой, что L(Σ)не содержит петель, а приведенная КС, не реализующая нулевых ФАЛ, является связным графом. Так, КС, показанная на рис. 4.3c, не является приведенной, а соответствующая ей приведенная КС получается из нее удалением вершины v.Рассмотрим теперь некоторые оценки числа контактныхсхем различных типов.

Пусть UK и Uπ — множество всех КСиз неориентированных контактов и множество всех π-схемсоответственно. Если UA — один из указанных классов схем,то через UA (L, n) будем обозначать множество приведенных(1, 1)-схем Σ из UA от БП X (n), для которых L (Σ) 6 L. Для42Глава 2. Основные классы управляющих системлюбого множества схем U в соответствии с §1 через |U| и kUkбудем по-прежнему обозначать число попарно не изоморфных и попарно не эквивалентных схем в U соответственно.При этом для любого из введенных выше множеств схемнеравенство (1.7) будет выполняться.Лемма 4.2.

При любых натуральных L и n выполняетсянеравенствоkUπ (L, n)k 6 (12n)L .(4.2)Доказательство. В силу леммы 4.1, достаточно доказать,что число попарно не эквивалентных формул F (x1 , . . . , xn )с поднятыми отрицаниями над базисом Б0 , для которыхR (F) 6 L, не превосходит (12n)L . Требуемая оценка вытекает из следствия к лемме 3.2.Лемма доказана.Лемма 4.3. При любых натуральных L и n выполняетсянеравенство KU (L, n) 6 (8nL)L .Доказательство. Возьмем произвольную КС Σ=K= Σ(x1 , . . .

, xn ; a1 ; a2 ), Σ ∈ U (L, n), и выделим в нейостовное дерево D с корнем a2 так, чтобы в D вошли всеинцидентные a2 контакты Σ, а вершина a1 была листом D.Пусть, далее, D0 — связанное с D остовное наддерево КСΣ, которое получается путем присоединения каждого изне вошедших в D ребер Σ к одной из своих концевых вершин, отличной от a1 (см. §1).

Рассмотрим ориентированноеупорядоченное дерево D00 , получающееся из D0 введением (условной) ориентации всех его ребер по направлению ккорню и таким их упорядочением, при котором вершина a1становится первым листом D00 (см. §1).Заметим, что число ребер (вершин, листьев) дерева D00не больше, чем L (соответственно L + 1, L), и поэтому, в§4.

Контактные схемы и π-схемы, оценка их числа43силу (1.4), число таких деревьев с учетом пометок их ребер символами x1 , . . . , xn , x1 , . . . , xn не больше, чем (8n)L .Заметим также, что КС Σ может быть получена в результате присоединения каждого листа дерева D00 к одной из еговершин, отличной от a2 . Следовательно, KU (L, n) 6 UK (L, n) 6 (8nL)L .Лемма доказана.Рассмотрим, в заключение, особенности функционирования КС с несколькими входами.