OK_metodichka_part_2 (1132797), страница 10
Текст из файла (страница 10)
Для любых двух эквивалентных КС Σ0 и Σ00от БП x1 , . . . , xn существует ЭП вида Σ0 ⇒ Σ00 .τnb0 и Σb 00 — канонические КС от БПДоказательство. Пусть Σx1 , . . . , xn , эквивалентные КС Σ0 и Σ00 соответственно. Изb0 ⇒ Σb 00 , и поэтому, в силу лемопределений следует, что Σ(n)t2§8. Отсутствие КПСТ в классе КС73мы 8.1, существует ЭП видаb0 ⇒ Σb 00 ⇒ Σ00 .Σ0 ⇒ Στn(n)t2τnТеорема доказана.Следствие 1. Система τn является КПСТ для ЭП КС изUK от БП x1 , .
. . , xn .Следствие 2. Система τ∞ является ПСТ для ЭП КС изUK .Докажем теперь отсутствие КПСТ в классе UK . Для КС Σот БП x1 , . . . , xn и набора α, α ∈ B n , определим величинуΘ (Σ, α) = |E (Σ|α )| − |V (Σ|α )| + |c (Σ|α )| ,которая (см. §1 главы 2) задает цикломатическое число графа Σ|α . Положим, далее,XΘ (Σ) =Θ (Σ, α) .α∈B nЛемма 8.2. Если Σ0 (x1 , . . . , xn )⇒Σ00 (x1 , .
. . , xn ), то{t1 −t5 }Θ (Σ0 ) = Θ (Σ00 ), а если Σ0 ⇒ Σ00 , где k < n, то Θ (Σ0 )−Θ (Σ00 )τkделится на 2n−k .Доказательство. Докажем, что Θ(Σ0 )=Θ(Σ00 ), если Σ0 −→Σ00tiдля любого i из отрезка [1, 5]. Действительно, пусть КС Σ00b 0 , которая имеполучается из КС Σ0 заменой ее подсхемы Σiет вид левой части тождества ti , на соответствующую ейb 00 этого тождества. Нетрудно проверить, чтоправую часть Σiдля любого i, i ∈ [1, 5], число линейно независимых циклов графов Σ|α0 и Σ|α00 одинаково при всех α, α ∈ B n , и,следовательно, Θ (Σ0 ) = Θ (Σ00 ).74Глава 2. Основные классы управляющих системПусть теперь Σ0 ⇒ Σ00 , причем k < n. Если КС Σ0 соτkдержит в качестве подсхемы цикл из k контактов с однимполюсом, то КС Σ00 содержит вместо него один лишь полюс.
Рассмотрим цикломатическое число сети Σ0 |α для различных α, α ∈ B n . Если цикл указанного вида в КС Σ0содержит контакты, помеченные различными буквами одной и той же БП, то, очевидно, для любого α, α ∈ B n ,Θ (Σ0 )−Θ (Σ00 ) = 0. В противном случае, пусть xj1 , . . . , xjm —все различные БП, встречающиеся среди пометок указанного цикла, причем m 6 k. Заметим, что если цикл проводитна наборе α, α ∈ B n , то он проводит и на всех 2n−m наборах, в которых значения переменных с индексами j1 , . . .
, jmсовпадают со значениями соответствующих переменных набора α. Таким образом, разностьXΘ Σ0 − Θ Σ00 =Θ Σ0 |α − Θ Σ00 |αα=(α1 ,...,αn )делится на 2n−m и, следовательно, делится на 2n−kЛемма доказана.Теорема 8.2. В классе UK не существует конечной полнойсистемы тождеств.Доказательство. Проведем доказательство от противного:пусть τ — КПСТ для ЭП КС UK , и пусть n — максимальноечисло БП, встречающихся в тождествах системы τ . Тогда(n+1)τn ⇒ τ и τn — КПСТ для UK . Докажем, что τn 6⇒ t6.0Для этого рассмотрим КС Σ , состоящую из простого цикладлины (n + 1), содержащего контакты с пометками xi , i ∈[1, n + 1], и имеющую единственный полюс с пометкой 1, ко(n+1)торая является левой частью тождества t6.
Очевидно,00что ей эквивалентна КС Σ , содержащая изолированный по(n+1)люс 1, которая является правой частью тождества t6. Ес-§9. Операция суперпозиции. Лемма Шеннона(n+1)ли τn ⇒ t675, то Σ0 ⇒ Σ00 . Согласно данным выше опредеτnлениям, Θ (Σ0 ) = 1, Θ (Σ00 ) = 0 и разность Θ (Σ0 )−Θ (Σ00 ) = 1не делится на 2, что противоречит утверждению леммы 8.2.(n+1)Таким образом, тождество t6не выводится из системыτn , а значит, и из системы τ .
Отсюда следует, что τ не можетявляться КПСТ для ЭП КС из класса UK .Теорема доказана.§9Операция суперпозиции и ее корректностьдля некоторых типов схем. Разделительныеконтактные схемы и лемма ШеннонаВ основе большинства структурных преобразований схемлежит ряд операций, которые обобщают операцию суперпозиции функций и используются для построения сложныхсхем из более простых. Базисом таких построений являетсяобычно схема из одной изолированной вершины, являющейся ее входом.
Указанная вершина называется тождественной вершиной кратности k, k > 0, если она одновременноявляется k-кратным выходом данной схемы. При этом кратность один, как правило, не указывается, а тождественнаявершины кратности 0 считается фиктивной.Простейшими видами суперпозиции схем являются: 1)операция переименования входов схемы с возможным ихотождествлением; 2) операция переименования выходов схемыс возможным их дублированием или снятием; 3) операцияобъединения схем, не имеющих общих вершин и общих входвыходных пометок, понимаемая, как обычное объединениесоответствующих графов.Будем говорить, что схема Σ имеет вид Σ = Σ00 (Σ0 ), тоесть является суперпозицией схем Σ00 и Σ0 без общих вершини вход-выходных пометок, если она получается в результате объединения этих схем и присоединения (части) входов76Глава 2.
Основные классы управляющих системсхемы Σ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 ) характерно, какправило, то, что схема Σ реализует функции, получающиеся в результате соответствующей подстановки (всех или части) функций, реализованных схемой Σ0 вместо (всех иличасти) входных переменных схемы Σ00 .
В случае стыковки, например, это означает, что схема Σ реализует наборфункций вида F00 (F0 ), где F00 и F0 — наборы функций, реализованные схемами Σ00 и Σ0 соответственно. СуперпозицияΣ = Σ00 (Σ0 ) считается правильной, если схема Σ обладаетуказанным свойством, и корректной, если, кроме того, в любой вершине Σ, которая соответствует выходной вершине Σ0 ,§9. Операция суперпозиции. Лемма Шеннонаx/1x2•/•/x1x2•&••w•'¬••z1 &Σ2x3--∨77•Σ22222...xq,,,,•Σ2z1a)b)Рис. 9.1: пример суперпозиции СФЭреализуется та же самая функция, что и в Σ0 .
Заметим, чтоправильная суперпозиция вида Σ00 (Σ0 ) автоматически является корректной, если кратность любой выходной вершиныΣ0 больше числа присоединяемых к ней входов Σ00 . Заметимтакже, что с содержательной точки зрения корректность суперпозиции вида Σ00 (Σ0 ) позволяет одновременно использовать выходы Σ0 в других суперпозициях.Заметим также, что любая СФЭ может быть получена врезультате многократного применения операции суперпозиции, на каждом шаге которой происходит дублирование выхода или присоединение одного ФЭ, к СФЭ, первоначальносостоящей из тождественных вершин.На рис.
9.1a показана СФЭ Σ⊕2 , имеющая сложность 4 иреализующая ФАЛ x1 ⊕ x2 , а на рис. 9.1b — СФЭ Σ⊕q , q > 3,которая является результатом «последовательной» суперпозиции (q − 1) схем Σ⊕2 и реализует ФАЛ `q (x1 , . . . , xq ) со78Глава 2. Основные классы управляющих системсложностью 4q − 4.Рассмотрим теперь вопросы, связанные с нахождениемфункционирования для суперпозиций сетей или КС. Из соображений удобства будем допускать наличие в КС вентилей и неориентированных ребер без пометок, которые проводят при любых значениях управляющих входных БП иназываются проводниками.
Это позволяет считать, что сетиявляются частным случаем КС и реализуют свои матрицыдостижимости, состоящие из константных ФАЛ.Операция суперпозиции КС и все ее частные случаи определяются обычным образом. При этом пометками входов ивыходов КС, в отличие от СФЭ, не обязательно являютсяпеременные, а БП, управляющие проводимостью контактовКС, никак не связаны с ее входами.Легко видеть, что перестановка входов(выходов) КС порождает в реализуемой ею матрице такую же перестановкусвязанных с ними строк (соответственно столбцов), а снятие(дублирование) выходов этой КС — удаление (соответственно добавление) связаных с ними столбцов. Заметим также,что КС Σ, которая является объединением КС Σ0 и Σ00 , реализующих матрицы F 0 и F 00 соответственно, реализует матрицу F вида1 :F0 0F =0 F 00Обратимся, далее, к особенностям функционирования КС,получающихся в результате применения операций суперпозиции общего вида.
Напомним, что суперпозиция общего вида сводится к последовательному выполнению операций переименования выходов, добавления тождественных вершинПредполагается, что номер любого входа (выхода) КС Σ0 меньшеномера любого входа (соответственно выхода) КС Σ00 в КС Σ, а внутренняя упорядоченность полюсов КС Σ0 и Σ00 в КС Σ сохраняется.В остальных случаях происходит необходимая перестановка входов ивыходов КС Σ.1§9. Операция суперпозиции. Лемма Шеннона? ????? . . . ????? . . . ?'.
. . ??'?? ''?? ' . . . ?? '' ??' a1aa1 a279apapa2aa)b)?'. . . ??'?? ''?? '?? '' ??' y1ypy2z1c)Рис. 9.2: проводящие и вентильная звезды порядка pи стыковки. При этом стыковка, в свою очередь, сводитсяк снятию выходов, отождествлению входов и бесповторнойстыковке.Заметим, что результат отождествления первых p входов КС Σ эквивалентен результату стыковки вида Σ (Σ0 ),а результат p-кратного дублирования первого выхода КСΣ — результату стыковки Σ00 (Σ), где КС Σ0 , Σ00 состоят из(1, p)-проводящей звезды (см. рис. 9.2a, a — вход) и тождеbственных вершин.
Заметим также, что стыковка вида Σ(Σ),b состоит из (p, 1)-проводящей звезды (см. рис. 9.2b,где КС Σa — выход) и тождественных вершин, соответствует отождествлению первых p выходов КС Σ.Схема называется разделительной по входам(выходам),если ФАЛ проводимости между любыми ее различными вхо-80Глава 2. Основные классы управляющих системдами (соответственно выходами) равна 0. Так (p, 1)-схемаΣ00 = Σ00 (y1 , . . . , yp ; z1 ), показанная на рисунке 9.2c, является разделительной по входам схемой, которая называетсявентильной звездой порядка p.
Примером разделительнойпо выходам (входам) КС может служить (1, 2n )- (соответственно (2n , 1)-) контактное дерево порядка n (см. рис. ??).Будем говорить, что КС Σ от БП x1 , . . . , xn разделительнана наборе α = (α1 , . . . , αn ) значений этих БП, если соответствующей разделительностью обладает сеть Σ|α . Следующее утверждение является обобщением известной леммыШеннона (см. [31, 14]).Лемма 9.1. Пусть КС Σ является результатом стыковки вида Σ = Σ00 (Σ0 ), а F , F 0 и F 00 — матрицы, реализуемыеКС Σ, Σ0 и Σ00 соответственно.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
