Содержание к диссертации
Введение
1 Предварительные сведения 24
2 Верхняя оценка функции Шеннона в базисе
3 Нижняя оценка для почти всех булевых функций в базиcе
3.1 Результаты главы 3 32
3.2 Вспомогательные сведения 33
3.3 Доказательство нижней оценки 40
4 Сложность симметрических функций в базисе
4.1 Результаты главы 4 44
4.2 Доказательство теоремы 4.1 45
4.3 Доказательство теоремы 4.2 61
5 Оценки функции Шеннона в базисах
5.1 Результаты главы 5 62
5.2 Вспомогательные сведения 63
5.3 Доказательство теоремы 5.2 68
5.4 Доказательство теоремы 5.3 73
5.5 Доказательство теоремы 5.5 90
Заключение 95
Список литературы 97
- Верхняя оценка функции Шеннона в базисе
- Вспомогательные сведения
- Доказательство нижней оценки
- Доказательство теоремы 5.2
Введение к работе
Актуальность темы
Диссертация относится к теории синтеза и сложности управляющих систем — одному из основных направлений дискретной математики и математической кибернетики1,2.
В работе изучается задача о сложности реализации булевых функций схемами из функциональных элементов в бесконечных базисах. Под базисом понимается произвольное функционально полное множество булевых функций. Базис называется бесконечным, если для всякого натурального числа существует функция в этом базисе, которая существенно зависит не менее чем от переменных; иначе базис называется конечным3.
Для каждой булевой функции ее сложность () в базисе определяется равенством () = min (), где минимум берется по всем схемам , реализующим функцию в этом базисе, () — сложность схемы , которая равна числу элементов в этой схеме. Вводится соответствующая базису функция Шеннона2 (), определяемая соотношением () = max (), где максимум берется по всем булевым функциям от переменных.
Число элементов схемы является важнейшей из ее мер сложности. Наряду с ней также изучают и другие меры сложности, такие как сумма весов (суммарная стоимость) элементов, глубина, задержка, мощность и ряд иных4, однако, в данной работе они не рассматриваются.
Известно, что для всех конечных базисов порядки роста функции Шеннона одинаковы и равны 2; точный вид асимптотики для произвольного конечного базиса был установлен О.Б. Лупановым,5: () 2 , где — зависящая от базиса постоянная6.
Поведение функции Шеннона для бесконечных базисов значительно разнообразнее, и с этой точки зрения, как и в целом, с точки зрения сложности реализации булевых функций, бесконечные базисы гораздо менее изучены.
1Яблонский С.В. Основные понятия кибернетики // Проблемы кибернетики, вып. 2. — М.: Физматгиз, 1959. — С. 7–38.
2Лупанов О.Б. Асимптотические оценки сложности управляющих систем / М.: Изд-во Московского университета, 1984. — 138 с.
3Касим-Заде О.М. Об одном методе получения оценок сложности схем над произвольным бесконечным базисом // Дискретный анализ и исследование операций. Сер. 1. — 2004. — Т. 11, № 2. — С. 41–65.
4См., например, Лупанов О.Б. Об асимптотических оценках сложности управляющих систем // Acta Cybernetica, 4. — 1980. — 317–323. Лупанов О.Б. Об асимптотических оценках сложности управляющих систем // Международный конгресс математиков в Ницце 1970. Доклады советских математиков. — М.: Наука, 1972. — С. 162–167.
5Лупанов О.Б. Об одном методе синтеза схем // Известия высших учебных заведений. Радиофизика. — 1958. — Т. 1, № 1. — С. 120–140.
6Символ «» обозначает асимптотическое равенство: () (), если lim (()) = 1.
Отметим что, вообще говоря, к рассмотрению схем из функциональных элементов в бесконечных базисах привела необходимость в разработке математических моделей для некоторых классов встречающихся на практике управляющих систем. В частности, возникают задачи моделирования реальных схем, в которых число входов элемента может быть сравнимо со сложностью схемы. С точки зрения теории, адекватным для подобных задач является класс схем из функциональных элементов, в которых число входов базисных элементов потенциально не ограничено. Одна из наиболее разработанных моделей с такими свойствами — схемы из пороговых функциональных элементов7'8. Порядок роста функции Шеннона сложности схем в базисе В пороговых функций установил Э.И. Нечипорук; полное решение задачи об асимптотике функции Шеннона было получено О. Б. Лупановым9, он доказал, что Ьв(п) ~ 2 (—)
Ряд результатов о сложности схем в бесконечных базисах извлекается из известных работ о сложности схем в конечных базисах из нетривиальных элементов с нулевыми весами. В частности, изучались схемы в базисах, в которых элементам, реализующим конъюнкции и дизъюнкции, приписывался вес 0, а инвертору — вес 1, и в качестве меры сложности рассматривалась сумма весов всех элементов схемы (инверсионная сложность)10'11. Для соответствующей задачи синтеза в классе контактных схем Э. Н. Гилберт показал, что порядок роста функции Шеннона инверсионной сложности равен log2 п; этот результат легко переносится на случай схем из функциональных элементов. Впоследствии А. А. Марков полностью решил задачу об инверсионной сложности произвольных булевых функций и получил точное выражение для функции Шеннона инверсионной сложности: |_log2(^ + 1)J. Соответствующий бесконечный базис состоит из всех монотонных булевых функций и их отрицаний, функция Шеннона в этом базисе асимптотически совпадает с функцией Шеннона инверсионной сложности.
В этом же направлении Э. И. Нечипорук12 установил асимптотики и порядки роста функций Шеннона для схем в некоторых базисах, часть которых составляют элементы с произвольными положительными весами, а оставшуюся часть — элементы с нулевыми весами. В частности, им найдена асимп-
7Захарова Е. Ю. О синтезе схем из пороговых элементов // Проблемы кибернетики, вып. 9. — М.: Наука, 1963. — С. 317-321.
8Нечипорук Э. И. О синтезе схем из пороговых элементов // Проблемы кибернетики, вып. 11. — М.: Наука, 1964. — С. 49-62.
9Лупанов О. Б. О синтезе схем из пороговых элементов // Проблемы кибернетики, вып. 26. — М.: Наука, 1973. — C. 109-140.
10 Gilbert Е. N. Lattice theoretic properties of frontal switching functions // J. Math. Phys. — 1954. —
V. 33, № 1. — P. 57-67.
11 Марков А. А. Об инверсионной сложности систем функций // ДАН СССР. — 1957. — Т. 116,
№ 6. — С. 917-919.
12Нечипорук Э. И. О сложности схем в некоторых базисах, содержащих нетривиальные элементы с нулевыми весами // Проблемы кибернетики, вып. 8. — М.: Физматгиз, 1962. — С. 123-160.
тотика функции Шеннона вида ~ л/2 2п'2 для базиса, в котором дизъюнкция двух переменных имеет вес 0, а отрицание — вес 1. Тот же порядок роста функции Шеннона имеет место для бесконечного базиса, состоящего из функции отрицания и всевозможных дизъюнкций переменных.
Отдельно упомянем еще бесконечный базис В всех булевых функций, для которого Ьв(п) = 1 при всех натуральных п.
Таким образом, было установлено, что существуют бесконечные базисы с порядками роста функций Шеннона сложности: 1, log2n, (—)1'2, 2п<2.
Такое разнообразие порядков роста функций Шеннона в бесконечных базисах вызвало естественные вопросы о том, какие вообще возможны порядки роста функций Шеннона в бесконечных базисах и как классифицировать бесконечные базисы по этим порядкам роста.
Отметим, что Н. А. Карпова13 получила полную характеризацию числовых функций, асимптотически равных функциям Шеннона в бесконечных базисах, в случае, когда базисным элементам приписаны произвольные неотрицательные веса, а сложность схемы определяется как сумма весов ее элементов. Описанная характеризация существенно зависит от возможности приписать элементам бесконечного базиса произвольные веса, и на случай меры сложности, равной числу элементов схемы, не переносится14. Как показали дальнейшие исследования, картина поведения функций Шеннона в случае меры сложности, равной числу элементов схемы, существенно отличается от общей картины, описанной Н. А. Карповой.
Качественную картину поведения порядков роста функций Шеннона в бесконечных базисах для меры сложности схем, выражающей количество элементов схемы, по-видимому, впервые описал О. М. Касим-Заде.
Если выполнено соотношение15 а(п) = 0(Ь(п)), то интервалом между функциями а(п) и Ь(п) называется множество всех действительнозначных функций с{п) натурального аргумента, принимающих положительные значения при всех достаточно больших п и удовлетворяющих условиям с{п) = Q(a(n)) и с{п) = 0(Ь(п)). Если функция с{п) лежит в интервале между функциями а{п) и Ъ{п) и по порядку роста не совпадает ни с одной из них, то будем говорить, что функция с{п) лежит строго в интервале между функциями а{п) и Ъ{п).
13Карпова Н. А. О некоторых свойствах функций Шеннона // Матем. заметки. — 1970. — Т. 8, вып. 5. — С. 663-674.
14Касим-Заде О. М. О порядках роста функций Шеннона сложности схем над бесконечными базисами // Вестник Моск. ун-та. Сер. 1. Математика. Механика. — 2013. — № 3. — С. 55-57.
15а(п) = 0(Ъ(п)) (и Ъ(п) = Q(a(n))), если существует такая константа с > 0, что а(п) ^ с Ъ(п) при всех достаточно больших п; если одновременно а(п) = Q(b(n)) и а(п) = 0(Ь(п)), то а(п) = Q(b(n)).
О. М. Касим-Заде16 доказал, что для всякого бесконечного базиса выполняется соотношение в() = {2п'2). Из результата Э.И. Нечипорука следует, что с точностью до константы эта оценка является, вообще говоря, не улучшаемой.
Согласно классификации, описанной О.М. Касим-Заде, для любого бесконечного базиса порядок роста функции Шеннона либо равен 1, либо лежит в одном из двух интервалов: или между функциями log2 и , или между функциями и 2п>2. Таким образом, для всякого бесконечного базиса порядок роста функции Шеннона либо равен 1, либо не меньше log2. Иначе говоря, не существует базиса, для которого порядок роста функции Шеннона лежит строго в интервале между функциями 1 и log2 .
В работе установлено, что существуют бесконечные базисы с порядком роста функции Шеннона равным . Из этого факта и приведенных выше результатов следует, что границы 1, log2, и 2п'2 каждого из интервалов, указанных в классификации порядков роста функций Шеннона, достижимы.
Отметим, что порядок роста функции Шеннона (—)1'2, относящийся к базису пороговых функций, лежит строго в интервале между функциями и 2п'2. Можно показать, что число базисов с различными порядками роста функций Шеннона в этом интервале бесконечно; обширное семейство таких базисов построено в работе.
Как известно, в большинстве случаев нижние оценки функций Шеннона в различных классах управляющих систем устанавливаются «мощност-ным» методом17'. О.М. Касим-Заде18 предложил новый метод получения двусторонних оценок функций Шеннона в произвольных бесконечных базисах, который позволяет, исходя из мощностной нижней оценки, при достаточно слабых ограничениях оценивать функцию Шеннона с точностью до полиномиальной эквивалентности. В частности, если полученная этим методом мощностная нижняя оценка функции Шеннона в данном бесконечном базисе по порядку не ниже линейной (и тем самым функция Шеннона попадает в интервал от до 2п'2), то функция Шеннона по порядку заключена между этой нижней оценкой и ее квадратом.
В интервале от log2 до это свойство, вообще говоря, не выполняется, зачастую для таких бесконечных базисов получение достаточно точных нижних оценок их функций Шеннона требует привлечения иных соображений.
16Касим-Заде О. М. Общая верхняя оценка сложности схем в произвольном бесконечном полном базисе // Вестник Моск. ун-та. Сер. 1. Математика. Механика. — 1997. — № 4. — С. 59-61.
17Riordan J., Shannon С. Е. The number of two-terminal series-parallel networks // J. Math. and Phys. — 1942. — V. 21, № 2. — P. 83-93. Сборник статей по математической логике и ее приложениям к некоторым вопросам кибернетики // Тр. МИАН СССР, 51. — Изд-во АН СССР, 1958. — 364 с.
18Касим-Заде О. М. Об одном методе получения оценок сложности схем над бесконечными базисами // Математические вопросы кибернетики, вып. 11. — М.: Наука. Физматлит, 2002. — С. 247-254.
По-видимому, впервые этот эффект был обнаружен при изучении базиса антицепных функций19.
Базис антицепных функций — это бесконечный базис, который состоит из всех антицепных функций (булева функция называется антицепной, если она принимает значение 1 лишь на некоторой антицепи булева куба)'20. Обычно этот базис обозначается через АС. В него также включаются функции-константы 0 и 1 (по соглашению не имеющие переменных). Множество АС замкнуто относительно операций подстановки констант и отождествления переменных, и всякая булева функция выражается через функции из множества АС с помощью операции суперпозиции.
В работе показано, что, по аналогии со случаем инверсионной сложности, мощностная нижняя оценка функции Шеннона для базиса антицепных функций имеет вид: Ьас(п) ^ 2^ё2п. В этой же работе О.М. Касим-Заде доказал нижнюю оценку порядка nl':i сложности линейной функции от п переменных, откуда была получена нижняя оценка функции Шеннона LAc(n) = Q(nl':i) (линейной функцией называется булева функция, определяемая соотношением ln(xi,..., хп) = Х\ + ... + хп (mod 2)). Такое несоответствие этой оценки функции Шеннона ее мощностной нижней оценке вызвало особый интерес к изучению базиса АС и интервала порядков роста от log2 п дога.
Базис АС оказался первым и до некоторого времени единственным известным базисом, в котором не мощностная нижняя оценка функции Шеннона по порядку роста экспоненциально превышает мощностную нижнюю оценку, причем эта не мощностная оценка устанавливается на некоторой последовательности конкретных булевых функций.
Позднее O.М. Касим-Заде доказал нижнюю оценку Q((n/lnn)l<2) для сложности линейной функции от п переменных в базисе АС, тем самым улучшив нижнюю оценку функции Шеннона. Что касается верхних оценок, то в базисе антицепных функций была установлена простейшая верхняя оценка п + 1 для сложности произвольной булевой функции от п переменных.
Таким образом, окончательный порядок роста функции Шеннона в базисе АС до сих пор оставался неизвестным.
В этом направлении естественными представлялись попытки улучшать нижнюю оценку для линейной функции и получать нижние оценки для других конкретных булевых функций. С этой целью в данной диссертации изучается сложность произвольных симметрических булевых функций и, в частности, линейных функций и функций голосования (функцией голосования
19Касим-Заде О. М. О сложности схем в одном бесконечном базисе // Вестник Моск. ун-та. Сер. 1. Математика. Механика. — 1994. — № 6. — С. 40-44.
20Касим-Заде О. М. О сложности реализации булевых функций схемами в одном бесконечном базисе // Дискретный анализ и исследование операций. — 1995. — Т. 2, № 1. — С. 7-20.
называется булева функция mn(xi,... , хп), равная 1 лишь на тех наборах, в которых число единиц не меньше |).
При синтезе схем часто рассматривают поведение наибольшей сложности функций от заданного числа переменных из некоторого специального класса, более узкого, чем класс всех булевых функций. С точки зрения такой постановки задачи симметрические булевы функции являются одним из наиболее изученных классов. Исследование вопросов сложности симметрических функций привлекает значительный интерес с различных точек зрения21.
О. Б. Лупановым22 было показано, что в классе схем из функциональных элементов в произвольной конечном базисе всякая симметрическая функция реализуется с линейной относительно числа переменных сложностью. Известны оценки сложности симметрических функций в различных конечных и бесконечных базисах23, отдельно стоит упомянуть работы X. Лая и С. Муроги, И. Вегенера, Ю. А. Комбарова24, где были получены точные формулы и оценки сложности линейной функции в некоторых бесконечных базисах.
Что касается интервала между функциями log2n и п, то до сих пор оставался неизвестным ответ на вопрос: существуют ли базисы, в которых порядки роста функций Шеннона лежат строго в этом интервале.
Цель работы
Основной целью данной диссертации является исследование поведения функции Шеннона сложности булевых функций при реализации схемами в бесконечном базисе антицепных функций и некоторых других связанных с ним базисах, разработка новых методов получения оценок сложности булевых функций в базисе антицепных функций и улучшение известных ранее оценок, выявление нетривиальных новых эффектов сложности.
21 Shannon С. Е. The synthesis of two-terminal switching circuits // Bell Syst. Techn. J. — 1949. — V. 28, № 1. — P. 59-98. Лупанов О. Б. К вопросу о реализации симметрических функций алгебры логики контактными схемами // Проблемы кибернетики, вып. 15. — М.: Наука, 1965. — C. 85-100. Храпченко В.М. Нижние оценки сложности схем из функциональных элементов // Кибернетический сборник, Сер. 2. — 1984. — Вып. 21. — С. 3-54.
22Лупанов О. Б. О об одном подходе к синтезу управляющих систем — принципе локального кодирования // Проблемы кибернетики, вып. 14. — М.: Наука, 1965. — C. 31-110.
23См., например, Воррапа R. В., Sipster М. The complexity of fnite functions // Handbook of Theoretical Computer Science. — Vol. A, Algorithms and Complexity. — Amsterdam: Elsevier, 1990. — P. 757-800. Wegener I. The complexity of Boolean functions / Teubner, Stuttgart: Willey-Teubner Ser. Comput. Sci., 1987. — 470 p.
24Lai H.Ch., Muroga S. Logic networks with a minimum number of NOR (NAND) gates for parity functions of n variables // IEEE Trans. Comput. — 1987. — C-36, № 2. — P. 157-166. Wegener I. The сomplexity of the parity function in unbounded fan-in, unbounded depth circuits // Theor. Comput. Sci. — 1991. — V. 85, № 1. — P. 155-170. Комбаров Ю. А. Верхняя оценка сложности реализации линейных функций схемами в одном базисе из многовходовых элементов // Вестник Моск. ун-та. Сер. 1. Математика. Механика. — 2015. — № 5. — С. 47-50.
Основные методы исследования
В диссертации используются методы дискретной математики и математической кибернетики, комбинаторного анализа, теории вероятностей.
Научная новизна работы
Все основные результаты работы являются новыми и получены автором самостоятельно. Основные результаты диссертации состоят в следующем.
-
Доказана новая верхняя оценка функции Шеннона в базисе антицепных функций (базис АС): Lac (ті) ^ ті.
-
Доказана нижняя оценка порядка л/п для сложности реализации почти всех булевых функций от п переменных схемами в базисе АС.
-
Получена точная формула, выражающая сложность произвольной симметрической булевой функции в базисе АС. Как следствие, в этом базисе установлены точные формулы для сложности линейной функции /п, ее отрицания 1п и функции голосования тп от п переменных: LAc(ln) = I ^г~ I , LAc(mn) = Lac (In) = Г^~1 при любом п ^ 2.
-
Для базиса АС установлен порядок роста функции Шеннона: Lac (ті) = О (ті).
-
Установлено, что в базисе, состоящем из всех антицепных функций и линейных функций от любого числа переменных, порядок роста функции Шеннона равен -^/п log2 п. Тем самым, по-видимому, впервые показано, что существует базис, для которого порядок роста функции Шеннона лежит строго в интервале между функциями log2 пип.
Теоретическая и практическая ценность
Работа носит теоретический характер. Результаты диссертации могут найти применение в теории синтеза и сложности управляющих систем и в других разделах дискретной математики и математической кибернетики.
Апробация результатов
Результаты по теме диссертации неоднократно докладывались автором на научно-исследовательских семинарах «Математические вопросы кибернетики» и «Синтез и сложность управляющих систем» под руководством профессора О.М. Касим-Заде (МГУ, 2013-2016 гг.).
Результаты по теме диссертации докладывались автором на следующих
всероссийских и международных конференциях:
IX и X «Молодежные научные школы по дискретной математике и ее приложениям» (г. Москва, ИПМ им. М. В. Келдыша РАН, 2013, 2015 гг.);
Конференция «Ломоносовские чтения» (г. Москва, МГУ, 2013 г.);
Индо-Российская конференция по алгебре, теории чисел, дискретной математике и их приложениям (г. Москва, МГУ, 2014 г.);
Международные научные конференции студентов, аспирантов и молодых ученых «Ломоносов-2013» и «Ломоносов-2015» (г. Москва, МГУ, 2013, 2015 гг.);
XII Международный семинар «Дискретная математика и ее приложения» им. академика О. Б. Лупанова (г. Москва, МГУ, 2016 г.).
Публикации
Основные результаты диссертации опубликованы автором в 6 печатных работах [1-, из них 3 [1-] в научных журналах из перечня, рекомендованного ВАК (список публикаций приведен в конце автореферата).
Структура и объем диссертации
Верхняя оценка функции Шеннона в базисе
А. В. Кочергин, по-видимому, первым начал исследовать поведение функции Шеннона глубины для случая конечных и бесконечных базисов, состоящих из функций /с-значной логики, где к 3, и ему удалось полностью описать качественную картину асимптотического поведения функции Шеннона глубины в этом случае [18,19]. В [19] было установлено, что для произвольного конечного базиса В функций /с-значной логики DB{TI) С п, где константа С выражается через логарифм некоторого алгебраического числа и зависит только от базиса, а также предложен алгоритм нахождения по базису указанной константы. Что касается бесконечных базисов, то в [18] было доказано, что порядок роста функции Шеннона глубины либо равен 1, либо равен log2n. Тем самым было показано что эффекты, описанные для случая булевых функций, распространяются и на случай функций /с-значной логики, где к 3.
Вернемся к изучаемой в диссертации характеристике схемы — сложности. В работе Н. А. Карповой [4] рассматривались бесконечные базисы, в которых каждому базисному элементу приписан произвольный неотрицательный вес, а сложность схемы определяется как сумма весов входящих в нее элементов, и исследовался следующий вопрос: какие числовые функции могут быть функциями Шеннона в таких базисах? Нахождение точного и полного ответа на этот вопрос представляется практически невозможным, поэтому задача рассматривалась с точки зрения асимптотической характеризации функций Шеннона. Н. А. Карпова установила необходимые и достаточные условия, которым должна удовлетворять числовая функция, асимптотически равная функции Шеннона в некотором бесконечном базисе из элементов с произвольными неотрицательными весами. Таким образом, была дана полная характеризация функций, асимптотически равных функциям Шеннона в таких бесконечных базисах [4]. Отметим, что задача нахождения по заданному бесконечному базису функции Шеннона сложности в этом базисе Н. А. Карповой в указанной работе не рассматривалась.
Вообще говоря, не известно какого-либо общего метода, с помощью которого по произвольному бесконечному базису можно найти порядок роста соответствующей функции Шеннона или хотя бы оценить ее с некоторой точностью, например, с точностью до полиномиальной эквивалентности (функции а(п) и Ь(п) называются полиномиально эквивалентными, если существуют такие многочлены Р\{х), Р2{%), что при всех достаточно больших п выполнено: а(п) Pi(b(n)), b(n) Р2(а(п))) [7].
Как известно, в большинстве случаев нижние оценки функций Шеннона в различных классах управляющих систем устанавливаются мощностным методом. Этот метод, по сути, основан на сравнении количества схем заданной сложности и количества функций, допускающих реализацию схемами этой сложности. Такой метод, по-видимому, впервые был использован в работе Дж. Риордана и К. Шеннона [63].
О. М. Касим-Заде [8] предложил новый метод получения двусторонних оценок функций Шеннона в произвольных бесконечных базисах, который позволяет при достаточно слабых ограничениях оценивать рост функций Шеннона с точностью до полиномиальной эквивалентности. Метод получения нижних оценок в [8] основан на «мощностных» соображениях и восходит к [29,36]. Что касается верхних оценок, то предложенный в [8] метод позволяет получать верхние оценки функции Шеннона, сопоставимые с ее мощностной нижней оценкой. Эти результаты получили развитие в [9], где были получены более точные оценки.
В общих чертах качественная картина поведения порядков роста функций Шеннона в бесконечных базисах была описана О.М. Касим-Заде в [13]. Для дальнейшего изложения введем еще два определения.
Если выполнено соотношение а(п) = 0(Ь(п)), то, следуя [13], интервалом между функциями а(п) и Ь(п) будем называть множество всех действительнозначных функций с{п) натурального аргумента, принимающих положительные значения при всех достаточно больших п и удовлетворяющих условиям с{п) = Q(a(n)) и с{п) = 0(Ь(п)). Если функция с{п) лежит в интервале между функциями () и () и по порядку роста не совпадает ни с одной из них, то будем говорить, что функция {) лежит строго в интервале между функциями {) и {).
В [7] О. М. Касим-Заде доказал, что для всякого бесконечного базиса выполняется соотношение в() = {2п/2). С точностью до константы эта оценка является, вообще говоря, не улучшаемой: из работы Э.И. Нечипорука [35], в частности, известен пример бесконечного базиса, в котором порядок роста функции Шеннона равен 2п/2. Результаты работ Э. Н. Гилберта [55] и А. А. Маркова [33] дают пример бесконечного базиса с порядком роста функции Шеннона равным log2. Результаты Э.И. Нечипорука [36] и О. Б. Лупанова [29] о схемах в базисе пороговых функций дают пример бесконечного базиса с порядком роста функции Шеннона равным (—)1/2. Отметим еще базис , состоящий из всех булевых функций, для которого в() = 1 при всех натуральных .
Согласно классификации, описанной в [13], для любого бесконечного базиса порядок роста функции Шеннона либо равен 1, либо лежит в одном из двух интервалов: или между функциями log2 и , или между функциями и 2п/2.
Таким образом, для всякого бесконечного базиса порядок роста функции Шеннона либо равен 1, либо не меньше log2. Иначе говоря, не существует базиса, для которого порядок роста функции Шеннона лежит строго в интервале между функциями 1 и log2 [13].
В [13] установлено, что существуют базисы с порядком роста функции Шеннона равным . Из этого факта и приведенных выше результатов следует, что границы 1, log2, и 2п/2 каждого из интервалов, указанных в классификации порядков роста функций Шеннона [13], достижимы.
Вспомогательные сведения
В результате этого процесса каждой вершине схемы будет сопоставлена некоторая функция.
Схема по определению реализует упорядоченную систему функций (вектор-функцию) (/і(Жі, , Хп), . . . , fm(Xi, . . . , Хп)), где fl(Xi, . . . , Хп) — функция, со поставленная 1-му выходу. Такие системы функций будем называть (п,т)-функциями» [30].
Мы будем рассматривать случай т = 1 и считать, что схема реализует одну функцию. Подробнее эти и другие понятия изложены в [30].
Если функции всех элементов схемы S принадлежат множеству В, то будем говорить, что схема S есть схема в базисе В [30].
Схема из функциональных элементов называется приведенной, если различные входы всякого элемента присоединены к различным вершинам схемы, а на выходе всякого элемента реализуется функция, отличная от константы (см. [6]). Отметим, что для любой схемы в базисе АС сложности s, реализующей функцию, отличную от константы, существует приведенная схема в базисе АС сложности не больше s, реализующая ту же функцию.
Нетрудно убедиться, что это верно и для базиса ACL: для любой схемы в базисе ACL сложности s, реализующей функцию, отличную от константы, существует приведенная схема в базисе ACL сложности не больше s, реализующая ту же функцию.
Отметим, что для базиса АСМ аналогичное утверждение неверно (для доказательства результатов об этом базисе данный факт не используется).
Нумерация элементов схемы называется правильной, если на входы каждого элемента могут подаваться выходы элементов с меньшими номерами или входы схемы. Известно [24], что такую нумерацию можно задать в любой схеме (возможно, несколькими способами). Символы переменных xi, Х2-, , хп, которые приписаны п входам схемы, будем называть входными переменными схемы. Обозначим через х произвольный набор значений аргументов (жі,... ,хп). Элементы схемы будем обозначать символом е, элемент с номером і — через ЄІ. Как правило (если не сказано иное), через gi будем обозначать антицепную функцию, которая соответствует элементу е , а через hi — функцию, которая реализуется на выходе элемента е . Значениe функции hi при подаче на входы схемы набора х будем обозначать через hi(x).
Пусть среди переменных х\,..., хп выделены t переменных. Зафиксируем произвольным образом значения этих t переменных, а остальным переменным будем присваивать произвольные значения. Полученное множество наборов называется подкубом булева куба {0,1}п размерности п — t.
Максимальный набор куба {0,1}п — набор 1 = (1,... , 1) будем называть верхним набором куба, а минимальный 0 = (0,..., 0), соответственно, нижним. Аналогично для всякого подкуба меньшей размерности верхним и нижним наборами будем называть соответственно максимальный и минимальный наборы этого подкуба.
Множество чисел {1, 2,..., п} будем обозначать через [п]. Для любого Р С [п] через хр обозначим такой двоичный набор х = (xi,..., хп), что для любого р Є [п] Хр = 1 тогда и только тогда, когда р Є Р.
Напомним, что под характеристической функцией множества наборов А С {0,1}п понимается функция, принимающая значение 1 на тех и только тех наборах, которые лежат в множестве А. Таким образом, каждая функция, входящая в АС, есть характеристическая функция некоторой антицепи булева куба соответствующей размерности. Приведем также для полноты изложения ряд известных понятий и обозначений, которые используются в работе для описания асимптотического поведения действительнозначных функций.
Пусть две действительнозначные функции () и () натурального аргумента при всех достаточно больших принимают положительные значения. Будем говорить, что порядок роста функции () не больше () и обозначать это через () = (()), если существует такая константа 0, что () () при всех достаточно больших . Будем также говорить, что порядок роста функции () не меньше (), и обозначать это через () = Q(()). Если одновременно () = Q(()) и () = (()), то будем говорить, что порядок роста () равен (), и обозначать это через () = 0(()).
Доказательство нижней оценки
Таким образом мы оценили вероятность указанного отклонения на к-м слое при фиксированных значениях переменных величиной 2е-т 2 . Ясно тогда, что для оценки вероятности отклонения для слоев по всему кубу следует домно-жить эту величину на оценку количества слоев s + 1, а для оценки вероятности события P (ar(f) 4 ) добавить еще множитель 2П, оценивающий количество подмножеств индексов переменных мощности р, которые мы выбирали в начале доказательства леммы. В результате получится следующая оценка: P ( оу(/) - ) 2П (s + 1) 2е-т 2 , 4 где величина в правой части неравенства стремится к нулю при — оо, поскольку /2. И Докажем еще одно вспомогательное утверждение, прежде чем приступить к доказательству основного результата. Лемма 3.7. Пусть функция (і,... ,k) антицепная и существенно зависит от всех своих переменных. Рассмотрим функцию (m+i,... ,k) = (і,..., то, m+i,..., k). Тогда либо зависит от переменных m+i,..., k существенно, либо = 0. Доказательство. От противного. Пусть существует набор (3 = (то+і,..., ), такой, что (/3) = 1, и, например, от k функция не зависит существенно. Тогда (m+i,..., k-i, 0) = (m+i,..., k-i, 1) = 1. Рассмотрим исходную функцию . Ясно, что (і, . . . , то, то+1, . . . , k-l, 0) = (і, . . . , то, то+1, . . . , /г-1, 1) = 1. Получено противоречие с тем, что — антицепная функция.3.3 Доказательство нижней оценки Перейдем к доказательству ключевого утверждения, из которого будут следовать заявленные результаты главы 3. Лемма 3.8. Пусть ,, — натуральные числа, — булева функция от переменных. Пусть — схема в базисе , реализующая функцию . Тогда AC\) min{-, i + 1)(1 — r\))\. Доказательство. Введем обозначение = min{-, ( + 1)(1 — r())}. Доказывать будем от противного: предположим, что AC{) . Будем считать, что в схеме S все входные переменные схемы (определение см. в главе 1), которые подаются на входы элементов, являются существенными для функций, реализуемых этими элементами. Введем на схеме правильную нумерацию элементов (определение см. в главе 1): ei,... ,Є. Для каждого элемента ЄІ рассмотрим функцию hei, реализуемую подсхемой схемы S с выходом ЄІ; множество входных переменных, которые подаются на входы элемента е , обозначим через Хе..
Определим некоторое множество переменных F. Будем строить его следующим образом. Вначале полагаем F = 0. Начинаем обход элементов схемы в порядке заданной нумерации. Для каждого элемента схемы ЄІ смотрим, сколько переменных содержится в множестве Хе. \ F. Если \Хе. \F\ s, то полагаем F := FUXe.. Если Xe.\F s, то переходим к следующему по порядку элементу схемы. После того, как пройдем один раз все элементы схемы, мы получим множество F, которое обозначим через F\. Так же совершим второй проход элементов схемы и получим новое множество переменных, которое обозначим через F i- И так далее.
Будем совершать проходы до тех пор, пока не получим, что Fk-\ = F} , т. е. новые переменные на к-м проходе уже не добавились. Ясно, что к t, а \Fk\ s t г. Полагаем F = Fk- Обозначим мощность множества F через р.
Поскольку р г, то можно зафиксировать переменные из F значениями а ,... ,a,i из определения величины оу(/) и далее рассматривать схему S как схему от оставшихся входных переменных, значения которых не зафиксированы. Тогда для любого элемента схемы S имеем следующее: 1) либо значения всех входных переменных, которые присоединены к его входам, зафиксированы; 2) либо у элемента не менее s входов, которые являются переменными, не входящими в F, а значит, их значения не зафиксированы, а остальные входные переменные зафиксированы. Тогда, по лемме 3.7, получаем, что соответству ющая функция he. либо тождественно равна нулю, либо существенно зависит от не менее чем s переменных. Для удобства обозначим п - р через п\. Рассмотрим наборы булева куба, в которых все переменные из множества F равны нулю. Они образуют подкуб {0,1}П1. Рассмотрим вероятностное распределение рП1 на этом подкубе. Мы будем доказывать, что для каждого і, 1 і , можно найти множество СІ {0,1}Пі, такое что рп (СІ) 1 - і (3.1) s + 1 и hei\ci = const,..., he._1\ci = const. (3.2) Рассуждение будет проходить по индукции по г. Положим CQ = {0,1}Пі. Тогда условие (3.1) выполнено. Пусть мы нашли множество Cj-i, такое, что выполнены условия (3.1) и (3.2). Рассмотрим элемент е . Для него возможны 2 случая: 1) либо все входные переменные, которые присоединены к его входам, принадлежат множеству F, а значит, они зафиксированы некоторыми значениями и функция /ге. — константа на множестве СІ-\. Тогда полагаем СІ = СІ-\; 2) либо не менее s его входов присоединены к входным переменным схемы, не лежащими в F, а значения остальных переменных, которые подаются ему на вход, зафиксированы. Тогда, по лемме 3.7, функция /ге. a) либо тождественно равна нулю, b) либо зависит не менее чем от s переменных существенно. В случае 2a полагаем СІ = СІ-\. Случай 2b изучим подробнее. Мы рассматриваем функцию от п\ переменных, не менее s из которых существенные. Оценим сверху число наборов, на которых функция /ге. принимает значение 1. Базис АС замкнут относительно подстановки констант, поэтому, если отбросим у /ге. несущественные переменные, то получим равную ей антицепную функцию Н(х ,..., Xis), существенно зависящую не менее чем от s переменных, которые являются входными переменными схемы, поскольку все элементы Є&, где к г, реализуют константы.
По лемме 3.3, имеем: pni(Nni(he.)) = p4(Ns(H)). Далее, поскольку функция Н — антицепная, то множество NS(H) представляет собой антицепь. Значит, согласно следствию 3.2, справедлива оценка s + 1 pni(Nni(he.)) = p(Ns(H)) Итак, в условиях случая 2b положим СІ = СІ-\ \ Nni(hei). Тогда Рп(Сг) = Рп(Сг-1 \ N 1(ПЄі)) РП(СІ-І) pni(N ( e)) рПі(Сг-і) s + 1 Таким образом строим множества Cj, по индукции находим С . Для множества Ct получим: pni(Ct) Рп(Со) = 1 — s + 1 s + 1 Следовательно, pni(Ct) crr(f). Функция het — константа на множе стве Cf. Получаем противоречие с определением 7Г(/). Отсюда следует, что LAC(S) t. Ш Завершим доказательства теорем 3.1 и 3.2. Для схем, реализующих почти все булевы функции от п переменных, положим s = \у/2п\,г = п/2. Тогда, по лемме 3.8, получим, что LAC(S) тг-т=.
Доказательство теоремы 5.2
В этом разделе мы приведем определения понятий, формулировки и доказательства некоторых утверждений, которые потребуются для доказательства основных теорем данной главы.
При доказательстве теоремы 5.2 будет использовано следующее утверждение (доказательство см., например, в [48]).
Наибольшая мощность цепи в конечном частично упорядоченном множестве равна наименьшему числу непересекающихся антицепей, на которые может быть разложено.
Также будут использованы некоторые результаты из теории кодирования. Приведенные ниже определения понятия линейного кода и некоторых других понятий подробнее можно найти, например, в [32]; мы дадим лишь их краткое изложение.
Пусть и , , — некоторые натуральные числа, — двоичная матрица, имеющая столбцов. Линейный код длины и размерности с проверочной матрицей состоит из всех двоичных векторов ж, таких что х = 0. Векторы х называются кодовыми словами. Если в матрице имеется — линейно независимых строк, то в линейном коде содержится 2Г кодовых слов. Число называется размерностью кода. Расстоянием (Хэмминга) между двумя кодовыми словами называется число позиций, в которых эти слова различаются. Минимальным расстоянием d кода называется минимальное расстояние между его словами. Код с минимальным расстоянием d может исправлять J ошибок. Минимальное расстояние линейного кода равно минимальному весу ненулевых кодовых слов, где вес кодового слова — это число ненулевых позиций в нем. Любые d — 1 столбцов проверочной матрицы линейного кода с минимальным расстоянием d линейно независимы. Известно, что для существования линейного двоичного кода длины п, размерности г с минимальным расстоянием не менее d достаточно выполнения следующего неравенства: d-2 J2Cn-i 2n r- (5.1) Это неравенство называют границей Варшамова - Гилберта [32]. Напомним известные оценки суммы биномиальных коэффициентов (см., например, [56]): (t\S —V А ( et\S - у С+ — . (5.2) s 2-— s г=0 Используя второе неравенство из выражения (5.2) для t = п — 1, s = d — 2, нетрудно получить следующее достаточное условие для выполнения неравенства (5.1): е(п — 1) (а — 2)log2 п — г. (5.3) а — 2 Таким образом, если неравенство (5.3) выполнено, то как следствие, выполнено неравенство (5.1), и значит, существует линейный двоичный код длины п, размерности г с минимальным расстоянием d.
Докажем лемму, которая потребуется при доказательстве теоремы 5.2.
Лемма 5.1. Пусть п — натуральное число, к = [ nlog2n\. При всяком достаточно большом п для указанного к существует семейство непустых подмножеств Ri,... , Rk С [п], такое что любое семейство непустых попарно не пересекающихся подмножеств В\,..., В С [п] обладает следующим свойством: хотя бы для одной пары i,j Є [п] величина \Bj П Ri\ — нечетна. Доказательство. Рассмотрим двоичный линейный код длины п, размерности п — к с минимальным расстоянием более .
Нетрудно понять, что такой линейный код существует. Действительно, при г = п — к, d = \т \ неравенство (5.3) имеет вид: (\т \ — 2 ) logo е}"Г к. Легко I к видеть, что при к = L\/n 0e2nJ последнее неравенство выполнено при всех достаточно больших п, что гарантирует существование описанного кода.
Рассмотрим проверочную матрицу этого кода, обозначим ее через Н. Матрица имеет размер к х п, ее строки — это упорядоченные наборы длины п, состоящие из нулей и единиц. Зададим подмножества Ri,..., Rk С [п] так: будем считать, что г-я строка матрицы 77 — это характеристический вектор (набор) множества Ri, а именно, множество Д; содержит элемент множества [п], если на соответствующей этому элементу позиции в характеристическом векторе множества Ri стоит единица.
Далее, рассмотрим произвольное семейство непустых попарно не пересекающихся подмножеств В\,..., Вк С [п]. Сопоставим каждому из множеств Bj его характеристический вектор, будем обозначать его через vR Є {0,1}п.
Требуется показать, что для указанного семейства множеств R\,... ,Rk и семейства множеств В].... .Ви найдется такое і Є \к], что і/ vR 7 0, где I ! .J L SXsUj І 0 Є {0,1}п. Подмножества і,..., Вк попарно не пересекаются, это означает, что суще ствует такое ji, что для Bj1 выполнено: \Bjx\ . Матрица Н является про верочной матрицей кода с минимальным расстоянием более . Следовательно, выполнено: Н \в Ф 0, где 0 {0 1}", а значит, существует такое і Є [&], что пересечение множеств Ri и Bjx есть множество нечетной мощности. Известно, что если существует двоичный линейный код длины п, исправляющий s ошибок и содержащий 2Г кодовых слов, то должно выполняться неравенство: S 2Г У Сгп 2П. (5.4) Обычно это неравенство называют границей Хэмминга (или «границей сферической упаковки») [32]. Используя первое неравенство в выражении (5.2), из условия (5.4) легко вывести следующее: п r + slog2— п. (5.5) S Таким образом, если существует двоичный линейный код длины п, исправляющий s ошибок и содержащий 2Г кодовых слов, то выполняется неравенство (5.5). При доказательстве теоремы 5.4 нам потребуется следующая лемма.