О сложности функций многозначной логики, принимающих два значения тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИМЕНИ М. В. ЛОМОНОСОВА

МЕХАНИКО-МАТЕМАТИЧЕСКИЙ ФАКУЛЬТЕТ

На правах рукописи

— - УДК 519.714

Дагаев Дмитрий Александрович

О СЛОЖНОСТИ ФУНКЦИЙ МНОГОЗНАЧНОЙ ЛОГИКИ, ПРИНИМАЮЩИХ ДВА ЗНАЧЕНИЯ

01.01.09 — дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Москва - 2011

1 9 МАЙ 2011

4846715

Работа выполнена на кафедре дискретной математики Механико-математического факультета Московского государственного университета имени М. В. Ломоносова.

Научный руководитель:

Официальные оппоненты:

Ведущая организация:

доктор физико-математических наук, профессор

Угольников Александр Борисович, доктор физико-математических наук, профессор Алексеев Валерий Борисович; кандидат физико-математических наук, доцент Стеценко Владимир Алексеевич. Казанский (Приволжский) федеральный университет.

Защита диссертации состоится 27 мая 2011 г. в 16 ч. 45 мин. на заседании диссертационного совета Д.501.001.84 при Московском государственном университете имени М. В. Ломоносова по адресу: Российская Федерация, 119991, Москва, ГСП-1, Ленинские горы, д. 1, МГУ, механико-математический факультет, аудитория 14-08.

С диссертацией можно ознакомиться в библиотеке механико-математического факультета МГУ (Главное здание, 14 этаж).

Автореферат разослан 27 апреля 2011 г.

Ученый секретарь ^

диссертационного совета у/ [/

Д.501.001.84 при МГУ доктор физико-математических наук, профессор А. О. Иванов

Общая характеристика работы Актуальность темы

Диссертация относится к теории синтеза и сложности управляющих систем — одному из основных разделов дискретной математики и математической кибернетики. В ней рассматривается задача о сложности реализации функций многозначной логики формулами над конечными системами.

Задача синтеза и сложности управляющих систем1 в общем случае формулируется следующим образом. Дан набор G базисных элементов некоторого типа (например, функциональные элементы или формулы), каждому из которых приписано некоторое положительное число — вес элемента. С помощью этих элементов по заданным правилам строятся более сложные объекты — схемы. Каждой схеме S ставится в соответствие некоторая функция / и число L(S), равное сумме весов всех входящих в нее элементов; при этом говорят, что функция / реализуется схемой S со сложностью L(S). Сложностью функции / называется величина LgU) = minL(5), где минимум берется по всем схемам S над G, реализующим функцию /. Для каждой функции f требуется найти минимальную схему S над G, реализующую / (то есть такую схему S, реализующую /, сложность которой удовлетворяет равенству L(S) = Laif))-При изучении функций из заданного конечного множества H рассматривается величина £<?(#) — maxLc(f), где максимум берется по всем функциям / из Н. Функция Lg(H) называется функцией Шеннона. Она характеризует сложность реализации в рассматриваемом классе управляющих систем самых сложных функций из множества Я. Эта функция была введена в работах К. Шеннона2, там же были получены первые значительные результаты о ее поведении.

Формулы и схемы из функциональных элементов (называемые далее схемами), реализующие дискретные функции, являются одними из основных модельных классов управляющих систем. Множество Pk всех функций fc-значной логики, к ^ 2, является важным примером класса дискретных функций, представляющим большой интерес как с теорети-

1Си.: Яблонский C.B. Основные понятия кибернетики //Проблемы кибернетики. 1959. Вып.2. С.7-38.

2Shannon С. Е. The synthesis of two-terminal switching circuits. Bell Syst. Techn. Journ. 1949. 28. JV11. P. 59-98 (русский перевод: Шеннон К. Работы по теории информации и кибернетике. М.: ИЛ, 1963. С. 59-101.).

ческой, так и с прикладной точек зрения. Одной из наиболее изученных классификаций функций /с-значной логики являются классы функций, замкнутые относительно операции суперпозиции3. В связи с этим возникает задача о реализации функций А;-значной логики из замкнутых классов формулами (или схемами) над конечными системами. В этой задаче можно выделить два направления исследований: синтез схем и формул в полных базисах и синтез схем и формул в неполных базисах.

В задаче о сложности реализации булевых функций основополагающие результаты были получены О. Б. Лупановым, предложившим асимптотически оптимальные методы синтеза для ряда классов управляющих систем. В частности, для произвольного полного конечного базиса С? булевых функций он показал4 справедливость следующих соотноше-ний5:

п п

где ЬдФЭ(Р2(п)) и Ьд(Р2(п)) — функции Шеннона при реализации функций схемами и формулами соответственно, ар — константа (минимальный приведенный вес элементов базиса), однозначно определяемая по базису (?. Оценки высокой степени точности для функций Шеннона при реализации булевых функций формулами и схемами в полных базисах получены в работах С. А. Ложкина6.

Задача о поведении функций Шеннона для множества всех булевых функций тесно связана с задачей о поведении функций Шеннона, соответствующих замкнутым классам булевых функций при реализации функций схемами и формулами в полных конечных базисах. Полное описание множества всех замкнутых классов булевых функций получено

3Яблонский C.B. Функциональные построения в fc-значной логике // Труды матем. ин-та АН СССР им. Стеклова. 1958. 51. С. 5-142.

4Лупанов О. В. Об одном методе синтеза схем // Известия вузов, Радаофизика 1.1958. С. 120-140.

Лупанов О. Б. О сложности реализации функций алгебры логики формулами // Проблемы кибернетики. 1960. Вып. 3. С. 61-80.

Лупанов О. Б. Об одном подходе к синтезу управляющих систем - принципе локального кодирования // Проблемы кибернетики. 1965. Вып. 14. С. 31-110.

"Здесь и далее всякий раз, когда речь идет об асимптотических оценках, подразумевается, что эти оценки имеют место при п —» оо.

6Ложкин С. А. Новые, более точные оценки функций Шеннона для сложности управляющих систем // Дискретный анализ и исследование операций. 1995. Т. 2, №3. С. 77-78.

Ложкин С. А. Оценки высокой степени точности для сложности управляющих систем из некоторых классов // Математические вопросы кибернетики. Вып. 6. М.: Наука, 1996. С. 190-214.

Э. Jl. Постом7. Он показал, что это множество счетно, причем каждый замкнутый класс имеет конечный базис. При реализации функций схемами для каждого замкнутого класса булевых функций, не содержащегося в множестве8 LU К U D, и любого полного конечного базиса А. Б. Уголь-никовым9 получена асимптотически точная формула для соответствующей функции Шеннона. При реализации функций формулами для всех замкнутых классов булевых функций, не содержащихся в множестве10 SöLLiKöD, и любого конечного полного базиса асимптотически точные формулы для соответствующих функций Шеннона получены А. Е. Андреевым11.

Следует отметить, что упомянутые выше методы синтеза схем и формул существенным образом используют полноту базисов. Поэтому задача о синтезе схем и формул в неполных базисах требует разработки других методов синтеза. Отметим некоторые результаты, полученные в задаче о сложности реализации булевых функций из замкнутых классов схемами и формулами в неполных базисах. При реализации функций схемами для замкнутых классов функций, сохраняющих константы, и любых конечных систем, порождающих эти классы, асимптотически точные формулы для соответствующих функций Шеннона были получены Э. И. Нечипо-руком12. Аналогичные утверждения справедливы также для ряда других замкнутых классов13. В задаче о сложности реализации функций форму-

7Post Е. L. Introduction to a general theory of elementary propositions // Amer. J. Math. 1921. 43, №3. P. 163-185.

Post E. L. The two-valued iterative systems of mathematical logic //' Annals of Math. Studies. 1941. № 5. Princeton Univ. Press.

8Через К и D обозначаются множества всех линейных функций, конъюнкций и дизъюнкций соответственно.

8 Угольников А. Б. О реализации функций из замкнутых классов схемами из функциональных элементов в полном базисе // Доклады АН СССР. 1983. Т. 271. №1. С. 49-51.

10Через S обозначается множество всех самодвойственных функций.

11 Андреев А. Е. Метод бесповторной редукции синтеза самокорректирующихся схем // Доклады АН СССР. Т. 283, №2. 1985. С. 265-269.

Андреев А. Е. О синтезе функциональных сетей. Докт. диссертация. М.: МГУ им. М. В. Ломоносова, 1985.

12 Нечипорук Э.И. О синтезе логических сетей в неполных и вырожденных базисах // Докл. АН СССР. 1964. Т. 155. №2. С. 299-301.

Нечипорук 9. И. О синтезе логических сетей в неполных и вырожденных базисах // Проблемы киберенетики. Вып. 14. М.: Наука, 1965. С. 111-160.

13 Угольников А. Б. Синтез схем и формул в неполных базисах. ДАН СССР, 1979. Т. 249, № 1. С. 60-62.

Угольников А. Б. О реализации булевых функций из некоторых замкнутых классов схемами из функциональных элементов в неполных базисах // Вестник Московского университета. Сер. 1, Математика. Механика. М.: Изд-во МГУ, 1985. №3. С. 87-89.

Андреев А.Е. О синтезе схем из функциональных элементов в полных монотонных базисах //

лами известно14, что для любого замкнутого класса В и любой конечной системы, порождающей класс В, сложность реализации формулами каждой функции из В имеет не более чем экспоненциальный порядок роста от числа переменных. Для некоторых замкнутых классов («близких» к множеству Р2) и любых конечных систем, порождающих эти классы, получены асимптотически точные формулы для соответствующих функций Шеннона15. Получен также ряд других результатов о верхних оценках сложности схем и формул (в неполных базисах), реализующих функции из некоторых замкнутых классов.

Таким образом, в задаче о сложности реализации булевых функций схемами и формулами в конечных базисах с положительными весами всех входящих в них элементов получен ряд существенных результатов. Получение аналогичных результатов для функций многозначной логики наталкивается на значительные трудности. Это связано с принципиальными отличиями многозначных логик от двухзначной. Одним из основных отличий является континуальность16 множества всех замкнутых классов функций fc-значной логики при к ^ 3. В связи с этим важным направлением исследований является изучение свойств отдельных семейств замкнутых классов. Среди таких семейств одно из центральных мест занимает семейство всех предполных классов, изучению свойств которого посвящено значительное число публикаций. Полное описание множества всех предполных классов при всех к ^ 3 получено И. Ро-зенбергом17. К числу наиболее изученных семейств замкнутых классов функций fc-значной логики относится также семейство всех замкнутых классов функций из Ру — множества всех функций fc-значной логики, принимающих значения только из множества {0,1,..., I — 1}, к > I ^ 2. Некоторые свойства этих классов изучены в работах Г. Буроша18 и дру-

Математические вопросы кибернетики, 1988. № 1. С. 114-139.

14 Угольников А. Б. О глубине и сложности формул, реализующих функции из замкнутых классов // Доклады АН СССР. 1988. Т. 298. №6. С. 1341-1344.

15 Угольников А. Б. Синтез схем и формул в неполных базисах. Препринт ИПМ АН СССР. М. 1980. №112.

16См.: Янов Ю.И., Мучник A.A. О существовании к-значных замкнутых классов, не имеющих конечного базиса // ДАН СССР. 1959. 127. №1. С. 44-46.

17Rosenberg I. G. La structure des fonctions de plusieurs variables sur un ensemble fini. Comptes Rendus, de l'Academ. Paris. 260. 1965. P. 3817-3819.

Rosenberg I. G. Über die funktionale Vollständigkeit in den mehrwertigen Logiken // Rozpr. ÖSAV fiada Mat. Pïiv. Vëd., Praha. 1970. 80. P. 3-93.

lsBurosch G. Über die Ordnung der prëvollstândigen Klassen in Algebren von Prädikaten. Preprint, WPU Rostock. 1973.

гих авторов19. В работах Д. Jlay20 и Н. Грюнвальда21 изучены некоторые свойства замкнутых классов функций из множества В этих работах рассматривается отображение (называемое проекцией) функций из множества Р3 2 в множество P<¿. На основе этого отображения для каждого множества F С Р32 определяется множество prF = Uprf, где prf — проекция функции /, а объединение берется по всем функциям f Е F. В результате каждому замкнутому классу В булевых функций сопоставляется семейство У1(В) всех замкнутых классов F функций из Рз$, таких, что prF = В. Для каждого замкнутого класса В булевых функций найдена мощность множества 91(B) и приведено описание этого множества для тех случаев, когда мощность 01(B) конечна или счетна.

Отметим некоторые результаты, полученные в задаче о сложности реализации функций многозначной логики. В. А. Орлов22 ввел понятие оптимального полного базиса (конечный полный в базис является оптимальным, если асимптотическое поведение соответствующей функции Шеннона определяется минимальным приведенным весом элементов базиса) функций fc-значной логики, к ^ 3, и для каждого такого базиса предложил асимптотически наилучший метод синтеза схем из функциональных элементов. Он показал также, что почти любой конечный полный в Р*. базис является оптимальным. При реализации функций схемами для любого полного конечного базиса асимптотически точная оценка соответствующей функции Шеннона анонсирована в работе С. А. Ложкина23. При реализации функций формулами для некоторых полных в Рк

19Lau D. Prävollständige Klassen von P¡e¡j // Elektron. Informationsverarb. Kybernet. EIK, 11. 1975. P. 10-12, 624-626.

Burosh G., Dassow J., Harnau W., Lau D. On subalgebras of an aigebra of predicates // J. Inf. Process Cybern. 1985. EIK 21, 1/2. P. 9-22.

Lau D. Über abgeschlossene Teilmengen von Pti2 // J. Inf. Process. Cybern. 19S8. EIK 24,10. P.495-513.

20inu D. Über abgeschlossene Teilmengen von P3,2 // J. Inf. Process. Cybern. 1988. EIK 24, 11/12. P.561-572.

21 Grünwald N. Bestimmung sämtlischer abgeschlossenen Mengen aus Pj,2, deren Projektion Fg ist // Rostock. Math. Kolloq. 1983. 23. P. 5-26.

Grünwald N. Beschreibung aller abgeschlossenen Mengen aus Рз,2, deren Projektion Ps" ist, mit Hilfe von Relationen // 1983. Rœtock. Math. Kolloq. 23. P. 27-34.

22 Орлов В. А. Реализация функций из Р* схемами в произвольном базисе из функциональных элементов // Докл. РАН. 1998. Т. 359, №3. С. 308-309.

Орлов В. А. Об оптимальности почти всех базисов из P¡, // Докл. РАН. 1998. Т. 363, Л*5. С. 602603.

23Ложкин С. А. Об асимптотическом поведении функции Шеннона для сложности схем из функциональных элементов в fc-значной логике // Труды IV Международной конференции «Дискретные модели в теории управляющих систем» (Красновидово, 19-25 июня 2000 г.). М.: МАКС Пресс, 2000. С. 64-67.

(.к ^ 3) базисов асимптотически точные формулы для соответствующих функций Шеннона получены в работах Е. Ю. Захаровой24, С. Б. Гашко-ва25 и других авторов. Примеры последовательностей функций многозначной логики, сложности которых в классе формул над некоторыми конечными неполными системами имеют сверхэкспоненциальный порядок роста от числа переменных, приведены в работах А. Б. Угольни-кова26. Экспоненциальные нижние оценки для сложности реализации функций /с-значной логики (к > 3) схемами из функциональных элементов в неполных базисах получены Г. А. Ткачевым27.

Цель работы

Целью работы является получение верхних и нижних оценок сложности реализации формулами над конечными системами функций трехзначной логики, принимающих значения из множества {0,1}.

Основные методы исследования

В диссертации используются методы дискретной математики и математической кибернетики, в частности, методы теории синтеза и сложности управляющих систем и теории функциональных систем.

Научная новизна

Все результаты работы являются новыми. В диссертации получены следующие основные результаты.

1. Для каждого конечно-порожденного замкнутого класса F функций из *Рз,2, отличного от множества всех псевдолинейных функций и

24Захарова Е.Ю. Реализация функций из Рк формулами // Матем. заметки. 1972. Т. И, №1. С.99-108.

25/Ъшкое С. Б. О параллельном вычислении некоторых классов многочленов с растущим числом переменных // Вестник Московского университета. Сер. 1, Математика. Механика. М.: Изд-во МГУ, 1990. №2. С. 88-92.

28 Угольников А. Б. О сложности реализации формулами одной последовательности функций многозначной логики // Математические вопросы кибернетики. М.: Наука, 1989. Л"» 2. С. 174-176.

Угольников А. Б. О сложности реализации формулами одной последовательности функций 4-значной логики // Вестник Московского университета. Сер. 1, Математика. Механика. М.: Изд-во МГУ, 2004. №3. С. 52-55.

27 Ткачев Г. А. О сложности реализации одной последовательности функций &-зкачной логики // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и кибернетика. 1977. №1. С. 45-57.

такого, что проекция F совпадает с множеством всех линейных булевых функций, и некоторой конечной системы, порождающей класс F, найдены точные формулы для соответствующих функций Шеннона. Приведены также примеры самых сложных функций для всех таких классов.

2. Для каждого конечно-порожденного максимального замкнутого класса F функций из и некоторой конечной системы, порождающей класс F, получены верхние и нижние оценки для соответствующих функций Шеннона. На основе этих оценок получены асимптотически точные формулы для функций Шеннона, соответствующих некоторым максимальным замкнутым классам.

3. Выделено некоторое счетное семейство В замкнутых классов булевых функций и показано, что для каждого замкнутого класса F функций из P3i2, проекция которого принадлежит семейству В, и любой конечной системы, порождающей класс F, функция Шеннона по глубине, соответствующая классу F, имеет линейный порядок роста.

Теоретическая и практическая ценность

Диссертация имеет теоретический характер. Результаты диссертации могут найти применение в исследованиях в теории синтеза и сложности управляющих систем.

Апробация результатов

Результаты диссертации неоднократно докладывались на семинаре «Функции многозначной логики и смежные вопросы» под руководством проф. С. Б. Гашкова, проф. Р. М. Колпакова и проф. А. Б. Угольнико-ва (2008 - 2010 гг.), на семинаре «Синтез и сложность управляющих систем» под руководством проф. О. М. Касим-Заде (2010 г.), на семинаре «Математические вопросы кибернетики» под руководством проф. О. М. Касим-Заде (2010 г.), на IX Межд. семинаре «Дискретная математика и ее приложения» (Москва, 18-23 июня 2007 г.), на VIII Межд. конференции «Дискретные модели в теории управляющих систем» (Москва, 6-9 апреля 2009 г.), на VII молодежной научной школе по дискретной математике и ее приложениям (Москва, 18-22 мая 2009 г.), на XVIII Межд.

школе-семинаре «Синтез и сложность управляющих систем» им. академика О.Б. Лупанова (Пенза, 28 сентября - 3 октября 2009 г.), на X Межд. семинаре «Дискретная математика и ее приложения» (Москва, 1-6 февраля 2010 г.), на Межд. научной конференции «Ломоносов-2010» (Москва, 12-15 апреля 2010 г.).

Публикации

Основные результаты диссертации опубликованы в 7 работах, список которых приведен в конце автореферата [1-7].

Структура и объем диссертации

Диссертация состоит из введения, четырех глав и списка литературы. Полный объем диссертации — 106 страниц, список литературы содержит 112 наименований.

Содержание работы

В диссертации рассматривается задача о сложности реализации функций из Рз,2 (множества всех функций трехзначной логики, принимающих значения из множества {0,1}) формулами над конечными системами. Для ряда конечных систем получены верхние и нижние оценки сложности реализации функций из замкнутых классов, порожденных этими системами.

Дадим необходимые определения. Пусть Ек = {0,1,.... к - 1}, к ^ 2. Обозначим через множество всех наборов а = (с^,.... ап), таких, что ах,...,ап 6 Е^, п > 1. Множество всех функций &-значной логики обозначим через Рк, а множество всех функций из принимающих значения только из множества Е2, — через Р^2-

Будем придерживаться следующих обозначений28 замкнутых классов булевых функций: Б — множество всех самодвойственных функций; Т, — множество всех функций, сохраняющих константу г, г = 0,1; -М" — множество всех монотонных функций; Ь — множество всех линейных функций; От — множество всех функций, удовлетворяющих условию

28См.: Угольников А. Б. Классы Поста. М.: Изд-во ЦПИ при механико-математическом факультете МГУ, 2008.

< 0т >,т = 2,3, ...,оо; 1т — множество всех функций, удовлетворяющих условию < 1т >, т — 2,3,..., оо; К — множество всех конъюнкций; £> — множество всех дизъюнкций; £/ — множество всех функций, существенно зависящих не более чем от одной переменной; С — множество всех функций, не имеющих существенных переменных. Пусть г € т = 2,..., оо. Положим

и = ЬПТ{, М{ = МПТи К{ = КПТи Д = £>ПТ<, ^ = £/ПТ<, С* = СПТ4;

Го1 = Т0ПТг,Мт = МоПМиЬп = ЬоПЬх.Яи = ЯЬПЯг.Дц = Д>ПГ>1;

Уо1 = £/оП£/1,501 ='5ПТ01,5М = 5ПМ, 51, = ЯШ;

ви = в пи, Ми = М П11,0™ = То П От,7Г - 21 П

МОт = МПОт,МГ = М П-Г,МО^ = МП 0?,М/^ = М П

Определим семейства N^N¡,N3 замкнутых классов булевых функций следующим образом. Положим

ЛГх = {Р2, Г0, Гь Т01, М, М0, Мг, М01,5,5Ьь 5М,

От, О™, МОт, 1т, /Г, МГ\ М/Г\ 2 < т < оо},

^з = {О00, МО00, М/°°, /Г, М0£°, м/г,

К, ^ь^оь А Г>0, £>ь £>01, и, Щ, ии Щ1, Ми, 5£/, С, С0; С1}.

Из результатов Э. Л. Поста следует, что Л^ и N2 и Л3 — это множество всех замкнутых классов булевых функций.

Пусть /(^1, ...,я„) € Рз,2- Проекцией функции /(хх,..., жп) называется такая булева функция (рг/)(х 1,...,хп), значение которой на произвольном наборе 5 £ £2П определяется равенством (рг/)(5?) = /(5). Таким образом, каждой функции / £ Р3 2 поставлена в соответствие функция рг/ £ Р2. В дальнейшем функцию (рг/)(жь ...,гп) будем обозначать через рг/(х1,..., хп). Проекцией ргР множества функций Р С Р3_2 называется множество и{Рг/}> гДе объединение берется по всем функциям / е Р.

Для каждого замкнутого класса булевых функций В определим множество функций

рг~1В - {/ е Рз,2 | рг! € 5}.

Легко видеть, что множество рг~1В является замкнутым классом функций из Р3)2. Замкнутый класс рг~1В называется максимальным классом (соответствующим классу В С Р2). Таким образом, каждому замкнутому классу В булевых функций соответствует максимальный класс рг~гВ С Р3 2. Очевидно, что класс рг~1В содержит каждый замкнутый класс Н из Рз.2, такой, что ргН — В. Для каждого замкнутого класса булевых функций В определим множество замкнутых классов

ЩВ) — {Л С Д2 | А - [Л], ргА = В}.

В вышеупомянутых работах показано, что максимальный класс рг~1В имеет конечную порождающую систему в тех и только тех случаях, когда В ф {С, Co,Ci}. Показано также, что если В £ N\, то семейство У1(В) конечно, если В £ N2, то У1(В) счетно, если В £ N3, то У1(В) имеет мощность континуума.

Функция / из называется псевдолинейной, если prf € L. Известно29 описание множества всех замкнутых классов псевдолинейных функций. Будем обозначать замкнутые классы, проекция которых совпадает с множеством L всех линейных булевых функций, через С, £г> ^2,0 П •^2,1 П С, £2,г, где г = 1,2,..., оо. Известно также, что все перечисленные классы, за исключением класса £2,00, являются конечно-порожденными.

Пусть Ф — конечная система функций из Рк, к ^ 2, [Ф] — замыкание системы Ф относительно операций суперпозиции и введения несущественной переменной. Пусть f(x 1, ...,хп) £ [Ф], Ф — формула над Ф, реализующая функцию /, а F С [Ф]. Через Ь(Ф) обозначим число символов переменных, входящих в формулу Ф (сложность формулы Ф), через Ьф(/) — сложность реализации функции / £ F над системой Ф, а через L9{F(n)) — функцию Шеннона по сложности для множества F. Через £>(Ф) будем обозначать глубину формулы Ф, через £>ф(/) — глубину реализации функции f £ F над системой Ф, а через Dy(F(n)) — функцию Шеннона по глубине для множества F.

Во введении приводится обзор известных результатов, связанных с темой диссертации, и формулируются основные полученные в диссертации результаты.

В главе 1 приводятся основные определения и обозначения, использующиеся в работе, а также вспомогательные утверждения. В частности, доказывается ряд свойств функций из находятся конечные поро-

29См.: Lau D. Function Algebras on Finite Sets. Springer-Verlag, Berlin, 2006.

ждающие системы некоторых замкнутых классов функций, приводятся известные простейшие методы синтеза.

В главе 2 изучаются конечные системы псевдолинейных функций и замкнутые классы, порожденные этими системами. Строятся конечные порождающие системы Dr, 21 и <£ классов £2,г, £2, -^2,0 П £ и Z2,1 П £ соответственно, 1 < г < оо. Для функций из этих классов доказываются верхние и нижние оценки сложности.

Для каждой псевдолинейной функции / строится каноническое представление. На основе этого представления определяются специальные множества функций Hf, Jf, Kf и Yj. Кроме того, для каждой функции / из класса £2 вводятся величины A(f) и B(f). Доказываются следующие теоремы о сложности функций из рассматриваемых классов.

Теорема 1. Пусть f(xi,...,xn), д(хi, ...,£„) и h{xi,...,x„) — произвольные функции из классов £2,г, П £ и 1 П £ соответственно, существенно зависящие от п переменных, тг^2,1^г<оо. Тогда имеют место равенства

LVr(f) = \Jf\ + \Hf\+r\Kf\,

Ыа) = Ш + \Н9\, Lz(h) = |Л| + \Нк\.

В этой главе также находятся точные оценки для соответствующих функций Шеннона.

Теорема 2. Пусть Q = Z2,о П С, U = д П £, г ^ 1. Тогда имеют место равенства

ЬЭг(£2») = 1 + п + т{С1п + С1 + ... + СЦ 1; (1)

£a(Q(n)) = Ie(ü(n)) = n + l, 2; (2)

ЫС2{п)) = п2п'1 + 2n+1 - 1, 2. (3)

Равенства (1) и (2) извлекаются непосредственно из теоремы 1. Опишем кратко схему доказательства равенства (3). Нижняя оценка в (3) доказывается следующим образом. Сначала изучаются свойства минимальных формул над системой Каждой минимальной формуле ставится в соответствие некоторое дерево. При этом все висячие вершины этого дерева разбиваются на два типа. Затем для каждого п ^ 2 определяется

функция тп(х 1,..., хп), каноническое представление которой имеет специальный вид. Для минимальной формулы Ф, реализующей функцию тп, рассматривается дерево Т, соответствующее формуле Ф. В дереве Т оценивается по-отдельности число висячих вершин каждого типа. В результате получается нижняя оценка для величины Ье.(тп), а, следовательно, и для величины Ь^С^п)).

Для получения верхней оценки в (3) сначала для любой функции / £ существенно зависящей от п > 2 переменных, доказываются

неравенства

\У}\ < п2п~1 + 2П, £(/) < 2" - 1. Затем доказывается неравенство

Из этих соотношений следует верхняя оценка для функции Ьц^С^п)).

В этой главе также для каждой функции / из множества Сч (п), существенно зависящей от п > 2 переменных, доказывается равенство £с(Л = \У/\ + Ж/)- Отсюда, с учетом неравенства Л(/) < #(/), в частности, следуют неравенства

^/КМ/КМ + ВД,

из которых для широкого класса последовательностей функций можно получить верхние оценки сложности, близкие к соответствующим нижним оценкам.

Кроме того, в главе 2 для максимального класса С = рг~1Ь и некоторой конечной порождающей системы 05 этого класса приведено асимптотически точное равенство для функции Ь^{С{п)) (доказательство которого следует из результатов главы 3).

Теорема 3. Имеетп место соотношение

Ьъ(£(п)) 3"

log2n

В главе 3 рассматривается задача о сложности реализации функций из конечно-порожденных максимальных замкнутых классов. Сначала с помощью градиентного алгоритма30 строится специальное разби-

30См.: Васильев Ю. Л., Глаголев В. В. Метрические свойства дизъюнктивных нормальных форм // Дискретная математика и математические вопросы кибернетики. T. 1. / Под ред. C.B. Яблонского и О. Б. Лупанова. М.; Наука, 1974. С. 99-148.

сние множества г > 3, на подмножества Щ, •••, 0~т(г)- При этом каждое множество {/¿, i = 1, ...,Т(г), обладает следующими свойствами:

1) 17, является подмножеством некоторого шара радиуса 1;

2) найдется I = 1(1), 1 ^ I ^ г, такое, что 1-я компонента в каждом наборе из Щ равна 2.

Затем оценивается мощность данного разбиения. Далее на основе этого разбиения строится представление функций из максимальных классов, аналогичное (третьему) представлению булевых функций из работы О. Б. Лупанова31. После этого на основе полученного представления вычисляются верхние оценки сложности реализации функций. Наконец, приводятся доказательства мощностных нижних оценок32 для соответствующих функций Шеннона.

В этой главе для каждого замкнутого класса булевых функций Б, такого, что {7о1 Я: В, определяется некоторая конечная система б = 6(5), которая порождает класс рг~1В. Доказывается следующая теорема.

Теорема 4. Пусть В — произвольный замкнутый класс булевых функций, такой, что С/01 ^ В. Тогда выполняются соотношения

3" <1с(рг-1В(п))<Т7^г + ЬртС(5(гг)).

Из этой теоремы следует, что задача о поведении функции Шеннона Ьс(рг~1В(п)) в некоторых случаях сводится к задаче о сложности реализации булевых функций в неполных базисах (то есть к задаче о поведении функции Ьрго(В(п))). В частности, из теоремы 4 и известных ранее оценок сложности булевых функций извлекаются асимптотически точные формулы для функций Шеннона, соответствующих некоторым максимальным классам.

Теорема 5. Пусть В — замкнутый класс булевых функций, такой, что выполняется по крайней мере одно из следующих условий:

1) Ь01 С В;

2) М01 С В-

3)Ве {0°°, 0§°, МОх, МОМ/°°,

4) В Е {Ап, Аь £>1, А #01, Ко, Ки К, С/, Би, иш,Ми, Щ, Щ}.

31 Лупанов О Б. О синтезе некоторых классов управляющих систем // Проблемы кибернетики. Вып. 10. М.: Наука, 1963. С. 63-97.

32Сы.: Лупанов О. Б. Асимптотические оценки сложности управляющих систем. М.: Изд-во Моск. ун-та, 1984.

Тогда выполняется соотношение

LG(pr^B(n)) 3

log2n

Отметим, что из теоремы 5 непосредственно следует утверждение теоремы 3.

В главе 4 рассматривается семейство замкнутых классов функций из Рзд, проекция которых принадлежит определенному выше множеству JVj замкнутых классов булевых функций. В диссертации для каждого класса В & Ni, для каждого класса Н из множества и для произвольной конечной системы G, порождающей класс Я, получено описание (с точностью до порядка) поведения функции Д<?(Я(п)).

Теорема 6. Пусть В — произвольный замкнутый класс булевых функций из множества Ni, Я — произвольный замкнутый класс функций из Рз,2, такой, что ргН = В, a G — произвольная конечная порождающая система класса Н. Тогда выполняется соотношение

Da(H(n)) * п.

При доказательстве этой теоремы используются методы синтеза формул над неполными системами, реализующих функции алгебры логики33.

Благодарности

Автор выражает глубокую благодарность своему научному руководителю, доктору физико-математических наук, профессору А. Б. Уголь-никову за постановку задачи и постоянное внимание к работе. Автор благодарит доктора физико-математических наук, профессора Р. М. Колпа-кова и кандидата физико-математических наук О. С. Дудакову за ценные замечания, способствовавшие улучшению текста диссертации. Автор признателен коллективу кафедры дискретной математики механико-математического факультета МГУ имени М. В. Ломоносова за помощь и поддержку.

33См.: Угольников А. Б. О глубине формул в неполных базисах // Математические вопросы кибернетики. 1988. Вып. 1. С. 242-245.

Угольников А. Б. Глубина формул в некоторых классах ^-значной логики // Вестник Московского университета. Сер. 1, Математика. Механика. М.: Изд-во МГУ, 1991. №4. С. 44-47.

Публикации автора по теме диссертации

1. Дагаев Д. А. О сложности псевдолинейных функций /'/' Вестник Московского университета. Серия 1. Математика. Механика. 2010. №2. С. 53-56.

2. Дагаев Д. А. О глубине формул, реализующих функции из некоторых классов трехзначной логики // Материалы IX Межд. семинара «Дискретная математика и ее приложения» (Москва, 18-23 июня 2007 г.). М.: Издательство механико-математического факультета МГУ, 2007. С. 84-87.

3. Дагаев Д. А. Глубина и сложность реализации формулами функций из некоторых классов трехзначной логики // Тезисы докладов XV Межд. конференции «Проблемы теоретической кибернетики» (Казань, 2-7 июня 2008 г.) Казань: Отечество, 2008. С. 24.

4. Дагаев Д. А. О сложности функций из некоторых классов Рз^ // Труды VIII Межд. конференции «Дискретные модели в теории управляющих систем» (Москва, 6-9 апреля 2009 г.). М.: Макс-Пресс, 2009. С. 76-78.

5. Дагаев Д. А. Оценки сложности псевдолинейных функций // Материалы VII молодежной научной школы по дискретной математике и ее приложениям (Москва, 18-23 мая 2009 г.). Часть 1. С. 28-30.

6. Дагаев Д. А. Об одном классе псевдолинейных функций // Материалы XVIII Межд. школы-семинара «Синтез и сложность управляющих систем» имени академика О.Б. Лупанова (Пенза, 28 сентября - 3 октября 2009 г.). М.: Изд-во механико-математического факультета МГУ, 2009. С. 31-33.

7. Дагаев Д. А. О сложности реализации псевдолинейных функций специального вида // Материалы X Межд. семинара «Дискретная математика и ее приложения» (Москва, 1-6 февраля 2010 г.). М.: Издательство механико-математического факультета МГУ, 2010. С.105-108.

Отпечатано в отделе оперативной печати Геологического ф-та МГУ Тираж/Р^ экз. Заказ № Щ

Введение

1 Определения и вспомогательные утверждения

1.1 Определения и обозначения

1.2 Связь между двумя мерами сложности формул.

1.3 Некоторые оценки сложности булевых функций.

1.4 Некоторые свойства функций из Рз,2.

1.5 Простейшие методы синтеза.

1.6 Порождающие системы максимальных классов.

2 Сложность псевдолинейных функций

2.1 Псевдолинейные функции и их свойства.

2.2 Классы г2Л П С, £2)Г и С.

2.3 Класс С2 .'.

2.3.1 Свойства минимальных формул.

2.3.2 Нижняя оценка для функции Шеннона.

2.3.3 Верхняя оценка для функции Шеннона.

2.3.4 Верхняя оценка сложности произвольной функции.

2.3.5 Нижняя оценка сложности произвольной функции.

3 Сложность функций из максимальных классов

3.1 Представление функций из максимальных классов.

3.1.1 Специальное разбиение множества Ё

3.1.2 Верхняя оценка мощности разбиения.

3.1.3 Представление функций из множества Н.п.

3.2 Верхние оценки для функций Шеннона.

3.3 Нижние оценки для функций Шеннона.

3.4 Асимптотически точные формулы для функций Шеннона.

4 Глубина формул, реализующих функции из Р

4.1 Классы, проекция которых содержит функцию 8Р или 5*

4.2 Классы, проекция которых совпадает с 5 или ^01.

4.3 Классы, проекция которых совпадает с классом ЯМ.

Данная диссертация относится к теории синтеза и сложности управляющих систем — одному из основных разделов дискретной математики и математической кибернетики. В ней рассматривается задача о сложности реализации функций многозначной логики формулами над конечными системами.

Задача синтеза и сложности управляющих систем [69, 30, 34, 103] в общем случае формулируется следующим образом. Дан набор G базисных элементов некоторого типа (например, функциональные элементы или формулы), каждому из которых приписано некоторое положительное число — вес элемента. С помощью этих элементов по заданным правилам строятся более сложные объекты — схемы. Каждой схеме S ставится в соответствие некоторая функция / и число L(S), равное сумме весов всех входящих в нее элементов; при этом говорят, что функция / реализуется схемой S со сложностью L(S). Сложностью функции / называется величина Laif) = minI/(«S), где минимум берется по всем схемам S над G, реализующим функцию /. Для каждой функции / требуется найти минимальную схему <S над G, реализующую / (то есть такую^ схему S, реализующую /, сложность которой удовлетворяет равенству L(S) = Lg{J)). При изучении функций из заданного конечного множества II рассматривается величина Lg(H) = maxLa(f), где максимум берется по всем функциям / из Н. Функция La(H) называется функцией Шеннона. Она характеризует сложность реализации в рассматриваемом классе управляющих систем самых сложных функций из множества II. Эта функция была введена К. Шенноном в работе [104], и там же были получены первые значительные результаты о ее поведении.

Формулы и схемы из функциональных элементов (называемые далее схемами), реализующие дискретные функции, являются одними из основных модельных классов управляющих систем. Множество Р^ всех функций /с-значной логики, к ^ 2, является важным примером класса дискретных функций, представляющим большой интерес как с теоретической, так и с прикладной точек зрения. Одной из наиболее изученных классификаций функций /с-значной логики являются классы функций, замкнутые относительно операции суперпозиции (см., например, [68, 71, 8, 35]). В связи с этим возникает задача о реализации функций fc-значной логики из замкнутых классов формулами (или схемами) над конечными системами. В этой задаче можно выделить два направления исследований: синтез схем и формул в полных базисах и синтез схем и формул в неполных базисах.

Приведем сначала некоторые результаты, полученные в этих направлениях для функций алгебры логики. В задаче о сложности реализации булевых функций основополагающие результаты были получены О. Б. Лупановым, предложившим асимптотически оптимальные методы синтеза для ряда классов управляющих систем [25-34].

В частности, для произвольного полного конечного базиса С булевых функций он показал [26, 27] справедливость следующих соотношений1: где (Р2(п)) и Ь®(Р2(п)) — функции Шеннона при реализации функций схемами и формулами соответственно, а р — константа2, однозначно определяемая по базису С. Оценки высокой степени точности для функций Шеннона при реализации булевых функций формулами и схемами в полных базисах получены в работах С. А. Ложкина

Задача о поведении функций Шеннона для множества всех булевых функций тесно связана с задачей о поведении функций Шеннона, соответствующих замкнутым классам булевых функций при реализации функций схемами и формулами в полных конечных базисах. Полное описание множества всех замкнутых классов булевых функций получено Э.Л. Постом [98, 99] (см. также [85, 72, 59, 102, 91, 38, 39, 92, 65]). Он показал, что это множество счетно, причем каждый замкнутый класс имеет конечный базис. В ряде работ [67, 70, 50, 48, 40,14,15, 82] изучалась задача о сложности реализации монотонных булевых функций (множество всех таких функций обозначается через М). Асимптотически точные формулы для функций Шеннона при реализации функций из класса М схемами в произвольных полных конечных базисах приведены в работах [52] и [97] (эти формулы получены на основе методов кодирования монотонных функций из работ [83] и [84] соответственно). При реализации функций схемами для каждого замкнутого класса булевых функций, не содержащегося в множестве3 Ь и К и О, и любого полного конечного базиса А. Б. Угольниковым [55, 60] получена асимптотически точная формула для соответствующей функции Шеннона. При реализации функций формулами для всех замкнутых классов булевых функций, не содержащихся в множестве4 5 и I/ и К и £), и для любого конечного полного базиса асимптотически точные формулы для соответствующих функций Шеннона получены А. Е. Андреевым [1, 2, 4].

Следует отметить, что упомянутые выше методы синтеза схем и формул существенным образом используют полноту базисов. Поэтому задача о синтезе схем и формул в неполных базисах требует разработки других методов синтеза. Отметим некоторые результаты, полученные в задаче о сложности реализации булевых функций из замкнутых классов схемами и формулами в неполных базисах. При реализации функций схемами для замкнутых классов функций, сохраняющих константы, и любых конечных систем, порождающих эти классы, асимптотически точные формулы для соответствующих функций Шеннона были получены Э.И. Нечиноруком [41, 42].

13десь и далее всякий раз, когда речь идет об асимптотических оценках, подразумевается, чго эти оценки имеют место при п оо.

Константа р называется минимальным приведенным весом элементов базиса.

3Через Ь,К и Б обозначаются множества всех линейных функций, конъюнкций и дизъюнкций соответственно.

4Через $ обозначается множество всех самодвойственных функций. п

19, 20, 22, 23].

Для ряда замкнутых классов функций алгебры логики аналогичные утверждения доказаны в работах [53, 54, 56, 3]. При реализации функций формулами для некоторых замкнутых классов («близких» к множеству Рг) и любых конечных систем, порождающих эти классы, асимптотически точные формулы для соответствующих функций Шеннона получены в работах [53, 54]. В работах [57, 58, 105] показано, что для любого замкнутого класса В и любой конечной системы, порождающей класс В, сложность реализации формулами каждой функции из В имеет не более чем экспоненциальный порядок роста от числа переменных (см. также [37]). Верхние оценки сложности реализации функций из некоторых замкнутых классов схемами и формулами в неполных базисах приведены в работах [43, 49, 2, 47, 56, 63].

Таким образом, в задаче о сложности реализации булевых функций схемами и формулами в конечных базисах с положительными весами всех входящих в них элементов получен ряд существенных результатов. Получение аналогичных результатов для функций многозначной логики наталкивается на значительные трудности. Это связано с принципиальными отличиями многозначных логик от двухзначной. Одним из основных отличий является континуальность множества всех замкнутых классов функций Ахзначной логики при к ^ 3 (см. [74]). В связи с этим важным направлением исследований является изучение свойств отдельных семейств замкнутых классов. Среди таких семейств одно из центральных мест занимает семейство всех нредполных классов5, изучению свойств которого посвящено значительное число публикаций (см., например, [66, 17, 18, 68, 36, 93, 94, 95, 96, 10, 11, 5]). Полное описание множества всех предполных классов при всех к > 3 получено И. Розенбергом [100, 101] (см. также [16, 73, 6, 92]). К числу наиболее изученных семейств замкнутых классов функций к -значной логики относится также семейство всех замкнутых классов функций из Рщ — множества всех функций А:-значной логики, принимающих значения только из множества {0,1,., I — 1}, А; > I ^ 2. Некоторые свойства этих классов изучены в работах Г. Буроша [75, 76] и других авторов [86, 87, 77, 88, 78, 92]. Свойства замкнутых классов функций из множества Рк<2, к ^ 3, изучались в работах [77, 88, 81, 78, 89, 92]. В работах Д. Лау [90, 92] и Н. Грюнвальда [79-81] изучены некоторые свойства замкнутых классов функций из множества Р^2- В этих работах рассматривается отображение (называемое проекцией) функций из множества Р^о в множество Р2. На основе этого отображения для каждого множества Р С Р3 2 определяется множество ргР = ирг/, где prf — проекция функции /, а объединение берется по всем функциям / € Р. В результате каждому замкнутому классу В булевых функций сопоставляется семейство 9?(7?) всех замкнутых классов Р функций из Р^, таких, что ргР = В. Для каждого замкнутого класса В булевых функций найдена мощность множества У1(В) и приведено описание этого множества'для тех случаев, когда мощность 91(Я) конечна или счетна.

Отметим некоторые результаты, полученные в задаче о сложности реализации функций многозначной логики. В. А. Орлов [44, 45] ввел понятие оптимального полного базиса6 функций Аьзначной логики, к ^ 3. и для каждого такого базиса предложил

53амкнутый класс Р С Рк называется предполным в Рк, к > 2, если Р / Рк и для любой функции / € Рь \ Р множество Р и {/} порождает Рк.

6Конечный полный в Рк базис является оптимальным, если асимптотическое поведение соответствующей функции Шеннона определяется минимальным приведенным весом элементов базиса. асимптотически наилучший метод синтеза схем из функциональных элементов. Он показал также [44-46], что почти любой конечный полный в Рк базис является оптимальным, причем доля базисов, не являющихся оптимальными, убывает трижды экспоненциально с ростом максимального числа входов элементов базиса и более чем 1 дважды экспоненциально с ростом к. При реализации функций схемами для любого полного конечного базиса асимптотически точная оценка соответствующей функции Шеннона анонсирована в работе ¡24]. При реализации функций формулами для некоторых полных в Рк (к ^ 3) базисов асимптотически точные формулы для соответствующих функций Шеннона получены в работах Е. Ю. Захаровой [12], С. Б. Гашкова [9] и других авторов (см. [13, 21, 46]). Примеры последовательностей функций из и Р5, сложность которых в классе формул над некоторой конечной неполной системой имеет сверхэкспоненциальный порядок роста от числа переменных, приведены в работах [64, 61, 57, 105]. Первые экспоненциальные нижние оценки для сложности реализации функций &-значной логики (к ^ 3) схемами из функциональных элементов в неполных базисах получены Г. А. Ткачевым [51].

В настоящей работе рассматривается задача о сложности реализации функций из (множества всех функций трехзначной логики, принимающих значения из множества {0,1}) формулами над конечными системами. Для ряда конечных систем получены верхние и нижние оценки сложности реализации функций из замкнутых классов, порожденных этими системами.

Дадим необходимые определения7.

Пусть Ек = {0,1,.,к - 1}, к ^ 2. Обозначим через множество всех наборов • 5 = (а>1, .,ап), таких, что аг, .,ап € Ек, п ^ 1. Множество всех функций /с-значной логики обозначим через Р^, а множество всех функций из Рк, принимающих значения только из множества Е2, — через Р^

В данной диссертации будем придерживаться обозначений для замкнутых классов булевых функций из работ [65, 59], а именно: £ — множество всех самодвойственных функций; Тг — множество всех функций, сохраняющих константу г, г = 0,1; М — множество всех монотонных функций; Ь — множество всех линейных функций; От — множество всех функций, удовлетворяющих условию < 0171 >, т = 2,3, .,оо; 1т — множество всех функций, удовлетворяющих условию < 1т >, т = 2,3, .,оо; К — множество всех конъюнкций; И — множество всех дизъюнкций; II — множество всех функций, существенно зависящих не более чем от одной переменной; С — множество всех функций, не имеющих существенных переменных.

Положим и = Ь П Тг, М; = м п Ти Кг = К П Тг, А = О П Ти иг = и Г) Тг, Сг = С Г) Ти г = 0,1;

7о1 ^ТъПТ^Мт = М0Г)Мг,Ь01 = Ь0ПЬиК0^ = К0ПКи Дп = ДЛ£>ъ£/01 = ^оГШь 501 = 5 П Тог, ЭМ = 5 П М, БЬ = 5 П Ь, 5С/ = 5 П и, Ми = М П £/;

О™ = Т0 Л От, 1[п = Тг Г) 1т, то = 2,., оо; МОт = М П От, МГ = М п 1т, МО£ = м П О'0п, МГ[п = М П /Г, т = 2,., оо.

7См. также главу 1.

Определим семейства Л^, N2,-/Vз замкнутых классов булевых функций следующим образом. Положим

N1 = {Р2, Т0,ТиТ01, М, М0, Ми Мои 5оь От, МОт, 1т, М1т, М1?, 2^т< оо}, = ¿о, ¿1, £,01}, Л/з = {0°°, МО00, М1°°, 02°,/Г, К, Ко, Къ Кох, А Д,, Г>1, Йог, и, 110, £/х, ¿/оь МЕ7, 5С/, С, С0, С,}.

Из результатов Э. Л. Поста следует, что /V] и АТ2 и А'.ч — это множество всех замкнутых классов булевых функций.

Пусть /(х\,.,хп) е Рз,2- Проекцией функции /(ж15.,жп) называется такая булева функция (рг/)(.т 1,.,.г„), значение которой на произвольном наборе а Е2 определяется равенством (рг/)(с?) — /(а). Таким образом, каждой функции / е /3,2 поставлена в соответствие функция рг/ е Р2. В дальнейшем для упрощения записи функцию (рг/)(х1, .,хп) будем обозначать через рг/(хх,., хп). Проекцией ргР множества функций Р С Р3 2 называется множество У {рг/}, где объединение берется по всем функциям / 6 Р.

Для каждого замкнутого класса булевых функций В определим множество функций рг~1в = {/ е Рз,21 рг/ е в}.

Легко видеть, что множество рг~хВ является замкнутым классом функций из /3,2-Замкнутый класс рг~1В называется максимальным классом (соответствующим классу В С Р2). Таким образом, каждому замкнутому классу В булевых функций соответствует максимальный класс рг~1В С Р32. Очевидно, что класс рг~1В содержит каждый замкнутый класс Н из Рл>2, такой, что ргН = В. Для каждого замкнутого класса булевых функций В определим множество замкнутых классов

ЩВ) = {А с Р3,2 | А = [А], ргА = В}.

Показано (см. [92]), что максимальный класс рг~хВ имеет конечную порождающую систему в тех и только тех случаях, когда В £ {С,Со,С\}. Показано также, что если В е N1, то семейство УХ(В) конечно, если В € N2, то 91(Б) счетно, если В е N3, то 91(5) имеет мощность континуума.

Функция / из Рз,2 называется псевдолинейной, если рг/ Е Ь. Описание множества всех замкнутых классов псевдолинейных функций см., например, в книге [92]. Будем обозначать замкнутые классы, проекция которых совпадает с множеством Ь всех линейных булевых функций, через £, С2, %2,оП£, Я2дП£, £2,г, где г = 1,2,., оо. Известно, что все перечисленные классы, за исключением класса £2,00, являются конечно-порожденными (см. [92]).

Пусть Ф — конечная система функций из Рк, к ^ 2, [Ф] — замыкание системы Ф относительно операций суперпозиции и введения несущественной переменной. Пусть /(ж1; .,хп) е [Ф], Ф — формула над Ф, реализующая функцию /, а^С [Ф]. Через

1/(Ф) обозначим число символов переменных, входящих в формулу Ф (сложность формулы Ф), через £ф(/) — сложность реализации функции / 6 Р над системой Ф, а через — функцию Шеннона по сложности для множества Р. Через -О(Ф) будем обозначать глубину формулы Ф, через £>ф(/) — глубину реализации функции / € Р над системой Ф, а через — функцию Шеннона по глубине для множества Р.

Диссертация состоит из введения, четырех глав и списка литературы. В диссертации используется следующая нумерация теорем и лемм. Теоремы нумеруются тройкой чисел, в которой первое число обозначает номер главы, второе число — номер параграфа внутри главы, третье число — номер теоремы внутри параграфа. Аналогичным образом нумеруется леммы. Во введении принята отдельная нумерация теорем, при этом в скобках указываются номера соответствующих теорем внутри основного текста диссертации.

1. Андреев А.Е. Метод бесповторной редукции синтеза самокорректирующихся схем // Доклады АН СССР. Т. 283, № 2. 1985. С. 265-269.

2. Андреев А. Е. О сложности монотонных функций // Вестник Московского университета. Сер. 1, Математика. Механика. М.: Изд-во МГУ, 1985. №4. С. 83-87.

3. Андреев А. Е. О синтезе схем из функциональных элементов в полных монотонных базисах // Математические вопросы кибернетики, 1988. №1. С. 114-139.

4. Андреев А. Е. О синтезе функциональных сетей. Докт. диссертация. М.: МГУ им. М. В. Ломоносова, 1985.

5. Байрамов P.A. Об одной серии предполных классов в ¿-значной логике // Кибернетика. 1967. Т. 1. С. 7-9.

6. Буевич В. А. Вариант доказательства критерия полноты для функций /с-значной логики // Дискретная математика. Т. 8, вып. 4. М.: Наука, 1996. С. 11-36.

7. Васильев Ю. Л., Глаголев В. В. Метрические свойства дизъюнктивных нормальных форм. В кн. Дискретная математика и математические вопросы кибернетики. Т. 1. Раздел 3. М.: Наука, 1974.

8. Гаврилов Г. П., Сапоженко A.A. Задачи и упражнения по дискретной математике. М.: Физматлит, 2004.

9. Гашков С. Б. О параллельном вычислении некоторых классов многочленов с растущим числом переменных // Вестник Московского университета. Сер. 1, Математика. Механика. М.: Изд-во МГУ, 1990. №2. С. 88-92.

10. Захарова Е. Ю. Об одном достаточном условии полноты и Рк /'/' Проблемы кибернетики. 1966. Вып. 16. С. 239-244.

11. Захарова Е. Ю. Критерий полноты системы функций из Рк // Проблемы кибернетики. 1967. Вып. 18. С. 5-10.

12. Захарова Е. Ю. Реализация функций из ¡\ формулами // Матем. заметки. 1972. Т.11, №1. С. 99-108.

13. Захарова Е. Ю., Яблонский С. В. Некоторые свойства невырожденных суперпозиций в Pk // Матем. заметки. 1972. Т. 12, №1. С. 3-12.

14. Коробков В. К. Оценка числа монотонных функций алгебры логики и сложности алгоритма отыскания разрешающего множества для произвольной монотонной функции алгебры логики // Докл. АН СССР. 1963. Т. 150, №4.

15. Коробков В. К. О монотонных функциях алгебры логики // Проблемы кибернетики. 1965. Вып. 13. С. 5-28.

16. Кудрявцев В, Б. Функциональные системы. М.: Изд-во Моск. ун-та, 1982.

17. Кузнецов A.B. О проблемах тождества и функциональной полноты для алгебраических систем // Труды 3-го Всесоюзного матем. съезда. М.: Изд-во АН СССР, 1956. Т. 2. С. 145-146.

18. Кузнецов A.B. Алгебра логики и ее обобщения // Математика в СССР за 40 лет (1917-1957). 1959. Т. 1. С. 102-115.

19. Лоэюкин С. А. Новые, более точные оценки функций Шеннона для сложности управляющих систем // Дискретный анализ и исследование операций. 1995. Т. 2, №3. С. 77-78.

20. Ложкин С. А. О синтезе некоторых типов схем на основе сдвиговых разбиений, порожденных универсальными матрицами // Вестник Московского университета. Сер. 15. Вычислительная математика и кибернетика. М.: Изд-во МГУ, 1996. №1. С. 62-69.

21. Ложкин С. А. О сложности реализации функций /означной логики формулами и квазиформулами // Материалы XI Международной конференции «Проблемы теоретической кибернетики» (г. Ульяновск, 10-14 июня 1996 г.). М.: РГГУ, 1996. С. 125-127.

22. Лоэюкин С. А. Оценки высокой степени точности для сложности управляющих систем из некоторых классов // Математические вопросы кибернетики. Вып. 6. М.: Наука, 1996. С. 190-214.

23. Ложкин С. А. Асимптотические оценки высокой степени точности для сложности управляющих систем. Докт. диссертация. М.: МГУ им. М. В. Ломоносова, 1997.

24. Лупанов О. Б. О синтезе контактных схем // ДАН СССР. 1958. Т. 119. № 1. С. 2326.

25. Лупанов О. Б. Об одном методе синтеза схем // Известия вузов, Радиофизика I. 1958. С. 120-140.

26. Лупанов О. Б. О сложности реализации функций алгебры логики формулами // Проблемы кибернетики. 1960. Вып. 3. С. 61-80.

27. Лупанов О. Б. Об одном классе схем из функциональных элементов // Проблемы кибернетики. 1961. Вып. 7. С. 60-114.

28. Лупанов О. Б. О принципе локального кодирования и реализации функций из некоторых классов схемами из функциональных элементов // ДАН СССР. 1961. Т. 140. №2. С. 322-325.

29. Лупанов О. Б. О синтезе некоторых классов управляющих систем // Проблемы кибернетики. 1963. Вып. 10. С. 63-97.

30. Лупанов О. Б. О сложности реализации функций алгебры логики релейно-контактными схемами // Проблемы кибернетики. 1964. Вып. 11. С. 25-48.

31. Лупанов О. Б. Об одном подходе к синтезу управляющих систем-принципе локального кодирования // Проблемы кибернетики. 1965. Выи. 14. С. 31-110.

32. Лупанов О. Б. О синтезе схем из пороговых элементов / / Проблемы кибернетики. 1973. Вып. 26. С. 109-140.

33. Лупанов О. Б. Асимптотические оценки сложности управляющих систем. М.: Изд-во Моск. ун-та, 1984.

34. Конспект лекций О. Б. Лупанова по курсу «Введение в математическую логику» / Отв. ред. A.B. Угольников. М.: Изд-во ЦПИ при мех.-матем. ф-те МГУ им. М. В. Ломоносова, 2007.

35. Мартынюк В. В. Исследование некоторых классов в многозначных логиках // Проблемы кибернетики. 1960. Вып. 3. С. 49-60.

36. Марченков С. С. О равномерном ¿¿-разложении булевых функций // Дискретная математика. 1990. Т. 2, вып. 3. С. 29-41.

37. Марченков С. С., Угольников А. Б. Замкнутые классы булевых функций. М., Инст. Прикл. Матем. им. М. В. Келдыша, 1990.

38. Марченков С. С. Замкнутые классы булевых функций. М.: Физматлит, 2000.

39. Нечипорук Э. И. О вентильных схемах // Международный симпозиум по теории релейных устройств и конечных автоматов. Тез. док. М., 1962. С. 42-43.

40. Нечипорук Э. И. О синтезе логических сетей в неполных и вырожденных базисах // Докл. АН СССР. 1964. Т. 155. №2. С. 299-301.

41. Нечипорук Э. И. О синтезе логических сетей в неполных и вырожденных базисах // Проблемы киберенетики. Вып. 14. М.: Наука, 1965. С. 111-160.

42. Нечипорук Э. И. О реализации дизъюнкции и конъюнкции в некоторых монотонных базисах // Проблемы киберенетики. Вып. 23. М.: Наука, 1970. С. 291-293.

43. Орлов В. А. Реализация функций из Рк схемами в произвольном базисе из функциональных элементов // Докл. РАН. 1998. Т. 359, №3. С. 308-309.

44. Орлов В. А. Об оптимальности почти всех базисов из Рк // Докл. РАН. 1998. Т. 363, №5. С. 602-603.

45. Орлов В. А. Об особенностях асимптотического поведения сложности реализации /с-значных и автоматных функций схемами в произвольном конечном базисе. Докт. диссертация. М.: РГГУ, 1999.

46. Редъкин Н. П. О реализации монотонных функций контактными схемами // Проблемы кибернетики. Вып. 35. М.: Наука, 1979. С. 87-110.

47. Резник В. И. О реализации монотонных функций схемами из функциональных элементов // Докл. АН СССР, 1979. Т. 139, №3. С. 566-569.

48. Рохлина М. М. О схемах, повышающих надежность // Проблемы кибернетики. М.: Наука, 1970. Вып. 23. С. 295-301.

49. Субоч Н. Н. Реализация монотонных функций алгебры логики контактными 7Г-схемами // Проблемы кибернетики. М.: Наука, 1966. Вып. 17. С. 247-254.

50. Ткачев Г. А. О сложности реализации одной последовательности функций к-значной логики // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и кибернетика. 1977. №1. С. 45-57.

51. Угольников А. Б. О реализации монотонных функций схемами из функциональных элементов // Проблемы кибернетики. М.: Наука, 1976. Вып. 31. С. 167-185.

52. Угольников А. Б. Синтез схем и формул в неполных базисах. ДАН СССР, 1979. Т. 249, №1. С. 60-62.

53. Угольников А. Б. Синтез схем и формул в неполных базисах. Препринт ИПМ АН СССР. М. 1980. №112.

54. Угольников А. Б. О реализации функций из замкнутых классов схемами из функциональных элементов в полном базисе // Доклады АН СССР. 1983. Т. 271. №1. С. 49-51.

55. Угольников А. Б. О реализации булевых функций из некоторых замкнутых классов схемами из функциональных элементов в неполных базисах // Вестник Московского университета. Сер. 1, Математика. Механика. М.: Изд-во МГУ, 1985. № 3. С. 87-89.

56. Угольников А. Б. О глубине и сложности формул, реализующих функции из замкнутых классов // Доклады АН СССР. 1988. Т. 298. №6. С. 1341-1344.

57. Угольников А. Б. О глубине формул в неполных базисах // Математические вопросы кибернетики. 1988. Вып. 1. С. 242-245.

58. Угольников А. Б. О замкнутых классах Поста // Изв. вузов. Сер. Матем. 1988. №7. С. 79-88.

59. Угольников А. Б. О реализации функций из замкнутых классов схемами из функциональных элементов // Математические вопросы кибернетики. М.: Наука, 1988. Вып. 1. С. 89-113.

60. Угольников А. Б. О сложности реализации формулами одной последовательности функций многозначной логики // Математические вопросы кибернетики. М.: Наука, 1989. №2. С. 174-176.

61. Угольников А. Б. Глубина формул в некоторых классах fc-значной логики // Вестник Московского университета. Сер. 1, Математика. Механика. М.: Изд-во МГУ, 1991. №4. С. 44-47.

62. Угольников А. Б. О сложности схем в неполных базисах // Вестник Московского университета. Сер. 1, Математика. Механика. М.: Изд-во МГУ, 1997. №2. С. 5861.

63. Угольников А. Б. О сложности реализации формулами одной последовательности функций 4-значной логики // Вестник Московского университета. Сер. 1, Математика. Механика. М.: Изд-во МГУ, 2004. №3. С. 52-55.

64. Угольников А. Б. Классы Поста. М.: Изд-во ЦПИ при механико-математическом факультете МГУ, 2008.

65. Яблонский С. В. О функциональной полноте в трехзначном исчислении // Доклады АН СССР. 1954. Т. 95, №,6. С. 1152-1156.

66. Яблонский С. В. О классах функций алгебры логики, допускающих простую схемную реализацию // УМН, т. 12, вып. 6. 1957. С. 189-196.

67. Яблонский С. В. Функциональные построения в /с-значной логике // Труды матем. ин-та АН СССР им. Стеклова. 1958. 51. С. 5-142.

68. Яблонский C.B. Основные понятия кибернетики // Проблемы кибернетики. 1959. Вып. 2. С. 7-38.

69. Яблонский С. В. Об алгоритмических трудностях синтеза минимальных контактных схем // Проблемы кибернетики. 1959. Вып. 2. С. 75-121.

70. Яблонский C.B. Введение в дискретную математику. М.: Высшая школа, 2008.

71. Яблонский С. В., Гаврилов Г. П., Кудрявцев В. Б. Функции алгебры логики и классы Поста. М.: Наука, 1966.

72. Яблонский С. В., Гаврилов Г. П., Набебин A.A. Предполные классы в многозначных логиках. М.: Изд-во МЭИ, 1997.

73. Янов Ю.И., Мучник A.A. О существовании /г-значных замкнутых классов, не имеющих конечного базиса // ДАН СССР. 1959. 127. №1. С. 44-46.

74. Burosch G. Uber die Ordnung der prëvollstândigen Klassen in Algebren von Prädikaten. Preprint, WPU Rostock. 1973.

75. Burosch G. Über Algebren von Prädikaten. Preprint Univ. Rostock. 1974.

76. BuroshG., Dassow ./., Harnau W., Lau D. Uber Algebren von Prädikaten. Preprint, WPU Rostock. 1979.

77. Burosh G., Dassow J., Harnau W., Lau D. On subalgebras of an algebra of predicates // J. Inf. Process Cybern. 1985. EIK 21, 1/2. P. 9-22.

78. Grünwald N. Bestimmung sämtlischer abgeschlossenen Mengen aus 2, deren Projektion F8n ist // Rostock. Math. Kolloq. 1983. 23. P.5-26.

79. Grünwald N. Beschreibung aller abgeschlossenen Mengen aus P3i2, deren Projektion Fg ist, mit Hilfe von Relationen // 1983. Rostock. Math. Kolloq'. 23. P. 27-34.

80. Grünwald N. Strukturaussagen über den Verband der abgeschlossenen Mengen von Pk,2, insbesondere von P3>2. Dissertation A, Universität Rostock, 1984.

81. Kleitman D., Markowsky G. On Dedekind's problem: the number of monotone Boolean functions, II // Trans. AMS. 1975. 213. P. 373-390.

82. Kuntzman J. Algèbra de Boole. Paris: Dunod. 1965.

83. Lau D. Prävollständige Klassen von Pk>г. // Elektron. Informationsverarb. Kybernet. EIK, 11. 1975. P. 10-12, 624-626.

84. Lau D. Kongruenzen auf gewissen Teilklassen von Pkti // Rostock. Math. Kolloq. 1977. 3. P. 37-43.

85. Lau D. Funktionenalgebren über endlichen Mengen. Dissertation B, Universität Rostock. 1984.

86. Lau D. Uber abgeschlossene Teilmengen von Pk2 // J. Inf. Process. Cybern. 1988. EIK 24, 10. P. 495-513.

87. Lau D. Über abgeschlossene Teilmengen von Pii2 // J. Inf. Process. Cybern. 1988. EIK 24, 11/12. P. 561-572.

88. Lau D. On closed subsets of Boolean functions (A new proof for Post's theorem) // J. Inform. Process Cybern. EIK 27, 3. 1991. P. 167-178.

89. Lau D. Function Algebras on Finite Sets. Springer-Verlag, Berlin, 2006.

90. Lo Czu Kai. Precompleteness of a set and rings of linear functions // Acta Sei. Natur. Univ. Jilinensis. 1963. 2.

91. Lo Czu Kai. On the precompleteness of the classes of functions preserving a partition // Acta Sei. Natur. Univ. Jilinensis. 1963. 2.

92. Lo Czu Kai, Lju Sjui Hua. Precomplete classes defined by binary relations in many-valued logics // Acta Sei. Natur. Univ. Jilinensis. 1963. 4.

93. Lo Czu Kai. Precomplete classes defined by normal /с-ary relations in /c-valued logics // Acta Sei. Natur. Univ. Jilinensis. 1964. 3.

94. Pippenger N.J. The complexity of monotone Boolean functions // Math. Systems Theory. 1978. Vol.11. P. 289-316.

95. Post E. L. Introduction to a general theory of elementary propositions // Ainer. J. Math. 1921. 43, №3. P. 163-185.

96. Post E. L. The two-valued iterative systems of mathematical logic // Annals of Math. Studies. 1941. №5. Princeton Univ. Press.

97. Rosenberg I. G. La structure des fonctions de plusieurs variables sur un ensemble fini. Comptes Rendus, de l'Academ. Paris. 260. 1965. P. 3817-3819.

98. Rosenberg I. G. Über die funktionale Vollständigkeit in den mehrwertigen Logiken // Rozpr. CSAV Rada Mat. Priv. Ved., Praha. 1970. 80. P. 3-93.

99. Reschke M., Denecke K. Ein neuer Beweis für die Ergebnisse von E. L. Post über abgeschlossene Klassen Boolescher Funktionen // J. Inform. Process Cybern. EIK 25, 7. 1989. P. 361-380.

100. Savage J. E. The complexity of computing. New York: Robert E. Kreiger Publishing Company, 1987 (русский перевод: Джон Э.Сэвидж. Сложность вычислений. М.: Факториал, 1998.).

101. Shannon С. Е. The synthesis of two-terminal switching circuits. Bell Syst. Techn. Journ. 1949. 28. №1. P. 59-98 (русский перевод: Шеннон К. Работы по теории информации и кибернетике. М.: ИЛ, 1963.).

102. Дагаев Д. А. Глубина и сложность реализации формулами функций из некоторых классов трехзначной логики // Тезисы докладов XV Международной конференции «Проблемы теоретической кибернетики» (Казань, 2-7 июня 2008 г.) Казань: Отечество, 2008. С. 24.