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

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

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

Акулов Ярослав Викторович

О КЛАССАХ БУЛЕВЫХ ФУНКЦИЙ,

ВЫРАЗИМЫХ ОТНОСИТЕЛЬНО РАСШИРЕННОЙ СУПЕРПОЗИЦИИ

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

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

2 9 ДПР 2015

Москва 2015

4

и

005568105

005568105

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

Научный руководитель: доктор физико-математических наук,

профессор Колпаков Роман Максимович.

Официальные оппоненты: Аблаев Фарид Мансурович,

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

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

Ведущая организация: ФГБУН «Институт прикладной математики им. М.В. Келдыша Российской Академии Наук».

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

С диссертацией можно ознакомиться в Фундаментальной библиотеке ФГБОУ ВО «Московский государственный университет имени М. В. Ломоносова» (Москва, Ломоносовский проспект, д. 27, сектор А, 8" этаж). Автореферат разослан 29 апреля 2015 года.

Ученый секретарь диссертационного совета у [/ Д 501.001.84, созданного на базе уч / уИ

ФГБОУ ВО МГУ,

доктор физнко математических наук, профессор Иванов Александр Олегович

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

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

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

В теории функциональных систем важное место занимают задачи классификации функций в соответствии с различными свойствами этих функций. Исследование свойств функций позволяет объединить эти функции в отдельные классы и зачастую помогает получить более полное понимание структуры функциональных множеств и на основе полученной классификации выделить некоторый более общий подход, применимый к другим задачам теории дискретных функций. Описание и изучение множеств функций, замкнутых относительно операции суперпозиции, является одним из наиболее известных подходов к решению задач классификационного характера. Классическим результатом в этой области является описание множества всех классов булевых функций, замкнутых относительно операции суперпозиции. Это описание было получено Э. Постом1'2 в 1920 году. Как показал Пост, мощность множества классов булевых функций, замкнутых относительно операции суперпозиции, является счетной. Ю. И. Янов и А. А. Мучник3 установили, что в fc-значной логике при к > 3 существуют примеры замкнутых классов, не имеющих базиса, а также классов со счетным базисом. Отсюда, в частности, следует, что множество всех замкнутых классов fc-значной логики при к > 3 имеет континуальную мощность, что значительно затрудняет исследование.

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

1 PostE.L. Introduction to я ^encrai theory of elementary propositions // Amer. J. Math. — 1921. — V.4.Î, №3. - Г. 183-185.

2 Post E. L. Two-valued iterative systems of mathematical logic // Annals of Math. Studies. Princeton-London: Princeton Univ. Press. — 1941. — V. 5. — P. 122.

3 Янов Ю. И., Мучиак А. А. О существовании fc-значных замкнутых классов, ne имеющих конечного базиса // Докл. АН СССР. - 1959. - Т. 127, .Y< 1. - С. 44-40.

Г

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

Перечислим работы, относящиеся к первому направлению исследований.

В работах С. С. Марченкова4'5,6 и Нгуен Ван Хоа7'8,9 исследуется S-замыкание, в котором наряду с операцией суперпозиции применяется операция перехода к двойственным функциям относительно фиксированной группы подстановок. Другими словами, 5-замкнутый класс для каждой принадлежащей ему функции содержит также всякую двойственную ей относительно указанной группы подстановок функцию. Таким образом, авторами изучается структура решетки замкнутых классов функций /с-значной логики при отождествлении похожих, в определенном смысле, функций. В частности, для симметрической группы множества Е* в этих работах установлено, что множество 5-замнутых классов функций /с-значной логики для любого к > 3 конечно.

В работе А. В. Кузнецова10 вводятся понятия параметрической выразимости и параметрического замыкания. В этой работе получено описание параметрически замкнутых классов булевых функций. В работе А. Ф. Данильченко11 показано, что при к = 3 множество параметрически замнутых классов функций Ахзначной логики конечно, а в работе С. Барриса и Р. Уилларда12 аналогичное утверждение доказано для к > 3.

4 Марчепков С. С. Основные отношения 5-клясс.ификации функций многозначной логики /'/' Дискретная математика. — 199G. — Т. 8, №1. — С. 99-128.

5 Марчепков С. С. S-классификация идемпотентных алгебр с конечными носителями // Докл. РАН. - 199S. - Т. 348, №5. - С. 587-589.

6 Марчепков С. С. S-классификация функций многозначной логики // Дискретная математика. — 1997. - Т. 9, №3. - С. 125-152.

7 Нгуен Ван Хоа О структуре самодвойственных замкнутых классов трехзначной логики в Р3 // Дискретная математика. — 1992. — Т. 4, №4. — С. 82-95.

8 Нгуен Ван Хоа О семействах замкнутых классов fc-значной логики, сохраняемых всеми автоморфизмами // Дискретная математика. — 1993. — Т. 5, №4. — С. 87-108.

9 Нгуеп Ван Хоа Описание замкнутых классов в к-значной логике, сохраняемых всеми автоморфизмами // Докл. АН Беларуси. — 1994. — Т. 38, К<3. — С. 16-29.

10 Кузнецов А. В. О средствах для обнаружения невыводимости и невыразимости. Логический вывод. — М.: Наука, 1979. — С. 5-33.

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

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

В работах Ю. В. Голункова и О.В.Андреевой13'14, В. А. Тайманова15,16 н В.Д.Соловьева17 изучаются вопросы полноты функционально-предикатных систем с операциями замыкания программного типа. Каждая операция программного типа определяется своим множеством предикатов. В работах В. А. Тайманова показано, что в зависимости от свойств указанных множеств предикатов мощность множества замкнутых классов может быть конечной, счетной или равняться мощности континуума.

В работах А. В. Кузнецова18, О. М. Касим-Заде19,20,21, Е. А. Ореховой22 и Е. В. Михайлец23,24 рассматриваются классы функций, допускающих неявное представление над некоторой системой функций.

В работах О. С. Тарасовой25,26,27 исследуются классы к-значной логики, к > 2, замкнутые относительно операций суперпозиции и перестановки с множеством наборов специального вида.

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

13Андреева О. В., Голупков Ю. В.Программно-замкнутые классы функций алгебры логики и предикатов//Кибернетика. 1081. N«5. С. 133.

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

15 Тайманов В. А. Функциональные системы с операциями замыкания программного типа: диссертация иа соискание ученой степени кандидата физико-математических наук. Москва, 1083.

16 Тайманов В. А. О функциональных системах ¿-значной логики операциями программного типа // Докл. АН СССР. - 1983. - Т. 208, X«G. - С. 1307-1310.

17 Соловьев В. Д. Замкнутые классы в А;-значной логике с операцией разветвления по предикатам // Дискретная математика. 1900. Т. 2, N«4. С. 18 25.

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

19 Касим-Заде О. А/. О неявной выразимости булевых функций // Вестник МГУ. Серия 1. Математика. Механика. — 1905. — N«2. — С. 44-49.

20 Касим-Заде О. М. О неявной полноте в fc-значной логике // Вестник МГУ. Серия 1. Математика. Механика. - 2007. - №3. - С. 9-13.

21 Касим-Заде О. А/. Об одной метрической характеристике неявных и параметрических представлений булевых функций /'/' Математические вопросы кибернетики. — 1990. — Вып.б. — С. 133-188.

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

23 Михайлец Е. В. О ранге неявных представлений над одним классом функций трехзначной логики // Вестник МГУ. Серия 1. Математика. Механика. — 2008. — Я» 2. — С. 65-70.

24 Михайлец Е. В. О ранге неявных представлений функций k-значной логики над классом монотонных функций // Математические воп]юс:ы кибернетики. — 2009. — Вып. 18.

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

26 Тарасова О. С. Классы функций трехзначной логики, замкнутые относительно операций суперпозиции и перестановки // Вестник МГУ. Серия 1. Математика. Механика. — 2004. — Вып. 1. — С. 25-29.

27 Тарасова О. С. Классы fc-значной логики, замкнутые относительно расширенной операции суперпозиции // Вестник МГУ. Серия 1. Математика. Механика. — 2001. — Вып. 6. — С. 54-57.

раций. В частности, в работах С. В. Яблонского28,29, О. М. Каснм-Заде30,31 и Г. Г. Аманжаева32 рассматриваются классы, инвариантные относительно подстановки некоторого множества функций одной переменной. В работах Ю. В. Кузнецова33,34 рассматриваются классы, инвариантные относительно отождествления переменных.

Необходимо отметить, что существуют также подходы к классификации функций fc-значной логики на основе их свойств. Так, например, работах Нгуена Ван Хоа35,36,37 изучается подход, состоящий в разбиении множества замкнутых классов функций fc-значной логики на классы эквивалентности, где отношения эквивалентности определяются свойствами входящих в них функций.

Теперь отметим работы, относящиеся ко второму направлению исследований.

В работе Г. А. Бурле38 описана надрешетка класса Щ всех функций fc-значной логики от одной переменной, и показано, что эта надрешетка содержит конечное число замкнутых классов. В работе И. Розенберга39 описаны все минимальные классы в Р*., содержащие все селекторные функции, и показано, что при фиксированном к их конечное число. В работе А. А. Нечаева40 описаны все предполные классы, содержащие класс поли-

28 Яблонский А. Б. Об одном семействе классов функций алгебры логики, допускающих простую схемную реализацию // Труды III Всесоюзного съезда. — 195G. — Т. 2. — С. 149.

29 Яблонский А. Б. Об алгоритмических трудностях синтеза минимальных контактных схем // Проблемы кибернетики. Вып. 2. — М.: Физматгиз, 19S9. — С. 75-121.

30 Касим-Заде О. М. О метрических свойствах обобщенных инвариантных классов // Математические вопросы кибернетики. — 2006. — Вып. 15. — С. 9-34.

31 Касим-Заде О. М. О классах функций, инвариантных относительно подстановки функций от одной переменной // Вестник МГУ. Серия 1. Математика. Механика. — 1995. — №3. — С. 79-82.

32Аманжаев Г. Р.О замыкании ненулевого инвариантного класса Яблонского по операции отождествления переменных //Вестник МГУ. Серия 1. Математика. Механика. — 1995. — №3. — С. 76-79.

33 Кузнецов Ю. В. О классах булевых функций, инвариантных относительно отождествления переменных // Докл. АН СССР. - 1986. — Т. 290, № 4. - С. 780-785.

34 Кузнецов Ю. В. Исследование инвариантных классов, связанных с функциональными системами. — Автореферат диссертации на соискание ученой степени кандидата физико-математических наук. М.: МГУ, 1987.

^ Нгуеп Ван Хоа Об ¿-эквивалентности систем функций в многозначных логиках // Алгебра и логика. - 1988. - Т. 27, № 1. - С. 37-47.

36 Нгуен Ван Хоа О G-полных замкнутых классах fc-зпачной логики // Elektronische Informationsverarbeitung Und Kybernetik. — 1990. — T. 26, № 5/6. — С. 301-313.

37 Нгуен Ван Хоа К описанию семейства G-полных замкнз'тых классах fc-значной логики /'/' Кибернетика. — 1990. — if" 5. — С. 9-12.

38Бурле Г. Л.Классы fc-значной логики, содержащие все функции одной переменной //Дискретный анализ. — 1007. - №10. — С. 3-7.

39 Rosenberg I. G. Minimal clones I: The five types // Lectures in Universal Algebra (Proc. Conf. Szegeil 1983). - 1986. - V.43 - P.405-427.

40 Нечаев А. А. Критерий полноты систем функций р"-значной логики, содержащий операции сложения и умножения по модулю рп // Методы дискретного анализа в решении комбинаторных задач. — 1980. - Вып. 34. - С. 74-89.

номов. В работе С. С. Марченкова41 были описаны все классы в Р¡¿, содержащие дуальный дискриминатор, т. е. функцию вида

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

Отметим, что даже в случае такого узкого класса, как Uk, надрешетка этого класса является конечной и очень просто устроенной. Тем самым рассмотрение надрешеток замкнутых классов в значительной части случаев представляет собой чрезмерное упрощение задачи описания структуры решетки замкнутых классов в РПоэтому представляет интерес выработка новых подходов к изучению решетки классов в Рк, являющихся в некотором смысле промежуточными между подходом, связанным с изучением отдельных надрешеток в Рк, и непосредственным изучением всей решетки замкнутых классов функций fc-значной логики. В качестве одного из таких подходов в иастоящией работе предлагается некоторое обобщение операции суперпозиции. Для корректного обоснования данного обобщения заметим, что задачу описания надрешеткн некоторого фиксированного класса F функций fc-значной логики можно переформулировать следующим образом. Вместо стандартной операции суперпозиции для функций fc-значной логики мы можем рассмотреть модифицированную операцию суперпозиции, заключающуюся в реализации функций формулами, в которых помимо функциональных символов функций из исходного порождающего функционального множества могут быть также использованы функциональные символы любых функций из F. Тогда надрешетка класса F в точности совпадает с решеткой функциональных классов, замкнутых относительно данной модифицированной операции суперпозиции. Естественным ослаблением рассмотренной модифицированной операции суперпозиции является реализация функций формулами, в которых любые функции из F могут применяться только к содержащимся в формуле переменных. Настоящая работа посвящена исследованию различных вопросов, связанных

41 Марченков С. С. Клоновая классификация дуально дискримпнаторных алгебр с конечным носителем // Математические заметки. — 1997. — Т. Gl. Л'13. — С. 359-366.

42 Baker К. A., Pixley A. F. Polynomial interpolation and the Chinese remainder theorem for algebraic systems 11 Mathematische Zeitschrift. — 1075. - V. 143. - P. 165-174.

43 Ларионов В. Б. Замкнутые классы ¿-значной логики, содержащие классы монотонных пли самодвойственных функций. — Автореферат диссертации на соискание ученой степени кандидата физико-математических наук. М.: МГУ, 201Ü.

с реализацией функций такими формулами. Таким образом, в данной работе исследуется подход, представляющий из себя комбинацию описанных выше методов изучения усилений операции суперпозиции и методов изучения надрешеток замкнутых классов функций А;-значной логики. Исследуется операция суперпозиции, состоящая в реализации функций формулами над некоторым исходным функциональным множеством 21, в которых в качестве исходных элементарных подформул рассматриваются не символы переменных, а формулы, реализующие любые функции из некоторого функционального множества Р. Такая операция называется в работе операцией расширенной суперпозиции, а множество всех функций, реализуемых данными формулами, называется пополнением 21 относительно Р. Отметим, что при фиксированном Р такой оператор пополнения не всегда обладает всеми свойствами замыкания. В работе изучаются пополнения замкнутых классов булевых функций относительно функциональных множеств определенного типа. Для рассматриваемых функциональных систем исследуются вопросы выразимости и полноты.

Цель работы

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

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

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

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

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

1. Получен критерий выразимости булевых функций относительно операции расширенной суперпозиции.

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

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

4. Получены критерии полноты операции расширенной суперпозиции для класса Р2 и всех предполных замкнутых классов булевых функций.

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

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

Апробация диссертации

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

1. Специальный семинар "Функции многозначной логики и смежные вопросы" под руководством проф. А.Б. Угольникова, проф. P.M. Кол-пакова и проф. С.Б. Гашкова (неоднократно: МГУ, 2010-2013гг.).

2. Специальный семинар "Математические вопросы кибернетики" под руководством проф. О.М. Касим-Заде (МГУ, 2013 г.).

3. X Международный семинар "Дискретная математика и ее приложения" (Москва, 1-6 февраля 2010г.).

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

5. Международная научная конференция "Ломопосов-2011" (Москва, 11-15 апреля 2011г.).

6. Научная конференция "Ломоносовские чтения" (Москва, 14-23 ноября 2011г.).

7. Научная конференция "Ломоносовские чтения" (Москва, 16 24 апреля 2012 г.).

8. Научная конференция "Ломоносовские чтения" (Москва, 15-2G апреля 2013 г.).

Публикации

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

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

Диссертационная работа состоит из Введения, пяти глав и списка литературы. Полный объем работы составляет 119 страниц. Список литературы содержит 53 наименования. Утверждения в диссертации нумеруются тройками чисел, где первое число обозначает номер главы, второе — номер раздела внутри главы, а третье — номер утверждения внутри раздела. Во Введении принята отдельная нумерация теорем, после номера каждой теоремы в скобках указан номер, который имеет соответствующее утверждение в тексте диссертации.

Краткое содержание диссертации

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

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

Пусть Р — множество булевых функций, содержащее все селекторные функции и замкнутое относительно операций введения несущественных переменных и переименования переменных (включая отождествление). Будем называть такие множества инвариантными классами. Пусть .Р — инвариантный класс булевых функций, 21 — некоторое множество булевых функций. Пару таких множеств (Р, 21) будем называть типом булевых функций. Определим понятие формулы над типом и = (Р, 21) индуктивно.

1. Выражение ...,Ж;п), где д € ж,-,,... ,х{п — символы переменных, п > 1, является формулой над II. Такие формулы будем называть тривиальными.

2. Пусть Фь ..., Ф„ — формулы над V, п > 1, а /(хь ..., хп) € 21. Выражение Ф вида /(Фх,..., Фп) является формулой над II. Будем называть Ф1,..., Ф„ подформулами формулы Ф. Формулу Ф и все подформулы формул Ф1,..., Фп будем также называть подформулами формулы Ф.

Пусть (Р, 21) — произвольный тип булевых функций. Пополнением системы 21 относительно класса Р назовем множество всех булевых функций, реализуемых нетривиальными формулами над типом (Р, 21) (обозначение [21]^). Пусть В — замкнутый класс булевых функций. Тип (.Р, 21) называется полным в В, если [21]р = В.

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

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

Пусть Я С Еп, где Е = {0,1}, п > 1. Пусть г(п) — отображение из множества Я в Е, которое задается функцией ... ,хп), где XI,..., хп — набор переменных. Функцию г^(х х,... ,хп) будем называть п-местпой частичной булевой функцией, определенной на множестве Я. Если а € Еп \ Я, то будем говорить, что функция не определена на наборе а.

Пусть п > 1, Л С Еп, г(х'х,... ,х„) — частичная булева функция, определенная на множестве Я. Будем говорить, что булева функция /(жх,... ,хп) доопределяет частичную функцию г(х\,... ,хп), если для любого набора а € Я выполнено равенство /(а) = г(а). Функцию ¡(х\,...,хп) будем называть доопределением частичной функции г(х х,...,х„).

Пусть А — замкнутый класс булевых функций, п.к > 1. Рассмотрим множество Я С Еп н частичную функцию г(х\,... ,хп), определенную на множестве Я. Функцию г(х\,...,хп) будем называть согласованной с замкнутым классом А, если существует такое доопределение /(х\,..., хп) функции г(жх, ...,хп), что / е А.

Пусть п > 1, к(х1,...,хп) — булева функция, Р — инвариантный класс булевых функций, Р(п) = {Л,...,/;}, I > 1. Рассмотрим множества Еп = {71,у2,... ,72"}, Я = ..., I2"}, где <5* = (/1(7')! • • ■. /((71)) € Е1, г = 1,...,2", и частичную функцию г(х\,..., ж;), определенную на множестве Я, и такую, что г(<5') = /1(7') для всех г = 1,..., 2". Назовем функцию г(:Гх,..., х{) декомпозицией функции Л относительно инвариантного класса Е.

Основным результатом главы 2 является

Теорема 1. Пусть А — замкнутый класс булевых функций, Р — инвариантный класс, /а(.х'х,... ,хп) е Р2, п > 1. Тогда Л, 6 если и только если декомпозиция функции И относительно Е является согласованной с классом А.

В главе 3 исследуется вопрос о представлении пополнений замкнутых классов в виде пересечения конечного числа других пополнений. Пусть А — замкнутый класс булевых функций. Будем называть А разложимым, если существуют такие отличные от А замкнутые классы ..., Вь, к > 2, что

А = ¿?1 П ... П В к- Будем называть А универсально разложимым, если существуют такие отличные от А замкнутые классы С\,... ,Ст, т > 2, что для произвольного инвариантного класса Р выполняется соотношение

[А]Р = [СгУ П ... П [Ст}Е.

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

Теорема 2. Произвольный замкнутый класс булевых функций, отличный от класса М17, универсально разложим тогда и только тогда, когда он разложим. Класс М17 является разложимым, но не является универсально разложимым.

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

В главе 4 исследуются пополнения замкнутых классов булевых функций относительно других замкнутых классов. Вводится понятие V-пополнения-, пополнение [Л]^ называется ^-пополнением, если А и Р являются замкнутыми классами, содержащими неконстантные функции. Приводится полное описание множества всех Р-пополнений. Здесь и далее обозначения для замкнутых классов взяты согласно работам А.Б. Уголышкова44,4''.

Положим

Л = {Моъ Ь, Кои Т0, О7", 5, Би, 17т}, 7 = {Мт,1, Ьо, Ьи 1т, вЬ, Каи Аи, ви, Т0, ТиТ01,О"1, О0"\ МО™, 1т, 1?, М /{", 5,5М, 501},

где т = 2, 3,..., оо. Рассмотрим всевозможные типы (Р, А), такие, что А £ Л, Р € Т. Соответствующие им пополнения будем называть базовыми V-пополнениями.

Пусть А С Р2. Обозначик£_через А* множество всех функций д 6 таких, что д* е А, а через А множество всех функций д е таких, что д 6 А. Обозначим через А(п), где п > 1, множество всех функций /(х\,..., хп) от п переменных, содержащихся в множестве А.

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

45 Угольников А. Б. О замкнутых классах Поста // Известия ВУЗов. Математика. — 1988. — №7(:114). - С. 79-88.

Положим ф2 = -F- Положим = U {Л U А}, где

Ле/

/ = {Toi, Км, Au, Lau Мои 0"\ Гп, ОЦ', /{", МО™, IT, SM}, m = 2,3,..., оо.

Пусть F замкнутый класс булевых функций. Обозначим через G'p (m = 2,3,..., оо) множество всех булевых функций д{х\,..., хп), п > 1, удовлетворяющих следующему условию: для любого q, 1 < q < m, и для любых q наборов, на которых функция д{х\,... ,хп) принимает нулевое значение, существует функция f(xi,... ,хп) S F, также принимающая на этих наборах нулевое значение. Обозначим через © множество, состоящее из классов GgV, m = 2,3,..., оо.

Пусть А — замкнутый класс булевых функций. Будем обозначать через 1{А) множество всех булевых функций h[xi,..., хп), таких, что существует функция g(xi,... ,хп) € А, такая, что /;, < д. Будем обозначать через Ь(А) множество всех булевых функций h(xi,... ,хп), таких, что существует функция д{х\,... ,хп) € А, такая, что h > д. Несложно видеть, что Ь(А) = 1(А)*. Обозначим через S множество, состоящее из классов l(S), ¿(Soi), l(SM),b{S), b(S01), b(SM).

Обозначим через AS множество всех таких функций f(x\,...,xn), п > 1, что для любых двух противоположных наборов а и à длины п выполняется соотношение /(а) = /(5). Положим 3 = {SU

Пусть А — замкнутый класс. Обозначим через К{А) множество всех функций f(x\,. ■., хп), п > 1, представимых в внде/(ж1,...,х„) = gi{xi,...,xn)k...kgk(xu...,xn), к > 1, где gi(x\,..., хп) € А, 1 < i < к. Положим

£ = {K(SU), K(L), K(L0), K{Li), K(Lai), K(SL)}.

Теорема 3. Множество G булевых функций является базовым V-пополиением тогда и только тогда, когда выполняется соотношение

Сеёизи©и£иф^иф2-

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

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

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

То П (То П Щ и {1}, 701 П с|01 П Я|01,

т = 2,3,..., оо, и двойственных к перечисленным. Обозначим через © множество, состоящее из классов, содержащихся в классе ©, классов Т\С\1(Зо\),Т\С\1{ЗМ), Мо\П1(ЗМ), классов, получающихся из них добавлением констант, а также классов, двойственных перечисленным. Обозначим через 3 множество, состоящее из классов 5иЛ5,,ТоП(5иЛ5),Т1П(5'иЛ5'), а также двойственных к перечисленным. Обозначим через £ множество, состоящее из классов, содержащихся в множестве £, классов, получающихся из них добавлением констант, а также классов, двойственных к перечисленным.

Основным результатом главы 4 является следующая теорема.

Теорема 4. Множество С булевых функций является V-пополнением тогда и только тогда, когда выполняется соотношение

СббиЗиби£и(р2иф2.

В главе 5 рассматриваются вопросы полноты операции расширенной суперпозиции. Рассматриваемая задача состоит в том, что для данных замкнутых классов А и В, где А С. В необходимо найти семейство всех таких инвариантных классов Р С В, что [А]р = В. Данное семейство инвариантных классов обозначается через д\(А,В). В главе 5 описаны все семейства В), такие, что В = Р2, Ь, Та, Т\, Б, А/, а А - замкнутый класс, такой, что АС В.

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

Александра Борисовича Угольникова , которому автор выражает благо-

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

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

[1] Акулов Я. В. О полноте систем функций для классов расширенной суперпозиции // Вестник МГУ. Серия 1. Математика. Механика. — 2011. №1. С. 36 41.

[2] Акулов Я. В. Критерий универсальной разложимости замкнутых классов булевых функций // Известия Иркутского университета. Математика. - 2013. — № 3. - С. 2-24.

[3] Акулов Я. В. Критерии полноты для классов расширенной суперпозиции // Дискретная математика и ее приложения: Материалы X Международного семинара (Москва, 1 С февраля 2010 г.). 2010. С.167 109.

[4] Акулов Я. В. О классах булевых функции, замкнутых относительно операции расширенной суперпозиции // Проблемы теоретической кибернетики. Материалы XVI Международной конференеции (Нижний Новгород, 20-25 июня 2011 г.). - 2011. - С. 20-24

[5] Акулов Я. В. О полноте систем функций в классе Т\ для классов расширенной суперпозиции // Дискретная математика и ее приложения: Материалы XI Международного семинара (Москва, 1823 июня 2012 г.). — 2012. - С.184-180.

Подписано в печать: 24.03.2015 Объем: 0,6 п.л. Тираж: 100 экз. Заказ № 363 Отпечатано в типографии «Реглет» 119526, г. Москва, пр-т Вернадского, д. (495) 363-78-90; www.reglet.ru