Материалы для подготовки к экзамену (2012-2013 учебный год), страница 9

Тогда функцией Шеннона для класса ФАЛ или операторов Q при их реализации в классе схем U относительно функционала сложности L называетсяфункция натурального аргументаL(Q(n)) = max L(f ),f ∈Q(n)где L(f ) — минимальная L–сложность схем из U, реализующих (систему) ФАЛ f .Для класса ФАЛ или операторов Q0 и класса ФАЛ Q00 введём такие функцииJ Q0 (n) =log |Q0 (n)|log log |Q0 (n)|и σQ (n) =log |Q00 (n)|,2nгде n = 1, 2, . . .

. При этом из определения следует, что 0 6 σQ (n) 6 1 для всех n,n = 1, 2, . . . .Класс ФАЛ (операторов) Q называется:1) невырожденным, если n + mQ (n) = o J Q(n) ;§8. Специальные классы функций432) строго невырожденным классом ФАЛ, если log n = o log |Q(n)| ;3) ненулевым классом ФАЛ, если limn→∞ σQ (n) > 0.На основе стандартного мощностного метода получения нижних оценок можноустановить справедливость следующего утверждения.Лемма 8.1. Если Q — невырожденный класс ФАЛ (операторов), то 1LИКС Q(n) & · J Q(n) ,2а если Q — строго невырожденный класс ФАЛ, тоLК Q(n) & J Q(n) .LCБ Q(n) & ρБ · J Q(n) ,Следствие. Для всякого ненулевого класса ФАЛ Q выполнены асимптотическиенеравенства2nLC,Б Q(n) & ρБ · σQ (n)n 1log |Q(n)|LИКС Q(n) & · σQ (n),2n2nLК Q(n) & σQ (n) .nКласс ФАЛ (операторов) Q называется стандартным относительно функционала сложности L класса схем UCБ , если выполнено асимптотическое неравенствоLCБ Q(n) .

ρБ · J Q(n) + O n + m(n) .Аналогично вводится определения стандартного класса операторов относительнодругих классов схем и функционалов их сложности, если соответствующая функция Шеннона имеет порядок роста 2n /n. Отметим, что при этом для невырожденного стандартного класса ФАЛ Q имеет место асимптотическое равенствоLCБ Q(n) ∼ ρБ · J Q(n) .Для n = 1, 2, . . .

и r = r(n) > 1 рассмотрим множество ФАЛ P2 (n, t), котороевключает в себя все ФАЛ из P2 (n), обращающиеся в 0 на наборах с номерамиt, t+1, . . . , 2n −1, и мощность которого равна, очевидно, 2t . Для любой функции r =r(n) > 1 рассмотрим класс ФАЛ Q, определённый равенствами Q(n) = P2 (n, r(n)),n = 1, 2, . . . .Лемма 8.2. Для любой функции r = r(n) > 1 соответствующий класс Q(n) =P2 (n, r(n)) является стандартным относительно функционала сложности Lсхем класса UCБ , то естьrLC+ O(n).Б Q(n) . ρБlog r44Глава 1.Доказательство. Будем считать, для удобства, что при лексикографической ν–нумерации наборов куба B n от БП X(n), n = 1, 2, .

. . , БП xi «старше» БП xj ,если i > j. Полученные при этом предположении оценки сложности будут справедливы, очевидно, и для «обычного» порядка «старшинства» БП.Рассмотрим сначала случай, когда r > 2n−1 . Выберем из множества P2 (n, r)произвольую ФАЛ f и построим для неё СФЭ Σf с помощью асимптотически наилучшего метода синтеза (см.

§5). Напомним, что при этом ФАЛ f (см. доказательство теоремы 5.1) разлагается по БП x00 = (xq+1 , . . . , xn ) следующим образом:_f (x0 , x00 ) =Kσ00 (x00 )fσ00 (x0 ),σ 00 ∈B n−qгде x0 = (x1 , . . . , xq ), и что для реализации каждой ФАЛ fσ00 (x0 ) в СФЭ Σf используется одна формула Ft . Из принадлежности ФАЛ f классу P2 (n, r) следует, чтопри ν(σ 00 ) > dr/2q e функция fσ00 (x0 ) тождественно равна нулю, и, таким образом,из схемы Σf можно удалить подсхемы, реализующие все указанные подфункции.e f в силу (5.9) будет выполняться нераДля сложности полученной при этом СФЭ Σвенствоl me f 6 Lj r t + O 2n−m + p · 2s + p · 2 2s +m ,L Σ2qиз которого при значениях параметров (5.10) следует, чтоe f .

ρБ r .(8.1)L Σlog rПусть теперь r 6 2n−1 . В этом случае найдём число k такое, чтоk < n,2k−1 < r 6 2kи, следовательно,f (x1 , . . . , xn ) = xk+1 · . . . · xn · f 0 (x1 , . . . , xk ).(8.2)Заметим, что функция f 0 принадлежит классу P2 (k, r), где r > 2k−1 , и для неё поe f 0 , удовлетворяющую (8.1). Искомаяпредыдущему случаю можно построить СФЭ Σe f строится на основе (8.2) так, чтоСФЭ Σef 6 L Σe f 0 + O(n) . ρБ r + O(n).L Σlog rЛемма доказана.Следствие. Если n = o logr r , то Q(n) = P2 (n, r(n)) — стандартный невырожденный класс ФАЛ, для которого выполнено асимптотическое равенствоr.LCБ Q(n) ∼ ρБlog r§8.

Специальные классы функций45Замечание. Аналогично доказывается стандартность класса Q(n) = P2 (n, r(n)) относительно функционала «обычной» сложности и классов схем UИКС , UК .Рассмотрим теперь следующие операции над ФАЛ:1) добавление и изъятие фиктивных БП (переход к равной ФАЛ);2) переименование БП без отождествления (переход к конгруэнтной ФАЛ);3) подстановка констант 0, 1 вместо БП (переход к подфункции).Если функция g получена из функции f применением операций 1–3, то говорят,что g является квазиподфункцией ФАЛ f , а f — квазинадфункцией ФАЛ g.

Длямножества функций F через F q и Fy будем обозначать множества всех квазинадфункций и квазиподфункций для функций из F соответственно.Множество ФАЛ Q, Q ⊆ P2 , называется инвариантным классом ФАЛ, если онозамкнуто относительно трёх указанных операций. Множества {0}, {1}, {0, 1} называются тривиальными инвариантными классами. Если инвариантный класс Q неявляется тривиальным, то Q ⊇ {0, 1}, поскольку Q содержит неконстантую функцию, из которой при помощи операции 3 можно получить обе константы. Отметим, что если класс Q замкнут по суперпозиции и {0, 1} ⊆ Q, то класс Q являетсяинвариантным.

Примерами инвариантных классов могут, следовательно, служитьb всех монотонных и всех линейных ФАЛ соответственно. При этомклассы M и Lкласс самодвойственных функций, а также классы T0 и T1 — классы сохраненияконстант 0 и 1 соответственно, — не являются инвариантными (они не замкнутыотносительно операции 3). Класс всех симметрических ФАЛ также не являетсяинвариантным, так как он не замкнут относительно операции 1.

При этом инвариантным является класс Sb — класс квазисимметрических ФАЛ, то есть функций,симметрических по всем своим существенным переменным.Лемма 8.3. Пусть Q — инвариантный класс ФАЛ. Тогда существует пределσQ = lim σQ (n) = limn→∞n→∞log |Q(n)|,2nгде число σQ удовлетворяет неравенствам 0 6 σQ 6 1.Доказательство. Из определения последовтельности σQ (n) следует, что для каждого n выполнено неравенство 0 6 σQ (n) 6 1, то есть эта последовательностьσQ (n) ограничена.

Покажем, что она монотонно не возрастает, откуда будет следовать её сходимость. В силу инвариантности класса Q, всякую функцию f измножества Q(n + 1) можно представить в видеf (x1 , . . . , xn+1 ) = xn+1 f0 (x1 , . . . , xn ) ∨ xn+1 f1 (x1 , . . . , xn ),46Глава 1.где fσ (x1 , . . . , xn ) = f (x1 , . . . , xn , σ), σ ∈ B, и обе ФАЛ f0 , f1 принадлежат множеству Q(n). Отсюда сразу вытекает неравенство|Q(n + 1)| 6 |Q(n)|2 ,из которого, в свою очередь, следуeт, чтоσQ (n + 1) =log |Q(n + 1)|log |Q(n)|6= σQ (n).2n+12nСходимость последовательности σQ (n), n = 1, 2, . . . , доказана, а принадлежностьеё предела σQ действительному отрезку [0, 1] следует из того, что ему принадлежатвсе члены данной последовательности.Лемма доказана.Замечание.

Предел σQ будем называть мощностной характеристикой класса Q.Инвариантный класс Q с характеристикой σQ = 0 называется нулевым. Покажем, что существует только один инвариантный класс Q с характеристикойσQ = 1 — это класс P2 . Действительно, если инвариантный класс Q не совпадает с P2 , то для некоторого m будет выполнено неравенство |Q(m)| < |P2 (m)|,которое равносильно неравенству σQ (m) < 1. Из последнего неравенства в силумонотонного невозрастания последовательности σQ (n), n = 1, 2, . . .

, и её сходимости к пределу σQ следует, что σQ 6 σQ (m) < 1.b и S.b Известно [],Найдём значение характеристик инвариантных классов M , Lчто2nlog |M (n)| ∼ Cndn/2e ∼ √,2πnоткуда следует, что σM = 0. Для класса линейных функций, очевидно, при люbбом n выполняется равенство |L(n)|= 2n+1 и, значит, σL = 0. Всякую функцию изbмножества S(n)можно получить так: сначала выбираем k её существенных БП, азатем не более чем 2k+1 способами определяем значение этой функции на каждомслое куба B k (в пределах одного слоя значение функции одно и то же).

Отсюдаследует, чтоnXb|S(n)|6Cnk · 2k+1 = 2 · 3n ,k=0b Sb являются нулевыми.и поэтому σSb = 0. Таким образом, все три класса M , L,Примером ненулевого инвариантного класса, отличного от P2 , является класс Q,состоящий из всех ФАЛ вида f (xi1 , . . . , xir )(xi1 ⊕ · · · ⊕ xir ⊕ σ), где 1 6 i1 < · · · < irи σ ∈ B. Действительно, класс Q замкнут относительно операций 1–3. При этомлюбая ФАЛ из Q(n) однозначно определяется множеством X её существенныхБП, X ⊆ X(n), и своими значениями на множестве тех наборов единичного куба§8.

Специальные классы функций47от БП X, которые имеют либо чётное, если σ = 1, либо нечётное, если σ = 0, числоединиц. Таким образом,2·22n−16 |Q(n)| 6nXr−12 · Cnr · 226 22n−1 +n+1r=0и, следовательно, σQ = 21 .Выше было установлено, что существует единственный инвариантный класс схарактеристикой 1. Можно доказать, что при при любом σ, 0 6 σ < 1 существуетконтинуум инвариантных классов с характеристикой σ. Докажем это в частномслучае σ = 0.Лемма 8.4.

Существует континуум различных инвариантных классов с характеристикой 0.Доказательство. Отметим, что число различных инвариантных классов не можетбыть больше континуума, поскольку множество P2 счётно.{0,m}Рассмотрим симметрические функции sm , определяемые при m > 1 следующим образом:s{0,m}(x1 , . . . , xm ) = x1 · . . . · xm ∨ x1 · . .