Содержание к диссертации
Введение
1 Функции переменных со сложностью не менее 23
1.1 Основные определения 23
1.2 Пример последовательности функций трёхзначной логики с экспоненциальной глубиной 30
1.3 Формулировка основного результата главы 37
1.4 Доказательство вспомогательных утверждений 39
1.5 Доказательство основной теоремы главы 44
2 Понижение значности логики с качественным сохранением нижней оценки 52
2.1 Формулировка основного результата главы 52
2.2 Доказательство вспомогательных утверждений 54
2.3 Доказательство основной теоремы главы 61
2.4 Уточнение нижней оценки 72
3 Высокие оценки сложности в бесконечных базисах 74
3.1 Сравнение роста сложности в конечных и бесконечных базисах для различных моделей 74
3.2 Простой пример высокой нижней оценки в бесконечном базисе
3.3 Построение класса с одинаковой сверхэкспоненциальной асимптотикой сложности в конечном и бесконечном базисах 80
3.4 Высокие оценки глубины функций трёхзначной логики из классов, не имеющих конечного базиса 88
3.5 Высокие оценки сложности функций четырёхзначной логики из классов, не имеющих конечного базиса 93
Заключение 98
Список литературы
- Формулировка основного результата главы
- Доказательство основной теоремы главы
- Доказательство вспомогательных утверждений
- Построение класса с одинаковой сверхэкспоненциальной асимптотикой сложности в конечном и бесконечном базисах
Введение к работе
Актуальность темы
Данная работа является исследованием в области теории синтеза и сложности управляющих систем, одного из центральных и быстроразвивающихся разделов дискретной математики и математической кибернетики, получающего постановки задач и находящего многообразные применения в информатике, а также в вычислительной и телекоммуникационной технике.
В общих чертах задача синтеза может быть описана следующим образом. Имеется множество элементарных средств (базис), из которых по некоторым правилам строятся более сложные объекты — схемы (в широком смысле, например, формулы или схемы из функциональных элементов). По каждой схеме определяется функция, которую эта схема реализует. Задача синтеза заключается в построении по заданной функции реализующей её схемы.
Зачастую для заданной функции требуется построить не произвольную реализующую её схему, а в некотором смысле наилучшую, оптимальную по тем или иным параметрам. Для измерения «качества» схемы вводятся различные меры сложности1, например, собственно сложность — количество элементов или, в общем виде, их вес (стоимость), глубина, объём или площадь схемы, мощность и т. д.
Для конечных базисов, как правило, существует универсальный метод решения задачи нахождения оптимальной схемы — перебор всех схем со сложностью не более некоторой величины. Однако на практике воспользоваться таким способом обычно невозможно, так как с ростом числа элементов количество схем растёт очень быстро, и применение тривиального метода становится практически неосуществимым. На самом деле большая трудоёмкость решения задачи оптимального синтеза в общем виде, по-видимому, присуща всем алгоритмам, предназначенным для её решения, — к этому выводу одним из первых пришёл и доказал в рамках некоторой естественной формализации С. В. Яблонский2. С тех пор эта точка зрения стала общепринятой, получив много косвенных подтверждений своей
хСм., например: ЛупановО.Б. Асимптотические оценки сложности управляющих систем. М.: Изд-во МГУ, 1984; ЛупановО.Б. О схемах из функциональных элементов с задержками // Проблемы кибернетики, вып. 23. М.: Наука, 1970. С. 43-81; ХрапченкоВ. М. Принципиальное расхождение между глубиной и задержкой // Дискретная математика. 2008. Т. 20, вып. 3. С. 51-72; Коршунов А. Д. Об оценках сложности схем из объёмных функциональных элементов // Проблемы кибернетики, вып. 19. М.: Наука, 1967. С. 275-284; Кравцов С. С. О реализации функций алгебры логики в одном классе схем из функциональных и коммутационных элементов // Проблемы кибернетики, вып. 19. М.: Наука, 1967. С. 285-292; McCollW.F., PatersonM.S. The depth of all boolean functions // SIAM J. Comput. 1977. V. 6, №2. P. 373-380; ВайнцвайгМ.Н. О мощности схем из функциональных элементов // Доклады АН СССР. 1961. Т. 139, №2. С.320-323; Касим-ЗадеО.М. Об одной мере сложности схем из функциональных элементов // Проблемы кибернетики, вып. 38. М.: Наука, 1981. С. 117-179.
2Яблонский С. В. Об алгоритмических трудностях синтеза минимальных контактных схем // Проблемы кибернетики, вып. 2. М.: Физматгиз, 1959. С. 75-121.
справедливости.
Таким образом, задача построения наилучшей схемы может быть решена, как правило, только для тривиальных случаев. Поэтому часто приходится рассматривать некоторые ослабления данной задачи. В этом направлении одним из наиболее естественных подходов является поиск не оптимальных, а в том или ином смысле близких к оптимальным схем, например, асимптотически или по порядку наилучших. Сформулируем такую постановку задачи, скажем, для реализации булевых функций схемами из функциональных элементов и формулами. Для оценки качества схем и формул возьмём классические меры — сложность и глубину. Сложность тесно связана со стоимостью, площадью, объёмом и весом реальных интегральных схем, а глубина, также как и близкая к ней, но не совпадающая с ней, задержка3, характеризует время их срабатывания.
Каждому элементу базиса *В сопоставляется неотрицательное число — вес элемента, и сложностью L<$(S) схемы S над базисом *В называется сумма весов входящих в неё элементов. Глубина D<$(S) схемы из функциональных элементов S над базисом *В определяется как количество элементов в самой длинной цепочке, соединяющей вход и выход схемы. Аналогичным образом можно определить понятие глубины формулы, однако глубина функции в случае реализации формулами оказывается равной глубине в случае реализации схемами (при некотором естественном сопоставлении формул и схем из функциональных элементов над одним и тем же базисом). Под сложностью формулы будем понимать количество входящих в неё символов переменных и констант. Стоит отметить, что в качестве меры сложности формулы также рассматривают сумму весов функциональных символов, но если вес базисной функции на единицу меньше количества её существенных переменных, то указанные меры сложности отличаются на единицу. Сложностью Ь^ФЭ(/) (L^(/)) реализации функции / схемами из функциональных элементов (формулами) над базисом *В называется минимальная сложность схемы (формулы) над базисом *В, реализующей данную функцию. Вводится функция Lrg{n) (Ь^ФЭ(п) для схем из функциональных элементов и Ь^(п) для формул), значение которой равно сложности реализации самой сложной функции от п переменных. Аналогичным образом определяются величины Drg{f) и D?g{n). Требуется найти метод синтеза схем, позволяющий для каждой функции f от п переменных строить схему, реализующую эту функцию и имеющую сложность, не превосходящую или мало превосходящую величину Lrg{n) (соответственно Drg{n)). Такой подход был предложен K. Шенноном4 в 1949 г. при исследовании
3ХрапченкоВ.М. Различие и сходство между задержкой и глубиной // Проблемы кибернетики, вып. 35. М.: Наука, 1979. С.141–168.
4 Shannon C. E. The synthesis of two-terminal switching circuits // Bell Syst. Techn. J. 1949. V. 28, № 1. P. 59–98.
контактных схем и впоследствии был перенесён на другие классы управляющих систем. Функцию Lrg{n) принято называть функцией Шеннона сложности, а функцию D
Для почти всех основных модельных классов управляющих систем5 О. Б. Лупановым, а также его учениками и последователями была решена задача нахождения асимптотики роста соответствующих функций Шеннона сложности6. В частности, для функций Шеннона сложности реализации булевых функций над произвольным конечным функционально полным базисом *В схемами из функциональных элементов и формулами, а также для функции Шеннона глубины имеют меcто следующие соотношения:
п log2 п
где р — константа (минимум приведённых весов элементов базиса), однозначно определяемая7 по базису *В, а т = (log2 m)_1, где m — максимальное число существенных переменных у функций из базиса *В.
Отметим, что для большинства модельных классов управляющих систем, в том числе для схем из функциональных элементов и формул, имеет место так называемый «эффект Шеннона» — почти все функции от п переменных имеют сложность, асимптотически совпадающую со сложностью функции Шеннона (тем самым, методы, дающие верхние оценки сложности функций, асимптотически совпадающие со значением соответствующей функции Шеннона, позволяют для почти всех функций строить асимптотически оптимальные схемы). Тем не менее, предъявить достаточно сложные объекты в явном виде для большинства модельных классов управляющих систем, за исключением отдельных классов, например, вентильных схем8 и схем конкатенации9, не удаётся.
5См., например, Яблонский С. В. Основные понятия кибернетики // Проблемы кибернетики, вып. 2. М.: Физматгиз, 1959. С. 7-38.
6См., в частности, Лупанов О. Б. О вентильных и контактно-вентильных схемах // ДАН СССР. 1956. Т. 111, №6. С. 1171-1174; Лупанов О. Б. Об одном методе синтеза схем // Известия вузов. Радиофизика. 1958. Т. 1, №1. С. 120-140; Лупанов О. Б. О синтезе контактных схем // ДАН СССР. 1958. Т. 119, № 1. С. 23-26; Лупанов О. Б. О сложности реализации функций алгебры логики формулами // Проблемы кибернетики, вып. 3. М.: Физматгиз, 1960. С. 61-80; Кузьмин В. А. Реализация функций алгебры логики автоматами, нормальными алгорифмами и машинами Тьюринга // Проблемы кибернетики, вып. 13. 1965. С. 75-96; НечипорукЭ.И. О топологических принципах самокорректирования // Проблемы кибернетики, вып. 21. М.: Физматгиз, 1969. С. 5-102; PippengerN. The minimum number of edges in graphs with prescribed paths // Math. Systems Theory. 1979. V. 12, №4. P. 325-346.
7См., например, Лупанов О. Б. Асимптотические оценки сложности управляющих систем. М.: Изд-во МГУ, 1984.
8См., например, Лупанов О. Б. О вентильных схемах // Acta Cybernetica. 1980. Tom. 4, Fasc. 4. P. 311– 315; КочергинВ.В. Теория вентильных схем (современное состояние) // Дискретная математика и ее приложения. Сборник лекций молодежных научных школ по дискретной математике и ее приложениям. Выпуск VII. М.: Изд-во ИПМ РАН, 2013. С. 23-40.
9BerstelJ., BrlekS. On the lenght of word chains // Inform. Process. Lett. 1987. V. 26, №1. P. 23-28; Кочергин В. В., Кочергин Д. В. Уточнение асимптотического поведения сложности сборки слов схемами конкатенации // Вестник Моск. ун-та. Сер. 1. Математика. Механика. 2016. №2. С. 12-18.
Каждая схема, реализующая функцию /, автоматически даёт верхнюю оценку сложности этой функции. Но, чтобы понять, насколько близко найденное решение к оптимальному, необходимо иметь хорошую нижнюю оценку сложности. Таким образом, возникает задача нахождения нижних оценок, которая состоит в доказательстве того, что ни одна схема, реализующая данную функцию, не может иметь сложность, меньшую заданной. Проблема нахождения нижних оценок сложности10, имеющая внушительную историю, — одна из наиболее трудных и важных в дискретной математике и математической кибернетике.
В большинстве случаев имеющиеся высокие нижние оценки функций Шеннона не являются конструктивными. Они опираются на мощност-ные соображения11 — количество различных схем относительно невысокой сложности, на входы которых подаются переменные из фиксированного множества xi,... ,хп, не превосходит количество различных функций от этих переменных, а значит самая сложная функция заведомо реализуется с большей сложностью. Однако сложность схем для интересных с практической точки зрения функций, как правило, значительно ниже мощност-ных нижних оценок, что также указывает на важность задачи получения высоких конструктивных нижних оценок. Отметим, что есть примеры12 индивидуальных последовательностей функций с экспоненциальной сложностью, но при их построении применяются «сильные» средства, сравнимые по своей мощности с полным перебором, например, такие как нумерация примитивно-рекурсивных функций или формальная теория большой выразительно силы. В дальнейшем речь пойдёт только о конструктивно заданных13 последовательностях функций.
В прикладном плане получение результатов, касающихся проблематики нижних оценок сложности, способствовало бы разработке более эффективных алгоритмов и созданию методов оценки качества алгоритмов и программ.
Получение нижних оценок для конструктивно задаваемых последовательностей функций и для узких классов функций является одним из приоритетных направлений исследований в задачах теории синтеза и сложности управляющих систем. Несмотря на трудность этих задач, их важность неоднократно отмечалась С.В.Яблонским и О. Б. Лупановым14.
10См., например, Нигматулин Р. Г. Нижние оценки сложности и сложность универсальных схем // Казань: Изд-во казанского ун-та, 1990.
11Cм., например, RiordanJ., Shannon C.E. The number of two-terminal series-parallel networks // J. Math. and Phys. 1942. V. 21, №2. P. 83-93.
12Cм., например, StockmeyerL. J. The complexity of decision problems in automata theory and logic // MAC Techn. Rep. 133, M.I.T., 1974; ШоломовЛ. А. Об одной последовательности сложно реализуемых функций // Математические заметки. 1975. Т. 17, вып. 6. С. 957-966; МарченковС. С. О сложности вычисления экспоненты // Математические заметки. 1982. Т. 31, вып. 3. С. 457-463.
13См., например, Нигматуллин Р. Г. Сложность булевых функций // М.: Наука, 1991.
14Cм., например, ЛупановО.Б. Об асимптотических оценках сложности управляющих систем // Международный конгресс математиков в Ницце, 1970. Доклады советстких математиков. М.: Наука,
Однако в случае реализации булевых функций схемами из функциональных элементов и формулами все известные нижние оценки для конструктивно задаваемых последовательностей функций принципиально ниже мощностных оценок. Более того, в случае схем из функциональных элементов такие оценки имеют рост не выше линейного от числа переменных.
В случае реализации булевых функций формулами известен ряд ме
тодов, позволяющих получать несколько более высокие нижние оценки
для конструктивно задаваемых последовательностей функций. Первый ме
тод получения нелинейных нижних оценок сложности формул в стандарт
ном базисе {V,&,} был предложен Б. А. Субботовской15. Этим методом
для реализации последовательности линейных функций была установлена
нижняя оценка сложности, имеющая порядок роста пъ'2 (здесь и далее в
этом абзаце п — количество переменных у функции). В. М.Храпченко был
предложен16 метод получения нижних оценок в классе П-схем (а также
формул в базисе {V, &, }), применимый к целому ряду функций. Наиболь
шая оценка, получающаяся этим методом, достигается также на линейных
функциях и имеет вид п2. Наилучшие известные конструктивные нижние
оценки для формул в произвольном полном конечном базисе (n2/logn) да
ёт метод Нечипорука17. А. Е. Андреев на основе обобщения метода Суббо
товской с использованием универсальной функции Нечипорука построил18
пример последовательности булевых функций, сложность реализации ко
торых над базисом {V, &, } растёт по порядку почти как п5'2. В настоящее
время самой высокой конструктивной нижней оценкой, по-видимому, яв
ляется оценка Й.Хастада19 для реализации явно заданной последователь
ности функций формулами над базисом {V, &,}, которая имеет порядок
роста уть vr.
(log п)'/''(log log п)^
Таким образом, для классов формул и схем из функциональных элементов, как и для многих других модельных классов управляющих систем, несмотря на то, что для почти всех функций сложность асимптотически совпадает с величиной функции Шеннона, не удаётся привести высокие конструктивные нижние оценки. Трудности решения проблемы нижних
1972. C. 162-167; Яблонский С. В. Обзор некоторых результатов в области дискретной математики // Всесоюз. конф. по проблемам теоретической кибернетики (Новосибирск, июнь 1969). Инф. мат-лы Научного совета АН СССР по комплексной проблеме «Кибернетика». 1970. Вып. 5 (42). C. 5-15.
15Субботовская Б. А. О реализации линейных функций формулами в базисе V, &, // ДАН CCCР. 1961. Т. 136, №3. С. 553-555.
16Храпченко В. М. Об одном методе получения нижних оценок сложности П-схем // Математические заметки. 1971. Т. 10, вып. 1. С. 83-92.
17Нечипорук Э. И. Об одной булевой функции // ДАН СССР. 1966. Т. 169, №4. C. 765-766.
18 Андреев А. Е. Об одном методе получения более чем квадратичных эффективных нижних оценок сложности 7г-схем // Вестник Московского университета. Серия 1. Математика. Механика. 1987. №1. С. 70-73.
19HastadJ. The Shrinkage Exponent of De Morgan Formulae is 2 // SIAM J Comput. 1998. V. 27, №1. P. 48-64.
оценок сложности в совокупности с важностью этой проблемы побуждают видоизменять исходную задачу, в частности, рассматривать более слабые модели вычислений, а именно схемы с различными ограничениями, и в первую очередь, схемы в неполных базисах. Разработка методов получения высоких нижних оценок сложности в неполных базисах важна как сама по себе (например, при реализации монотонных функций в монотонном базисе20), так и для разработки методов получения высоких нижних оценок в полных базисах21.
В случае реализации функций в неполных базисах получены принципиально более высокие конструктивные нижние оценки, чем в полных базисах. Э. И. Нечипоруком для сколь угодно большого числа с приведён22 пример неполного базиса и последовательности функций, сложность реализации которых формулами над этим базисом имеет сложность порядка пс (здесь и далее в этом абзаце п — количество переменных у функции). А. А. Разборов получил23 оценку вида nclogn для сложности реализации монотонных функций специального вида схемами из функциональных элементов над монотонным базисом. Квазиэкспоненциальные нижние оценки сложности были получены А. Е. Андреевым. Им приведён24 пример последовательности функций со сложностью реализации схемами из функциональных элементов в монотонном базисе вида 2n .
Для глубины реализации булевых функций формулами или схемами из функциональных элементов также неизвестны конструктивные высокие нижние оценки. Это связано, в частности, с тем, что любая конечная система булевых функций «равномерна». Конечная система функций A называется равномерной, если существуют такие константы cиd (зависящие от системы A), что для любой функции / Є [A] выполняется неравенство
АA(/) ^ с log ivФ A (/) + d.
Равномерность систем булевых функций изучалась многими авторами25.
20См., например, Андреев А. Е. О синтезе схем из функциональных элементов в полных монотонных базисах // Математические вопросы кибернетики, вып. 1. М.: Наука, 1988. С. 114-139.
21См., например, ОкольнишниковаЕ. А. О сведении оценок сложности в полном базисе к оценкам сложности в неполном базисе // Методы дискретного анализа в теории графов и схем, вып. 42. Новосибирск: Институт математики СО АН СССР, 1985. С. 80-90.
22Нечипорук Э. И. О реализации дизъюнкции и конъюнкции в некоторых монотонных базисах // Проблемы кибернетики, вып. 23. М.: Наука, 1970. С. 291-293.
23Разборов А. А. Нижние оценки монотонной сложности некоторых булевых функций // ДАН СССР. 1985. Т. 281, №4. С. 798-801.
24 Андреев А. Е. Об одном методе получения эффективных нижних оценок монотонной сложности // Алгебра и логика. 1987. Т. 26, №1. С. 3-26.
25Cм., например, Яблонский С. В., Козырев В. П. Математические вопросы кибернетики // Информационные материалы, вып. 19а. М.: Научный совет по комплексной проблеме «Кибернетика» АН СССР, 1968. С. 3-15; Храпченко В. М. О соотношении между сложностью и глубиной формул // Методы дискретного анализа в синтезе управляющих систем, вып. 32. Новосибирск: Институт математики СО АН СССР, 1978. С. 76-94; Pratt V.R. The effect of basis on size of Boolean expressions // 16th Ann. Symp. Found. Comput. Sci. 1975. New York. N.Y., 1975. P. 119-121; SpiraP. M. On time-hardware complexity tradeoffs for Boolean functions // Proc. 4th Hawai Symposium on System Sciences. North Hollywood:
Завершающие шаги по доказательству равномерности любой конечной (не обязательно полной) системы булевых функций были сделаны А. Б. Уголь-никовым26. Таким образом, если бы существовала система функций A, такая что порядок роста глубины реализации формулами над системой A некоторой последовательности функций превосходил бы величину logn, где п — количество переменных у функции, то из условия равномерности автоматически получалось бы, что сложность реализации этой последовательности функций росла бы быстрее любого полинома.
В отличие от случая функций двузначной логики, во множестве Pk (к ^ 3) функций многозначной логики существуют конечные системы функций, не являющиеся равномерными27. Надо отметить, что изучение сложности реализации функций /с-значной логики в связи с возрастающей ролью многозначной логики в информатике и математической кибернетике, а также в различных приложениях, становится важным направлением исследований. В частности, перспективным направлением разработки методов получения высоких конструктивных нижних оценок является исследование сложности реализации функций /с-значной логики схемами и формулами в неполных базисах.
Своеобразие множества функций многозначной логики, имеющего ряд принципиальных отличий от множества булевых функций28, способствует получению высоких нижних оценок для конструктивно заданных последовательностей функций /с-значной логики. Так для случая реализации функций 3-значной логики схемами из функциональных элементов Г. А. Ткачёвым приведён29 пример неполного базиса и конструктивно заданной последовательности функций от п переменных, асимптотика слож-ности реализации которых имеет вид 2Сп , что превосходит аналогичные результаты для булевого случая. В случае реализации функций формулами А. Б. Угольниковым были специальным образом подобраны30 неполный базис B и последовательность /n(#i, , хп) функций 4-значной логики, для
Western Periodicals Company, 1971. P. 525-527; Wegener I. Relating Monotone Formula Size and Monotone Depth of Boolean Functions // Information Processing Letters, 16. 1983. P. 41-42.
26Угольников А. Б. О полиномиальной эквивалентности формул для замкнутых классов двузначной логики // VII Всесоюзная конференция «Проблемы теоретической кибернетики»: тезисы докладов. Часть 1. Иркутск: Изд-во Иркутского государственного университета, 1985. С. 194-195. (см. также RagazM.E. Parallelizable algebras. Archiv fur mathematische Logik und Grundlagenforschung 26 (1986/7). P. 77-99).
27Угольников А. Б. О глубине и полиномиальной эквивалентности формул для замкнутых классов двузначной логики // Математические заметки. 1987. Т. 42, вып. 4. С. 603-612.
28См., например, Янов Ю. И., Мучник А. А. О существовании /г-значных замкнутых классов, не имеющих конечного базиса // ДАН СССР. 1959. Т. 127, №1. С. 44-46; Яблонский С. В. Введение в дискретную математику. М.: Высшая школа, 2003.
29 Ткачёв Г. А. О сложности реализации одной последовательности функций /г-значной логики //
Вестник Московского университета. Серия 15. Вычислительная математика и кибернетика. 1977. №1.
С. 45-57.
30 Угольников А. Б. О сложности реализации формулами одной последовательности функций 4-знач
ной логики // Вестник Московского университета. Сер. 1. Математика. Механика. 2004. №3. С. 52-55.
которых значение сложности определяется равенством
L$g(/n) = 2 ([^/2] + 1) — [п/2].
Подобная конструкция также позволяет получить пример последовательности функций 3-значной логики, глубина которых растёт экспоненциально от числа переменных.
Цель работы
Целью диссертационной работы является разработка новых методов получения высоких нижних оценок сложности и глубины реализации функций многозначной логики формулами и схемами из функциональных элементов над неполными системами.
Основные методы исследования
В диссертации используются методы дискретной математики и математической кибернетики, в частности, методы теории синтеза и сложности управляющих систем, теории функциональных систем и теории графов, а также методы математического анализа.
Научная новизна
Все основные результаты работы являются новыми, получены автором самостоятельно. Основные положения диссертации, выносимые на защиту, следующие:
-
Для заданных в явном виде неполных базисов и функций шести- и более значной логики получены нижние оценки сложности реализации формулами, растущие асимптотически быстрее, чем 23, где п — число переменных у функции.
-
Для заданных в явном виде неполных базисов и функций шести- и более значной логики получены нижние оценки глубины, имеющие порядок роста Зп, где п — число переменных у функции.
-
Приведён пример конечного и бесконечного базисов функций к-знач-ной логики (к ^ 5), таких, что они порождают один и тот же замкнутый класс, функции Шеннона глубины и сложности реализации формулами над этими базисами попарно асимптотически равны (и при этом растут не медленнее, чем экспоненциально и, соответственно, сверхэкспоненциально), причём каждая функция бесконечного базиса используется хотя бы в одной минимальной формуле, реализующей функцию, на которой достигается значение функции Шеннона.
-
Построен бесконечный базис функций трёхзначной логики и предъявлена конкретная последовательность функций, такая, что глубина (а, следовательно, и сложность реализации схемами из функциональных элементов) функций из этой последовательности ограничена снизу величиной 2n_1, где п — число переменных у функции.
-
Построен бесконечный базис функций четырёхзначной логики и предъявлена конкретная последовательность функций, такая, что асимптотика роста сложности реализации формулами над этим базисом функций данной последовательности превосходит п 22 , где п — число переменных у функции.
Теоретическая и практическая ценность работы
Диссертация имеет теоретический характер. Результаты диссертации могут найти применение в исследованиях по теории синтеза и сложности управляющих систем. Некоторые разделы диссертации могут быть использованы в спецкурсах для студентов и аспирантов, обучающихся по специальности «Математика».
Апробация работы
Результаты диссертации неоднократно докладывались на семинаре «Функции многозначной логики и смежные вопросы» под руководством проф. А. Б. Угольникова, проф. Р. М. Колпакова и проф. С.Б.Гашкова (2010– 2012гг.), на семинаре «Синтез и сложность управляющих систем» под руководством проф. О. М. Касим-Заде (2014г.), на семинаре «Математические вопросы кибернетики» под руководством проф. О. М. Касим-Заде (2016г.), на XIX международной конференции «Ломоносов 2012» (Москва, 2012 г.), на XI международном семинаре «Дискретная математика и её приложения», посвящённом 80-летию со дня рождения академика О. Б. Лупанова (Москва, 2012г.), на IX молодёжной научной школе по дискретной математике и её приложениям (Москва, 2013г.), на IX международной конференции «Дискретные модели в теории управляющих систем» (Москва и Подмосковье, 2015г.), на X молодёжной научной школе по дискретной математике и её приложениям (Москва, 2015г.).
Публикации
Основные результаты диссертации опубликованы в 7 работах, 3 из которых — в журналах, рекомендованных ВАК РФ. Список публикаций приведён в конце автореферата [1-7].
Структура и объем диссертации
Формулировка основного результата главы
Введём необходимые определения и обозначения, используемые в дальнейшем. Все неопределённые понятия, как правило, общеизвестны, при необходимости их определения можно посмотреть в книге [81].
Обозначим через k, 2, множество {0,1,..., — 1}. Иногда, если из контекста понятно о каком значении идёт речь, будем использовать обозначение вместо k. Через будем обозначать множество всех наборов = (i,..., п) длины , каждая компонента І которых лежит во множестве k ( Є {1,... ,}). Функция (n (i,..., п) называется (-местной) функцией -значной логики от переменных i,..., п, если её областью определения является множество , а областью значений — множество k. Будем указывать у функции верхний индекс, обозначающий количество её переменных, только в случае, когда его значение существенно, но неочевидно из контекста. Обозначим через k множество всех функций -значной логики.
Пусть (i,... , п) — функция -значной логики. Переменная І называется существенной переменной для функции , если существуют такие два набора о" = ( 7i,... , (тп) иа = ( 7i,..., 7j_i, т , 7І+І,... , тп), что /(5") ф /(5" ). Если таких наборов не существует, то переменная ХІ называется несущественной (фиктивной) для функции /.
Будем говорить, что (п + 1)-местная функция g n+l (xi,... , жп+і) получена из n-местной функции f(n (xi,... , хп) операцией добавления несущественной переменной хп+\, если для всех наборов а Є EJ!+ верно равенство д(п+1 (сгі,. . . , 7n+i) = f(n (ai,. . . , (7n).
Функции f(n\xi,..., жп) и g iyXi,..., жп) из Pk будем называть равными, если для любого набора д = ( 7i,..., (тп) Є Е% верно равенство /(n)(o"i,..., 7П) = (о"і,..., 7П). Пусть f(n\xi,..., хп), g(m (xi,... , xm) Є Pfc, m п, и пусть функция h n (xi,..., Хп) получена из функции g(m (xi,... ,xm) операцией добавления фиктивных переменных xm+i,... , хп. Тогда функции f n (xi,..., хп) и g m (xi,..., xm) называются равными, если равны функции f n (xi,..., хп) и h n (xi,..., хп). Аналогично определение равных функций можно распространить на случай двух функций, зависящих от произвольных переменных.
Определим понятие формулы. Пусть задано некоторое (конечное или счётное) множество A = { f\ni (хл і,..., Хл „-,), fo (хо },..., Хопп) Л функ-ций /с-значной логики, называемое базисом. Здесь и далее в работе под базисом будет пониматься система функций вне зависимости от полноты и минимальности по включению. Выражения вида ХІ являются формулами над системой A. Если Фі,..., Фп. — формулы над базисом A, то выражение j\ (Фі,..., Фщ) также является формулой над системой A. Других формул над базисом A нет. Формулы, представляющие из себя символ переменной или константы, будем называть тривиальными. Формулу Ф, в которую из символов переменных входят только симво лы xi,..., хп, будем обозначать Ф(жі,..., хп). Определим значение формулы Ф(жі,..., Хп) на наборе д = ( 7і,... , тп) из Е . Если формула Ф представляет собой переменную Хі, то её значение на наборе д определим как а І. Пусть формула Ф имеет вид Ф = /(т)(Фі,..., Фто), и пусть известны значения формул Фі,..., Фто на наборе 5", и они равны 7ь 7т соответственно. Тогда положим Ф(сг) = / (7ъ 7т).
Таким образом, определено значение формулы на любом наборе, тем самым каждой формуле Ф(хі,... ,хп) сопоставлена некоторая функция f(xi,..., Хп). Будем говорить, что функция f(xi,..., хп) реализуется формулой Ф. Если некоторая нетривиальная формула над системой A реализует функцию /, то будем говорить, что функция / получена операцией суперпозиции из функций системы A.
Пусть Ф = /(Фі,... , Фп) — формула. Определим понятие подформулы формулы Ф индуктивно. Формулы Фі,..., Фп являются подформулами формулы Ф (эти подформулы называются главными). Подформулами формулы Ф являются также сама формула Ф и все подформулы формул Фі,... ,ФП. Других подформул у формулы Ф нет.
Под тривиальной подформулой некоторой формулы Ф понимаем подформулу формулы Ф, которая является тривиальной формулой.
Под сложностью Ь(Ф) формулы Ф будем понимать количество символов переменных и констант, входящих в эту формулу. Кроме данного определения сложности в литературе распространено понятие сложности Ь (Ф) формулы Ф как суммы весов входящих в формулу функциональных символов. Если за вес функционального символа принять величину, на единицу меньшую количества его переменных, то рассматриваемые меры сложности будут отличаться на единицу, а именно Ь(Ф) = Ь (Ф) + 1. Таким образом, большую часть результатов, полученные в диссертации, можно интерпретировать и как релультаты для другой меры сложности. Понятие глубины -О(Ф) формулы Ф определим индуктивно. Глубину тривиальной формулы будем считать равной нулю. Если формула имеет вид Ф = /(Фі, , Фп), то глубина -О(Ф) формулы Ф определяется соотношением Р(Ф) = max (1)(Ф )) + 1. г=1,...,п Пусть A — некоторое множество функций из Pk. Будем обозначать через [A] замкнутый класс, порождаемый функциями из A при помощи операций суперпозиции и введения фиктивной переменной. Множество A будем называть полным, если [A] = Р&.
Под графом будем понимать конечный граф без петель, но допускающий кратные рёбра (используемые определения графа и основных понятий, связанных с графами, соответствуют, например, книгам [35, 66]). При упоминании ориентированных графов также будем понимать, что они конечны, и что кратные рёбра допустимы, а петли — нет.
Пусть Хо = {xi,X2, } — счётное множество переменных, а B = {/ь/2?---} — произвольный базис функций /с-значной логики. Пусть mi,m2,... — всевозможные значения количеств переменных у функций из базиса B. Схемой из функциональных элементов над базисом
Доказательство основной теоремы главы
Предположим, что третий пункт доказываемого утверждения ложен. Тогда найдётся белая подформула формулы , такая что на наборе её первый аргумент (в случае, когда формула имеет вид (,), в случае вида (, , ) первые два аргумента) принимает значение 1, а сама она на этом наборе принимает значение, отличное от 1. Тогда мы получаем проти воречие с определением функций или , что и завершает доказательство утверждения. Утверждение 2.2. Пусть формула над системой A реализует функцию n(, i,..., п), и этой формуле описанным выше способом сопоставлено раскрашенное дерево. Пусть — чёрная главная подформула белой формулы , а — чёрная подформула формулы . Пусть формула не принима ет значения 3 на всех наборах а = (ско,..., ап) из Е + , таких, что «о = 0. Пусть — формула, получающаяся из формулы заменой подформулы С на константу 2. Тогда формула также реализует функцию fn.
Доказательство. Пусть С — чёрная главная подформула белой формулы 8 , а А — чёрная подформула формулы С, формула А не принимает значения 3 на наборах а = («о, . . ., (У.П) из Е + , таких, что CIQ = 0, = (70, . . ., 7n) — произвольный набор из Е%+ , В — формула, получающаяся из формулы В заменой подформулы С на константу 2. Согласно утверждению 2.1, формула В имеет вид /i(D, F, С) или A(D, С), где D, F, С — белые формулы. Далее считаем, что формула В имеет вид /i(D,F, О), второй случай рассматривается аналогично. Пусть C(j) = 3. Согласно свойству 2.2, имеем (7) = 3. Значит, формула С не принимает значения 3 на всех наборах а = (ско,... , ап) из Е%+ , таких, что CIQ = 0. Рассмотрим следующие случаи. Пусть 7о = 1. Из утверждения 2.1 следует, что D(j) = F(j) = 1. В силу соотношений /І(1, 1, С) = /І(1, 1, 2)= 1 верны равенства B(j) = В ( ) = 1, (7) = (7) = 1. Пусть 7о = 0, (7і,...,7п) Ф Qn. Тогда по определению функции fn имеем (7) = 0. Согласно свойству 2.1, -8(7) = 0. Из определения функции /І следует, что C(j) = 2, и на рассматриваемых наборах формулы и принимают одинаковые значения.
Пусть 7о = 0, (7i,...,7n) Qn. Тогда по определению функции fn имеем (7) = 1. Если D(j) = F(j) = 1, то -8(7) = 1 вне зависимости от значения, принимаемого формулой С, поэтому -8(7) = В (і) = 1. Если D(j) = F(j) = 0, то C(j) Є {2,3}, так как в противном случае -8(7) = 2, и по свойству 2.1 имеем (7) = 2, а это неверно. Но по условию C(j) = 3, следовательно, C(j) = 2, и можно заменить формулу С на константу 2 без изменения реализуемой функции. В остальных случаях (т.е. при -0(7) = F(l) = 0,1 или при - (т) = F(l)) получаем -8(7) = В (і) = 2.
Пусть 7о Ф {0,1}. Согласно утверждению 2.1 каждая белая подформула формулы имеет вид или /i(D, F, J), или A(D, J), где D, F, J формулы; D, F белые формулы. Это означает, что для любой белой подформулы формулы найдётся цепь, у которой все вершины и рёбра белые, и которая соединяет вершину, соответствующую этой подформуле, и некоторую висячую белую вершину. Возьмем произвольную белую подформулу G формулы и вершину вышеописанной цепи, соседнюю с висячей. Соответствующая ей формула, очевидно, имеет вид /i(y, К, F), fi(K, у, F) или Х(у, F), где K,F — формулы. Поэтому такая формула на наборе принимает значение 2 при любых значениях формулы F. А из свойства 2.1 следует равенство G(j) = 2. Тогда из равенств /І(2,2,С) = /І(2,2,2) = 2 получаем, что формулы и на рассматриваемых наборах принимают одинаковые значения. Таким образом, формулы и реализуют равные функции. Утвер ждение доказано. Утверждение 2.3. Пусть формула над системой A реализует функцию fn(y, %i,..., хп) и этой формуле описанным выше способом сопоставлено раскрашенное дерево. Если Ь() = LA(fn), то каждая нетривиальная чёрная подформула формулы на некотором наборе принимает значение 3 и имеет вид (pm(F, G), где т Є {3, ...,& — 1}; F, G — формулы.
Доказательство. Рассмотрим произвольную нетривиальную чёрную подформулу А формулы . Очевидно, что в цепи, соединяющей корень дерева с вершиной Д все вершины чёрные или белые. Корень дерева белый, А — чёрная формула, значит, в рассматриваемой цепи найдётся некоторая белая формула с главной чёрной подформулой. Пусть С — чёрная главная подфор мула белой формулы , а А — чёрная подформула формулы С. Допустим, что формула А ни на одном наборе не принимает значения 3. Тогда, заменив формулу С на константу 2, получим формулу . В результате этой опера ции уменьшится сложность формулы. Кроме того, согласно утверждению 2.2, формулы и реализуют равные функции. Следовательно, формула не является минимальной, что противоречит условию. То есть в формуле каж дая нетривиальная чёрная подформула принимает значение 3 на некотором наборе. Так как функции /І и Л не принимают значения 3 ни при каких зна чениях аргументов, каждая нетривиальная чёрная подформула формулы имеет вид (pm(F, G), где F, G — формулы, аm Є {3, ...,& — 1}. Утверждение доказано.
Сформулируем и докажем лемму, при этом в процессе доказательства проделаем основные шаги, необходимые при доказательстве теоремы 2.1. Эта лемма фактически даст экспоненциальную нижнюю оценку на глубину произвольной формулы над базисом A, реализующей функцию fn(y, Жі,..., хп). В дальнейшем (при доказательстве теоремы 2.1) станет понятно, что эта лемма даёт также экспоненциальную нижнюю оценку на глубину произвольной формулы над базисом B, реализующей функцию fn(y, Жі,..., хп). Лемма 2.1. Пусть — произвольная формула над системой A , реализующая функцию fn(y, Xi,..., Хп) из Pk и имеющая вид = А(А(... А(А(у, Zi), Z2),...), ZN), где Z\,..., Zjy — формулы над системой A , к 4, п и N — натуральные
Доказательство вспомогательных утверждений
Рассуждение из доказательства теоремы 3.3 в совокупности с построением базиса и утверждением теоремы 3.2 доказывают утверждение, анонсированное в начале данного параграфа, формулирующееся следующим образом (определения функций fi(x,y,z) и (рт(х,у), где т Є {3,... ,к - 1}, описаны в начале данного параграфа).
Теорема 3.4. Пусть 03 = {/І, (/?з, , Фк-і, 2} — конечный базис функций к-значной логики (к 5), а — бесконечный базис функций к-значной логики (к 5), получающийся объединением базиса 03 и множества всех функций, реализуемых формулами вида (рт1(... (pms(xs+i, xs),... ,хі) для всех натуральных значений числа s. Тогда справедливы следующие утверждения: 1) [03] = [(] (и, следовательно, класс [(] конечно порождён); 2) функции Шеннона глубины и сложности реализации формулами над этими базисами асимптотически равны (и растут не медленнее, чем экспоненциально и, соответственно, сверхэкспоненциально): D?g{n) D r{n) (к - 3)п - (к - 4)п, 3) каждая функция базиса используется хотя бы в одной минималь ной формуле, реализующей функцию, на которой достигается значе ние функции Шеннона {как сложности реализации формулами, так и глубины). Таким образом, приведён пример конечно-порождённого класса, а также конечного и бесконечного базисов, его порождающих, для которых совпадают асимптотики роста функций Шеннона глубины и сложности реализации формулами.
Отметим, что при рассмотрении меры сложности Ь (Ф) формулы Ф, равной количеству функциональных символов в формуле, асимптотика функции Шеннона сложности при переходе от базиса В к базису уменьшится в п раз, но всё ещё будет расти сверхэкспоненциальным образом. Асимптотика функции Шеннона глубины не изменится при рассмотрении другой меры сложности.
Приведённый пример показывает, что даже для замкнутых классов с таким высоким порядком роста сложности функций Шеннона удаётся сохранить асимптотику при переходе к бесконечному базису. Полученные классы, очевидно, являются конечно-порождёнными. Однако для случая замкнутых классов, не являющихся конечно-порождёнными, можно достичь даже более высоких асимптотик роста функций Шеннона, чем у известных [54, 65, 109] соответствующих нижних оценок в случае конечно-порождённых классов. В следующих параграфах пример таких классов будет приведён.
Построим замкнутые классы функций многозначной логики, не являющиеся конечно-порождёнными, в которых для всех типов рассматриваемых функций Шеннона при соответствующем выборе базиса (очевидно, бесконечного) будут справедливы нижние оценки с более высоким порядком роста, чем у известных [54, 65, 109] соответствующих нижних оценок в случае конечно-порождённых классов.
Пусть (р(х) —функция трёхзначной логики, принимающая значение 1 при х = 2 и значение 0 в остальных случаях. Пусть (х) —отображение из Е% в 2, которое набору (жі,..., хп) сопоставляет набор (ср(хі) ..., ср(хп)). Пусть а — набор из Е%. Определим функцию Л(г/,жі,... ,хп) из Рз следую щим образом.
Из свойства 3.4 следует, что в семействе формул над базисом, состоящим из константы 0 и функций , где G 2, в минимальных по сложности фо-мулах все подформулы могут иметь нетривиальные подформулы только в качестве первого аргумента. То есть в таких базисах все минимальные формулы «вытянуты в цепочку». Определим функции трёхзначной логики п(ь . . . ,п), 1, следующим образом. Функция принимает значение 0, если среди её аргументов чётное количество двоек, и значение 1, если нечётное. Докажем следующее утверждение. Теорема 3.5. Пусть Aз — неполный бесконечный базис функций трёхзначной логики, определяемый следующим соотношением: Aз = {0} U {й Є г}, где 2 = U . Тогда для функции трёхзначной логики , 1, выпол neN няется равенство (3) 2п—1
Доказательство. Для начала отметим, что Є [Aз]. В процессе доказательства формула над Aз, реализующая указанную функцию, будет естественным образом получена. Пусть формула F реализует функцию („. Если у некоторой её подформулы есть нетривиальные подформулы не в качестве первого аргумента, то заменим их на константу 0. Согласно свойству 3.4, реализуемая формулой функция от этого не поменяется, а глубина и сложность не увеличатся. В дальнейшем считаем, что у всех подформул все аргументы, кроме первого, тривиальны. Итак, формула F имеет вид F = Ай ( 4І,О, 4І,Ь J Аі ті), 1,0 = AU2(A2j0, -42,1, 2,m2), Ad-1,0 = &d(Ad,0, ЛіД, , Ad,md), ( ) где Аід,..., А\іГПі1..., Дц,.. , -4d,md и ,о — тривиальные формулы. Из определения функций А следует, что если на некотором наборе формула Aifi (і {1,... , d}) принимает значение 1, то и формула F на нём также принимает значение 1. Также из определения следует, что если на некотором наборе формула F принимает значение 0, то и для всех і {1,... ,d - 1} формулы Aifi также принимают значение 0.
Пусть формула А о имеет вид ХІ для некоторого і. Тогда на наборе (1,1,..., 1) функция Сп(жь хп) принимает значение 0, а формула F — значение 1. Следовательно, А о представляет из себя константу 0. Рассмотрим формулы В\ = Ай (0, АІД, ..., Аі ті), Bd = Ай (0, Ац,..., Ad, Если какая-нибудь из них реализует константу 0, то, согласно свойству 3.5, можно выкинуть соответствующую ей подформулу из соответствующей «цепочки» ( ). При этом реализуемая функция не изменится, глубина формулы не увеличится, а сложность уменьшится. Проделаем такую операцию со всеми подформулами, реализующими ноль. Далее будем считать, что все формулы ВІ не реализуют константу 0, а, значит, равны единице на некотором наборе (значения 2 они принимать не могут). Для формулы ВІ обозначим такой набор ді. Заметим, что в силу показанных ранее соотношений формула F на всех наборах ді (і = 1,... , d), принимает значение 1.
Пусть найдутся такие числа і и j, что в формулу ВІ не входит переменная Xj (і Є {1,...,cf}, j Є {1,...,n}). Тогда в наборе ді заменим j-ю компоненту: если она равнялась двум, то заменим её нулём, а если нет, то заменим её двойкой. В результате получим набор [. С одной стороны, у этого набора и у набора ді разная чётность количества двоек, и, следовательно, функция ( принимает на них разные значения. С другой стороны, эти наборы отличаются только в j -й компоненте. А так как переменная Xj не входит в формулу ВІ, то В І (а І) = В{([). Значит, В{(д[) = 1 и F(d i) = 1. Полученное противоречие показывает, что во всех формулах ВІ присутствуют все переменные хі,... , хп в качестве подформул.
Согласно определению функции Л, все наборы, на которых формула ВІ принимает значение 1, отображением переводятся в один и тот же набор из Р2 (если переменные упорядочены и встречаются по одному разу, то этот набор — а). Рассмотрим все наборы, на которых функция ( принимает значение 1. При отображении эти наборы перейдут в 2n_1 наборов из Р 2. Принимая во внимание то, что для равенства формулы F единице на некотором наборе необходимо, чтобы на этом наборе хотя бы одна из формул ВІ принимала значение 1, получаем, что количество d формул ВІ удовлетворяет
Построение класса с одинаковой сверхэкспоненциальной асимптотикой сложности в конечном и бесконечном базисах
Предположим, что найдется число р {1,...,}, такое, что формула Ні не является переменной из множества X. Тогда при Р не может выполняться равенство Щ () = тпр, пір {3,4, 5} (ни одна функция из A не принимает значений 3, 4 и 5, и при этом 7о?7і {3,4,5}). Следовательно, Zi(j) = 1 при всех j Р и Zi можно убрать из формулы без увеличения сложности. Предположим, что найдутся такие p,q {1, ...,}, р = q, что Щ = Щ , но тр = mq. Тогда не могут одновременно выполняться соотношения Щ (j) = тр, Hi (j) = mq.
Следовательно, Zi(j) = 1 при всех 7 Р , и Zi также можно убрать из формулы без увеличения сложности. А если найдутся такие р, q {1,..., }, р = q, что Hi = Hi и nip = vfiq (р q), то можно заменить формулу на формулу без увеличения сложности формулы (т.е. убрать из цепи (fim). Значение формулы при таком преобразовании не изменится. Будем проделывать такие преобразования в формуле Zi до тех пор, пока это возможно. Преобразуем таким образом все подформулы Zi формулы . В результате получим эквивалентную формулу меньшей сложности (и не большей глубины), у которой для любой подформулы Zi среди подформул Hi встречаются только переменные из множества X, причем каждая не более одного раза. Рассмотрим формулу Zi, 1 і N. Пусть в нее входит г переменных из множества X, например, жо,... , жг-ъ причем без ограничения общности переменная жр подается на вход функции (ртр. Предположим, что г п. Тогда для набора а = (71,72 0, , скп), где 71 = 7, 72 = 1, «о = о, , QV-i = гПг-1: аг = ... = ап = 2, выполняются соотношения Zi(a) = 1, Ф(а) = 8, что противоречит определению функции fn. Таким образом, г п, т.е. L(Zi) п + 1.
Рассмотрим произвольное г, 0 г п, и произвольный набор /3 = (/Зі,... ,/Зп), состоящий только из троек, черверок и пятерок. Допустим, что среди подформул Zi не найдется такой, что переменная хо подаётся на вход функции ippi: х\ подаётся на вход ср 2, ... , хг-\ подаётся на вход ср г, хг+\ подаётся на вход /?/?г+1, и т.д., хп подаётся на вход ср п, а переменная хг не входит в Zi. Тогда рассмотрим набор а = (71,725 ао, , скп), где 71 = 7, 72 = 1, «о = (Зі,..., otr-i = (3Г: OLT = 2, ar+i = (3r+i,..., an = (Зп. На этом наборе ни одна из подформул Zi не обратится в 1, и, значит, Ф(а) = 7, что противоречит определению функции fn. Полученное противоречие показывает, что N не меньше, чем число способов выбрать г и /3, т.е.
Доказательство теоремы 1.2. Нижняя оценка. Пусть Ф — произвольная минимальная формула над В, реализующая функцию /n; Т — соответствующее этой формуле корневое дерево, раскрашенное описанным выше способом; v — корень дерева Т. Из свойств 1.4 и 1.6 следует, что У(Ф) = {yi}, %(Ф) = {у2} Рассмотрим произвольную раскрашенную в белый цвет невисячую вершину v. Если формула Av имеет вид Av = ipm(B, С), где В,С — формулы, то в силу определения функций (рт для любого набора а Є En+Z выполняется неравенство Av(a) ф 9, что противоречит свойству 1.3. Пусть формула Av имеет вид Av = /i( ,C, D), где B,C,D — формулы над базисом B (вершины VB И VC раскрашены в белый цвет). Пусть а = (ско,... ,an+2) произвольный набор из EQ . Если CIQ = б, ТО В силу свойства 1.4 выполняются равенства B{6L) = C\dt) = 6. Пусть «о ф 6. Предположим, что выполняется неравенство В (а) ф С (а). Тогда Av(a) = fj,(B(a), С (a), D(a)) = 6. Поэтому в силу свойства 1.3 имеем Ф(й) = б, что противоречит определению функции fn. Таким образом, В (а) = С (а) для любого набора а Є EQ .
Будем преобразовывать формулу Ф без увеличения сложности и одновременно строить формулу С специального вида над системой A, реализующую функцию fn. Пусть Ф имеет вид Ф = /І(АІ, Ві, Сі), где Аі, і,Оі — формулы, и пусть (без ограничения общности) L{A\) L{B\). Положим Фі = ц(Аі, Аі, Сі), G\ = Х(Аі, Сі). Очевидно, что формулы Фі и G\ реализуют функцию /п, и выполняется неравенство Ь(Фі) 1 (Ф). Легко видеть, что А\ — либо тривиальная формула, либо формула вида А\ = /І( 2, 2, CQ), где УІ2, В2 2 — формулы. Во втором случае (пусть, например, L{A2) L( 2)) положим А1 = /І( 2, А2, С2), А1 = Х(А2,С2), Ф2 = Ц(А1, А1,С\) = /і(/і(Л2, А2, С2), fJ,(A2, А2, С2)1 Сі), С2 = А(ЛІ5 Сі) = А(А(УІ2, С2), Сі). Выполним над формулами Ач аналогичные преобразования, и т. д. В конце концов после некоторого числа N преобразований мы получим формулы Фдг над базисом B и GN над базисом A, реализующие функцию /п, такие, что сложность формулы Фдг удовлетворяет неравенству