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

На основе мощностныхсоображений (см. (5.19)) аналогично тому, как это было сделано в теореме 5.1 для случая Q = P2 , доказывается следующее утверждение.Лемма5.2. Для класса ФАЛ Q такого, что n =log|Q(n)|= o log log|Q(n)| (log n = o (log log |Q(n)|)), выполняются следующие асимптотические неравенстваLC (Q (n)) &(соответственноlog |Q (n)|,log log |Q(n)|LK (Q (n)) &log |Q (n)|).log log |Q(n)|(5.20)(5.21)Пусть, например, класс Q состоит из всех ФАЛ, симметричных по первым двум БП. Легко видеть, что при этомВведение473 n|Q (n)| = 2 4 2 , так как f ∈ Q(n) тогда и только тогда, когдавторая и третья четверти столбца значений αef совпадают.Следовательно, в силу леммы 5.2, отсюда вытекает, чтоLC (Q(n)) &§63 2n· ,4 nLK (Q (n)) &3 2n· .4 n(5.22)Дизъюнктивно-универсальные множествафункций.

Асимптотически наилучшийметод О. Б. Лупанова для синтезасхем из функциональных элементовв базисе {&, ∨, ¬}Рассмотрим метод синтеза схем из класса UC , который былпредложен О.Б. Лупановым [14] и позволил впервые установить асимптотику функции Шеннона LC (n). Этот метод,как и метод Шеннона (см. §4), основан на представленииреализуемой ФАЛ f, f ∈ P2 (n), в виде (4.5) и построенииискомой СФЭ Σ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 ∨ . . .

∨ gp ,48Введениегде gi ∈ G при всех i, i = 1, . . . , p. Стандартный способ построения таких множеств связан с разбиениями единичногокуба.Пусть Π = (π1 , . . . , πp ) — разбиение куба B m , и пусть длявсех i, i = 1, . . . , p, ФАЛ ψi (x1 , . . . , xm ) — характеристическая ФАЛ множества πi , а G(i) — множество всех тех ФАЛg, g ∈ P2 (m), которые обращаются в 0 вне πi . Заметим, чтомножество ФАЛ G видаG = G(1) ∪ .

. . ∪ G(p)является ДУМ порядка m и ранга p. Действительно, любаяФАЛ g, g ∈ P2 (m), может быть представлена в видеg = g1 ∨ . . . ∨ gp ,(6.1)где gi = ψi g и, следовательно, gi ∈ G(i) для всех i, i = 1, . . . , p.Заметим также, что мощность множества G(i) , i = 1, .

. . , p,равна 2si , где si = |πi |, и что множество G(i) ∩ G(j) состоит из ФАЛ, тождественно равной 0, если 1 6 i < j 6 p.Следовательно,p pXX (i) λ = |G| =2si 6 p2s ,G − (p − 1) 6i=1i=1гдеs = max si .16i6pУказанное ДУМ G будем называть ДУМ, связанным сразбиением Π. Компоненты разбиения Π будем при этом называть полосами ДУМ G, а ФАЛ ψ1 = χδ1 , .

. . , ψp = χδp —его характеристическими ФАЛ. Заметим, что характеристические ФАЛ попарно ортогональны, то есть одновременно в 1 не обращаются, и принадлежат G. Заметим также,Введение49g1 g2 . . .g2s g2s +1. . .g2s+1 −1 . . . g(p−1)(2s −1)+2. . . gλx1 x2 . . . xm−1 xm... 00 0 01 0 0 ... 0...π1 ............π2 ...πp−1 πp 0...0...0...00 0 .... . .. .

.. . .0 0 ...1...0...0.........0...00...0.........0...1.........0 0 ... 01...1...0...00 0 .... . .. . .. . .0 0 ...0...0...1.........0...01...0.........0...0...............0 1 ... 1......0...0...0...0...0.........0...00...0.........0...0.........0......0 0 .... .

.. . .. . .0 0 ......0 0 ... 00...0...1...1...0 0 .... . .. . .. . .0 0 ...0...0...0.........0...00...0.........1...0.........o2s/o/O...2s −1s=s2...0...O00 0 ... 0...s=s10......Oos2 p −1s=sp−10Osp 6s0/Рис. 6.1: к определению дизъюнктивно-универсальногомножествачто представление (6.1) в случае рассматриваемого ДУМ Gравносильно представлению:g = ψ1 g1 ∨ ψ2 g2 ∨ · · · ∨ ψp gp(6.2)Будем считать стандартным ДУМ порядка m и высоты s, гдеs 62m ,(6.3)50ВведениеДУМ ранга p, p = d2m /se, связанное с разбиением Π =(π1 , . . . , πp ) куба B m на последовательные отрезки, для которого номер любого набора из множества πi меньше номералюбого набора из множества πj , если i < j, и выполнены соотношенияs1 = s2 = · · · = sp−1 = s,sp = 2m − (p − 1) s 6 s.(6.4)Таблица значений ФАЛ ДУМ G приведена на рис.

6.1.Из проведенных построений и отмеченных выше свойствстандартного ДУМ вытекает справедливость следующего утверждения.6.1. Для любых натуральных p, m и s, где p =Лемма2m,существуетстандартное ДУМ G порядка m и высоsты s, которое является ДУМ ранга p и для которого:1) λ = |G| 6 p2s ;2) система из p характеристических ФАЛ ψ1 , . .

. , ψpДУМ G обладает тем свойством, что для любойФАЛ g, g ∈ P2 (m), и соответствующих ФАЛg1 , . . . , gp из G справедливо не только представление(6.1), но и представление (6.2).Теорема 6.1. Для любой ФАЛ f, f ∈ P2 (n), существуетреализующая ее СФЭ Σf , Σf ∈ UC , такая, что2n5 log n + O (1)L (Σf ) 61+.(6.5)nnДоказательство. Пусть x0 = (x1 , . . .

, xq ), x00 = (xq+1 , . . . , xn )и fσ00 (x0 ) = f (x0 , σ 00 ) для всех σ 00 из B n−q . Пусть, далее,Σ00 — мультиплексор порядка (n − q) от адресных БП x00 иинформационных БП y = (y0 , . . . , y2n−q −1 ), который построен в соответствии с леммой 2.3, представляет собой формулуFn−q и реализует мультиплексорную ФАЛ µn−q (x00 , y).Введение51Пусть s — некоторый параметр, удовлетворяющий (6.3),а G — стандартное ДУМ порядка m = q и высоты s, удовлетворяющее требованиям леммы 6.1. Обозначим через ΣG→−СФЭ, которая реализует систему ФАЛ G и представляетсобой объединение схем, построенных для каждой из них всоответствии с леммой 1.2.

Заметим, что, в силу леммы 2.3,(1.3) и леммы 6.1, выполнены неравенстваL Σ00 6 4 · 2n−q ,(6.6)L (ΣG ) 6 3p2s+q .Схема Σ0 содержит СФЭ ΣG в качестве подсхемы и реализует каждую ФАЛ fσ00 (x0 ), где σ 00 ∈ B n−q , на одном из своих выходов как ФАЛ g (x0 ) вида (6.1) с помощью СФЭ из(p − 1) ФЭ ∨, входы которой присоединены к соответствующим выходам ΣG .

Искомая СФЭ Σf имеет вид Σf = Σ00 (Σ0 )и реализует ФАЛ f в соответствии с разложением (4.5). Длянее, в силу (6.6), будут выполняться неравенстваL (Σf ) 6 2n−q (p − 1) + L Σ00 + L (ΣG ) 66 2n−q (p − 1) + 4 · 2n−q + 3p2s+q ,из которых, выбрав значения параметровs = dn − 5 log ne ,m = q = d2 log ne ,удовлетворяющие (6.3), в соответствии с леммой 6.1 получим n2n2L (Σf ) 6+O=n − 5 log nn22n5 log n + O (1)=1+.nnТеорема доказана.52ВведениеСледствие. Из (6.5) с учётом следствия из теоремы 5.1вытекает, что2nLC (n) ∼.nОтметим, в заключение, что в соответствии с (6.5) и теоремой 5.1 сложность LC (f ) для почти всех ФАЛ f, f ∈P2 (n), асимптотически равна функции Шеннона LC (n), тоесть сложности самой сложной ФАЛ из P2 (n).

Тем самым,в отличие от класса ДНФ (см. §7 главы 1), в классе схемUC имеет место т. н. эффект Шеннона — асимптотическоеравенство сложности почти всех ФАЛ и сложности самойсложной ФАЛ от заданного числа БП, стремящегося к бесконечности.§7Регулярные разбиения единичного куба и моделирование функций переменными. Асимптотически наилучший метод синтеза формулв базисе {&, ∨, ¬}.Множество δ, δ ⊆ B q , называется m-регулярным множеством наборов куба B q , если m < q, |δ| = 2m и все префиксы1 длины m наборов из δ различны. Заметим, что mрегулярному множеству δ, δ ⊆ B q , можно взаимнооднозначно сопоставить систему ФАЛ ψ = (ψ1 , .

. . , ψq−m ) из P2q−m (m)так, что набор α = (β, γ), где β ∈ B m и γ ∈ B q−m , принадлежит δ тогда и только тогда, когда ψ (β) = γ. Заметим также, что любая ФАЛ g, g ∈ P2 (q), совпадает наm-регулярном множестве наборов δ, δ ⊆ B q , с некоторойФАЛ из P2 (m), если рассматривать P2 (m) как множествовсех ФАЛ из P2 (q) с несущественными БП xm+1 , .

. . , xq . Приэтом любая ФАЛ из связанной с δ системы функций совпадает на δ с соответствующей БП куба B q .1Для слова (набора) α вида α = βγ слово β (γ) считается его префиксом (соответственно суффиксом).Введение53Для наборов β = (β1 , . . . , βq ) и α = (α1 , . . .

, αq ) черезβ ⊕ α будем обозначать набор вида (β1 ⊕ α1 , . . . , βq ⊕ αq ).Для множества δ, δ ⊆ B q , и набора α, α ∈ B q , определиммножество δ ⊕ α как множество различных наборов видаβ ⊕ α, где β ∈ δ, то есть множество, получающееся из множества δ сдвигом (параллельным переносом) на набор α.Заметим, что для m-регулярного множества δ, δ ⊆ B q , илюбого набора α, α ∈ B q , множество δ ⊕ α также являетсяm-регулярным. Если при этом ν (α) < 2q−m , то естьα = (0, . .

. , 0, γ),| {z }mгде γ = (γ1 , . . . , γq−m ) и ν (γ) = ν (α), а множество наборовδ соответствует системе ФАЛ g = (g1 , . . . , gq−m ), то множество наборов δ ⊕ α будет соответствовать системе ФАЛ(g1 ⊕ γ1 , . . . , gq−m ⊕ γq−m ), получающейся из системы g инвертированием некоторых ФАЛ.Лемма 7.1. Для любых натуральных m, λ и q = m + λ идля любой системы ФАЛ g = (g1 , . . .

, gλ ) из P2λ (m) существует m-регулярное разбиение ∆ = (δ1 , . . . , δ2q−m ) куба B qтакое, что любая ФАЛ gi на любой компоненте δj совпадает либо с одной из БП xm+1 , . . . , xq , либо с её отрицанием.Доказательство. Пусть δ = δ1 — m-регулярное множество,соответствующее системе ФАЛ g = (g1 , . . . , gλ ), и пусть δi =δ1 ⊕ α, где ν(α) = i − 1, для всех i, i = 1, . . . , 2q−m . Из построения системы множеств ∆ = (δ1 , . .

. , δ2q−m ) следует, чтокаждое из них обладает требуемым свойствами, связаннымис можелированием ФАЛ из g с помощью БП.Покажем теперь, что ∆ — покрытие куба B q . Для этоговозьмем произвольный набор из B q вида (β, γ), где β ∈ B mи γ ∈ B q−m , а по нему найдем в множестве δ набор вида(β, γb), который имеется в δ в силу m-регулярности этого54Введениемножества.