оки3 (1155746), страница 2
Текст из файла (страница 2)
В частности,ΦΨCБ (F ) 6 ΨБ (F ) ,ΨK (F ) 6 Ψπ (F )§1. Задача синтеза9и т. д. Довольно часто выделение подклассов из основныхклассов схем происходит за счет наложения различных дополнительных свойств на рассматриваемые схемы. В частности, из класса КС выделяют π-схемы, КС, обладающиесвойствами разделительности, и. т. п.Заметим, что для сложности 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 .10Глава 3. Синтез и сложность управляющих системСледствие 2. В силу следствия 1 и с учётом следствия 2из теоремы 2.1 главы 2 справедливо неравенствоD(n) 6 n + dlog ne + 2.Следующее утверждение доказывается моделированиемсовершенной ДНФ с использованием контактного дерева.Лемма 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(рис. 1.1) в результате снятия тех его выходов, где реализу-xn• a0xn• a1•x1•x2x2••x2••1•x1x2...ai•/ xσ1 . . . xσnn1•xn• a2n −2•xn• a2n −1Рис. 1.1: (1, 2n )-контактное дерево порядка n§1. Задача синтеза11ются ЭК, не входящие в совершенную ДНФ ФАЛ f , отождествления остальных выходов КД и перехода к соответствующей приведенной КС. Так как при удалении вершиныудаляются и все инцидентные ей контакты, тоL (Σf ) 6 2 (2n − 1) − (2n − |Nf |) = 2n + |Nf | − 2.Формула Ff получается в результате моделирования построенной π-схемы Σf в классе формул с поднятыми отрицаниями (см.
§2 гл. 2), и поэтомуR (Ff ) = L (Σf ) ,L (Ff ) = R (Ff ) + L− (Σf ) − 1,где L− (Σf ) — число размыкающих контактов в схеме Σ.Следовательно,L (Ff ) 6 L (Σf ) + 2n − 2 6 2n+1 + |Nf | − 4,так как число размыкающих контактов в КД порядка n равно 2n − 1.Лемма доказана.Следствие.Lπ (n) 6 2n+1 − 2,(1.2)LΦ (n) 6 3 · 2n − 4.(1.3)К схемам, полученным на основе простейших методовсинтеза, полезно применять с целью уменьшения их сложности эквивалентные преобразования и, в частности, следующие операции приведения.Пусть вершина w СФЭ Σ не достижима из ее вершины v,а СФЭ Σ0 получается из СФЭ Σ в результате удаления вершины v, объявления вершины w начальной вершиной всехисходивших из v дуг и переноса в вершину w всех выходных БП, приписанных вершине v.
Тогда СФЭ Σ0 считаетсярезультатом применения к СФЭ Σ операции присоединения12Глава 3. Синтез и сложность управляющих системвершины v к вершине w. Заметим, что для любых двух вершин схемы одну из них всегда можно присоединить к другой. Две вершины СФЭ называются эквивалентными, еслив них реализуются равные ФАЛ. Применяя к СФЭ Σ операцию присоединения одной из двух эквивалентных вершинк другой, мы получим СФЭ Σ0 , которая, очевидно, эквивалентна Σ.Приведенная схема называется строго приведенной, если в ней нет эквивалентных вершин. Из любой СФЭ можнополучить эквивалентную ей строго приведенную СФЭ с помощью операции присоединения эквивалентных вершин иоперации удаления висячих вершин.Аналогичным образом определяется операция присоединения вершин в КС, с той лишь разницей, что на нее не накладываются какие-либо ограничения, связанные с достижимостью вершин.→−Для множества ФАЛ G, G ⊆ P2 (n), через G будем обозначать систему, состоящую из всех различных ФАЛ множества G, упорядоченных в соответствии с номерами их столб→−цов значений.
При этом систему ФАЛ P 2 (n) будем называть универсальной системой порядка n.Довольно часто задачу синтеза приходится решать дляследующих ФАЛ и систем ФАЛ:1. линейной ФАЛ порядка n, то есть ФАЛ `n или ФАЛ `n ;2. мультиплексорной ФАЛ µn порядка n;→−→−3. дешифратора Q n (дизъюнктивного дешифратора J n )порядка n;→−4. универсальной системы P 2 (n) порядка n.Лемма 1.3. Для каждого натурального n в UCБ существу→−ет СФЭ Un , которая реализует систему ФАЛ P 2 (n) иnсложность которой равна 22 − n.§2. Нижние оценки13Доказательство. В силу полноты базиса, в UCБ существует система формул Σ от БП x1 , . .
. , xn , которая реализу→−ет систему ФАЛ P 2 (n). Искомая СФЭ Un является строго приведенной СФЭ, которая эквивалентна Σ и получаетсяиз нее в результате применения операций присоединения эквивалентных вершин, а также операций удаления висячихвершин (см. §4 главы 2). Действительно, из построения следует, что число всех вершин СФЭ Un , включая n ее входов,nравно 22 и поэтомуnL (Un ) = 22 − n.Лемма доказана.Следствие.§2→−nLCP(n)6 22 − n.2БНижние оценки сложности ФАЛ, реализация некоторых ФАЛ и минимальность некоторых схем.Рассмотрим сначала простейшие нижние оценки сложностиФАЛ и связанные с ними примеры минимальных схем.Лемма 2.1. Если ФАЛ f (x1 , . . . , xn ) существенно зависитот всех своих БП, тоLC (f ) > n − 1,LK (f ) > n.(2.1)Если при этом ФАЛ f не является монотонной ФАЛ (каждая БП xi , i ∈ [1, k], не является ни монотонной, ни инмонотонной БП ФАЛ f ), тоLC (f ) > n(соответственно LK (f ) > n + k).(2.2)14Глава 3.
Синтез и сложность управляющих системДоказательство. Пусть Σf — минимальная по сложностиСФЭ из UC , реализующая ФАЛ f . Из существенной зависимости ФАЛ f от БП x1 , . . . , xn следует, что R (Σf ) > n, ипоэтому, в силу соотношений (2.6) главы 2,LC (f ) > L&, ∨ (Σf ) > n − 1.Если же, кроме того, ФАЛ f не является монотоннойФАЛ, то схема Σf должна содержать хотя бы один ФЭ ¬ и,следовательно, в указанном случаеLC (f ) = L (Σf ) > n.Таким образом, первые из неравенств (2.1) и (2.2) доказаны.Пусть теперь Σf — минимальная по сложности (1, 1)-КС,реализующая ФАЛ f . Из существенной зависимости ФАЛ fот БП 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.§2.
Нижние оценки15[0,n−1]Замечание. Нижние оценки сложности ФАЛ f = sn,вытекающие из леммы 2.1, доказывают минимальность πсхемы, моделирующей ЭД x1 ∨ · · · ∨ xn = f , в классе КС иминиальность формулы (x1 . . . xn ) = f в классе СФЭ, чтоустанавливает равенства LK (f ) = n и LC (f ) = n.Лемма 2.2. Для системы F = (f1 , .
. . , fm ), состоящей изпопарно различных ФАЛ отличных от констант (от переменных), справедливо неравенствоLK (F ) > m(соответственно LCБ (F ) > m).(2.3)Доказательство. Второе из неравенств (2.3) вытекает изтого, что все ФАЛ fi , i = 1, . . . , m, реализуются на попарно различных выходах СФЭ, отличных от ее входов.Пусть теперь ΣF — приведенная (1, m)-КС, реализующая систему ФАЛ F .
Из приведенности ΣF и условий леммы вытекает, что ΣF — связный граф с не менее чем (m + 1)вершиной, и поэтому, в силу неравенства (1.2) главы 2,L (ΣF ) > |V (ΣF )| − 1 > m.Лемма доказана.Следствие.→− LC Q n > 2 n ,→− LC J n > 2 n ,→−nLCP(n)> 22 − n,2Б→− L K Q n > 2n ,→− L K J n > 2n ,→−nLK P 2 (n) > 22 − 2.Замечание. В силу следствия универсальная СФЭ Un , построенная в лемме 1.3, является минимальной по сложностиСФЭ в классе UCБ.16Глава 3. Синтез и сложность управляющих системРассмотрим некоторые схемные реализации и соответствующие им верхние оценки сложности для некоторых ФАЛи систем ФАЛ.
Будем, как обычно, называть (схемным) мультиплексором, дешифратором, дизъюнктивным дешифратором и универсальным многополюсником любую схему, которая реализует соответствующую систему ФАЛ.Лемма 2.3. Для любого натурального n выполняются неравенства:nn→−→−LC ( Q n ) 6 2n + O(n · 2 2 ), LC ( J n ) 6 2n + O(n · 2 2 ); (2.4)→−LK ( Q n ) 6 2n+1 − 2;(2.5)Lπ (µn ) 6 3 · 2n − 2,LC (`n ) 6 4n − 4,LΦ (µn ) 6 2n+2 − 3;(2.6) 1LC (`n ) 6 4n − 4 +. (2.7)nДоказательство.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
