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

• Автор: Дудакова, Ольга Сергеевна
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2007
• Место защиты: Москва
• Количество страниц: 107 с.

1 Определения и вспомогательные утверждения

1.1 Основные определения и обозначения

1.2 Свойства частично упорядоченных множеств

1.3 Доопределение частичных функций и монотонных отображений

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

2.1 Вспомогательные утверждения

2.2 Операторы ф и ф и их свойства

2.3 Теорема о существовании монотонного доопределения не всюду определенного отображения
2.4 Существование монотонной мажоритарной функции и достаточное условие конечной порожденности класса Мр
3 Критерий конечной порожденности класса всех функций, монотонных относительно множества ширины два

3.1 Семейство нредполных классов монотонных функций, не имеющих конечного базиса

3.2 Необходимые и достаточные условия конечной порожденности класса Л4р
Литература

Данная работа относится к теории функциональных систем. В ней изучаются свойства преднолных классов функций многозначной логики. Рассматривается задача о конечной порождеииости преднолных классов монотонных функций.
В теории функций многозначной логики важное место занимают задачи классификационного характера. Одной из наиболее естественных и хорошо изученных классификаций является разбиение множества Рк всех функций А'-значной логики па классы, замкнутые относительно операции суперпозиции (см. [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 были найдены в работах 118, 11, 34, 35, 36, 37]. Полное описание преднолных классов в Рк было получено И. Розенбергом [42, 43] (см. также [22, 23, 8, 14, 4|), который выделил шесть семейств предполных классов: классы самодвойственных функций — классы типа Р, классы линейных функций — классы типа Е, классы функций, сохраняющих разбиения множества Ек — {0,1, — 1} — классы типа Е, классы функций, сохраняющих
центральные отношения — классы типа С, классы функций, сохраняющих сильно голоморфные прообразы //-адических элементарных отношений — классы типа В, и классы функций, монотонных относительно частично упорядоченных множеств с наименьшим и наибольшим элементами — классы типа О (мы пользуемся обозначениями из [23]).
Одной из наиболее важных проблем, связанных с семействами замкнутых классов функций многозначной логики, является задача о конечной порождеииости, то есть задача о выразимости всех функций из замкнутого класса формулами над некоторым конечным множеством функций, принадлежащих этому же классу. Из результатов Поста [38, 39] следует, что каждый замкнутый класс булевых функций имеет конечный базис. В многозначных логиках этот результат не имеет места: для любого к > 3 в Рк существуют замкнутые классы как со счетным базисом, так и не имеющие базиса (см.

Рис. 1: множество V%
[24]). К настоящему времени отсутствует полное описание всех конечно-порожденных классов в Рк при к> 3 даже для семейства предполных классов. Д. JTay [31, 32) показала, что любой предполный класс в Рк из семейств P,L,E, С и В порождается конечным числом функций. Для предполных классов всех функций, монотонных относительно частично упорядоченных множеств (классов из семейства О) этот результат вереи, вообще говоря, лишь при к < 7 (см. [31, 32]). Г. Тардошем [44] приведен пример такого частично упорядоченного множества из восьми элементов, что предполный класс всех функций, монотонных на этом множестве, не имеет конечного базиса (см. рис. 1).
К настоящему времени получен ряд достаточных условий конечной порожденности предполных классов монотонных функций. Из интерполяционной теремы К. Бейкера и А. Пиксли [25] (см. также [26, 27, 28)) следует, что если в замкнутом классе содержится мажоритарная функция, то класс является конечно-порожденным. В работе [27] приводится следующее условие: предполный класс всех функций, монотонных на частично упорядоченном множестве V, имеет конечный базис, если множество V представляется в виде С1С, где С — решетка, а К, — выпуклое подмножество Д, не содержащее наименьшего и наибольшего элементов С (определения см. в [3]). Отсюда, в частности, следует конечная порожденность классов функций, монотонных относительно решеток и линейно упорядоченных множеств. В [28] показано, что это условие эквивалентно отсутствию в множестве V четверки элементов a,b,c,d, таких, что а,Ь < с, элементы а и b не имеют точной верхней грани и элементы с и d не имеют ночной верхней грани. Доказательство конечной порожденности класса монотонных функций, приведенное в работе [27], опирается на существование в классе мажоритарных функций. Отметим, что условие существования мажоритарных функций в классе не является необходимым для конечной порожденности этого класса даже для замкнутых классов булевых функций (см. [39]). Примеры частично упорядоченных множеств, таких что классы всех функций, монотонных относительно этих множеств, являются конечно-порожденными, но не содержат мажоритарных функций, приведены в работе [29|, однако эти классы не являются предполиыми.
В диссертации исследуются предполные классы функций, монотонных относительно частично упорядоченных множеств ширины два. Для всех множеств ширины два в терминах свойств этих множеств получены необходимые и достаточные условия конечной порожденности соответствующих предполных классов монотонных функций.
Дадим некоторые определения.

( (е) Еслхх выполняется неравенство г < в, то элементы г и хи несравнимы.
(}) Если выполняется неравенство г < в, то выполняются соотношения {г, и'} = !5йр(гД ,Ь2) и в = Й1ф(г, хи).
Доказательство. Обозначим (Ь, Ь2, А) через 'В. Доказательство леммы разобьем на несколько этапов.
1. Из условия (3) следует, что {иь?с2} € Дз(я, А) И4(а, А), следовательно, выполняется включение {«1,^2} £ Ь(2{а,А) С Ы^а^А). По свойству 1 множества^ существз'ет ю = кн1)(и1,и2) = вирДгд, и2), и выполняется пе|)авепство хи < А. По определению множества И2 элементы IV и а несравнимы. Так как в силу условия (2) элементы а и и2 несравнимы, то но свойству 1 множества Ы2 выполняется неравенство и > гд.
2. Так как в силу условия (1) {Ьу,Ь2,А) € V*, то элементы Ь1 11 Ь2 несравнимы. Кроме того, так как согласно условию (1) значение ф((Ьу,Ь2, Л)) определено, то в силу определения оператора ф множество С(Ь1,Ь2,А) непусто. Из неравенства а > гд (см. п. 1) в силу неравенства Ъ>а (см. условие (1)) следует неравенство 61 > гд.
3. Покажем, что элементы Ь[ и у2 несравнимы, элементы /д и хи несравнимы, и элементы Ь2 и гд несравнимы.
Если выполняется неравенство Ьу > и2, то в силу условия (4) леммы выполняется неравенство 61 > Ъ2, что невозможно, так как элементы Ь и Ь2 несравнимы (см. п. 2). А если выполняется неравенство Ь < и2, то в силу установленного в п. 2 неравенства выполняется неравенство гд < у2, что невозможно, так как элементы гд и у2 несравнимы (см. условие (2)). Поэтому элементы Ъ и у2 несравнимы.
Если выполняется неравенство £д > хи, то в силу соотношения га = 8ир(гд,гд), выполняется неравенство Ь > у2, что невозможно, так как, как было показано выше, элементы 61 н у2 несравнимы. А если выполняется неравенство Ь < хи, то в силу неравенства 1>1 > а (см. условие (1)) выполняется неравенство а < хи, что невозможно, так как элементы а и гг несравнимы (см. и. 1). Поэтому элементы Ь и хи несравнимы.
Если выполняется неравенство Ь2 > гд, то в силу условия (4) леммы выполняется неравенство у2 > гд, что невозможно, так как элементы У и г>2 несравнимы. А если выполняется неравенство Ь-2 < гд, то в силу неравенства Ь > гд (см. п. 2) выполняется неравенство Ь > Ь2, что невозможно, так как элементы Ъ и Ь2 несравнимы. Поэтому элементы Ъ2 и У несравнимы.
4. Покажем, что гв является минимальной верхней гранью элементов гд и Ь2. Действительно, в силу неравенств хи > гд и хи > у2 > Ь2 (см. п. 1 и условие (4)) элемент хи является верхней гранью элементов VI и Ъ2. Далее, элементы гд и и2 несравнимы (см. условие (2)), элементы £д и Ь2 несравнимы (см. п. 2). Кроме того, выполняется неравенство гд < Ь (см. п. 2), и в силу условия (4) выполняется неравенство и2 > Ь2. Согласно п. 3 элементы гд и Ь2 несравнимы, и элементы Ид и у2 несравнимы. Тогда, так как хи является минимальной верхней гранью элементов гд и у2 (см. н. 1), а элементы хи и ?д несравнимы (см. н. 3), то выполнены условия леммы 2.1.12. А значит элемент и> является минимальной верхней гранью элементов гд и Ь2.
5. Пусть в £ С(а,хи,Л). Покажем, что неравенство Ь} > з выполняться не может. Действительно, пусть £д > я. Тогда так как я — минимальная верхняя грань элементов