О конечной порожденности предполных классов монотонных функций многозначной логики тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат физико-математических наук Дудакова, Ольга Сергеевна
- Специальность ВАК РФ01.01.09
- Количество страниц 107
Оглавление диссертации кандидат физико-математических наук Дудакова, Ольга Сергеевна
Введение
1 Определения и вспомогательные утверждения
1.1 Основные определения и обозначения.
1.2 Свойства частично упорядоченных множеств.
1.3 Доопределение частичных функций и монотонных отображений.
2 Достаточные условия конечной порожденности классов всех функций, монотонных относительно множеств ширины два
2.1 Вспомогательные утверждения.
2.2 Операторы ф и ф и их свойства.
2.3 Теорема о существовании монотонного доопределения не всюду определенного отображения.
2.4 Существование монотонной мажоритарной функции и достаточное условие конечной порожденности класса М-р.
3 Критерий конечной порожденности класса всех функций, монотонных относительно множества ширины два
3.1 Семейство иредполных классов монотонных функций, не имеющих конечного базиса.
3.2 Необходимые и достаточные условия конечной порожденности класса М-р
Рекомендованный список диссертаций по специальности «Дискретная математика и математическая кибернетика», 01.01.09 шифр ВАК
О порождении монотонных функций из некоторых классов многозначной логики2013 год, кандидат наук Панин, Дмитрий Юрьевич
О замкнутых классах функций многозначной логики, порожденных симметрическими функциями2009 год, кандидат физико-математических наук Михайлович, Анна Витальевна
Об условиях равномерности систем функций многозначной логики2016 год, кандидат наук Тарасов Павел Борисович
О пересечениях и объединениях предполных классов многозначной логики2013 год, кандидат физико-математических наук Нагорный, Александр Степанович
О глубине и сложности формул в предполных классах k-значной логики2004 год, кандидат физико-математических наук Сафин, Ринат Фатехович
Введение диссертации (часть автореферата) на тему «О конечной порожденности предполных классов монотонных функций многозначной логики»
Данная работа относится к теории функциональных систем. В ней изучаются свойства преднолиых классов функций многозначной логики. Рассматривается задача о конечной порожденное™ предполных классов монотонных функций.
В теории функций многозначной логики важное место занимают задачи классификационного характера. Одной из наиболее естественных и хороню изученных классификаций является разбиение множества Рвсех функций А'-значпой логики па классы, замкнутые относительно операции суперпозиции (см. [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]).
Одной из наиболее важных проблем, связанных с семействами замкнутых классов функций многозначной логики, является задача о конечной порожденное™, то есть задача о выразимости всех функций из замкнутого класса формулами над некоторым конечным множеством функций, принадлежащих этому же классу. Из результатов Поста [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 следует критерий конечной порожденное™ класса М-р.
Теорема 3 (теорема 3.2.1). Пусть V — частично упорядоченное множество из семейства А2. Класс Мр всех функций, монотонных относительно множества V, является конечно-порожденным тогда и только тогда, когда для любых двух несравнимых элементов а и b в V существует либо sup (a, Ь), либо sup2(a, 6).
Этот результат можно переформулировать следующим образом.
Теорема 4 (теорема 3.2.2). Пусть V G А2. Класс Мр является конечно-порожденным тогда и только тогда, когда он содержит некоторую мажоритарную функцию.
Из теоремы 3 следует алгоритмическая разрешимость задачи распознавания конечной порожденное™ предиолных классов функций, монотонных относительно частично упорядоченных множеств ширины два.
Теорема 5 (теорема 3.2.3). Для любого частично упорядоченного множества V ширины два с наименьшим и наибольшим элементами существует алгоритм распознавания конечной порожденное™ класса Мр.
Нетрудно показать, что этот алгоритм имеет полиномиальную сложность (см. [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 А^1', некоторой мажоритарной функции, число переменных которой зависит только от мощности множества V. Из этого результата с помощью теоремы Бейкера и Пиксли (см. [25]) получено утверждение о конечной порожденное™ класса М-р для любого множества V из семейства А^1'.
В главе 3 доказывается критерий конечной порожденное™ класса всех функций, монотонных относительно множеств ширины два с наименьшим и наибольшим элемено) тами. В параграфе 3.1 приводится семейство А^ частично упорядоченных множеств ширины два, которым соответствуют предполные классы монотонных функций, не имеющие конечного базиса. Основной результат сформулирован в теореме 3.1.1. Для доказательства используется метод Тардоша из работы [44], а именно, рассматривается
2) произвольное множество V £ А;2 , для каждого значения п > 4 строится множество Ир<п наборов элементов множества V, устанавливается ряд свойств наборов из этого множества, с помощью этих свойств показывается, что при всех значениях к < | множество Лр1П сохраняется всеми функциями из класса Мр, зависящими от к переменных, и, далее, что существует функция /(хь. ,х2п) £ Мр, которая не сохраняет множество 71-р,п. В диссертации при доказательстве лемм 3.1.2 и 3.1.3 метод Тардоша
2) обобщается для семейства множеств А^ произвольной мощности. В параграфе 3.2 на основе результатов предыдущего параграфа и главы 2 приводится критерий конечной порожденное™ класса Мр, где V — произвольное множество из семейства А.
В диссертации принята следующая нумерация утверждений, теорем и лемм. Утверждения нумеруются тройками чисел, где первое число — номер главы, второе — номер параграфа, третье — номер утверждения внутри параграфа. Леммы и теоремы (кроме основных теорем, приведенных во введении) нумеруются аналогичным образом. Следствия не нумеруются.
Основные результаты диссертации опубликованы в работах [45, 46, 47, 48].
Похожие диссертационные работы по специальности «Дискретная математика и математическая кибернетика», 01.01.09 шифр ВАК
О классах функций многозначной логики, замкнутых относительно усиленной операции суперпозиции2014 год, кандидат наук Подолько, Дмитрий Константинович
Условия выразимости и полноты пропозициональных исчислений2013 год, кандидат наук Боков, Григорий Владимирович
Дискретные преобразования конечных распределений рациональных вероятностей2004 год, доктор физико-математических наук Колпаков, Роман Максимович
Замкнутые классы k-значной логики, содержащие классы монотонных или самодвойственных функций2010 год, кандидат физико-математических наук Ларионов, Виталий Борисович
О сложности функций многозначной логики, принимающих два значения2011 год, кандидат физико-математических наук Дагаев, Дмитрий Александрович
Список литературы диссертационного исследования кандидат физико-математических наук Дудакова, Ольга Сергеевна, 2007 год
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. Börner 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 Gründl. Math. 1978. 24. P. 79-96.
32. Lau D. Über 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. Pöschel R., Kaluznin L. A. Funktionen- und Relatiorienalgebren. Berlin, 1979.
38. Reschke M., Denecke K. Ein neuer Beweis für die; Ergebnisse von E. L. Post über 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 Vollständigkeit 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.
Обратите внимание, представленные выше научные тексты размещены для ознакомления и получены посредством распознавания оригинальных текстов диссертаций (OCR). В связи с чем, в них могут содержаться ошибки, связанные с несовершенством алгоритмов распознавания. В PDF файлах диссертаций и авторефератов, которые мы доставляем, подобных ошибок нет.