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

В частности,ΦΨCБ (F ) 6 ΨБ (F ) ,ΨK (F ) 6 Ψπ (F )и т. д. Довольно часто выделение подклассов из основныхклассов схем происходит за счет наложения различных до-8Глава 3. Синтез и сложность управляющих системполнительных свойств на рассматриваемые схемы. В частности, из класса КС выделяют π-схемы, КС, обладающиесвойствами разделительности, и. т. п.Заметим, что для сложности L (F ) системы ФАЛ F =(f1 , . . . , fm ) в любом из рассматриваемых классов схем выполняются неравенстваmax L (fi ) 6 L (F ) 616i6mmXL (f )i .i=1Задача синтеза допускает тривиальное решение, связанное с использованием переборного алгоритма, который, однако, имеет большую трудоемкость и практически не применим, если число БП больше 5.Для реализации произвольных ФАЛ и получения верхних оценок их сложности можно использовать другой простейший метод синтеза схем, основанный на моделированиисовершенной ДНФ.

На основе этого моделирования, в частности, доказывается следующее утверждение.Лемма 1.1. Для любой функции алгебры логики f (x1 , . . . , xn ),f 6= 0, существуют формула Ff , Ff ∈ UΦ , и π-схема Σf ,которые реализуют f и для которых справедливы неравенства:L (Ff ) 6 2n · |Nf | − 1,L (Σf ) 6 n |Nf | .(1.1)Следствие 1. В силу (1.1), с учетом того, что ФАЛ 0можно реализовать π-схемой сложности 2, а также формулой из UΦ , имеющей сложность 2, выполняются неравенстваLC (n) 6 LΦ (n) 6 n · 2n+1 − 1,LK (n) 6 Lπ (n) 6 n · 2n .§1.

Задача синтеза9Следующее утверждение доказывается моделированиемсовершенной ДНФ с использованием контактного дерева.Лемма 1.2. Для любой ФАЛ f, f ∈ P2 (n) и f 6= 0, существуют π-схема Σf и формула Ff , Ff ∈ UΦ , которыереализуют f и для которых, наряду с (1.1), справедливытакже неравенства:L (Σf ) 6 2n + |Nf | − 2,L (Ff ) 6 2n+1 + |Nf | − 4.Доказательство.

В качестве Σf можно взять π-схему, которая получается из (1, 2n )-КД порядка n от БП x1 , . . . , xn(см. рис. ??a из ?? главы 2) в результате снятия тех еговыходов, где реализуются ЭК, не входящие в совершеннуюДНФ ФАЛ f , отождествления остальных выходов КД и перехода к соответствующей приведенной КС. Так как приудалении вершины удаляются и все инцидентные ей контакты, тоL (Σf ) 6 2 (2n − 1) − (2n − |Nf |) = 2n + |Nf | − 2.Формула Ff получается в результате моделирования построенной π-схемы Σf в классе формул с поднятыми отрицаниями (см.

?? гл. 2), и поэтомуL (Ff ) = R (Ff ) + L− (Σf ) − 1,R (Ff ) = L (Σf ) ,где L− (Σf ) — число размыкающих контактов в схеме Σ.Следовательно,L (Ff ) 6 L (Σf ) + 2n − 2 6 2n+1 + |Nf | − 4,так как число размыкающих контактов в КД порядка n равно 2n − 1.Лемма доказана.Следствие.Lπ (n) 6 2n+1 − 2,ΦnL (n) 6 3 · 2 − 4.(1.2)(1.3)10Глава 3. Синтез и сложность управляющих системДовольно часто задачу синтеза приходится решать дляследующих ФАЛ и систем ФАЛ:1.

линейной ФАЛ порядка n, то есть ФАЛ `n или ФАЛ `n ;2. мультиплексорной ФАЛ µn порядка n;→−→−3. дешифратора Q n (дизъюнктивного дешифратора J n )порядка n;→−4. универсальной системы P 2 (n) порядка n, состоящей извсех различных ФАЛ множества P2 (n), упорядоченныхв соответствии с номерами их столбцов значений.Рассмотрим некоторые схемные реализации и соответствующие им верхние оценки сложности для указанных ФАЛи систем ФАЛ. Следуя ?? главы 2, будем называть (схемным) мультиплексором, дешифратором, дизъюнктивным дешифратором и универсальным многополюсником любую схему, которая реализует соответствующую систему ФАЛ. Примером контактного дешифратора порядка n является (1, 2n )контактное дерево, показанное на рисунке ??, а пример контактного мультиплексора порядка n дает π-схема, приведенная на рис.

??b главы 2.Лемма 1.3. Для любого натурального n выполняются неравенства:n→−LC ( Q n ) 6 2n + O(n · 2 2 ),Lπ (µn ) 6 3 · 2n − 2,LC (`n ) 6 4n − 4,→−LK ( Q n ) 6 2n+1 − 2;(1.4)LΦ (µn ) 6 2n+2 − 3;(1.5) 1LC (`n ) 6 4n − 4 +. (1.6)nДоказательство. В классе UC построим схемный дешифратор порядка n, удовлетворяющий первому неравенству (??),следующим образом:§1.

Задача синтеза111. разобьем набор БП X(n) на группы x0 == (x1 , . . . , xq ), x00 = (xq+1 , . . . , xn ), где q = dn/2e;2. возьмем дешифраторы Σ0 и Σ00 от БП x0 и x00 порядкаq и (n − q) соответственно, реализующие каждую своюсистему ЭК по лемме 1.1;3. объединим СФЭ Σ0 и Σ00 , после чего конъюнктируемкаждый выход Σ0 с каждым выходом Σ00 , а выходы всехиспользованных для этого 2n ФЭ & (и только их) объявим выходами искомого дешифратора.Искомым контактным дешифратором порядка n является(1, 2n )-контактное дерево, показанное на рисунке 6.4a §6 главы 2, а искомым контактным мультиплексором порядка n —π-схема, приведенная там же на рис. 6.6b. Заметим, чтосложность схем, показанных на рис.

6.4a и 6.6b, равна 2n+1 −2 и 3 · 2n − 2 соответственно, то есть удовлетворяет неравенствам (??) и (1.5), причем число размыкающих контактов вкаждой из них равно 2n − 1.В результате моделирования π-схемы, показанной на ??b,можно построить бесповторную по информационным БПформулу (см. ??,?? главы 2)Fn (x1 , . . . , xn , y0 , . . . , y2n −1 ) =! !___=xσ1 1 xσ2 2 · · ·xσnn yν(σ1 ,...,σn ) · · ·  ,σ1 ∈Bσ2 ∈Bσn ∈Bкоторая удовлетворяет второму неравенству (1.5), так какреализует ФАЛ µn , имеет сложность 4 · 2n − 3 и альтернирование 2n − 1.Неравенства (1.6) при n = 1, очевидно, выполняются.Искомой СФЭ, реализующей линейную ФАЛ `n , n > 2, сосложностью (1.6), является СФЭ Σ⊕n , показанная на рис. 4.112Глава 3. Синтез и сложность управляющих системглавы 2.

Аналогичная СФЭ для ФАЛ `n получается в результате замены ФЭ & на ФЭ ∨ и ФЭ ∨ на ФЭ & в первой⊕подсхеме вида Σ⊕2 схемы Σn (см. рис. 4.1b главы 2).Лемма доказана.Рассмотрим, далее, некоторые нижние оценки сложности ФАЛ и примеры минимальных схем.Лемма 1.4. Если ФАЛ f (x1 , . . . , xn ) существенно зависитот всех своих БП, тоLC (f ) > n − 1,LK (f ) > n.(1.7)Если при этом ФАЛ f не является монотонной ФАЛ (каждая БП xi , i ∈ [1, k], не является ни монотонной, ни инмонотонной БП ФАЛ f ), тоLC (f ) > n(соответственно LK (f ) > n + k).(1.8)Доказательство. Пусть Σf — минимальная по сложностиСФЭ из UC , реализующая ФАЛ f .

Из существенной зависимости ФАЛ f от БП x1 , . . . , xn следует, что R (Σf ) > n, ипоэтому, в силу соотношений ?? главы 2,LC (f ) > L&, ∨ (Σf ) > n − 1.Если же, кроме того, ФАЛ f не является монотоннойФАЛ, то схема Σf должна содержать хотя бы один ФЭ ¬ и,следовательно, в указанном случаеLC (f ) = L (Σf ) > n.Таким образом, первые из неравенств (1.7) и (1.8) доказаны.Пусть теперь Σf — минимальная по сложности (1, 1)-КС,реализующая ФАЛ f . Из существенной зависимости ФАЛ f§1. Задача синтеза13от БП xi , i ∈ [1, n], следует, что либо контакт вида xi , либоконтакт вида xi встречается в КС Σf , и поэтомуLK (f ) = L (Σf ) > n.Если же, кроме того, БП xi , i ∈ [1, k], не является ни монотонной, ни инмонотонной БП ФАЛ f , то как контакт видаxi , так и контакт вида xi входят в Σf , и, следовательно, вданном случаеLK (f ) = L (Σf ) > n + k.Лемма доказана.Следствие.LC (`n ) > n,LK (`n ) > 2n,LC (µn ) > 2n + n,LK (µn ) > 2n + 2n.Лемма 1.5.

Для системы F = (f1 , . . . , fm ), состоящей изпопарно различных ФАЛ отличных от констант (от переменных), справедливо неравенствоLK (F ) > m(соответственно LCБ (F ) > m).(1.9)Доказательство. Второе из неравенств (1.9) вытекает изтого, что все ФАЛ fi , i = 1, . . .

, m, реализуются на попарно различных выходах СФЭ, отличных от ее входов.Пусть теперь ΣF — приведенная (1, m)-КС, реализующая систему ФАЛ F . Из приведенности ΣF и условий леммы вытекает, что ΣF — связный граф с не менее чем (m + 1)вершиной, и поэтому, в силу неравенства ??главы 2,L (ΣF ) > |V (ΣF )| − 1 > m.Лемма доказана.14Глава 3. Синтез и сложность управляющих системСледствие.−→ L Q n > 2n ,−→ LC J n > 2n ,−→nLCP(n)> 22 − n,2БC−→ Q n > 2n ,L−→ LK J n > 2n ,−→nLK P 2 (n) > 22 − 2.KПусть вершина w СФЭ Σ не достижима из ее вершины v,а СФЭ Σ0 получается из СФЭ Σ в результате удаления вершины v, объявления вершины w начальной вершиной всехисходивших из v дуг и переноса в вершину w всех выходных БП, приписанных вершине v.

Тогда СФЭ Σ0 считаетсярезультатом применения к СФЭ Σ операции присоединениявершины v к вершине w. Заметим, что для любых двух вершин схемы одну из них всегда можно присоединить к другой. Две вершины СФЭ называются эквивалентными, еслив них реализуются равные ФАЛ. Применяя к СФЭ Σ операцию присоединения одной из двух эквивалентных вершинк другой, мы получим СФЭ Σ0 , которая, очевидно, эквивалентна Σ.Приведенная схема называется строго приведенной, если в ней нет эквивалентных вершин. Из любой СФЭ можнополучить эквивалентную ей строго приведенную СФЭ с помощью операции присоединения эквивалентных вершин иоперации удаления висячих вершин.Аналогичным образом определяется операция присоединения вершин в КС, с той лишь разницей, что на нее не накладываются какие-либо ограничения, связанные с достижимостью вершин.Лемма 1.6.

Для каждого натурального n в UCБ существует универсальная СФЭ Un порядка n, сложность которойnравна 22 − n.§2. Метод каскадов для КС и СФЭ15Доказательство. В силу полноты базиса, в UCБ существует система формул Σ от БП x1 , . . . , xn , которая реализу→−ет систему ФАЛ P 2 (n). Искомая СФЭ Un является строго приведенной СФЭ, которая эквивалентна Σ и получаетсяиз нее в результате применения операций присоединения эквивалентных вершин, а также операций удаления висячихвершин (см. ?? главы 2).

Действительно, из построения следует, что число всех вершин СФЭ Un , включая n ее входов,nравно 22 и поэтомуnL (Un ) = 22 − n.Лемма доказана.Замечание. В силу следствия из леммы 1.5, построенная схема Un является минимальной по сложности универсальнойСФЭ порядка n, и поэтому, в частности,−→nLCP(n)= 22 − n.2Б§2Метод каскадов для контактных схем исхем из функциональных элементов.Метод ШеннонаПриведенные в §1 простейшие методы синтеза позволяютстроить формулы и π-схемы, специфика которых не допускает многократного использования «промежуточных результатов».