О конечной порожденности предполных классов монотонных функций многозначной логики

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

В теории функций многозначной логики важное место занимают задачи классификационного характера. Одной из наиболее естественных и хороню изученных классификаций является разбиение множества Рвсех функций А'-значпой логики па классы, замкнутые относительно операции суперпозиции (см. [20, 10, 8]). Все замкнутые классы функций двузначной логики были описаны Э. Постом [38, 39], который показал, что число таких классов счетно. В книге [21] дано более простое изложение этих результатов. Описание классов Поста содержится также в работах [30, 16, 13, 15, 41, 33]. Некоторые важные свойства замкнутых классов булевых функций изучены в [5, 6, 12, 7].

Несмотря на то, что многозначные логики во многом похожи па двузначную, имеют место и принципиальные различия. К их числу относится пример континуального семейства замкнутых классов в при к > 3, приведенный в работе 10. И. Янова и А. А. Мучника [24]. Континуальность семейства всех замкнутых классов Д при к > 3 приводит к значительным трудностям при их изучении. К настоящему времени изучены только некоторые семейства замкнутых классов в Д. К числу таких семейств относятся иредполные классы функций. Из теоремы А. В. Кузнецова [9] (см. также [19, 20]) следует, что при любом к > 2 в Д существует конечное число предполных классов. При к = 3 описание всех предполных классов было получено С. В. Яблонским ([17, 18[). Отдельные семейства предполных в Р^ классов при к > 4 были найдены в работах [18, 11, 34, 35, 36, 37]. Полное описание предполных классов в Р^ было получено И. Розенбергом [42, 43] (см. также [22, 23, 8, 14, 4]), который выделил шесть семейств предполных классов: классы самодвойственных функций — классы типа Р, классы линейных функций — классы типа 1Ь, классы функций, сохраняющих разбиения множества Е^ = {0,1,., к — 1} — классы типа Е, классы функций, сохраняющих центральные отношения — классы типа С, классы функций, сохраняющих сильно голоморфные прообразы /1-адических элементарных отношений — классы типа В, и классы функций, монотонных относительно частично упорядоченных множеств с наименьшим и наибольшим элементами — классы типа О (мы пользуемся обозначениями из [23]).

Одной из наиболее важных проблем, связанных с семействами замкнутых классов функций многозначной логики, является задача о конечной порожденное&trade-, то есть задача о выразимости всех функций из замкнутого класса формулами над некоторым конечным множеством функций, принадлежащих этому же классу. Из результатов Поста [38, 39] следует, что каждый замкнутый класс булевых функций имеет конечный базис. В многозначных логиках этот результат не имеет места: для любого к > 3 в Рк существуют замкнутые классы как со счетным базисом, так и не имеющие базиса (см.

Рис. 1: множество V%.

24]). К настоящему времени отсутствует полное описание всех конечно-порожденных классов в Рк при к > 3 даже для семейства преднолных классов. Д. Jlay [31, 32] показала, что любой преднолпый класс в Д из семейств Р, L, Е, С и В порождается конечным числом функций. Для преднолных классов всех функций, монотонных относительно частично упорядоченных множеств (классов из семейства О) этот результат верен, вообще говоря, лишь при к < 7 (см. [31, 32]). Г. Тардошем [44] приведен пример такого частично упорядоченного множества из восьми элементов, что предполный класс всех функций, монотонных на этом множестве, не имеет конечного базиса (см. рис. 1).

К настоящему времени получен ряд достаточных условий конечной порожденности предполных классов монотонных функций. Из интерполяционной теремы К. Бейкера и А. Пиксли [25] (см. также [26, 27, 28]) следует, что если в замкнутом классе содержится мажоритарная функция, то класс является конечно-порожденным. В работе [27] приводится следующее условие: предполный класс всех функций, монотонных на частично упорядоченном множестве V, имеет конечный базис, если множество V представляется в виде С /С, где С — решетка, а /С — выпуклое подмножество не содержащее наименьшего и наибольшего элементов? (определения см. в [3]). Отсюда, в частности, следует конечная порожденность классов функций, монотонных относительно решеток и линейно упорядоченных множеств. В [28] показано, что это условие эквивалентно отсутствию в множестве V четверки элементов а, Ь, с, d, таких, что а, Ь < с, элементы, а и b не имеют точной верхней грани и элементы end не имеют точной верхней грани. Доказательство конечной порожденности класса монотонных функций, приведенное в работе [27], опирается на существование в классе мажоритарных функций. Отметим, что условие существования мажоритарных функций в классе не является необходимым для конечной порожденности этого класса даже для замкнутых классов булевых функций (см. [39]). Примеры частично упорядоченных множеств, таких что классы всех функций, монотонных относительно этих множеств, являются конечно-порожденными, но не содержат мажоритарных функций, приведены в работе [29], однако эти классы не являются предполными.

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

Дадим некоторые определения.

Обозначим через, А семейство всех конечных частично упорядоченных множеств с наименьшим и наибольшим элементами. Число элементов множества V обозначается через |V. Шириной частично упорядоченного множества V называется максимальное число попарно несравнимых элементов V) ширина множества V обозначается через Wp. Обозначим через Л2 подсемейство семейства А, состоящее из всех множеств V, для которых выполняются неравенства Р > 2 и wp < 2- множества из А2 будем называть множествами ширины два.

Пусть V? А2, a, b G V, элементы, а и b несравнимы. Точная верхняя грань элементов, а и b обозначается через sup (a, b). Пусть несравнимые элементы, а и b не имеют точной верхней грани, пусть cud — две минимальные верхние грани элементов, а и и существует е — точная верхняя грань элементов си d. Тогда е называется точной верхней гранью второго порядка элементов, а и b и обозначается через sup2(a, b).

Функция /i: Vn —> V, где п > 3, называется мажоритарной, если для любых a, b EV выполняются равенства a, b,., b) = fi (b, a, b,., b) =. = ц (Ь, ., b, a) = b.

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

Теорема 1 (теорема 2.4.2). Пусть V — частично упорядоченное множество из семейства Аг, такое, что для любых двух несравнимых элементов, а и b н 'Р существует либо sup (a, b), либо sup2(a, b). Тогда класс Мр всех функций, монотонных относительно множества V, является конечно-порожденным.

Теорема 2. (теорема 3.1.1). Пусть V — частично упорядоченное множество из семейства А2, такое, что найдутся два несравнимых элемента, а и Ь, для которых в V не существует ни sup (a, b), ни sup2 (a, b). Тогда класс Мр всех функций, монотонных относительно множества V, не имеет конечного базиса.

Из теорем 1 и 2 следует критерий конечной порожденное&tradeкласса М-р.

Теорема 3 (теорема 3.2.1). Пусть V — частично упорядоченное множество из семейства А2. Класс Мр всех функций, монотонных относительно множества V, является конечно-порожденным тогда и только тогда, когда для любых двух несравнимых элементов, а и b в V существует либо sup (a, Ь), либо sup2(a, 6).

Этот результат можно переформулировать следующим образом.

Теорема 4 (теорема 3.2.2). Пусть V G А2. Класс Мр является конечно-порожденным тогда и только тогда, когда он содержит некоторую мажоритарную функцию.

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

Теорема 5 (теорема 3.2.3). Для любого частично упорядоченного множества V ширины два с наименьшим и наибольшим элементами существует алгоритм распознавания конечной порожденное&tradeкласса Мр.

Нетрудно показать, что этот алгоритм имеет полиномиальную сложность (см. [1, 2]).

Следует отметить, что семейству А2 принадлежит множество, приведенное в работе [44]. Отметим также, что начиная с к — 10 в А2 существуют множества из к элементов, которым соответствуют конечно-порожденные предполные классы монотонных функций, но для которых не выполняются условия из работ [27] и [28].

Опишем кратко содержание работы.

Работа состоит из введения, трех глав и списка литературы.

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

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

В этой главе рассматривается семейство А^ частично упорядоченных множеств ширины два с наименьшим и наибольшим элементами, состоящее из всех таких множеств V, что для любой пары несравнимых элементов, а и Ь в V существует либо кпр (а, Ь), либо йпр2(а, Ь). В параграфе 2.1 устанавливается ряд соотношений для элементов произвольного множества V € А.^1'. В параграфе 2.2 определяются операторы фиф специального вида, и доказывается ряд свойств этих операторов. В параграфе 2.3 рассматриваются отображения /': О! —> V, где 0! — некоторое подмножество произвольного частично упорядоченного множества Я, а V — произвольное множество из семейства А^, и с помощью операторов ф и ф, определенных в предыдущем параграфе, задается доопределение отображения /' на множество (2'. Основным результатом параграфа 2.3 является теорема о необходимых и достаточных условиях существования монотонного доопределения отображения /': 2' —> V на множество О, (теорема 2.3.1). В параграфе 2.4 на основе полученного критерия существования монотонного доопределения не всюду определенного отображения доказана теорема (теорема 2.4.1) о существовании в классе Мр, где V 6 А¹', некоторой мажоритарной функции, число переменных которой зависит только от мощности множества V. Из этого результата с помощью теоремы Бейкера и Пиксли (см. [25]) получено утверждение о конечной порожденное&tradeкласса М-р для любого множества V из семейства А¹'.

В главе 3 доказывается критерий конечной порожденное&tradeкласса всех функций, монотонных относительно множеств ширины два с наименьшим и наибольшим элемено) тами. В параграфе 3.1 приводится семейство А^ частично упорядоченных множеств ширины два, которым соответствуют предполные классы монотонных функций, не имеющие конечного базиса. Основной результат сформулирован в теореме 3.1.1. Для доказательства используется метод Тардоша из работы [44], а именно, рассматривается.

2) произвольное множество V? А-2, для каждого значения п > 4 строится множество Ир<�п наборов элементов множества V, устанавливается ряд свойств наборов из этого множества, с помощью этих свойств показывается, что при всех значениях к < | множество Лр1П сохраняется всеми функциями из класса Мр, зависящими от к переменных, и, далее, что существует функция /(хь., х2п)? Мр, которая не сохраняет множество 71-р, п. В диссертации при доказательстве лемм 3.1.2 и 3.1.3 метод Тардоша.

2) обобщается для семейства множеств А^ произвольной мощности. В параграфе 3.2 на основе результатов предыдущего параграфа и главы 2 приводится критерий конечной порожденное&tradeкласса Мр, где V — произвольное множество из семейства А.

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

Основные результаты диссертации опубликованы в работах [45, 46, 47, 48].

1. Алексеев В. Б.

Введение

в теорию сложности алгоритмов. ?V1.: Издательский отдел ф-та ВМиК МГУ, 2002. 84 с.

2. Лхо А., Хопщюфт Док., Ульман Дж. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979. 530 с.

3. Биркгоф Г. Теория решеток. М.: Наука, 1984. 568 с.

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

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

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

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

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

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

10. Мальцев А. И. Итеративные алгебры и многообразия Поста // Алгебра и логика. 1960. 5, Д*2. С. 5 24.

11. Мартыток В. В. Исследование некоторых классов в многозначных логиках // Проблемы кибернетики. М.: Наука, 1960. Т. 3. С. 49 60.

12. Марчеиков С. С. К существованию конечных базисов в замкнутых классах булевых функций // Алгебра и логика. 1981. 23, ЛП. С. 88 99.

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

14. Марченков С. С. Предполпота замкнутых классов в Рк предикатный подход. // Математические вопросы кибернетики. Выи. 6. Под ред. С. В. Яблонского. М.: Наука. Физматлит, 1996. 368 с.

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

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

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

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

19. Яблонский С. В.

Введение

в теорию функций fc-значной логики // Дискретная математика и математические вопросы кибернетики, I. М.: Паука, 1974. С. 9 66.

20. Яблонский С. В.

Введение

в дискретную математику. М.: Высшая школа, 2001. 384 с.

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

22. Яблонский С. В., Гаврилов Г. П., Набебин А. А. Анализ и синтез схем в многозначных логиках. Ч. 1. М.: Изд-во МЭИ, 1989. 118 с.

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

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

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

26. Borner F., Haddad L. Maximal Partial Clones with no Finite Basis // Algebra Universalis. 1988. 40. P. 453−476.

27. Demetrovics J., Hannah L., Ronyai L. Near unanimity functions and partial orderings // Proc. 14 ISMVL, Manitoba. 1984. P. 52−56.

28. Demetrovics J., Hannah L., Ronyai L. On algebraic properties of monotone clones // Order. 1986. 3. P. 219−225.

29. Demetrovocs J., Ronyai L. Algebraic properties of crowns and fences // Preprint, MTA SZTAKI. 1. 88.

30. Kuntzman J. Algebra de Boole. Bibliothegue de l’lngenieur // Automaticien. Paris: Dunod. 1965.

31. Lau D. Bestimmung der Ordnung maximaler Klassen von Funktionen der A-wert igen Logik // Z. math Log. und Grundl. Math. 1978. 24. P. 79−96.

32. Lau D. Uber partielle Funktionenalgebren // Rostok. math. Kolloq. 1988. 33. P. 23−48.

33. Lau D. On closed subsets of Boolean functions (A new proof for Post’s theorem) // J. Process. Cybern. EIK. 1991. Bd. 23, 3. P. 167 178.

34. Lo Czu Kai. Precompleteness of a set and rings of linear functions. Acta sc. iiatur Univ. Jilinensis. 1963. № 2.

35. Lo Czu Kai, Lju Sjui Hua. Precomplete classes defined by binary relations in many-valued logics. Acta sc. natur Univ. Jilinensis. 1964. № 4.

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

37. Poschel R., Kaluznin L. A. Funktionenund Relatiorienalgebren. Berlin, 1979.

38. Reschke M., Denecke K. Ein neuer Beweis fur dieErgebnisse von E. L. Post uber abgeschlossene Klassen Boolescher Funktionen // J. Process. Cybern. EIK. 1989. Bd. 7. P. 361 380.

39. Rosenberg I. G. La structure des functions de plusieurs variables sur un ensemble firiil. Coinptes Renclus, de l’Acadcm. Paris, 260. 1965. P. 3817−3819.

40. Rosenberg I. G. Uber die funktionale Vollstandigkeit in den mehrwertigen Logiken // Rozpr. CSAV. MPV. 1970. 80. P. 3−93.

41. Tardos G. A not finitely generated maximal clone of monotone operations // Order. 1986. 3. P. 211−218.Публикации автора по теме диссертации.

42. Дудакова О. С. Об одном семействе предполных классов функций ¿—значной логики, не имеющих конечного базиса // Вести. Моск. ун-та. Серия 1. Математика. Механика. 2006. Л" «2. С. 29−33.

43. Дудакова О. С. О свойствах предполных классов монотонных функций ¿—значной логики // Труды VII Международной конференции «Дискретные модели в теории управляющих систем» (Покровское, 4−6 марта 200G г.). М.: МАКС Пресс. 2006. С. 107−113.