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

. , 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Введение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Введениевершины 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.Введение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ВведениеДоказательство. Пусть Σ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.Введение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ВведениеРассмотрим некоторые схемные реализации и соответствующие им верхние оценки сложности для некоторых ФАЛи систем ФАЛ. Будем, как обычно, называть (схемным) мультиплексором, дешифратором, дизъюнктивным дешифратором и универсальным многополюсником любую схему, которая реализует соответствующую систему ФАЛ.Лемма 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Доказательство. В классе UC построим схемный дешифратор порядка n, удовлетворяющий первому неравенству (2.4),следующим образом:1.

разобьем набор БП 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, удовлетворяющий второму неравенству (2.4).Введение17xn•xn••x1•x2x2••x2••a1x1x2y0y1a2y2n −2•xn•xn•y2n −1•Рис.

2.1: π-схема для ФАЛ µnИскомым контактным дешифратором порядка n является (1, 2n )-контактное дерево, показанное на рис. 1.1, а искомым контактным мультиплексором порядка n являетсяπ-схема, приведенная на рис. 2.1. Заметим, что сложностьсхем, показанных на рис. 1.1 и 2.1, равна 2n+1 − 2 и 3 · 2n − 2соответственно, то есть удовлетворяет неравенствам (2.5) и(2.6), причем число размыкающих контактов в каждой изних равно 2n − 1.В результате моделирования указанной π-схемы можнопостроить бесповторную по информационным БП формулуFn (x1 , . .

. , xn , y0 , . . . , y2n −1 ) =! !___=xσ1 1 xσ2 2 · · ·xσnn yν(σ1 ,...,σn ) · · ·  ,σ1 ∈Bσ2 ∈Bσn ∈Bкоторая удовлетворяет второму неравенству (2.6), так как18Введениеx1x2•x1x2•••Σ⊕2x3•&•w•'¬∨Σ⊕2•...•z1 &xn•Σ⊕2z1a)b)Рис. 2.2: СФЭ для ФАЛ `2 и `nреализует ФАЛ µn и имеет сложность 4 · 2n − 3.Неравенства (2.7) при n = 1, очевидно, выполняются.Искомой СФЭ, реализующей линейную ФАЛ `n , n > 2,со сложностью (2.7), является СФЭ Σ⊕n , показанная нарис. 2.2a,b.

Аналогичная СФЭ для ФАЛ `n получается в результате замены ФЭ & на ФЭ ∨ и ФЭ ∨ на ФЭ & в первой⊕подсхеме вида Σ⊕2 схемы Σn (см. рис. 2.2a).Лемма доказана.Следствие.→−→−LС ( Q n ) ∼ LС ( J n ) ∼ 2n .Лемма 2.4. Если система ФАЛ F = (f1 , . . . , fm ) состоит из попарно различных ФАЛ от БП X(n), отличныхВведение19от 0 и 1, тоKL (F ) > 21−nmXNf .jj=1Доказательство. Возьмем приведенную (1, m)-КС Σ, реализующую систему ФАЛ F , и заметим, что при любом α, α ∈B n , в сети Σ|α имеется связная компонента, которая содержит вход Σ и те ее выходы, где реализуемые ФАЛ обращаются в 1 на наборе α. Из неравенства (1.2) главы 2 следует,что при этом|E (Σ|α )| > f1 (α) + · · · + fm (α).Суммируя полученное неравенство по всем наборам α, α ∈B n , придем к неравенству2n−1 L(Σ) >mXNf ,jj=1из которого вытекает неравенство леммы.Лемма доказана.Следствие.LK (Jn ) > 2n+1 − 2.Замечание.

В силу следствия (1, 4)-КС с входом a, котораясостоит из двух непересекающихся по внутренним вершинам(a − a)-цепей (циклов) длины 3 с ЭК проводимости x1 x2 x1и x1 x2 x1 , является минимальным дизъюнктивным контактным дешифратором порядка 2.Лемма 2.5. Если для ФАЛ f , f ∈ P2 (n), и для любого σ,σ ∈ B, ФАЛ fσ (x1 , . .

. , xn−1 , σ) 6≡ 0, 1, тоCCLC&,∨ (f ) > min{L&,∨ (f0 ), L&,∨ (f1 )} + 2.(2.8)20ВведениеДоказательство. Пусть Σ — минимальная по числу ФЭ &и ∨ СФЭ из класса UC , которая реализует ФАЛ f и котораяне содержит цепочек из двух последовательно соединенныхФЭ ¬. Из условия леммы следует, что выход ФЭ ¬, присоединённого к входу xn СФЭ Σ не может быть её выходом.Пусть цепь C соединяет вход xn СФЭ Σ с её выходом z1и пусть константа σ, σ ∈ B, равна 0 тогда и только тогда,когда БП xn подается в C либо на вход ФЭ &, либо на входФЭ ¬, к выходу которого в C присоединён ФЭ ∨.b которая реализует ФАЛ fσ , fσ 6≡ 0, 1,Рассмотрим СФЭ Σ,и получена из СФЭ Σ в результате подстановки xn = σ, атакже последующего ЭП на основе тождеств τ ПК (см.

§5гл. 2) вплоть до устранения всех вхождений констант. Убедимся в том, что при указанном ЭП будут удалены по крайней мере два ФЭ типа & или ∨.Действительно, в случае σ = 0 из СФЭ Σ будет удаленФЭ E0 , являющийся первым ФЭ типа & или ∨ цепи C. Заметим, что выход ФЭ E0 не может быть выходом схемы и неможет быть входом ФЭ ¬, выход которого является выходомсхемы, так как при этом ФАЛ fσ была бы равна константе.Следовательно, на цепи C СФЭ Σ имеется ФЭ E00 типа &или ∨, на вход которого поступает либо выход E0 , либо выход ФЭ ¬, присоединенного к выходу E0 . Легко видеть, чтоb и, следоваФЭ E00 тоже будет удален при переходе от Σ к Σтельно, справедливы неравенстваb + 2 > L&,∨ (fσ ) + 2,L&,∨ (f ) = L&,∨ (Σ) > L&,∨ (Σ)из которых вытекает (2.8).Случай σ = 1, когда БП xn подаётся в C либо на входФЭ ∨, либо на вход ФЭ ¬, к выходу которого присоединёнФЭ типа &, рассматривается аналогично.Лемма доказана.Введение21Следствие 1.LC (µn ) > 2n+1 + n − 1.(2.9)Действительно, (2.9) получается в результате применения леммы 2.5 последовательно ко всем информационнымБП y2n −1 , .