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

ФГБОУ ВО «Московский государственный университет имени М.В. Ломоносова»

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

Подолько Дмитрий Константинович

О КЛАССАХ ФУНКЦИЙ МНОГОЗНАЧНОЙ ЛОГИКИ, ЗАМКНУТЫХ ОТНОСИТЕЛЬНО УСИЛЕННОЙ ОПЕРАЦИИ СУПЕРПОЗИЦИИ

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

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

2 3 ЯНЗ

Москва — 2014

005558080

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

Научный руководитель: Кочергин Вадим Васильевич,

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

Официальные оппоненты: Глухов Михаил Михайлович,

доктор физико-математических наук, профессор (Академия криптографии РФ, академик-секретарь отделения); Дагаев Дмитрий Александрович, кандидат физико-математических наук, доцент (ФГАОУ ВПО "Национальный исследовательский университет "Высшая школа экономики", общеуниверситетская кафедра высшей математики).

Ведущая организация: ФГБУН Институт математики имени

СЛ. Соболева Сибирского отделения Российской академии наук.

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

С диссертацией можно ознакомиться в Фундаментальной библиотеке ФГБОУ ВО МГУ имени М.В. Ломоносова по адресу: Москва, Ломоносовский проспект, д.27, сектор А, и на сайте http://mech.math.msu.su/ Автореферат разослан 13 января 2015 года.

Ученый секретарь диссертационного совета Д.501.001.84, созданного на базе ФГБОУ ВО МГУ имени М.В. Ломоносова, доктор физико-математических наук, профессор

Иванов Александр Олегович

Общая характеристика работы

Актуальность темы

Диссертация относится к одному из основных направлений дискретной математики и математической кибернетики — теории функциональных систем1. Функциональная система представляет собой пару (21; ф), где 21 является некоторым множеством функций, а ф — некоторым отображением множества всех подмножеств системы 21 в себя. Функциональные системы, как правило, имеют содержательную связь с реальными кибернетическими моделями управляющих систем. К числу важнейших задач теории функциональных систем можно отнести задачи о полноте, о выразимости одних функций через другие, о структуре замкнутых классов, о тождественных преобразованиях и т.д. Результаты, получаемые при исследовании функциональных систем, позволяют разрабатывать новые подходы для решения других задач дискретной математики и математической кибернетики. Поэтому С. В. Яблонский утверждал2, что роль функциональных систем в дискретной математике можно сравнить с ролью математического анализа в непрерывной математике.

Одним из центральных направлений в теории функциональных систем является изучение систем уэ), где Рк — множество функций А'-значной логики, к > 2, а (р — некоторый оператор на множестве всех подмножеств Р^. В качестве операторов (р часто рассматриваются операторы, являющиеся операторами замыкания3, т.е. обладающие тремя свойствами: А С :р{А) (экстенсивность), ■-р(А) С (р(В) при А С. В (монотонность) и р(р(А)) = :р(А) (идемпотентность).

Основными типами задач, возникающих при исследовании функций к-значной логики являются задачи выразимости и полноты4. К первому из данных типов относятся задачи определения по множеству А и произвольной функции из Р^ принадлежности этой функции множеству !~р(Л). Задачи второго типа для заданных множеств ^ и А из Р/. направлены на исследование вопроса порождаемое™ множеством F всех функций из А, т.е. выполнения условия :-р{Р) = А. При этом важное место занимают задачи исследования классов на наличие конечных порождающих систем, а также задачи о существовании базиса, то есть порождающей системы, при удалении любой функции из которой эта система уже перестает быть порождающей. Также важным направлением при изучении

1 Яблонский С. В. Функциональные построения в ¿-значной логике // Труды матем. ин-та АН СССР им. Стсклова. 1958. Т. 51. С. 5-142. Кудрявцев В.Б. Функциональные системы. М.: Изд-во МГУ, 1982.

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

3См.: Кон П. Универсальная алгебра. — М.: Мир, 1968.

4См.: Угольников А. Б. О некоторых задачах в области многозначных логик. Мат-лы X Междупар. семинара "Дискретная математика и ее приложения" (Москва, МГУ, 1-6 февраля, 2010 г.). М.: Изд-во ЦПИ при мех.-мат. ф-те МГУ, 2010. С. 18-34.

функций ft-значной логики является исследование свойств семейства классов {<р(А) IЛ С 1\ }. К этой проблематике можно отнести задачи определения мощности такого семейства классов, его структуры, свойств его элементов и т.д.

Для функциональных систем функций двузначной логики с операцией суперпозиции Э. Л. Пост показал5, что каждый класс булевых функций, замкнутый относительно данной операции, имеет конечный базис и описал все такие классы. Тем самым установлена счетность семейства замкнутых классов булевых функций и построена решетка замкнутых классов. Данные результаты в более доступном изложении позднее представлены в книге C.B. Яблонского, Г.П. Гав-рилова и В. Б. Кудрявцева6. При этом в отличие от работ Поста, в этой книге рассматривались классы, замкнутые относительно двух операций: суперпозиции и введения несущественной переменной. Такой подход позволил получить более простую структуру замкнутых классов, исключив семнадцать классов, которые не являются замкнутыми относительно операции введения несущественной переменной.

Результаты, полученные в двузначной логике, способствовали развитию исследований функциональных систем функций fc-значной логики при к > 3. С. В. Яблонский решил7 задачу о полноте в множестве функций 3-значной логики с операциями суперпозиции и введения несущественной переменной и описал все 18 предполных классов в Р3, а A.B. Кузнецовым8 установлена конечность семейства всех предполных классов в Рt при любом к. В работах многих исследователей выявлены различные семейства предполных классов9, а описание всех предполных классов функций из Pk завершено И. Розенбергом10.

5Post E.L. Introduction to a general theory of elementary propositions // Amer. J. Math. 1921. 43, 3. 163- 185. The two-valued iterative systems of mathematical logic. Annals of Math. Studies. Princeton Univ. Press. 1941. 5.

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

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

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

9Мартынюк В. В. Исследование некоторых классов в многозначных логиках // Проблемы кибернетики. М.: Наука, 1960. Вып. 3. С. 49-60. Pan Jun-Cze. A solving method for finding all precomplete classes in many-valued logics // Acta Sei. Natur. Univ. Jilinensis. 1962. V. 2. Lo Czu Kai. Precomplete classes defined by normal k-ary relations in fc-valued logics // Acta Sei. Natur. Univ. Jilinensis. 1964. 3. 39-50. Lo Czu Kai, Lju Sjui Hua. Precomplete classes defined by binary relations in many-valued logics // Acta Sei. Natur. Univ. Jilinensis. 1963. 4. Захарова Е.Ю. Критерий полноты системы функций из Г\ // Проблемы кибернетики. М.: Наука. 1967. Вып. 18. С. 5-10. Байрамов P.A. Об одной серии предполных классов в /г-значной логике // Кибернетика. 1967. № 1. С. 7-9.

10Rosenberg 1. G. La structure des functions de plusieurs variables sur un ensemble fini // C. R. Acad. Sei. Paris, Group 5. 1965. 260. 3817-3819. Über die funktionale Vollständigkeit in den mehrwertigen Logiken // Rozpr. CSAV Rada Mat. Píiv. Vëd., Praha. 1970. 80. 3-93.

Пост предполагал5, что для исследования функций многозначной логики можно воспользоваться методом моделирования таких функций в двоичной системе и получить результаты, подобные результатам для булевых функций. Однако позднее были выявлены существенные различия между двузначной и /г-значной логикой при к > 3. Так, Ю. И. Янов и А. А. Мучник привели примеры замкнутых классов без базиса и классов со счетным базисом11, тем самым установив, что семейство замкнутых классов функций многозначной логики является континуальным.

Изучение семейства замкнутых классов функций fc-значной логики при к > 3 наталкивается на значительные трудности в связи с его континуальностью. Поэтому для его исследования используются различные подходы, которые условно можно разделить4 на два направления: изучение свойств конкретных семейств замкнутых классов и изучение функциональных систем Р£ = 'р+), в которых в качестве оператора ip+ рассматривается какое-либо усиление оператора суперпозиции tp.

К первому из описанных направлений естественным образом относится задача исследования свойств предполных классов функций fc-значной логики. Помимо их описания, для данных классов рассматривался вопрос наличия у них конечных базисов. Д. Лау приведены12 конечные порождающие системы для всех предполных классов в Р): при любом к, кроме классов типа О (классов монотонных функций), а также для классов типа О при к < 7. Пример пред-полного класса монотонных функций из Pg, который не имеет конечного базиса, построен Г. Тардошем13. В работах Я. Деметровича, JI. Ханнака, JI. Роняй14 описаны некоторые достаточные условия конечной порожденное™ предполных монотонных классов при любом к. В дальнейшем существенные продвижения в данном направлении получены в работах О. С. Дудаковой", в которых найден критерий наличия конечного базиса у предполных классов функций, монотонных относительно частично упорядоченных множеств ширины 2.

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

пЯнов Ю.И., Мучник Л. А. О существовании А:-значных замкнутых классов, не имеющих конечного

базиса // ДАН СССР. 1959. Т. 127, № 1. С. 44 - 46.

uLau D. Bestimmung der Ordnung maximaler Klassen von Funktionen der ¿-wertigen Logik II Zeitschr.

f. Math. Logik und Grundlagen, d. Math. 1978. 24. 79-96.

13Tardos G. A not finitely generated maximal clone ofmonotone operations // Order. 1986. 3. 211 - 218.

nDemetixnics J-, Hannàk L., Rônyai L. Near unanimity functions and partial orderings // Proc. 14 ISMVL, Manitoba. 1984. 52-56. On algebraic properties of monotone clones // Order. 1986. 3. 219-225. On monotone clones // MTA SZTAKI Tanulmanyok. 1987. 202. 39-62.

15Дудакова О. С. О классах fc-значной логики, монотонных относительно множеств ширины два // Вестн. Моск. ун-та. Матем. Механ. 2008. № 1. С. 31 -37. О конечной порожденное™ предполных классов монотонных функции многозначной логики // Математические вопросы кибернетики. М.: Физмат-лит, 2008. Вып. 17. С. 13-104.

рые в нем содержатся. В работах С. С. Марченкова, Я. Деметровича, JI. Ханна-ка16 доказано, что при любом к множество замкнутых классов, содержащихся в любом предполном классе, является континуальным, за исключением классов типа L (классов линейных функций), в которых при простых к данное множество является конечным, а при к, равных степеням простых чисел — счетным.

Помимо исследования предполных классов большое внимание уделялось изучению семейств классов, содержащих простые естественные множества функций. Е. Слупецкий привел17 критерий полноты замкнутых классов многозначной логики, содержащих все функции одной переменной, и показал, что число таких классов является конечным, а Г. А. Бурле описал18 данные классы. С. В. Яблонским найден1 критерий полноты классов функций многозначной логики, содержащих все одноместные функции, принимающие не более к — 1 значения. В работах В.Б. Кудрявцева" изучаются свойства систем функций, которые принимают все значения из Ей = {0,1, ... .к — 1} (такие системы называются ¿'-системами), приводится описание всех 5-предполных 5-множеств, устанавливается асимптотическое поведение числа таких множеств и их типов.

При изучении конкретных семейств замкнутых классов функций из Pk одними из первых часто исследуются семейства Pk.i функций fc-значной логики, которые принимают только значения из множества Ei, где I > 2. В работах Д. Лау20 и Н. Грюнвальда21 для каждого класса В булевых функций установлена мощность семейства замкнутых классов функций из Рц.->, которые содержат только функции, ограничение которых на множестве Е2 принадлежит классу В, и описаны такие семейства в тех случаях, когда они являются конечными или

16Марченков С. С. О замкнутых классах самодвойственных функций многозначной логики II // Проблемы кибернетики. 1983. Вып 40. С. 261 -266. Demetrovics J.. Hannâk L. The cardinality of closed sets in precomplete classes in fc-valued logics // Acta Cybernetica. 1979. 4, 3. 273-277. On the cardinality of self-dual closed classes in fc-valued logics // MTA SZTAKJ Közlemenyek. 1979. 23. 7-16. Demetmvics J., Hannâk t., Marchenkov, S. S. Some remarks on the structure of .P3 // C. R. Math. Rep. Acad. Sei. Canada. 1980. 2.215-219.

xlShtpecki J. Kriterium pe lnosci wielowartosciowych systemow logiki zdan // C. R. Séanc. Soc. Sei. Varsovie, CI. III. 1939. 32. 102-109.

i%Eypie Г. А. Классы fc-значной логики, содержащие все функции одной переменной // Дискретный анализ. 1967. Вып. 10. С. 3-7.

19Кудрявцев В.Б. Относительно S-систем функций fc-значной логики // ДАН СССР. 1971. Т. 199, № I.C. 20 -22. О свойствах 5-сиетем функций fc-значной логики//Дискретный анализ. 1971.Вып. 19. С. 15-47. О свойствах 5-систем функций fc-значной логики // Akademie-Verlag Berlin. Е1К. 1973. 9, № 1/2. С. 81-105.

20Lau D. Kitngruenzen auf gewissen Teilklassen von P^f II Rostock, Math. Kolloq. 1977. 3. 37-43. Über abgeschlossene Teilmengen von II 1. Inform. Process. Cybern. EIK. 1988. 24, 10. 395-513.

2,Griinnald N. Bestimmung sämtlicher abgeschlossenen Mengen aus P32, deren Projektion Fg ist // Rostock, Math. Kolloq. 1983. 23. 5-26. Strukturaussagen über den Verband der abgeschlossenen Mengen von Pfci2, insbesondere von P3 2- Dissertation A, Universität Rostock. 1984.

счетными. Также некоторые специальные семейства классов функций из Рк.2 исследовались в работах А. В. Михайлович22.

Относительная простота некоторых классов функций из Ркл, достигнутые в этом направлении результаты и разработанные методы позволили в отдельных случаях исследовать задачи о сложности представления функций формулами. Д. А. Дагаевым23 для почти всех замкнутых классов булевых функций получены асимптотически совпадающие с «мощностными» нижними оценками верхние оценки функций Шеннона, характеризующих сложность множества всех функций из Р3.2 с проекцией (булевым ограничением) в заданный класс булевых функций, при реализации формулами над некоторыми порождающими системами, а для почти всех замкнутых классов псевдолинейных функций (проекции которых совпадают с классом всех линейных булевых функций) из Р^ установлен точный рост соответствующих функций Шеннона для некоторых порождающих систем.

Значительное число работ посвящено исследованиям функциональных систем (Рк',У>+), в которых оператор <р+ является усилением оператора суперпозиции. Использование такого подхода позволяет, как правило, получать семейства замкнутых классов с более обозримой структурой. Стоит отметить, что упомянутые выше работы Е. Слупецкого и Г. А. Бурле можно отнести к данному направлению исследований, поскольку задачи, рассматриваемые в данных работах, естественным образом можно переформулировать в терминах усиленной операции суперпозиции, допускающей в качестве тривиальных формул формулы, реализующие функции одной переменной.

С. С. Марченков и Нгуен Ван Хоа рассматривали24 ^-замкнутые классы функций &-значной логики (классы, которые вместе с каждой функцией содержат функции, двойственные к ней относительно заданной группы перестановок) и показали, что семейство таких классов является конечным при любом к > 3, и при этом число таких классов растет сверхэкспоненциально с ростом к.

22Михайлович А. В. О классах функций трехзначной логики, порожденных монотонными симметрическими функциями // Вестн. Моск. ун-та. Матем. Механ. 2009. № 1. С. 33-37. О замкнутых классах функций многозначной логики, порожденных симметрическими функциями // Математические вопросы кибернетики. М.: Физматлит, 2013. Вып. 18. С. 123-212.

2}ДагаевД.А. О сложности псевдолинейных функций // Вестн. Моск. ун-та. Матем. Механ. 2010. № 2. С. 53-56. О сложности функций многозначной логики, принимающих два значения // Математические вопросы кибернетики. М.: Физматлит, 2013. Вып. 18. С. 35-122.

2А Марченков С. С. Основные отношения 5-классификации функций многозначной логики // Дискретная математика. 1996. Т. 8, вып. 1. С. 99-128. ^-классификация функций многозначной логики // Дискретная математика. 1997. Т. 9, вып. 3. С. 125-152. Нгуен Ван Хоа. Описание замкнутых классов к-значной логики, сохраняемых всеми автоморфизмами // Докл. АН Беларуси. 1994. Т. 38, № 3. С. 16- 19. Структура симметрических замкнутых классов /г-значной логики. Докт. диссертация. Минск, 1995.

В работе А. В. Кузнецова25 введены понятия параметрической выразимости и оператора параметрического замыкания, а также установлены критерии параметической выразимости для fc-значных логик при к > 2 и найдены все параметрически замкнутые классы при к = 2. В дальнейшем А.Ф. Даниль-ченко установлена26 конечность семейства параметрически замкнутых классов при к = .3, а С. Баррисом и Р. Уиллардом27 — при к > 3. На основе понятия параметрической выразимости О. М. Касим-Заде определено28 понятие неявной выразимости. Им установлена эквивалентность параметрической и неявной выразимости при к = 2 и, тем самым, установлена конечность множества классов неявно выразимых булевых функций. Критерии неявной полноты множеств функций /с-значной логики получены О. М. Касим-Заде28 и Е. А. Ореховой29 при к = 2 и к = 3 соответственно. При этом в работе Ореховой критерий неявной полноты для к — 3 формулируется не в терминах предполных (т.е. максимальных неполных) классов, а в терминах минимальных полных классов.

Функционально-предикатные системы с операциями замыкания программного типа, определяемые своими множествами предикатов, рассматривались в работе Ю. В. Голункова30, в которой исследовалась задача полноты таких систем. Работы В. А. Тайманова и В. Д. Соловьева31 посвящены изучению функциональных систем функций А:-значной логики, к > 2, с операциями программного типа. В. А. Тайманов установил, что в зависимости от свойств множеств предикатов, семейства замкнутых классов могут быть конечными, счетными и континуальными. Примеры конечных описаний замкнутых классов для некоторых операций программного типа рассматривались В. Д Соловьевым.

К этому же направлению относятся и работы О. С. Тарасовой32. В них определены операторы замыкания относительно суперпозиции и перестановок,

-5K)'3Hetfoe А. В. О средствах для обнаружения невыводимости и невыразимости // Логический вывод. М.: Наука, 1979. С. 5-33.

26Данюъченко А. Ф. О параметрической выразимости функций трехзначной логики // Алгебра и логика. 1977. Т. 16, № 4. С. 397-416.

21 Barris S., Willard R. Finitely many primitive positive clones // Proc. of the American Mathematical Society. 1987. 101, 3. 427-430.

28Касим-Заде О. M. О неявной выразимости булевых функций // О неявной выразимости булевых функций // Вестн. Моск. ун-та. Матем. Механ. 1995. № 2. С. 44-49.

29Орехова Е. А. Об одном критерии неявной полноты в трехзначной логике // Математические вопросы кибернетики. М.: Физматлит, 2003. Вып. 12. С. 27-75.

30Голунков Ю. В. Полнота систем функций в операторных алгоритмах, реализующих функции к-значной логики // Вероятностные методы и кибернетика. 1980. Вып. 17. С. 23-24.

31 Соловьев В. Д. Замкнутые классы в fc-значной логике с операцией разветвления по предикатам // Дискретная математика. 1990. Т. 2, вып. 4. С. 18-25. Тайманов В. А. О функциональных системах к-значной логики операциями программного типа // Докл. АН СССР. 1983. Т. 268, № 6. С. 1307-1310. Функциональные системы с операциями замыкания программного типа. Диссертация. 1983.

3~ Тарасова О. С. Классы функций fc-значной логики, замкнутые относительно операции суперпозиции и перестановки // Математические вопросы кибернетики. 2004. Вып. 13. С. 59 -112.

основанных на разбиении множеств Е", и приведены примеры перестановок, при которых семейство замкнутых классов функций fc-значной логики является счетным при к > 3, а также пример оператора, для которого семейство замкнутых классов функций из Рь является счетным при к = 3 и континуальным при к >5.

Таким образом, при исследовании функциональных систем (F\] ¡р+) в качестве оператора <р+, как правило, выбирается оператор, возникающий при решении других задач или представляющий практический интерес. Немаловажное значение при этом имеет наличие новых качественных «эффектов», выявляемых при изучении семейств классов, замкнутых относительно оператора <р+, и возможность использования полученных результатов для исследования классов, замкнутых относительно операции (обычной) суперпозиции.

В настоящей работе изучаются функции fc-значной логики при к = 2т, т > 2. Каждое число из множества {0,1, ... , к — 1} кодируется в двоичной системе счисления. Тем самым этому числу взаимно-однозначно сопоставляется двоичный вектор из множества {0,1}т. На основе этого кодирования каждой функции из Pk сопоставляется булева вектор-функция, состоящая из гп компонент. Идея применения такого подхода для изучения функций многозначной логики была предложена, как уже говорилось, еще Э. JI. Постом и часто используется в различных областях дискретной математики33, а в отдельных случаях является настолько эффективной, что позволяет получать в некотором смысле окончательные результаты34.

В диссертации на основе представления функций А;-значной логики в виде булевых вектор-функций определен оператор /3-замыкания, который является усилением оператора суперпозиции, и исследуются структуры семейств ß-замкнутых классов функций из множества Рцг (множества функций fc-значной логики, которые принимают не более г значений). Каждому /3-замкнутому классу Л естественным образом сопоставлен класс булевых функций, равный замыканию компонент всех функций из Л и называемый булевым замыканием. Показано, что для каждого замкнутого класса В булевых функций семейство ß-замкнутых классов функций из с булевым замыканием В является конечным (и непустым) и описаны все такие классы. Тем самым установлена счетность множества /3-замкнутых классов функций £-значной логики, которые принима-

33Поспелов Д. А. Логические методы анализа и синтеза схем. М.: Энергия, 1974. Гаврилов Г.П., Ca-пожеико А. А. Задачи и упражнения по дискретной математике. М.: Физматлит, 2004. Яблонский С. В. Элементы математической кибернетики. М.: Высшая школа, 2007. Шашиов JI. А. Основы теории дискретных логических и вычислительных устройств. СПб.: Лань, 2011.

ъ*Трахтенброт Б. А. Асимптотическая оценка сложности логических сетей с памятью. // ДАН СССР. 1959. Т. 127, № 2. С. 281-284. Кочергин А. В. О глубине функций fc-значной логики в бесконечных базисах // Вести. Моск. ун-та. Матем. Механ. 2013. № 1. С. 56-59.

ют не более двух значений. При значениях г, равных трем и четырем, для каждого замкнутого класса В булевых функций показано, что семейство /3-замкнутых классов функций из Рк\г с булевым замыканием В может быть либо конечным, либо континуальным, а также найдены условия, при которых это семейство имеет соответствующую мощность. В частности, приведена полная классификация семейств /3-замкнутых классов функций из Р\ с фиксированным булевым замыканием по их мощности. Кроме того, указаны замкнутые классы В булевых функций, для которых семейства /3-замкнутых классов с булевым замыканием В являются конечными при к = 4 и континуальными при к = 2т, т > 3.

Цель работы

Исследование свойств оператора /3-замыкания и /3-замкнутых классов функций А:-значной логики при к = 2т, т > 2.

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

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

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

Все результаты являются новыми, получены автором самостоятельно. В диссертации для функций /с-значной логики (к = 2т, т> 2) получены следующие основные результаты.

1. Установлена счетность семейства /3-замкнутых классов функций А>значной логики, которые принимают не более двух значений. Приведено описание всех /3-замкнутых классов из этого семейства.

2. Построены примеры континуальных семейств /3-замкнутых классов, содержащих только функции ^-значной логики, принимающие не более трех значений. Для каждого класса В булевых функций установлено, что семейство /3-замкнутых классов, которые содержат только такие функции и имеют булево замыкание В, является либо конечным, либо континуальным. Установлено явное разбиение всех замкнутых классов булевых функций по этому признаку.

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

8

конечным, либо континуальным. Установлено явное разбиение всех замкнутых классов булевых функций по этому признаку. В частности, приведена полная классификация семейств /3-замкнутых классов функций из Р4 с фиксированным булевым замыканием по их мощности.

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

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

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

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

1. Семинар "Функции многозначной логики и смежные вопросы" под руководством профессоров А. Б. Угольникова, С. Б. Гашкова и Р. М. Колпакова, механико-математический факультет МГУ им. М. В. Ломоносова, 2011 г.

2. Семинар "Синтез управляющих систем" под руководством профессора О. М. Касим-Заде, механико-математшеский факультет МГУ им. М. В. Ломоносова, 2014 г.

3. Семинар "Математические вопросы кибернетики" под руководством профессора О. М. Касим-Заде, механико-математический факультет МГУ им. М.В. Ломоносова, 2014 г.

4. XI Международный семинар "Дискретная математика и ее приложения", Москва, МГУ им. М.В. Ломоносова, 18-23 июня 2012 г.

5. XXI Международная конференция студентов, аспирантов и молодых ученых "Ломоносов", Москва, МГУ им. М.В. Ломоносова, 8-12 апреля 2013 г.

6. Научная конференция "Ломоносовские чтения", Москва, МГУ им. М. В. Ломоносова, 2013 -2014 гг.

7. IX молодежная научная школа по дискретной математике и ее приложениям, Москва им. М.В. Ломоносова, ИПМ им. М.В. Келдыша РАН, 16-21 сентября 2013 г.

8. XXI Международная конференция студентов, аспирантов и молодых ученых "Ломоносов", Москва, МГУ им. М. В. Ломоносова, 7-11 апреля 2014 г.

9. XVII международная конференция "Проблемы теоретической кибернетики", Казань, КФУ, 16-20 июня 2014 г.

Публикации

Основные результаты по теме диссертации изложены в 6 печатных изданиях, 3 из которых изданы в журналах, рекомендованных ВАК. Список публикаций приведен в конце автореферата [1-6].

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

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

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

Обозначим через Рк множество всех функций А:-значной логики для каждого к > 2, а через Рщг — множество всех функций из Рк, принимающих не более г значений, где 1 < г < к. Для замкнутых классов булевых функций будем использовать следующие обозначения35: То — множество всех функций, сохраняющих константу 0; Т\ — множество всех функций, сохраняющих константу 1; М — множество монотонных функций; Ь — множество линейных функций; 5 — множество самодвойственных функций; 0м — множество всех булевых функций /, таких, что у произвольных ц наборов, на которых функция / равна 0, имеется общая нулевая компонента, /1 = 2,3,...; Ох — множество всех булевых функций /, для которых справедливо соотношение / > х, где х — одна из переменных функции /; — классы, двойственные к О11, ц = 2,3, ... ,со;П — множество всех дизъюнкций; К — множество всех конъюнкций; и — множество всех одноместных функций; С — множество всех констант. Пусть /х = 2,3, ... , ос.

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

Положим:

В0 = В П Т0, Bi = В П Ти где В равен M, L, D, К, U или С;

Тт=Т0ПТи В01 = ВП Той где В равен M. L, S, D, К или U;

SM = SnM, SL = S П L, SU = SD U, MU = M П U;

MO" = M Cl О'1, MI? = M П 7";

Оg = 0"П T0, /f = /"ПТ1;

л/о;; = д/о" n тп; = ji№ n тг.

В диссертации рассматриваются функциональные системы функций из Pk при к = 2m, m > 2, со специальными операциями суперпозиции.

Во введении кратко изложена история вопроса и описаны основные результаты работы.

В первой главе введены основные понятия и определены новые операторы замыкания. Каждая функция F из Рк, зависящая от n переменных, n > 1, естественным образом кодируется в двоичной системе счисления. Тем самым ей сопоставляется булева вектор-функция F, содержащая m компонент, каждая из которых зависит от mn переменных, и называемая двоичным представлением функции F. В разделе 1.2 определена операция двоичной S-суперпозиции, которая подобна операции (обычной) суперпозиции, но, в отличие от нее, позволяет при построении новых функций специальным образом переставлять компоненты двоичных представлений функций fc-значной логики между собой. Для оператора замыкания относительно операции двоичной S-суперпозиции, который назван So-замыканием, на основе примера замкнутых классов со счетным базисом, предложенного Ю.И. Яновым и А. А. Мучником11, установлена континуальность семейства So-замкнутых классов функций из Рц2 (теорема 1.1).

В разделе 1.3 для каждого множества А из Pk определено его булево замыкание В(А) — класс булевых функций, который равен замыканию всех компонент двоичных представлений функций из А относительно операций суперпозиции и введения несущественной переменной. Также определено Д-замыкание множества А как множество всех функций А'-значной логики с двоичным представлением F(r}\. ... ,ffmn), где F е А и д\, ... ,дт„ € В (А) (здесь n — число переменных функции F). В этом разделе доказаны некоторые свойства такого оператора, а в разделе 1.4 установлено, что оператор /3-замыкания эквивалентен оператору замыкания относительно операций двоичной S-суперпозиции и введения несущественной переменной (теорема 1.2). В разделе 1.5 приведен критерий полноты ^-замкнутых классов (теорема 1.3) и описаны все /З-предполпыс классов. Оказалось, что их число не завивисит от к и равно шести. Пять из них соответствуют предполным классам булевых функций и состоят из всех

11

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

В главе 2 исследуются /3-замкнутые классы функций из Рф- В разделе 2.1 показано, что для каждого замкнутого класса В булевых функций семейство /3-замкнутых классов функций из с булевым замыканием В является конечным и непустым (теорема 2.1). В качестве простого следствия этого утверждения установлена счетность семейства /3-замкнутых классов функций из Рф (теорема 2.2), в то время как семейство классов функций из замкнутых относительно операций суперпозиции и введения несущественной переменной, является континуальным. В разделе 2.2 приведено описание этого семейства /3-замкнутых классов (теорема 2.3) и описан подход к построению решетки /3-замкнутых классов функций из Рк\2- При этом доказано, что при замыкании относительно операции двоичной ¿'-суперпозиции семейство замкнутых классов функций из Рк|2 является континуальным, а при замыкании относительно двоичной ¿-суперпозиции и введения несущественной переменной — счетным.

В разделе 3.1 приведен пример континуального семейства /3-замкнутых классов функций из Рф с булевым замыканием О00 (теорема 3.1), и тем самым установлена континуальность семейства /3-замкнутых классов. При их изучении в главах 3-5 применяется подход, намеченный в главе 2 — для каждого замкнутого класса В булевых функций исследуется семейство /3-замкнутых классов функций из Рк|г с булевым замыканием В, где к = 2Г", т > 2, г = 3,4, к. В этом разделе вводятся следующие обозначения: С}{к,г) — множество классов булевых функций, для которых такие семейства /3-замкнутых классов являются континуальным, С(к, г) — множество классов булевых функций, для которых соответствующие семейства /3-замкнутых классов являются конечными.

В разделе 3.2 установлена принадлежность некоторых классов булевых функций множеству С(к,к), а также множеству С{к, 3) (теоремы 3.2 и 3.3). На основе этих результатов показано, что для множества (}{к, 3) справедливы следующие соотношения {О30, 1°°} С СЦ(к, 3) и С}(к, 3) С {О00, Iх} и{С\ /'' | ¡1 > 3}. В разделе 3.3 доказано, что на самом деле справедливы следующие равенства (теоремы 3.4 и 3.5):

<?(*,-, 3) = {О30,7=°} I" I и > 3}; С(к,3) = {В С р2 | [В] = В, В $ <?(*;, 3)}.

В разделе 3.5 для каждой тройки попарно различных чисел а, Ь, с исследуются функции ¿-значной логики, которые принимают значения из множества {а, Ъ, с}. Для каждого такого множества {а, Ь, с} и класса В булевых функций из

множества <3(к, 3) установлено, что семейство /3-замкнутых классов функций, которые принимают только значения из множества {а, Ь. с}, с булевым замыканием В может быть пустым, конечным или континуальным, и найдены соотношения для чисел а, Ь и с, при которых оно имеет соответствующую мощность (теорема 3.6). Также показано, что семейство /3-замкнутых классов функций, которые принимают значения только из множества {а, 6, о}, может быть конечным, счетным или континуальным и выявлен критерий, позволяющий это определить (теорема 3.7).

В главе 4 изучаются семейства /3-замкнутых классов функций из Рщ с фиксированным булевым замыканием. В разделе 4.1 континуальные семейства /3-замкнутых классов функций из Рф обобщены на случай функций из Рк|4 (теорема 4.1), в разделе 4.2 найдены некоторые классы из множества С {к, 4) (теорема 4.2), а в разделе 4.3 показано, что класс О2 содержится в множестве С{к, 4) при к = 4 (теорема 4.3) и в множестве 4) при к = 2™, т > 3 (теорема 4.4). На основе результатов этой и предыдущих глав доказаны следующие равенства (теоремы 4.5 и 4.6):

<3(4,4) = {о°°, л/о30, мо?, Iх, М1Х, М113°} и и {о<\ оц, мол го;;, г}', и/», М1[' \ ц > з};

С(4,4) = {В С р21 [В] = В, В £ <2(4,4)};

С2(к, 4) = д(4,4) и{02,12} при к = 2т. т > 3;

С{к, 4) = {В С Р2 | [В] =В, В £ <3(к, 4)} при к = 2т, т > 3.

Таким образом приведена полная классификация семейств /3-замкнутых классов функций из Р\ с фиксированным булевым замыканием по их мощности. В главе 5 получены следующие результаты относительно подобных семейств /3-замкнутых классов для случая Рк, где к = 2т, т > 3 (теорема 5.1):

{Р2, То, Т1; Т01,5,501, Ь, Ь0, Ьи БЬ, Ьт} С С(к, к);

{В, Ва, А, Вох, К, К0, Кь Коь и, Би, Ми, Щ, ии 11т,С, С0, С^} С С(к, к);

{О2, МО2, МО2,12, М12, М1о2} и <2(к, 4) С <3(А:, к).

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

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

13

наук, профессору Вадиму Васильевичу Кочергину за обсуждение диссертации,

ценные рекомендации и постоянное внимание к работе.

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

1. Подолько Д. К. О классах функций, замкнутых относительно специальной операции суперпозиции // Вестник Моск. ун-та. Сер. 1. Математика. Механика. 2013. №6. С. 54-57.

2. Подолько Д. К. Об одном континуальном семействе бета-замкнутых классов функций многозначной логики II Прикладная дискретная математика. 2014. №2(24). С. 12-20.

3. Подолько Д. К. О классах функций ¿-значной логики, принимающих не более трех значений // Учен. зап. Казан, ун-та. Сер. Физ.-матем. науки. 2014. Т. 156, кн. 3. С. 98-109.

4. Подолько Д. К. О некоторых свойствах операции суперпозиции специального вида II Материалы XI Международного семинара «Дискретная математика и ее приложения», посвященного 80-летию со дня рождения академика О.Б. Лупанова (Москва, МГУ, 18-23 июня 2012 г.). / Под редакцией О. М. Касим-Заде. М.: Изд-во механико-математического факультета МГУ, 2012. С. 213-215.

5. Подолько Д. К. Об особенностях специальной операции суперпозиции в многозначной логике // Материалы IX молодежной научной школе по дискретной математике и ее приложениям (Москва, 16-21 сентября 2013 г.). Под редакцией А.В. Чашкина. М.: Изд-во ИПМ РАН, 2013. С. 92-97.

6. Подолько Д. К О мощности некоторых семейств бета-замкнутых классов функций многозначной логики // Проблемы теоретической кибернетики. Материалы XVII международной конференции (Казань, 16-20 июня 2014 г.). Под редакцией Ю.И. Журавлева. Казань: Отечество, 2014. С. 232-234.

Подписано в печать 10.12.2014г. Бумага офсетная. Печать цифровая. Формат 60x90/16. Усл. печ. л. 1. Заказ № 173. Тираж 100 экз. Типография «КОПИЦЕНТР» 119234, г. Москва, Ломоносовский пр-т, д.20 Тел. 8(495)213-88-17