О.Б. Лупанов - Курс лекций по дискретной математике, страница 10

Стало быть, число функций от n + 1 переменных из Q никакне больше, чем число пар функций из Q от n переменных. Итак,PQ (n + 1) 6 PQ (n)2 .Извлекая из этого неравенства корень степени 2n+1 , получаемqqqn+1n+1nqn+1 = 2PQ (n + 1) 6 2PQ (n)2 = 2 PQ (n) = qn ,(23)(24)что и требовалось доказать. С другой стороны, ясно, что qn > 1 при всех n (так как Q 6= ∅ и потому PQ (n) > 1). Значит, существуетпредел у этой последовательности.Определение. Числоσ(Q) := log lim qn(25)n→∞называется параметром инвариантного класса.Поскольку 1 6 qn 6 2, получаем, что σ(Q) ∈ [0, 1].

Сейчас мы докажем, что P2 — единственный инвариантныйкласс с параметром 1.Утверждение 3.5. σ(Q) = 1 ⇔ Q = P2 . Справа налево — очевидно. Обратно, пусть Q 6= P2 . Значит, в нём нет какой-либо функции от m переmменных. Стало быть, PQ (m) < 22 , и потому qm < 2. Но эта последовательность убывает, поэтому и предел неможет быть равен 2.

Замечание. Можно доказать, что для каждого σ 6= 1 существует континуум инвариантных классов с параметром σ. Это нетривиальная теорема, мы не будем её здесь доказывать.31Так как lim qn = 2σ , то qn = 2σ (1 + εn ), где εn → 0. Логарифмируя это равенство, получаем1log PQ (n) = σ + δn ,2n(26)δn := log(1 + εn ) → 0.Умножая на 2n обе части, имеемlog PQ (n) = 2n σ + 2n δn .(27)Если σ 6= 0, то главный член этой последовательности определяется первым слагаемым, и log PQ (n) ∼ σ · 2n .Если же σ = 0, то log PQ (n) = o(2n ).Теорема 3.6. Имеет место асимптотическая оценкасложности функций из класса с параметром σ: еслиnnσ 6= 0, то L(f ) .

σ · 2n , а если σ = 0, то L(f ) . o 2n . Будем нумеровать функции из нашего класса последовательностями нулей и единиц. Ясно, что длянумерации всех функций от n переменных из Q достаточно брать ln := ⌈log PQ (n)⌉ двоичных разрядов. Итак,ln ∼ σ · 2n , а при σ = 0 имеем ln = o(2n ).Возьмём какую-либо функцию f ∈ Q от n переменных, выберем k < n и обозначим m := n − k. Положим l :=lk для краткости.

Оставим первые k переменных, а вместо остальных будем подставлять константы αk+1 , . . . , αn .При подстановке констант будем получать функции от k аргументов, которые тоже лежат в Q, поскольку этоинвариантный класс. Каждой такой функции f (x1 , . . . , xk , αk+1 , . . . , αn ) соответствует какой-то номер. Итак,для фиксированной функции f получаем отображение нумерации(28)ϕ : (αk+1 , . . . , αn ) 7→ (τ1 , . . .

, τl ).А теперь построим схему Φ, которая реализует это отображение. Нам нужно построить l функций, каждаяmиз которых зависит от m аргументов xk+1 , . . . , xn . Значит, на каждую функцию уйдёт порядка 2m элементов, аmвсего на схему Φ уйдёт порядка l · 2m элементов.Через ∆ обозначим схему, которая будет по номеру функции f (x1 , . .

. , xk , αk+1 , . . . , αn ), то есть по набору(τ1 , . . . , τl ), генерировать её таблицу значений. Эта схема будет иметь l входов и 2k выходов, поэтомуL(∆) . 2k ·2l.l(29)К этому декодеру подключим схему Σ, которая получает на вход набор (α1 , .

. . , αk ) и таблицу истинностифункции от k переменных (ту самую, которую выдаёт декодер ∆), а на выходе даёт значение этой функции нанаборе (α1 , . . . , αk ). Схема Σ имеет 2k + k входов, поэтому её сложность имеет порядокkL(Σ) .kk22 +k22 +k6= 22 .kk2 +k2(30)Теперь считаем сложность агрегата, полученного соединением ∆, Φ и Σ. (обозначим его F ).

Соединяя полученные выше оценки, получаемk2m2lL(F ) . l ·+ 2k · + 22 .(31)mlxФункция 2x монотонно возрастает при больших x, поэтому в силу того, что l 6 2k , имеем1◦ . Пусть σ 6= 0. Тогда имеем l ∼ σ · 2k , и потому2llk6222k.kkkkk2m222m2n2nL(F ) . σ · 2 ·+ 2k · k + 22 = σ · 2k ·+ 2 · 22 = σ ·+ 2 · 22 . σ ·+ 2 · 22 .m2mn−knjk√Волевым решением полагая k := log2 n , получаем 2k 6 n, поэтомуk√2n2n+2·2 n .σ·.nnn2◦ . Если σ = 0, то аналогично показывается, что L(F ) . o 2n . L(F ) . σ ·(32)(33)Следствие 3.2 (С.

В. Яблонский). Пусть fk (x1 , . . . , xk ) — самая сложная функция от k переменных,∞то есть L(f ) = L(k). Рассмотрим множество функций F := {fi }i=1 . Тогда замыкание [F ] относительноподстановки констант даст все булевы функции. К сожалению, мы не можем утверждать, что [F ] — инвариантный класс, поскольку априори неясно,что он замкнут относительно добавления и удаления несущественных переменных. Однако мы видим, что внём (по построению) есть функции от любого числа переменных и потому для него тоже можно корректно32определить параметр σ (пройдёт рассуждение с ограниченностью снизу последовательности qn ).

Доказаннаятолько что теорема вовсе не использует данное свойство инвариантных классов, поэтому она справедлива идля [F ]. Осталось заметить, что никакие значения параметра,кроме 1, для [F ] не подходят, потому что иначеnасимптотическая сложность была бы строго меньше 2n , а у нас есть все самые сложные функции. Значит,параметр множества [F ] равен 1, а потому [F ] = P2 .

Было ещё сказано, что «если допустить отождествление переменных, то инвариантных классов не будет». Почему это так, и вкаком смысле это надо понимать, неясно, потому что, например, из линейных функций даже используя отождествление переменных,ничего лучше линейных функций получить нельзя.4. Теория автоматов4.1. Автоматы4.1.1. Детерминированные функцииРассмотрим два алфавита A = {a1 , a2 , . .

. , aν }, B = {b1 , b2 , . . . , bµ } и функции вида f : A∞ → B ∞ , то естьфункции, преобразующие бесконечные последовательности букв алфавита A в бесконечные последовательностибукв алфавита B.Пример 1.1. Пусть f переводит последовательность, состоящую сплошь из нулей, в себя, а все остальные —в последовательность, состоящую сплошь из единиц. Для такой функции существует последовательность —состоящая лишь из нулей, для которой невозможно определить её образ, зная лишь конечное число членов. Этопричиняет неудобства при вычислении, поэтому введём понятие детерминированности.Мы будем обозначать символы входной последовательности через a(t), где t = 1, 2, 3, .

. ., а выходной последовательности — через b(t).Определение. Функция f : A∞ → B ∞ называется детерминированной, если b(t) однозначно определяетсяпервыми t членами входной последовательности a(1), a(2), . . . , a(t).Пример 1.2. Детерминированными функциями являются:• Функция 0, . . . , 0, 1, ?, . . . , ?, . . . 7→ 0, . . . , 0, 1, 1, . . . , 1, . . .

. Здесь «?» — любой символ.tt• Функция чётности b(t) = a(1) ⊕ . . . ⊕ a(t);• Функция единичной задержки a(1), a(2), . . . , a(t), . . . →70, a(1), a(2), . . . , a(t − 1), . . . ;(1, t = 2m ;• Функция b(t) =0, t 6= 2m .Без ограничения общности можно считать, что входной алфавит состоит из двух символов: 0 и 1. Тогдадетерминированные функции можно задавать на бинарных деревьях. Бинарное дерево — это дерево с корнем,такое что из каждой вершины выходит 2 ребра, и во все вершины, кроме корня, входит одно ребро. Каждойбесконечной двоичной последовательности поставим в соответствие определённый путь на дереве: движениеначинается из начальной вершины, и если a(i) = 0, то идём по левой ветке, а если a(i) = 1, то по правой.

Приэтом очередному звену пути приписываем значение b(i). Легко видеть, что такое соответствие осуществляетбиекцию между деревьями и детерминированными функциями.Пример 1.3.0 101 11 11101 10 11011 01 01100 101Рис. 10. Деревья детерминированных функцийДеревья на рис. 10 иллюстрируют первые два примера детерминированных функций, приведённых выше.Можно было бы и не ограничивать выходной алфавит двумя символами. Тогда вместо бинарных деревьевследовало бы рассматривать деревья, у которых из каждой вершины растёт по µ веток.334.1.2.

АвтоматыОпределение. Ограниченно детерминированные функции (конечные автоматы) — детерминированныефункции, деревья которых содержат лишь конечное число различных поддеревьев.Замечание. Слово «конечный» в названии «конечный автомат» часто опускают. Мы тоже будем это делать,всегда подразумевая конечный автомат.Пронумеруем различные поддеревья. Номера будем писать в начальных вершинах поддеревьев.Пример 1.4.1000110110Рис. 11. Поддеревья функции чётностиРассмотрим снова функцию чётности. Её дерево содержит только 2 вида поддеревьев.

Эту диаграмму надопонимать так: если мы находимся в дереве №1 и на входе 0, то выход — 0 и мы остаёмся в дереве №1, а если навходе 1, то выход — 1 и мы переходим в дерево №0. Аналогично для дерева №0.В общем случае, если речь идёт о конечно детерминированных функциях, можно утверждать, что достаточнознание конечного числа конечных фрагментов дерева, чтобы найти образ любой последовательности.Определение. Номера поддеревьев называются состояниями автомата.Фрагменты дерева могут задаваться диаграммами переходов (диаграммами Мура). Они представляют собойориентированные графы, вершины которых соответствуют состояниям, а каждому ребру приписывается парасимволов, первая компонента которой соответствует входу, а вторая — выходу.

Направление ребра соответствуетпереходу из одного состояния в другое.Пример 1.5. Диаграмма Мура для функции чётности (см. рис. 12).(1, 1)(0, 0)01(0, 1)(1, 0)Рис. 12. Диаграмма Мура функции чётностиАвтомат можно задавать функцией перехода q(t + 1) = G a(t), q(t) и функцией выхода b(t) = F a(t), q(t) .Здесь q(t) — состояние в момент t. Удобно считать q(1) = 0.

Эти три уравнения называются уравнениямиавтомата.Пример 1.6.(1, 0)(0, 0)01(1, 1)(0, 1)Рис. 13. Диаграмма Мура функции единичной задержкиНайдём уравнения автомата единичной задержки, т. е. функции с выходом b(1) = 0, b(t) = a(t − 1), t > 1.Построим диаграмму Мура (см. рис. 13). По ней видно, что q(t + 1) = a(t), а b(t) = q(t). При этом q(1) = 0.Можно также задавать диаграммы функций таблицами.

Например, функция единичной задержки задаётсяследующей таблицей:a0011q0101F (a, q), G(a, q)(0, 0)(1, 0)(0, 1)(1, 1)Теорема 4.1. Любой автомат можно реализовать СФЭ, используя элементы 4 видов: конъюнкцию, дизъюнкцию, отрицание и функцию единичной задержки. Пусть автомат работает на алфавитах A и B и имеет λ состояний. Положим n := log |A| , m := log |B| .Занумеруем буквы A и B двоичными последовательностями длины n и m соответственно.Состояния автоматаq0 , . .

. , qλ−1 также занумеруем двоичными последовательностями длины l := log2 λ , причём q0 соответствует(0, . . . , 0). Введём новые функции перехода и выхода, определённые уже на наборах из 0 и 1:(β1 (t), . . . , βm (t) = Fe α1 (t), . . . , αn (t), ω1 (t), . . . , ωl (t) ,(1)e α1 (t), . . . , αn (t), ω1 (t), . . .

, ωl (t) .ω1 (t + 1), . . . , ωl (t + 1) = G34α1f1αnω1ωlg1glfmРис. 14. АвтоматКаждая из компонент векторов βe и ωe реализуется некоторой булевой функцией (вообще говоря, не всюдуопределённой). Построим СФЭ, совместно реализующую все эти функции (обозначим их через f1 , . . . , fm иg1 , . . . , gl ).Соединим выходы g1 , . . . , gl через элементы единичной задержки (они показаны на рис.

14 прямоугольниками) с входами ω1 . . . ωl . Очевидно, что такая схема будет работать согласно приведённым выше уравнениямавтомата (при условии, что элементы единичной задержки в первый момент времени выдают нули). Обратное также верно: любая СФЭ типа той, что была рассмотрена выше, моделирует некоторый автомат.4.2. Регулярные события. Теорема Клини4.2.1. Регулярные событияПусть, как и раньше, мы рассматриваем конечные автоматы с алфавитами A и B. Зафиксируем некотороеподмножество B ′ ⊂ B.Определение. Рассмотрим слово w := a(1), . . .