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

В последнем случае, кроe 00 ,ме того, из аналогичного равенства, связанного с КС Σкоторая получается из КС Σ00 в результате объявления ееe 00 , следует развходов входами и, одновременно, выходами Σделительность КС Σ по входам.Заметим, наконец, что стыковка общего вида Σ = Σ00 (Σ0 )сводится к последовательномувыполнению отождествления000000bвходов вида Σ = Σ Σ̌ и бесповторной стыковки видаb 00 (Σb 0 ), где КС Σ̌00 состоит из проводящей звезды и тожΣ=Σb 0 получается из КС Σ0 снятиемдественных вершин, а КС Σнекоторых выходов.

При этом неравенство (в случае разделительности КС Σ00 по входам равенство) 4.1 для КС Σ, Σ0 ,Σ00 вытекает из установленных выше аналогичных соотноb 00 , Σ̌00 , Σ00 и КС Σ, Σb 0, Σb 00 в силу ассоциатившений для КС Σности произведения матриц. Случай разделительности КСΣ0 по выходам рассматривается аналогично.Лемма доказана.§4. Операция суперпозиции. Лемма Шеннона39Следствие 1. В случае разделительности КС Σ00 по входам в каждой вершине КС Σ, Σ = Σ00 (Σ), которая соответствует выходу КС Σ0 , реализуется тот же самый столбецФАЛ, что и в КС Σ0 .Действительно, полагая v 0 = a0i и v 00 = aj , где i ∈ [1, p], аj ∈ [1, q], из 4.3 получим требуемое равенство f = fj0 . Случайстыковки общего вида рассматривается аналогично.Следствие 2.

Равенство 4.1 выполняется на любом наборезначений БП, на котором КС Σ00 разделительна по входамили КС Σ0 разделительна по выходам.Стыковка (суперпозиция) КС вида Σ = Σ00 (Σ)0 называется правильной, если она удовлетворяет равенству 4.1, исчитается корректной, если она, кроме того, удовлетворяеттребованиям следствия 1 из леммы ??1 Аналогичным образом определяется правильность и корректность суперпозиции КС на заданном наборе значений управляющих БП.Заметим, что при правильной стыковке (1, p)-КС 0 и (p,0 1)КС,строку и столбец из ФАЛ f1 , . . .

, fp и 00 реализующихf1 , . . . , fp00 соответственно, получается (1, 1)-КС, реализующая ФАЛ f10 f100 ∨· · ·∨fp0 fp00 , при правильном отождествлениивходов (выходов) КС в реализуемой ею матрице происходитпоразрядная дизъюнкция тех строк (соответственно столбцов), которые соответствуют отождествленным входам (соответственно выходам) и т. п.Легко видеть, что операции переименования входов безотождествления, переименования выходов и объединения корректны в любом случае.

Из леммы ?? и ее следствий выте1Эти определения соответствуют определениям ?? в рамках моделитак называемых преобразующих КС. Требования следствия 1 леммы?? не распространяются, как правило, на тождественные вершины КСΣ0 , добавленные для согласования числа ее выходов с числом входовКС Σ00 .40Глава 3. Синтез и сложность управляющих системкает, что для разделительной по входам КС Σ00 любая суперпозиция вида Σ00 (Σ0 ) является корректной. Это относится, в частности, к последовательному соединению (1, 1)-КС(см. ??). В то же время параллельное соединение (1, 1)-КС,при котором сначала отождествляются входы, а затем выходы соединяемых КС, не является корректной операциейсуперпозиции, так как не удовлетворяет требованиям следствия 1 из леммы 4.1.

Заметим, что параллельное соединение КС является при этом правильной суперпозицией, таккак полученная КС реализует дизъюнкцию ФАЛ, реализуемых исходными КС, и что корректное дизъюнктированиевыходных ФАЛ можно осуществить с помощью стыковкиисходной КС с вентильной звездой (см. рис. 4.2c).В общем случае операции отождествления входов, а также операции стыковки не всегда являются правильными.§5Нижние мощностные оценкифункций ШеннонаУстановим ряд нижних оценок для введенных в §1 функций Шеннона.

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

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

Напомним, что(см. леммы 2.3, 2.4, 6.2, 6.3 из главы 2) для любых натуральных n и L справедливы неравенства: CU (L, n) 6 (8 (L + n))L+1 ,(5.3) ΦL+1U (L, n) 6 (8n),(5.4) KLU (L, n) 6 (8nL) ,(5.5)|Uπ (L, n)| 6 (16n)L .(5.6)Лемма 5.1. Для положительных действительных чиселa, y, q из неравенствa log q > 1,(ay)y > q,(5.7)следует неравенствоlog qy>log (a log q)log log (a log q)1+log (ae log q),(5.8)где e — основание натуральных логарифмов, а из неравенствa > 1, ay > q — неравенствоy>log q.log a(5.9)42Глава 3. Синтез и сложность управляющих системДоказательство.

Рассмотрим сначала случай, когда a = 1и log q > 1. В этом случае неравенство (5.8) следует из того,что левая часть (5.7) монотонно возрастает по 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 e+=6 log q (1 + ε) 1 −log log qlog log q= log q (1 + ε) (1 − ε) = log q 1 − ε2 6 log q.= (1 + ε)Заметим, что в случае a > 0 неравенство (5.7) эквивалентнонеравенству(ay)ay > q a ,и поэтому неравенство (5.8) получается из неравенства y > y 0в результате замены y на ay и log q на a log q, если выполненоусловие a log q > 1.Неравенство (5.9) в случае a > 1 получается в результате логарифмирования неравенства ay > q и деления обеихчастей полученного неравенства на log a.Лемма доказана.Теорема 5.1.

Для некоторой последовательности ε=ε(n),n = 1, 2, . . ., такой, что ε (n) > 0 при n > n0 и ε (n) стремится к 0 при n стремящемся к бесконечности, выполня-§5. Нижние мощностные оценки функций Шеннона43ются неравенства2n,n2nLΦ (n) > (1 − ε (n)),log n2nLK (n) > (1 − ε (n)) ,n2nπ.L (n) > (1 − ε (n))log nLC (n) > (1 + ε (n))(5.10)(5.11)(5.12)(5.13)Доказательство. Неравенства (5.10)–(5.13) выводятся из соответствующего рассматриваемому классу схем U с функционалом сложности L неравенства (5.3)–(5.6) на основе мощностного равенства (5.1) с использованием леммы 5.1, гдеnq = 22 , и1)2)3)4)a = 8,a = 8n,a = 8n,a = 16n,yyyy= LC (n) + n,= LΦ (n) + 1,= LK (n),= Lπ (n),еслиеслиеслиеслиU = UC ;U = UΦ ;U = UK ;U = Uπ .Действительно, подставляя указанные значения в (5.8) получим2nlog(n + 3)C1) L (n) >1+−n>n+3n+5(5.14)2nlog n − 3 − o(1)>1+nnn22n3 + o(1)Φ2) L (n) >−1>1−(5.15)log n + 3log nlog n2nlog(n + 3 + log n)3) LK (n) >1+>n + 3 + log nn + 5 + log n(5.16)3 + o(1)2n>1−nn44Глава 3.

Синтез и сложность управляющих системСледовательно, неравенство (5.10) ((5.11), (5.12)) будетсправедливо для достаточно больших n при ε (n) = log nn−4(соответственно ε (n) = log4 n , ε (n) = n4 ).Аналогичным образом устанавливается справедливость(5.13) при ε (n) = log5 n .Теорема доказана.Следствие 1.LC (n) &2n,n2n2n, LK (n) &,log nn2n.Lπ (n) &log nLΦ (n) &Следствие 2. Нижние оценки (5.10)–(5.13) при указанныхв доказательстве значениях ε(n) справедливы для сложности почти всех ФАЛ f, f ∈ P2 (n), при их реализации всоответствующих классах схем.nДействительно, замена величины q = 22 величиной q =1 2nпри получении оценок (5.14)–(5.16) с помощью лемn2мы 5.1 повлияет только на участвующие в их последнихнеравенствах функции вида o(1). При этом, в силу (5.2),b — правая часть соответствующего неравенгде δ = n1 , а Ψства (5.10)–(5.12), вновь полученная оценка будет справедлива для почти всех ФАЛ f, f ∈ P2 (n).

Справедливостьнижней оценки (5.13) для почти всех ФАЛ устанавливаетсяаналогично.Аналогичным образом на основе (5.9) и леммы 2.3 главы2 доказывается следующее утверждение.Теорема 5.2. Для n = 1, 2, . . . справедливо неравенствоD(n) > n − log log n + o(1).(5.17)Замечание. Оценка (5.17) справедлива для глубины D(f )почти всех ФАЛ f , f ∈ P2 (n).§6. Метод Лупанова синтеза СФЭ§645Дизъюнктивно-универсальные множествафункций. Асимптотически наилучшийметод О.

Б. Лупанова для синтезасхем из функциональных элементовв базисе {&, ∨, ¬}Рассмотрим метод синтеза схем из класса UC , который былпредложен О.Б. Лупановым [14] и позволил впервые установить асимптотику функции Шеннона LC (n). Этот метод,как и метод Шеннона (см. §2), основан на представленииреализуемой ФАЛ f, f ∈ P2 (n), в виде (2.4) и построенииискомой СФЭ Σf , реализующей ФАЛ f , как суперпозициисхем вида Σf = Σ00 (Σ0 ). При этом схема Σ00 по-прежнему является мультиплексором порядка (n − q) от адресных БПx00 = (xq+1 , . . .

, xn ), а схема Σ0 реализует все ФАЛ видаfσ00 (x0 ), где x0 = (x1 , . . . , xq ) , σ 00 ∈ B n−q , и fσ00 (x0 ) = f (x0 , σ 00 ).Однако, в отличие от метода Шеннона, каждая ФАЛ fσ00 (x0 )берется не с выхода универсального многополюсника от БПx0 , а реализуется на выходе Σ0 как дизъюнкция некоторыхФАЛ, выбранных из специального множества G, G ⊆ P2 (q),реализованного на выходах соответствующей подсхемы схемыΣ0 .Множество ФАЛ G, G ⊆ P2 (m), называется дизъюнктивно-универсальным множеством (ДУМ) порядка m и ранга p, если любая ФАЛ g, g ∈ P2 (m), может быть представлена в видеg = g1 ∨ . .