Замкнутые классы k-значной логики, содержащие классы монотонных или самодвойственных функций

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

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

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

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

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

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

Следуя авторам, будем обозначать через Pk множество всех &—значных функций.

Задача описания всех замкнутых классов функций двухзначной логики была решена Э. Постом [75, 76]. Было показано, что в Pi счетное число замкнутых классов, каждый из которых имеет конечный базис. Существует в точности пять предполных классов, образующих критериальную систему для разрешения проблемы полноты. В более простой форме результаты Поста появились позднее в СССР и Франции [62, 66, 67, 70]. В дальнейшем рядом авторов были предложены различные подходы к изучению замкнутых классов булевых функций, а также несколько вариантов доказательств результатов Поста (в хронологическом порядке: С. В. Яблонский — [60, 61]- С. С. Марчен-ков — [25]- Г. П. Гаврилов — [5, 6]- А. Б. Угольников — [53]- С. С. Марченков и А. Б. Угольников — [36]). Отметим результаты А. И. Мальцева [22, 23], предложившего алгебраический подход. В рамках этого подхода рассматривается так называемая алгебра — множество функций &—значной логики, замкнутое относительно некоторого набора операций (через эти операции выражается операция суперпозиции).

В [57] С. В. Яблонским были описаны все 18 предполных классов в Им же в [58] описываются некоторые предполные классы в и их свойства для произвольных к (также см. [8]). И. Розенбергом в [77] были окончательно описаны все предполные классы fc-значной логики. Было показано, что они образуют шесть семейств. Сами классы описываются через множества сохраняемых предикатов. Детальное описание и свойства указанных семейств и соответствующих предикатов можно найти в работе [63].

В [9] была установлена асимптотика числа предполных классов в Рк-Оказалось, что это число растет очень быстро с ростом к, поэтому критериальная система из предполных классов для разрешения проблемы полноты является неэффективной. Но самые большие трудности в изучении решетки замкнутых классов к-значных функций показал результат Ю. И. Яно-ва, А. А. Мучника [64], где было доказано, что в Рк существуют замкнутые классы со счетным базисом, а также замкнутые классы, не имеющие базиса. Следствием этого результата является континуальная мощность множества замкнутых классов fc-значных функций при к ^ 3. Оказалось, что описать решетку классов в Рк для к ^ 3, как это было сделано для невозможно.

Отношение сохранения предиката функцией было определено А. В. Кузнецовым в [10]. В работе [11] он указывал на возможность построения теории Галуа для решетки замкнутых классов булевых функций. Само построение для решетки замкнутых классов &—значных функций было проведено независимо В. Г. Боднарчуком, JI. А. Калужниным, В. Н. Котовым, Б. А. Ромовым в [2] и Д. Гейгером в [69]. Был установлен антиизоморфизм между частично упорядоченным множеством замкнутых классов fc-значных функций, содержащих все селекторные функции и частично упорядоченным множеством замкнутых относительно некоторых операций классов предикатов, содержащих все диагонали. Этот результат позволил изучать решетку замкнутых классов функций новым методом. Сначала устанавливаются требуемые свойства для решетки замкнутых классов предикатов, а потом, используя антиизоморфизм, указанные свойства переносятся на решетку замкнутых классов функций. Отметим в этой области работу С. С. Марченкова [26], в которой доказана минимальность предикатов, задающих предполные классы в Рк, к ^ 2. С. В. Яблонским в работе [59] рассмотрена связь предикатной опису-емости замкнутого класса функций со строением его верхней окрестности в решетке замкнутых классов.

В связи с указанными выше трудностями работы по изучению решетки замкнутых классов в Р&для к ^ 3 разделились на два направления. Первое из них — разработка более сильных операторов замыкания, которые позволяли бы сжимать решетку замкнутых классов до счетного или конечного множества, которое уже возможно описать и исследовать. Второе направлениеизучение различных подмножеств решетки замкнутых классов в Pk.

В первом направлении отметим работу А. В. Кузнецова [12], в которой вводится понятие параметрического замыкания и доказывается, что существует 25 параметрически замкнутых классов булевых функций. С. С. Марченковым в работе [29] изучается параметрическое и lL-замыкание.

5-замыкание, при котором в каждом замкнутом классе наряду с функцией есть двойственные ей функции, исследуется в работах [27, 40, 41]. В [31] С. С. Марченковым описаны все^{-замкнутые} классы трехзначных функций. В работах [33, 34] определяется эквациональное замыкание и доказывается, что в Pk существует конечное число эквационально замкнутых классов. Ряд работ посвящен описанию операторов замыкания с дополнительными операциями программного типа. К таким работам относятся [49, 50], где вводится операция разветвления по предикату и описываются все замкнутые с использованием указанной операции классы в Pk (их конечное число). Другие операторы замыкания описаны в работах [7, 39, 51, 52]. Большая часть этих операторов позволяет сжать решетку замкнутых классов к-значных функций до конечного множества.

Данная диссертация принадлежит ко второму направлению по изучению решетки замкнутых классов fc-значных функций при к ^ 3. В работе И. Ро-зенбергом [77] изучены все предполные классы в решетке замкнутых классов.

6-значных функций (то есть первый уровень указанной решетки), в его же работе [79] изучается второй уровень решетки в PkВ случае к = 3 в работе [71] второй уровень решетки описан полностью.

Минимальные клоны (то есть замкнутые классы, содержащие все селекторные функции) в Рк описаны в работе [78], там же доказано, что при фиксированном к их конечное число.

Надструктура классов самодвойственных функций в Р3 изучалась в работе [35]. В [80] исследована надструктура классов линейных функций в случае, когда число к свободно от квадратов. Г. А. Бурле в работе [4] описал все замкнутые классы в Р&-, содержащие все функции одной переменной.

Ряд работ посвящен изучению надструктуры класса полиномов. В [58] было показано, что для простого к любая fc-значная функция может быть представлена полиномом по модулю к, то есть класс полиномов при указанном к совпадает со всем Pk. Там же было доказано, что при составном к класс полиномов не является даже предполным. А. А. Нечаевым в работе [42] описаны все предполные классы, содержащие класс полиномов.

А. Н. Череповым в работах [55, 56] и Д. Г. Мещаниновым в [37] была полностью описана надструктура класса полиномов при составном к, свободном от квадратов, а также при к = рр2, где Pi, Р2 ~ простые числа. В [38] Д. Г. Мещаниновым были установлены необходимые и достаточные условия представимости А—значных функции полиномом по модулю к, приведен алгоритм построения полинома по функции. А. Б. Ремизов в [43] показал, что при к = рр2, где р, Р2 — простые числа, существует бесконечная цепочка содержащих друг друга различных замкнутых классов, каждый из которых содержит класс полиномов. Данный результат свидетельствует о сложности надструктуры класса полиномов в общем случае.

В [28] С. С. Марченковым были описаны все классы в Pk, содержащие дуальный дискриминатор, то есть функцию: х: если х — у] z, если х фу.

Отметим, что конечность множества подобных классов следует из работы [65]. В [32] описаны все 144 замкнутых класса функций в Рз, содержащие тернарный дискриминатор.

В работах [68, 72, 73] рассматриваются подклассы класса Р^ = {/ Е Рк-> f (x)? {0,1,.,? — 1} для любого 5}. Для каждой функции из Pk, i определяется проекция — функция из Pi, получающаяся сужением области определения до ЕИзучается вопрос о мощности множества 1(A) классов такого, что 1(A) С Рк 2 и проекция любого класса из 1(A) равна А.

К смежному направлению относится исследование решетки замкнутых классов частичных функций (Р£). В работе [54] Р. Фрейвальдом была решена проблема полноты для случая к = 2, а Б. А. Ромовым в [48] — для к ^ 3. В работе [3] исследовалась надрешетка в Р2* предполных классов из Р2. Подробный обзор изучения решетки замкнутых классов частичных &—значных функций можно найти в [74].

Еще одним близким направлением является исследование решетки вектор-функций. В. А. Тайманов в [50] описал все замкнутые классы вектор функций двухзначной логики (Р$) — Б. А. Ромов в работах [44−47] получил альтернативное описание указанных классов, перенес результаты теории Галуа на прямые произведения алгебр Поста, описал все минимальные fc-основые предикаты.

Целью данной диссертации является изучение надструктуры замкнутых классов монотонных и самодвойственных функций в Р&при произвольном к^Ъ. Среди шести семейств предполных классов в Pj~ при к ^ 3, установленных в [77], существует два, обозначаемые через М и S и являющиеся соответственно подмножествами всех монотонных и самодвойственных классов в Рк.

В работе [24] В. В. Мартынюком установлено, что класс монотонных функций, сохраняющих частичный порядок г, принадлежит семейству М (то есть является предполным) тогда и только тогда, когда г имеет в точности единственный минимальный и единственный максимальный элементы.

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

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

В диссертации ставятся следующие задачи:

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

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

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

4. Описать основные свойства надрешетки классов монотонных функций.

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

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

Объем диссертации 158 страниц. Работа состоит из введения, четырех глав и списка литературы. Во введении.

1. Арнольд И. В. Теоретическая арифметика. Учпедгиз, Москва, 1938.

2. Бондарчук В. Г., Калужнин В. А., Котов В. Н., Ромов Б. А. Теория Талу, а для алгебр Поста // Кибернетика. 1969. № 3. С. 1−10. № 5. С. 1−9.

3. Алексеев В. Б., Вороненко А. А. О некоторых замкнутых классах в частичной двухзначной логике // Дискретная математика. 1994. Т. 6, № 4. С. 58−79.

4. Бурле Г. А. Классы k-значной логики, содержащие все функции одной переменной // Дискретный анализ. 1967. № 10. С. 3−7.

5. Гаврилов Г. П. Индуктивное представление булевых функций и конечная порождаемость классов Поста // Алгебра и логика. 1984. Т. 23, № 1. С. 3−26.

6. Гаврилов Г. П. Функциональные системы дискретной математики. М.: Изд-во МГУ, 1985.

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

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

9. Захарова Е. Ю., Кудрявцев В. Б., Яблонский С. В. О предполных классах в k-значной логике // Доклады АН СССР. Т. 186, № 3. С. 509−512.

10. Кузнецов А. В. Алгебра логики и ее обобщения // Яновская С. А. Математическая логика и основания математики. Математика в СССР за сорок лет, Физматгиз, 1959. Т. 1. С. 13−120.

11. Кузнецов А. В. Структуры с замыка-пием и критерии функциональной полноты // Успехи матем. наук. 1961. Т. XVI, № 2(98). С. 201−202.

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

13. Ларионов В. Б. О некоторых свойствах монотонных функций в многозначных логиках // Тезисы докладов XV Международной конференции «Проблемы теоретической кибернетики» (Казань, 2—7 июня 2008 г.), издательство «Отечество», Казань, 2008. С. 71−72.

14. Ларионов В. Б. О полооюении некоторых классов монотонных к-знач-ных функций в решетке замкнутых классов // Дискретная математика. 2009. Т. 21, № 5. С. 111−116.

15. Ларионов В. Б. О монотонных замкнутых классах функций многозначной логики с бесконечной надструктурой // Материалы VII молодежной научной школы по дискретной математике и ее приложениям (18−23 мая 2009 г.), М.: ИПМ им. М. В. Келдыша РАН, 2009. С. 7−12.

16. Ларионов В. Б. О положении самодвойственных k-значных функций в решетке замкнутых классов // Сборник статей молодых ученых факультета ВМК МГУ, вып. 6, издательский отдел факультета ВМК МГУ, Москва, 2009. С. 90−105.

17. Ларионов В. Б. О надструктуре классов монотонных функций в многозначных логиках // Сборник статей молодых ученых факультета ВМК МГУ, вып. 7, издательский отдел факультета ВМК МГУ, Москва, 2009.

18. Мальцев А. И. Итеративные алгебры и многообразия Поста / Алгебра и логика. 1966. Т. 5, № 2. С. 5−24.

19. Мальцев А. И. Итеративные алгебры Поста. Новосибирск: Изд-во НГУ, 1976.

20. Мартынюк В. В. Исследование некоторых классов функций в многозначных логиках // Проблемы кибернетики, вып. 3. М.: Наука, 1960. С. 49−61.

21. Марченков С. С. К существованию конечных базисов в замкнутых классах булевых функций // Алгебра и логика. 1984. Т. 23, № 1. С. 88−99.

22. Марченков С. С. Предполнота замкнутых классов в Рпредикатный подход // Математические вопросы кибернетики, вып. 6. М.: Наука, 1996. С. 117−132.

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

24. Марченков С. С. Клоповая классификация дуально дискриминаторных алгебр с конечным носителем // Математические заметки. 1997. Т. 61, вып. 3. С. 359−366.

25. Марченков С. С. О выразимости функций многозначной логики в некоторых логико-функциональных языках // Дискретная математика. 1999. Т. 11, № 4. С. 110−126.

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

27. Марченков С. С. S-классификация функций трехзначной логики. Физматлит, Москва, 2001.

28. Марченков С. С. Дискриминаторные классы трехзначной логики // Математические вопросы кибернетики. 2003. Вып. 12. С. 12−26.

29. Марченков С. С. Эквационалъное замыкание // Дискретная математика. 2005. Т. 17, № 2. С. 117−126.

30. Марченков С. С. О строении эквационалъно замкнутых классов // Дискретная математика. 2006. Т. 18, №- 4. С. 18−30.

31. Марченков С. С., Деметрович Я., Ханнак JI. О замкнутых классах самодвойственных функций в Рз // Методы дискретного анализа в решении комбинаторных задач, вып. 34. Новосибирск, 1980. С. 38−73.

32. Марченков С. С., Угольников А. Б. Замкнутые классы булевых функций. М.: Изд-во ИПМ АН СССР, 1990.

33. Мещанинов Д. Г. О надструктуре класса полиномов в Р^ // Тезисы докладов VII Всесоюзной конференции «Проблемы теоретической кибернетики» (18−20 сентября 1985). Ч. I, Иркутск, 1985, С. 135.

34. Мещанинов Д. Г. Метод построения полиномов для функций к-значной логики // Дискретная математика. 1995. Т. 7, № 3. С. 48−60.

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

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

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

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

39. Ремизов А. Б. О надструктуре замкнутого класса полиномов по модулю к // Дискретная математика. 1989. Т. 1, № 1. С. 3−15.

40. Ромов Б. А. Алгоритм решения проблемы полноты в классе векторных функциональных систем // Математические модели сложных систем, Киев: ИК АН УССР, 1973. С. 151−155.

41. Ромов Б. А. О решетке подалгебр прямых произведений алгебр Поста конечной степени j j Математические модели сложных систем, Киев: ИК АН УССР, 1973. С. 156−158.

42. Ромов Б. А. О полноте на квадрате функций алгебры логики и в системе Pkx Pi // Кибернетика. 1987. № 4. С. 9−14.

43. Ромов Б. А. Об одной серии максимальных подалгебр прямых произведений алгебр конечнозначных логик // Кибернетика. 1989. № 3. С. 11−16.

44. Ромов Б. А. О проблеме полноты в алгебре частичных функций многозначной логики // Кибернетика. 1990. № 1. С. 102−106.

45. Соловьев В. Д. Замкнутые классы k-значной логики с операцией разветвления по предикату // Дискретная математика. 1990. Т. 2, № 4. С. 19−25.

46. Тайманов В. А. О функциональных системах k-значной логики с операциями программного типа // Доклады АН СССР. 1983. Т. 268, JV5 6. С. 1307−1310.

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

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

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

50. Фрейвальд Р. Критерии полноты для частичных функций алгебры логики и многозначных логик // Доклады АН СССР. 1966. Т. 167, № 6. С. 1249−1250.

51. Черепов А. Н. Описание структуры замкнутых классов в Pk, содержащих класс полиномов // Проблемы кибернетики, вып. 40. М.: Наука, 1983. С. 5−18.

52. Черепов А. Н. Надструктура класса сохранения отношений сравнения в многозначной логике // Тезисы докладов XII Всесоюзной конференции «Проблемы теоретической кибернетики» (18−20 сентября 1985). Ч. I, Иркутск, 1985. С. 135.

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

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

55. Яблонский С. В. О строении верхней окрестности для предикатно-опи-суемых классов в Рк // Доклады АН СССР. 1974. Т. 218, № 2. С. 304−307.

56. Яблонский С. В. О некоторых результатах в теории функциональных систем // Труды Международного конгресса математиков, Хельсинки, 1978. С. 963−971.

57. Яблонский С. В. О замкнутых классах в Р2 / / Проблемы кибернетики, вып. 39. М.: Наука, 1982. С. 262.

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

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

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

61. Baker К. A., Pixley A. F. Polynomial interpolation and the Chinese remainder theorem for algebraic systems // Math. Z. 1975. Volume 143. P. 165−174.

62. Benzaken C. Definitions et proprieties de certains families de fonctions booleennes croissantes // C. R. Acad. Sci. Paris. 1964. T. 259, group I. P. 1369−1371.

63. Benzaken C. Les families de fonctions booleennes deduites de certaines families de fonctions booleennes croissantes. Criteres de determination de I’indice d’une function croissante // C. R. Acad. Sci. Paris. 1965. T. 260, group I. P. 1528−1531.

64. Burosch G., Dassow J., Harnau W., Lau D. On subalgebras of an algebra of predicates // J. Inf. Process Cybern. 1985. EIK 21, ½. P. 9−22.

65. Geiger D. Closed systems of functions and predicates // Pacific J. Math. 1968. Volume 27. P. 95−100.

66. Kuntzman J. Algebre de Boole. Paris Dunod, 1965.

67. Lau D. Submaximale Klassen von P% / / J. Inf. Process. Cybern. 1982. EIK 18, 4/5. P. 227−243.

68. Lau D. Uber abgeschlossene Mengen linearer Funktionen in mehrwertigen Logiken // J. Inf. Process. Cybern. 1988. EIK 24, 7/8. P. 367−381.

69. Lau D. Uber abgeschlossene Teilmengen von Pkj2 // JInf. Process. Cybern. 1988. EIK 24, 10. P. 495−513.

70. Lau D. Function algebras on finite sets. Springer Monographs in Mathematics, 2006.

71. Post E. L. Introduction to a general theory of elementary propositions // Amer. J. Math. 1921. Volume 43, № 4. P. 163−165.

72. Post E. L. Two valued iterative systems of mathematical logic // Annals of Math. Studies, Princeton Univ. Press, 1951. V. 5.

73. Rosenberg I. G. La structure des fonctions de plusiers variables sur un ensemble fini // Comptes Rendus Acad. Sci. Paris. 1965. Volume 260. P. 3817−3819.

74. Rosenberg I. G. Minimal clones I: The five types // Lectures in Universal Algebra (L. Szabo, A. Szendrei eds.), Colloq. Math. Soc. J. Bolyai 43, North Holland, 1986. P. 405−427.

75. Rosenberg I. G. Completeness properties of multi-valued logic algebras // Computer science and multivalued logic: Theory and Applications, second edition, D.C. Rine, ed., Amsterdam: North-Holland, 1984. P. 144−186.

76. Szendrei A. On closed sets of linear operations over finite sets of squarefree cardinality // Electron. Inform. Verarb. und Kibern. 1978. Volume 14,14. P. 547−559.