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

4.4 — соответствующая ей КС ΣF , а на рис. 4.5 —СФЭ UF .Другим примером КС, построенной по методу каскадовдля линейной ФАЛ `n , где n > 2, является известная схемаВведение37x1x1x4•x4x3 ⊕ x4x2•x1x31x4x4•x3f2•x2 (x3 ⊕ x4 )x3x3 x4•x2x2 ∨ x3 x4•x1x2f1Рис. 4.3: пример КС с помеченными вершинами,построенной методом каскадовx1x1x4••x2f2•x3x1x31x4•x3x2•x2•x1f1Рис.

4.4: пример КС, построенной методом каскадов38Введениеx1x4•x3••¬•¬ •&¬ •x2•&••∨•∨&••$&&•&•&•∨•)∨••f2f1Рис. 4.5: СФЭ для системы ФАЛ F , построенная методомкаскадов1x2•x1x2x1••...xn−1xn−1x2x2••...••xnxn−1 xnxn−1•Рис. 4.6: схема Кардо для линейной функции `n`nВведение39Кардо [32], показанная на рис. 4.6. Заметим, что эта КСимеет сложность (4n − 4) и является минимальной.

В то жевремя СФЭ, построенная для `n , n > 2, по методу каскадовимеет сложность (7n − 9) и не является минимальной, таккак имеет бо́льшую сложность по сравнению со схемой Σ⊕nсложности (4n − 4), показанной на рис. 2.2. Аналогичныеоценки справедливы для ФАЛ `n (см. лемму 2.3).При построении по методу каскадов (1, 2n )-КС, реализу→−ющей систему функций алгебры логики Q n , мы получимконтактное дерево порядка n, показанное на рис. 1.1. Какбудет показано далее это КД не является минимальным контактным дешифратором.Аналогичным образом с помощью метода каскадов можно построить контактный дизъюнктивный дешифратор порядка n и сложности не больше, чем 2n+2 − 6, контактныйуниверсальный многополюсник порядка n и сложности неnбольше, чем 2 · 22 , а также контактный мультиплексор порядка n и сложности 3 · 2n − 2, показанный на рис. 2.1 (см.лемму 2.3).

Заметим, что указанный мультиплексор получается при разложении ФАЛ µn сначала по адресным, а затемпо информационным БП. В то же время, контактный мультиплексор порядка n, построенный по методу каскадов приразложении ФАЛ µn сначала по информационным, а затемпо адресным БП, содержит КД порядка 2n от информациnонных БП и поэтому имеет сложность не меньше, чем 22 +1 .Это показывает, что выбор «правильного» порядка переменных при разложении ФАЛ может существенно уменьшитьсложность КС, построенной по методу каскадов.Учитывая все сказанное выше, дополним леммы 1.3 и 2.3следующим утверждением.Лемма 4.2. Для любого натурального n и σ ∈ B выполня-40Введениеются неравенства:KL(`σn ) →−1n,LK P 2 (n) 6 2 · 22 ,6 4n − 4 +n− K →L J n 6 2n+2 − 6.Рассмотрим, в заключение, метод Шеннона для синтеза КС и СФЭ (см.

[33, 14]), который позволяет установитьпорядок роста функций Шеннона LK (n) и LC (n).Метод Шеннона заключается в выборе некоторого параметра q, 1 6 q 6 n, и построении схемы Σf , реализующейпроизвольную ФАЛ f (x1 , . . . , xn ) на основе ее разложенияпо части переменных:_σq+1f x0 , x00 =xq+1· · · xσnn · fσ00 x0 ,(4.5)σ 00 =(σq+1 ,...,σn )где x0 = (x1 , .

. . , xq ) , x00 = (xq+1 , . . . , xn ) и fσ00 (x0 ) == f (x0 , σ 00 ) при всех σ 00 , σ 00 ∈ B n−q . При этом схема Σf представляет собой суперпозицию вида Σ00 (Σ0 ), где Σ00 — мультиплексор порядка (n − q) от адресных БП x00 , информационные входы которого при выполнении указанной суперпозиции присоединяются к выходам универсального многополюсника Σ0 порядка q от БП x0 в соответствии с (4.5).Полагаяq = blog (n − 2 log n)c ,построим для ФАЛ f (x1 , .

. . , xn ) указанным выше способомКС (СФЭ в базисе Б0 ) Σf , где Σ00 — (2n−q , 1)-КД порядка(n − q) (соответственно формула Fn−q из леммы 2.3), а Σ0 —универсальный многополюсник из леммы 4.2 (соответственно леммы 1.3). Корректность построенной суперпозиции, т.е.реализация схемой Σf ФАЛ f в случае СФЭ очевидна, а вслучае КС обеспечивается тем, что её можно представитьв виде результата многократной операции присоединенияВведение41двух противоположенных контактов, корректность которойбыла отмечена выше (см. рис. 4.1).

Для сложности полученной схемы Σf будут справедливы оценки n2n+222qn−q,L (Σf ) 6 2 · 2 + 2 · 26+On − 2 log nn2если Σf ∈ UK , иqL (Σf ) 6 22 + 4 · 2n−q 68 · 2n+On − 2 log n2nn2,если Σf ∈ UC . Таким образом, доказано следующее утверждение.Теорема 4.1. Для функций Шеннона LK (n) и LC (n) выполнены соотношения:LK (n) . 4§52n,nLC (n) . 82n.nНижние мощностные оценки функции Шеннона, их обобщение на случай синтеза схемдля функций из специальных классовУстановим теперь ряд нижних оценок для введенных в §1функций Шеннона.

Все эти оценки получены с помощьюмощностного метода, предложенного Шенноном [33, 14], который основан на том, что число ФАЛ от БП x1 , . . . , xn неможет быть меньше числа тех попарно не эквивалентныхсхем, сложность которых не превосходит значения соответствующей функции Шеннона от аргумента n.Пусть U — один из рассмотренных в главе 2 классов схем,Ψ — введенный там функционал сложности, а Ψ (n) — функция Шеннона для класса U относительно Ψ.

Обозначим через U (Ψ, n) множество тех схем Σ, Σ ∈ U, которые реализу-42Введениеют одну ФАЛ из P2 (n) и для которых Ψ (Σ) 6 Ψ. Следующее «мощностное» равенство вытекает непосредственно изопределений:nkU (Ψ (n) , n)k = 22 .(5.1)Заметим также, что если для некоторого натурального n иb δ, где 0 < δ < 1, выполняется неравендействительных Ψ,ство nb n b(5.2) 6 δ · 22 , то Ψ(f ) > ΨU Ψ,nдля не менее чем (1 − δ) · 22 ФАЛ f из P2 (n).Верхние оценки величины kU(Ψ, n)k, установленные вглаве 2 для различных классов схем и функционалов сложности, а также соотношения (5.1)–(5.2) служат основой дляполучения нижних мощностных оценок соответствующих функций Шеннона и сложности почти всех ФАЛ. Напомним, что(см.

леммы 4.3, 4.2, 6.2, 6.3 из главы 2) для любых натуральных n и L справедливы неравенства: CU (L, n) 6 (8 (L + n))L+1 ,(5.3) ΦU (L, n) 6 (8n)L+1 ,(5.4) KLU (L, n) 6 (8nL) ,(5.5)kUπ (L, n)k 6 (12n)L , ΦU [L, n] 6 (8n)2D .(5.6)(5.7)Лемма 5.1. Для положительных действительных чиселa, y, q из неравенствa log q > 1,(ay)y > q,(5.8)следует неравенствоlog qy>log (a log q)log log (a log q)1+,log (ae log q)(5.9)Введение43где e — основание натуральных логарифмов, а из неравенствa > 1, ay > q — неравенствоy>log q.log a(5.10)Доказательство.

Рассмотрим сначала случай, когда a = 1и log q > 1. В этом случае неравенство (5.9) следует из того,что левая часть (5.8) монотонно возрастает по y, и дляy 0 = (1 + ε)log q,log log qгдеlog log log q,log (e log q)справедливы соотношенияε=y 0 log y 0 =log q(log log q − log log log q + log e ln (1 + ε)) 6log log qlog log log qε log e6 log q (1 + ε) 1 −+=log log qlog log q= log q (1 + ε) (1 − ε) = log q 1 − ε2 6 log q.= (1 + ε)Заметим, что в случае a > 0 неравенство (5.8) эквивалентнонеравенству(ay)ay > q a ,и поэтому неравенство (5.9) получается из неравенства y > y 0в результате замены y на ay и log q на a log q, если выполненоусловие a log q > 1.Неравенство (5.10) в случае a > 1 получается в результате логарифмирования неравенства ay > q и деления обеихчастей полученного неравенства на log a.Лемма доказана.44ВведениеТеорема 5.1. Для некоторых последовательностей εi =εi (n),где i = 1, .

. . , 5 и n = 1, 2, . . ., таких, что εi (n) > 0 приn > n0 и εi (n) стремится к 0 при n стремящемся к бесконечности, для почти всех ФАЛ f , f ∈ P2 (n), выполняютсянеравенства2n,n2nLΦ (f ) > (1 − ε2 (n)),log n2nLK (f ) > (1 − ε3 (n)) ,n2nLπ (f ) > (1 − ε4 (n)),log nD (f ) > n − log log n − ε5 (n).LC (f ) > (1 + ε1 (n))(5.11)(5.12)(5.13)(5.14)(5.15)Доказательство. Неравенства (5.11)–(5.14) выводятся из соответствующего рассматриваемому классу схем U с функционалом сложности L неравенства (5.3)–(5.6) на основе мощностного неравенства (5.2), где δ = 1/n с использованиемnлеммы 5.1, где q = 22 /n, и1)2)3)4)a = 8,a = 8n,a = 8n,a = 12n,yyyy= LC (n) + n,= LΦ (n) + 1,= LK (n),= Lπ (n),еслиеслиеслиеслиU = UC ;U = UΦ ;U = UK ;U = Uπ .Действительно, подставляя указанные значения в (5.9) по-Введение45лучим, что доля тех ФАЛ f , f ∈ P2 (n), для которыхlog(n + 3) − o(1)2nC1+−n>1) L (f ) >n+3n+5(5.16)2nlog n − 3 − o(1)>1+;nnn3 + o(1)2 − log n2nΦ1−;(5.17)2) L (f ) >−1>log n + 3log nlog n2nlog(n + 3 + log n) − o(1)3) LK (f ) >1+>n + 3 + log nn + 5 + log n2n3 + o(1)1−,>nn(5.18)не меньше, чем (1 − 1/n).

Следовательно, неравенство (5.11)((5.12), (5.13)) будет справедливо для достаточно большихn при ε1 (n) = log nn−4 (соответственно ε2 (n) = log4 n , ε3 (n) =4n ).Аналогичным образом устанавливается справедливость(5.14) и (5.15) при ε4 (n) = log6 n = ε5 (n).Теорема доказана.Следствие.D(n) > n − log log n − o(1),2n2nLC (n) &, LΦ (n) &,nlog n2n2nLK (n) &, Lπ (n) &.nlog nМощностные соображения можно использовать при получении нижних оценок для функций Шеннона, связанныхс реализацией ФАЛ из класса Q, Q = Q (1) , Q (2) , . .

.. . . , Q (n) , . . . , гдеQ ⊆ P2 и Q (n) = Q ∩ P2 (n) 6= ∅,n = 1, 2, . . . .46ВведениеПусть U — один из рассмотренных в главе 2 классов схем,Ψ — введенный там функционал сложности, а Ψ (Q (n)) —функция Шеннона (для класса схем U относительно функционала сложности Ψ), связанная с классом ФАЛ Q, то естьΨ (Q (n)) = max Ψ (f ) .f ∈Q(n)Следующее «мощностное» неравенство обобщает равенство (5.1)и вытекает непосредственно из определений:kU (Ψ (Q (n)) , n)k > |Q (n)| .(5.19)Оно позволяет получить нижнюю оценку функции Шеннона Ψ (Q (n)) на основе известной верхней оценки величиныkU (Ψ, n)k.Рассмотрим, в частности, нижние мощностные оценкидля функций LC (Q (n)) и LK (Q (n)), то есть функций Шеннона для сложности реализации ФАЛ из класса Q схемамииз классов UC и UK соответственно.