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

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

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

Панин Дмитрий Юрьевич

О ПОРОЖДЕНИИ МОНОТОННЫХ ФУНКЦИЙ ИЗ НЕКОТОРЫХ КЛАССОВ МНОГОЗНАЧНОЙ ЛОГИКИ

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

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

005545117

Москва — 2014

I 3 ФЕВ 2014

005545117

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

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

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

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

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

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

Ведущая организация: ФГВУН Институт математики им.

С. Л. Соболева Сибирского отделения РАН. '

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

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

Автореферат разослан 28 января 2014 г.

Ученый секретарь диссертационного совета Д 501.001.84, созданного на базе ФГБОУ ВПО МГУ, доктор физико-математических наук,

профессор Иванов Александр Олегович

Общая характеристика работы Актуальность темы

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

Одной из основных задач в теории функциональных систем является задача о полноте. В общем случае она может быть сформулирована следующим образом. Рассматривается функциональная система (Р; ф), состоящая из некоторого множества Р и некоторого отображения <р : В{Р) -> В{Р), где В{Р) — множество всех подмножеств множества Р, a ip является оператором замыкания1. Требуется по заданным подмножествам 21 и # множества Р установить, имеет ли место равенство <р{Щ = то есть порождает ли множество 21 множество 3". Можно уточнить эту задачу, потребовав, чтобы множество 21 обладало некоторыми дополнительными свойствами. Например, задача о конечной порожденное™ заключается в том, чтобы определить, существует ли конечное множество 21, порождающее Другим примером является задача о базируем ости, которая состоит в том, чтобы определить, существует ли множество 21, такое, что ^(21) = J и для любого собственного подмножества 21' С 21 выполняется соотношение <¿>(21') ^ ^ (такое множество 21 называется базисом

В теории функциональных систем важное место занимает исследование множества Pk (к > 2) всех функций fc-значной логики с операцией суперпозиции. В частности, особый интерес представляет описание различных классов из решетки £ft (семейства замкнутых классов функций из Pk, упорядоченных по включению). Случай к — 2 описан в работах Э. Поста2,3, где было показано, что семейство £2 счетно и каждый класс из семейства £2 имеет конечный базис. Ряд результатов, полученных для двузначной логики, обобщается на случай многозначных логик, например, решение проблемы о функциональной полноте и описание иредполных классов. Однако есть и принципиальные различия между двузначной и /с-значной логикой при к > 3. В частности, Ю. И. Яновым и А. А. Мучником4 были построены примеры замкнутых классов в Р3, как имеющих счетный базис, так

'Отображение ч> : В(Р) -л В(Р) называется оператором замыкания, если для каждых Я, 25 € В[Р) выполнены следующие свойства: 1) Я Ç у>(Я), 2) если Я С <8, то С <¿>(03), 3) </>(р(Я)) = уз(Я).

2Post. Е. L. Introduction to a general theory of elementary propositions il Amer. J. Math. 1921. 43. 3. 163-185.

3Post E. L. The two-valued iterative systems of mathematical logic 11 Annals of Math. Studies. Princeton Univ. Press. - 1941. - 5.

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

и не имеющих базиса. Из этих результатов следует, что семейство при к > 3 имеет мощность континуума. Более того, в работах Р. Пёшеля и Л. А. Калужнина5 приводятся примеры цепей и антицепей континуальной мощности в решетке £3. При изучении свойств функций многозначной логики возникают существенные проблемы, связанные с труднообозримостью структуры замкнутых классов в P¡; при к > 3. Поэтому одним из направлений исследований является изучение свойств отдельных семейств классов.

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

A. В. Кузнецова6,7 была доказана конечность числа предполных классов в Рк при всех к > 3. Все предполные классы функций трехзначной логики были оиисаны С. В. Яблонским8. Отдельные семейства предполных классов в Pk при к > 4 были найдены С. В. Яблонским9, JIo Чжу-Каем10,11,12,

B. В. Мартынюком13 и другими исследователями. Полное описание всех предполных классов функций многозначной логики было получено И. Ро-зенбергом14,15. Стоить отметить, что так же, как и решетка Zk при к > 3, большинство решеток, состоящих из замкнутых классов, содержащихся в заданном предполном классе, имеет нетривиальную структуру. Так, в работах С. С. Марченкова16, Я. Деметровича и Л. Ханнака17 было показано, что каждый предполный класс в Р*. при к > 3 содержит континуальное множество замкнутых подклассов тогда и только тогда, когда он не явля-

5Pöschel R., Kaluznin L.A. Funktionen- und Relationenalgebren. Berlin. 219 p. — 1979.

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

7Кузнецов А. В. Структуры с замыканием и критерии функциональной полноты /'/ Усп. мат. наук. 1961. Т. 16 (98). С. 201-202.

8Яблонский C.B. О функциональной полноте в трехзначном исчислении // Доклады АН СССР. — 1954 - Т. 95. X« 6. - С. 1152-1156.

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

laLo Czu-Kai. The precompleteness of a set and rings of linear functions // Acta. Sei. Natur. Univ. Jilinensis. — 1963. — V. 2. — P. 1-14 (Chinese).

11 Lo Czti-Kai. On the precompleteness of the classes of functions preserving a partition // Acta. Sei. Natur. Univ. Jilinensis. — 1963. — V.2. - P. 10-5-116 (Chinese).

12 Lo Cza-Kai. Preoomplete classe» ileflned by normal fc-ary relations in ir-valued logics // Acta. Sei. Natur. Univ. Jilinensis. — 1964. — V.3. - P. 39-50 (Chinese).

13Мартынюк В. В. Исследование некоторых классов функций в многозначных логиках // Проблемы кибернетики. — Т. 3. — 1960. — С. 49-60.

14Rosenberg I. G. La structure des functions de plusieurs variables sur en ensemble finil. Comptes Rendus, de i'Acadeiu/ Paris, 26U. — 1.965. — P. 3817-3819.

15Rosenberg I. G. Über die funktionale Vollständigkeit in den mehrwertigen Logiken // Rozpr. CSAV. MPV. - 1970. - 80. — P. 3-93.

16Марчек!соо С. С. О замкнутых классах самодвойственных функций многозначной логики II ,// Проблемы кибернетики. — Т. 40. — 1983. — С. 261-266.

17Demetrovics J., Наппак L. The number of reducts of a preprimal algebra. // Algebra Universalis. — 1983 V. 16 1 - P. 178-185.

ется классом типа18 L.

Одним из наиболее естественных вопросов, возникающих при изучении свойств предполных классов, является вопрос об их конечной порожденное™. Д. Лау19 установила, что каждый предполный класс функций многозначной логики, за исключением классов из семейства20 О, имеет конечный базис, кроме того, она доказала, что классы типа О являются конечно-порожденными при к < 7. Г. Тардош21 привел пример частично упорядоченного множества R$ ширины 2, состоящего из восьми элементов, такого, что предполный класс MRs всех функций, монотонных относительно множества не имеет конечного базиса. В работах О. С. Дуда-ковой22'23,24 приводится необходимое и достаточное условие конечной по-рожденности для предполных классов функций, монотонных относительно частично упорядоченных множеств ширины 2 с наименьшим и наибольшим элементами.

На данный момент предполные классы монотонных функций — это единственное семейство предполных классов, для которых вопрос конечной порожденное™ исследован не полностью, таким образом, оказалось, что это семейство является в некотором смысле наиболее сложным для изучения. В связи с этим, исследования в данной области представляют особый интерес. Также стоит отметить, что множество R& — это такое наименьшее по мощности частично упорядоченное множество, что предполный класс функций монотонных относительно него не имеет конечной порождающей системы. Поэтому класс MRi занимает особое положение среди классов типа О. В настоящее время вопрос, имеет ли класс MRa бесконечный базис, остается открытым. Одним из возможных подходов к решению этой проблемы является изучение свойств «просто устроенных» подклассов МЛз, а также получение критериев полноты для множеств функций из MRs, зависящих от определенного числа переменных.

18Под классами типа L понимаются классы линейных функций.

10 Lau D. Bestimmung der Ordnung maximaler Klassen von Funktionen der k-wertigen Logik // Z. .math Log und Gründl. Math. - 1978. - 24. - P. 79-96.

20Ссмейство О — это классы функций, монотонных относительно некоторых частично упорядоченных множеств с наименьшим и наибольшим элементами.

21 Tardos G. A not finitely generated maximal clone of monotone operations // Order. — 1986. — V. 3. — P, 211-218.

22Дуда.кова О. С. Об одном семействе предполных классов функций fc-значной логики, не имеющих коночного базиса // Вестник Московского университета. Математика, Механика. — 2000. Выи. 2. — С. 29-32.

23Дудакова О. С. О классах функций /с-значной логики, монотонных относительно множеств ширины два // Вестник Московского университета. Математика. Механика. — 2008. Вып. 1. — С. 31-37.

2*Дудакооа О. С. О конечной порожденности предполных классов монотонных функций многозначной логики // Математические вопросы кибернетики. Вып. 17. М.: Физматлнт, 2008. ■ С. 13 104.

Цель работы

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

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

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

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

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

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

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

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

4. Найден критерий полноты для класса всех одноместных функций, монотонных относительно частичного порядка типа башня с максимальным элементом.

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

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

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

Результаты диссертации докладывались автором на семинаре "Функции многозначной логики и смежные вопросы" под руководством проф. А.Б. Угольникова, проф. P.M. Колиакова и проф. С.Б. Гашкова (неоднократно: МГУ, 2010-2013гг.), на семинаре "Синтез и сложность управляющих систем" под руководством проф. О.М. Касим-Заде (МГУ, 2013 г.), на семинаре "Математические вопросы кибернетики" под руководством проф. О.М. Касим-Заде (МГУ, 2013 г.), на XVI Международной конференции "Проблемы теоретической кибернетики" (Нижний Новгород, 20-25 июня 2011г.), на VIII молодежной научной школе но дискретной математике и ее приложениям (Москва, 24-29 октября, 2011г.), на XI Международном семинаре "Дискретная математика и ее приложения" (Москва. 18-23 июня 2012г.), на IX молодежной научной школе по дискретной математике и ее приложениям (Москва, 16-21 сентября 2013 г.), на Международных научных конференциях студентов, аспирантов и молодых ученых "Ломоносов-2011" (Москва, 11-15 апреля 2011г.), "Ломоносов-2012" (Москва, 9-13 апреля 2012 г.), на научных конференциях "Ломоносовские чтения" (Москва, 16-22 апреля 2010г.), "Ломоносовские чтения" (Москва, 14 23 ноября 2011г.), "Ломоносовские чтения" (Москва, 16-24 апреля 2012 г.), "Ломоносовские чтения" (Москва, 15-26 апреля 2013 г.).

Публикации

Основные результаты диссертации опубликованы в 7 работах автора, список которых приведен в конце автореферата [17].

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

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

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

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

В главе 1 приводятся основные определения и обозначения, а также доказываются вспомогательные утверждения. В частности, определяется класс ограниченно селекторных функций, обозначаемый через Ш7, и понятие частично упорядоченного множества типа башня. Будем обозначать через А семейство всех конечных частично упорядоченных множеств с наименьшим и наибольшим элементами. Наименьший и наибольший элементы множества ? 6 А будем обозначать через 0 и 1 соответственно. Шириной частично упорядоченного множества У € А будем называть максимальное число попарно несравнимых элементов из 7. Будем обозначать через Аг подсемейство семейства А, состоящее из всех множеств, ширина которых не превосходит 2.

Пусть У 6 Аг, а и Ь — элементы множества У. Элементы а и & называются 1-несравнимыми, если они несравнимы и не имеют точной верхней храни. Элементы а и b называются 2-несравнимыми, если они 1-несравнимы и найдутся две их минимальные верхние грани, являющиеся 1-несравнимыми.

Пусть У G А2. Будем обозначать через М7 замкнутый класс всех функций /с-значной логики, монотонных относительно частично упорядоченного множества У, где к = |У|.

Положим U — {0,1}. Пусть 1 < i < п. Будем обозначать через 9Лf(n) множество всех функций f(xi,..., хп) 6 М7, для которых выполнены следующие условия:

1) для любых элементов fa,...,6n из множества И справедливо равенство f(6i,...,6n) — 8i\

2) для любых элементов fa,..., 5п из множества У \ U справедливо par венство f(Si,. ...5п) = Si.

Определим множества 0Л;Г (п) и Ш7 следующим образом. Положим

ro?(n) = Uanf(n), =

¿=1 П>1

Функции из множества Ш7 будем для краткости называть ограниченно селекторными функциями. Будем обозначать через Ту семейство всех замкнутых классов А, таких, что Ш7 С АС М7.

Будем обозначать через М| множество всех функций f(xь ..., хп) из класса М7, таких, что f(6, ...,5) <6, для всех 5 G У. Функции из множества М< будем для краткости называть невозрастающими функциями.

Пусть п > 1. Положим Уп = {0, ах, Ь\,... ,ап,Ьп, 1}, ь а0 = 6о = 0, ап+1 = Ьп+1 = 1, Д< = {а,-Д}, где О < г < п + 1. Введем на элементах множества "?п от-а"~1 ь"'1 ношение частичного порядка < следующим образом (см.

рис. 1):

1) £г < £} ДЛЯ всех ТаКИХ, ЧТО 6 Д,-, Еу 6 Д^, о < г < ] < п + 1;

2) е < е для всех е е Т„;

3) других сравнимых элементов нет. Множество Тп будем называть множеством типа башня

высоты п с максимальным элементом. Множество ф,, = СРП\{1} будем называть множеством типа башня высоты п без максимального элемента. Отметим, что множество из работы Г. Тардоша21 является множеством типа башня высоты 3 с максимальным элементом.

В главе 2 исследуются свойства семейства Т7, где У — произвольное частично упорядоченное множество из семейства Аг, содержащее пару 2-несравнимых элементов. Семейство Ту состоит из всех замкнутых классов, содержащихся в классе М7 — множестве функций, монотонных относительно У, и содержащих класс Ш7 — множество ограниченно селекторных функций. Из результатов О. С. Дудаковой24 следует, что класс Му не является конечно порожденным. В § 2.2 устанавливается отсутствие конечной порождающей системы для всех классов из семейства Т7. При доказательстве используется метод из работы Г. Тардоша21 и его обобщение из работы О. С. Дудаковой24. А именно, для каждого значения п, такого, что п > 4, определяется некоторое множество наборов элементов множества которое сохраняется всеми функциями из класса М9, зависящими от к (к < п/2) переменных, и доказывается, что в классе Ш7 найдется функция /(&!,... ,£211+3)1 которая не сохраняет это множество наборов. В § 2.3 показано, что семейство Т7 содержит как цепь, так и антицеиь замкнутых классов континуальной мощности. Основными результатами главы 2 являются следующие теоремы.

Теорема 1. Пусть У — произвольное множество из семейства Аг, содержащее пару 2-несравнимых элементов, А — произвольный замкнутый класс, такой, что Ш7 С А С М7. Тогда класс А не является конечно порожденным.

Теорема 2. Пусть У — произвольное множество из семейства Аг, содержащее пару 2-несравнимых элементов. Тогда в семействе Т7 найдется как цепь, так и антицепь континуальной мощности.

В главе 3 исследуется порождение одноместных функций из множеств и М<п — множеств невозрастающих функций, монотонных относительно частично упорядоченных множеств типа башня (тг > 3). Отметим, что множество удовлетворяет соотношению С М<" Ç МТп, поэтому из теоремы 1 следует, что класс М<" не является конечно порожденным. Для удобства изложения положим F = М<"( 1) и F1 = М<"( 1). Сначала на множествах F и F1 вводятся операции композиции и свертки, обозначаемые через о и v соответственно. Результатом применения операции свертки к функциям f и g является функция (/ V <?)> определяемая следующим образом:

\j{x), если <Д£] = 0.

Операция свертки интересна тем, что позволяет получить критерий порождения множества F относительно только операции композиции, используя критерий порождения множества F относительно операций композиции и свертки. Критерий полноты для множества всех двухместных ограниченно селекторных функций, монотонных относительно частично упорядоченного множества типа башня с максимальным элементом, также был получен с использованием операции свертки (см. главу 4). В §3.2 определяются множества функций G\,

Za, Zb,

семейство множеств функций <3 и устанавливается критерий полноты для функциональной системы (F, {о, v}) в терминах этих множеств. Далее, с использованием этого результата строятся множества функций D, D1 и К1, являющиеся единственными минимальными по включению порождающими множествами для функциональных систем (F, {о}), (F1, {о}) и (F1, {о, у}) соответственно. Основные результаты главы 3 могут быть сформулированы следующим образом.

Теорема 3. Пусть А С F. Замыкпыыс множества А относительно операций {о, у} совпадает Г тогда и только тогда, когда G\ С А и найдется G Е &, такое, что G С. А.

Теорема 4. Пусть АС F. Замыкание множества А относительно операций {о} совпадает с F тогда и только т,огда, когда DCA.

Теорема 5. Пусть А С F1. Замыкание множества А относительно операций {о} совпадает с F1 тогда и только тогда, когда D1 С А.

Теорема 6. Пусть А С F1. Замыкание множества А относительно операций {о, v} совпадает с F1 тогда и только тогда, когда К1 С А.

В главе 4 устанавливается критерий полноты для множества Ш® (2) — множества двухместных ограниченно селекторных функций, монотонных относительно <3, где С) является частично упорядоченным множеством типа башня высоты п (п > 3) с максимальным элементом. Отметим, что из теоремы 1 следует, что класс Ш® не является конечно порожденным, поэтому представляется интересным получение критериев полноты для множеств функций из этого класса, зависящих от определенного числа переменных. Множество состоит только из селекторных функций, поэтому критерий полноты для него тривиален.

В §4.1 вводятся множества одноместных функций и рассматри-

вается множество Р, которое состоит из упорядоченных пар одноместных функций, таких, что первый элемент пары принадлежит множеству а второй — множеству Далее определяются отображения да и которые каждой функции из множества ШТ^(2) сопоставляют функцию из множеств и соответственно. После этого определяется отображение которое каждой двухместной функции / из множества Ш® ставит в соответствие пару одноместных функций (до(1), £>1(/))- Затем на множествах _Р> определяются операции Фо и Фь являющиеся обобщениями операции свертки (см. главу 3). Далее на множестве ^ рассматриваются операции специального вида <8> и Ф, определенные следующим образом:

(/о, к) ® (9о, 9г) = (/о ° <7о, к ° Зг),

Ф((/о, к), (9о,91), (Ло.ЛО) = (Фо(/о,ЯьЛо),Ф1(/1,01,Л1)).

Операции ®иФ интересны тем, что позволяют в некотором смысле сводить изучение вопросов порождения двухместных функций из множества 071^ к изучению порождения множества Ё относительно этих операций. А именно, показывается, что замыкание произвольного множества А С 9Я®(2) содержит множество ЙЛ^(2) тогда и только тогда, когда замыкание множества д(А) и {е} относительно операций ® и Ф совпадает с Р1, где е -тождественная функция на множестве В §4.2 устанавливается критерий полноты для системы Ф}) в терминах свойств нар функций и порождения множеств относительно множеств операций {о, Ф0}, Ф1} соответственно. В §4.3 показывается, что множество В С ^ порождает относительно операций {о, Ф0}, тогда и только тогда, когда двойственное множество В* С Р> порождает F> относительно операций {о,Ф!}. В §4.4 определяется множество функций С?2 и с использованием теоремы 3 (см. главу 3) доказывается критерий порождения множества Р< относительно операций {о, Ф0}. Основным результатом главы 4 является

следующий критерий порождения множества в терминах свойств

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

Теорема 7. Пусть А С ЙН®(2). Соотношение Ш®(2) С [Л] выполняется тогда и только тогда, когда выполнены следующие условия

1) для каждого а е Дг и для каждого 6 £ Д1 и • • • и Д„, множество д(А) содержит элемент (/о,/\), такой, что /о(а) = а и /1(6) ф 6;

2) для каждого 5 ё Д1 и • • • и Д„ и для каждого а е Д„, множество д(А) содержит элемент (/о, /1), такой, что /о(<5) ф 5 и /\(а) — а;

3) для каждого множества С из семейства (¿Р!^))*} выполнены соотношения Сг С (3, С Za, й и найдется множество Веб, такое, что В С С.

В главе 5 рассматривается задача о полноте для множества М<э( 1) ■• множества одноместных функций, монотонных относительно С}, где ф является частично упорядоченным множеством типа башня высоты п (п > 3) с максимальным элементом. Отметим, что при п > 3 множество типа башня высоты п с максимальным элементом содержит пару 2-несравнимых элементов, поэтому класс всех функций, монотонных относительно <5, не является конечно порожденным.

Сначала определяются множество #1, состоящее из функций множества М®(1), принимающих все значения, и отображение Уе^ : Н\ Щ, которое сопоставляет каждой функции из Н\ некоторый вектор из нулей и единиц длины п. Показывается, что множество А С Н\ порождает множество Н\ тогда и только тогда, когда ранг25 матрицы, составленной из векторов УесЬф), Н € А, равен п. Далее вводится понятие неразложимых множеств, которое содержательно заключается в том, что функции из неразложимого множества А С М®(1) нельзя получить, используя только функции не из А. После этого строится семейство множеств У, такое, что каждое множество из построенного семейства является неразложимым. Наконец, доказывается следующий критерий полноты для систем функций из М«( 1).

Теорема. 8. Пусть А С М®(1). Соотношение [Л] = М®( 1) выполняется тогда и только тогда, когда справедливы следующие условия:

1) ЯапкСУесЦЯ! П Л)) = п;

2) для каждого Р £ 5 выполняется А П Р ф 0.

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

25Под рангом матрицы понимается максимальное число линейно независимых столбцов.

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

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

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

[1] Панин Д. Ю. О порождении одноместных монотонных функций многозначной логики // Вестник Московского университета. Математика. Механика, - 2010. Вып. 6. - С. 52-55.

[2] Панин Д. Ю. Критерии полноты для некоторых классов монотонных одноместных функций в Рк // Вестник Московского университета. Математика. Механика. — 2013. Вып. 3. — С. 57-61.

[3] Панин Д. Ю. Об одном семействе классов монотонных функций многозначной логики, не имеющих конечного базиса // Известия Иркутского университета. Математика. — 2013. Т. 6, № 3. С. 97-108.

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

[5] Панин Д. Ю. О свойствах одноместных монотонных функций многозначной логики // Материалы VIII Молодежной научной школы по дискретной математике и ее приложениям (Москва, 24-29 октября 2011 г.). - 2011. - С. 23-25.

[6] Панин Д. Ю. О полноте систем монотонных одноместных функций в Рк // Дискретная математика и ее приложения: Материалы XI Международного семинара (Москва, 18-23 июня 2012 г.). — 2012. — С. 210-212.

[7] Панин Д. Ю. Критерий порождения некоторых множеств монотонных функций многозначной логики // Материалы IX Молодежной научной школы по дискретной математике и ее приложениям (Москва, 16 21 сентября 2013 г.). - 2013. С. 88-92.

Отпечатано в отделе оперативной печати Геологического ф-та МГУ Тираж ¡00 экз. Заказ №

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

имени М. В. Ломоносова»

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

04201453501

Панин Дмитрий Юрьевич

О ПОРОЖДЕНИИ МОНОТОННЫХ ФУНКЦИЙ ИЗ НЕКОТОРЫХ КЛАССОВ МНОГОЗНАЧНОЙ логики

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

Диссертация на соискание ученой степени кандидата физико-математических наук

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

Москва - 2013

Оглавление

Введение 4

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

1.1 Системы функций................................................14

1.2 Частично упорядоченные множества............................17

2 Свойства семейства Та' 21

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

2.2 Отсутствие конечного базиса у всех замкнутых классов, принадлежащих отрезку [Ш1е; М]....................................25

2.3 Цепь и антицепь континуальной мощности в множестве Т . 29

3 Порождение одноместных функций из множества А/< 33

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

3.2 Необходимое условие я-полноты в множестве Р ..............37

3.3 Достаточное условие з-полноты в множестве Р................42

3.4 Описание всех полных систем в множестве Р..................63

3.5 Описание всех полных систем в множестве Р1................67

3.6 Описание всех 5-иолных систем в множестве Р1..............70

4 Критерий порождения множества 9Яе(2) 74

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

4.2 Критерий полноты в множестве Р..............................83

4.3 Принцип двойственности ........................................89

4.4 Критерий полноты в множестве Р< относительно композиции

и операции Ф......................................................91

ч

5 Критерий порождения всех одноместных функций из мно-

жества Мр 104

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

5.2 Принцип двойственности ........................................107

5.3 Необходимое условие полноты в множестве М( 1) ............108

5.4 Достаточное условие полноты в множестве М( 1)..............124

Список литературы 135

и

Введение

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

Одной из основных задач в теории функциональных систем является задача о полноте. В общем случае она может быть сформулирована следующим образом. Рассматривается функциональная система (Р; (/?), состоящая из некоторого множества Р и некоторого отображения <р : В(Р) —> В(Р), где В(Р) — множество всех подмножеств множества Р, a tp является оператором замыкания1. Требуется по заданным подмножествам 21 и £ множества Р установить, имеет ли место равенство <¿>(21) = то есть порождает ли множество 2( множество Можно уточнить эту задачу, потребовав, чтобы множество 21 обладало некоторыми дополнительными свойствами. Например, задача о конечной порождеппости заключается в том, чтобы определить, существует ли конечное множество 21, порождающее Другим примером является задача о базируемое™, которая состоит в том, чтобы определить, существует ли множество 21, такое, что <¿>(21) = & и для любого собственного подмножества 21' С 21 выполняется соотношение </?(21') ф £ (такое множество 21 называется базисом

В теории функциональных систем важное место занимает исследование множества Рд. (к > 2) всех функций /с-значной логики с операцией суперпозиции. В частности, особый интерес представляет описание различных классов из решетки (семейства замкнутых классов функций из Pit, упорядоченных по включению). Случай к = 2 описан в работах Э. По-

1 Отображение ip : В{Р) —> В(Р) называется оператором замыкания, если для каждых 21,03 G В(Р) выполнены следующие свойства: 1) 21 С ip(21), 2) если 21 С 03, то <¿(21) с (¿(03), 3) с^(21)) = (¿(21) (см. [2,9]).

ста [40,41], где было показало, что семейство £2 счетно и каждый класс из семейства £2 имеет конечный базис. Описание классов Поста содержится также в работах [19-22,25,31,33,43]. Ряд результатов, полученных для двузначной логики, обобщается па случай многозначных логик, например, решение проблемы о функциональной полноте (см. [11,13-16,23,24,46,47,49]) и описание предполпых классовом. [44,45]). Однако есть и принципиальные различия между двузначной и /с-значной логикой при к > 3. В частности, Ю. И. Яновым и A.A. Мучником [28] были построены примеры замкнутых классов в Р3, как имеющих счетный базис, так и пе имеющих базиса. Из этих результатов следует, что семейство при к > 3 имеет мощность континуума. Более того, в работах Р. Псшеля и JI. А. Калужница [42] приводятся примеры цепей и антицепей континуальной мощности в решетке £3. При изучении свойств функций многозначной логики возникают существенные проблемы, связанные с труднообозрпмостыо структуры замкнутых классов в Р^ при к > 3. Поэтому одним из направлений исследований является изучение свойств отдельных семейств классов.

К наиболее изученным семействам замкнутых классов функций многозначной логики относится семейство предполпых классов. В работах A.B. Кузнецова [11,12] была доказана конечность числа предполпых классов в Pk при всех к > 3. Все предполные классы функций трехзначной логики были описаны C.B. Яблонским [23]. Отдельные семейства пред-полных классов в Р/. при к > 4 были найдены C.B. Яблонским [24], Ло Чжу-Каем [36,37,39], В. В. Мартышоком [17] и другими псследователя-мн(см. в частности, [1,7,8,35,38]). Полное описание всех предполпых классов функций многозначной логики было получено И. Розенбергом [44,45]. Стоить отмстить, что так же, как и решетка при к > 3, большинство решеток, состоящих из замкнутых классов, содержащихся в заданном пред-полном классе, имеет нетривиальную структуру. Так, в работах С. С. Мар-ченкова [18], Я. Деметровича и JI. Ханнака [29] было показано, что каждый предиолный класс в Р^ при к > 3 содержит континуальное множество замкнутых подклассов тогда и только тогда, когда он не является классом тина2 L.

2Под классами типа L понимаются классы линейных функций.

Одним из наиболее естественных вопросов, возникающих при изучении свойств предполных классов, являются вопрос о конечной порожден-ностп. Д. Лау [32] установила, что каждый предполный класс функций многозначной логики за исключением классов из семейства3 О имеет конечный базис, кроме того, она доказала, что классы типа О являются конечно-порожденными при к < 7. Результаты, связанные с указанными, также можно найти в работах [1,8,17,24,33,42,45,48]. Г. Тардош [50] привел пример частично упорядоченного множества Т?8 ширины 2, состоящего из восьми элементов, такого, что предполный класс всех функций, монотонных относительно множества не имеет конечного базиса. В работах О. С. Дудаковой [4-6] приводится необходимое п достаточное условие конечной порожденное™ для предполных классов функций, монотонных относительно частично упорядоченных множеств ширины 2 с наименьшим и наибольшим элементами.

На данный момент предполные классы монотонных функций - это единственное семейство предполных классов, для которых вопрос конечной порожденности исследован не полностью, таким образом, оказалось, что это семейство является в некотором смысле наиболее сложным для изучения. В связи с этим, исследования в данной области представляют особый интерес. Также стоит отметить, что множество — это такое наименьшее по мощности частично упорядоченное множество, что предполный класс функций монотонных относительно него, не имеет конечной порождающей системы. Поэтому класс М11& занимает особое положение среди классов типа О. В настоящее время вопрос, имеет ли класс М^8 бесконечный базис, остается открытым. Одним из возможных подходов к решению этой проблемы является изучение свойств «просто устроенных» подклассов М1*8, а также получение критериев полноты для множеств функций из МЙ8, зависящих от определенного числа переменных.

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

3Семеиство О эго классы функций, монотонных относительно некоторых частично

упорядоченных множеств с наименьшим и наибольшим элементами.

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

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

В главе 1 приводятся основные определения и обозначения, а также доказываются вспомогательные утверждения. В частности, определяется класс ограниченно селекторных функций, обозначаемый через , и понятие частично упорядоченного множества типа башня. Будем обозначать через А семейство всех конечных частично упорядоченных множеств с наименьшим и наибольшим элементами. Наименьший и наибольший элементы множества СР Е А будем обозначать через 0 и 1 соответственно. Шириной частично упорядоченного множества У Е А будем называть максимальное число попарно несравнимых элементов из СР. Будем обозначать через А2 подсемейство семейства А, состоящее из всех множеств, ширина которых не превосходит 2.

Пусть СР Е А2, а и Ъ — элементы множества О3. Элементы а и Ь называются 1-несравнимыми, если они несравнимы и не плюют точной верхней грани. Элементы а и 6 называются 2-несравнимыми, если они 1-иесравнпмы и найдутся две их минимальные верхние грани, являющиеся 1-несравнимыми.

Пусть СР Е А2. Будем обозначать через Му замкнутый класс всех функций /с-значпой логики, монотонных относительно частично упорядоченного множества СР, где к = |СР|.

Положим и — {0,1}. Пусть 1 < I < п. Будем обозначать через (п) множество всех функций /(х\,... ,хп) Е для которых выполнены следующие условия:

1) для любых элементов $1,..., 5п из множества 1С справедливо равенство

/(¿ъ • ■ - А) = й;

2) для любых элементов ¿>1,. ... 5п из множества У \ И справедливо равенство ... ,6п) — Определим множества и следующим образом. Положим

п

ш"е(п) = []ш!(п),

¿=1 ?г>1

Функции из множества будем для краткости называть ограниченно селекторными функциями. Будем обозначать через Т'-Р семейство всех замкнутых классов А, таких, что Шрс С А С М7.

Буднем обозначать через М< множество всех функций /(х\:..., хп) из класса таких, что /(5,..., < 6, для всех 6 Е У. Функции из множества М< будем для краткости называть невозрастающими функциями.

Пусть п > 1. Положим Уп = {0, а\. Ь\1.. ., ап, Ьп, 1},

Аа0 = Ь0 = 0, ап+1 = Ьп+1 = 1, Аг = {аг,6,}, где

^ 0 < % < п + 1. Введем на элементах множества СР7, от-ь

11 1 ношение частичного порядка < следующим образом (см. ! рис. 1):

1) < Для всех таких, что £{ Е Дг-, £3 Е Д^-, О < г < з < п + 1;

2) £ < £ для всех е Е Рис. 1

3) других сравнимых элементов нет.

Множество будем называть множеством типа башня высоты п с максимальным элемент,ом,. Множество = !Р„ \ { 1} будем называть мноэ/се-ством, типа башня высоты п без максимального элемента. Отметим, что множество /?,§ из работы Г. Тардоша [50]является множеством типа башня высоты 3 с максимальным элементом.

В главе 2 исследуются свойства семейства Т^, где У — произвольное частично упорядоченное множество из семейства А2, содержащее пару 2-несравпимых элементов. Семейство Ту состоит из всех замкнутых классов, содержащихся в классе Мт — множестве функций, монотонных относительно СР, и содержащих класс — множество ограниченно селекторных функций. Из результатов О. С. Дудаковой [6]следует, что класс М'у не является конечно порожденным. В §2.2 устанавливается отсутствие конеч-

ной порождающей системы для всех классов из семейства Т^. При дока-

зательстве используется метод из работы Г. Тардоша [50]и его обобщение из работы О. С. Дудаковой [6]. А именно, для каждого значения п, такого, что п > 4, определяется некоторое множество наборов элементов множества СР, которое сохраняется всеми функциями из класса М']\ зависящими от к (к < п/2) переменных (см. также [4]), и доказывается, что в классе УЯ^ найдется функция /(х1,...,х2?;+з), которая не сохраняет это множество наборов. В § 2.3 показано, что семейство содержит как цепь, так и антицепь замкнутых классов континуальной мощности. Основными результатами главы 2 являются следующие теоремы.

Теорема 1 (теорема 2.2.1). Пусть У — произвольное множество из семейства А2; содержащее пару 2-иссравнимых элементов, А — произвольный замкнутый класс, такой, что Ш^ С /I С М7'. Тогда класс А не является конечно порожденным.

Теорема 2 (теорема 2.3.9). Пусть У — произвольное множество из семейства А27 содержащее пару 2-несравнимых элементов. Тогда в семействе Т3, найдется как цепь, так и антгщепь континуальной мощности.

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

О У

М< и М<" — множеств певозрастающпх функций, монотонных относительно частично упорядоченных множеств типа башня (п > 3). Отметим, что множество М<" удовлетворяет соотношению С М<" С МТп, поэтому из теоремы 1 следует, что класс М<" не является конечно порожденным. Для удобства изложения положим

^ = М%п( 1) и Г1 = М£"(1). Сначала на множествах /'' и вводятся операции композиции и свертки, обозначаемые через о и V соответственно. Результатом применения операции свертки к функциям /ид является функция (/ V д), определяемая следующим образом:

Операция свертки интересна тем, что позволяет получить критерий порождения множества Г относительно только операции композиции, используя

х, если д(х) ^ 0; /(х), если д(х) = 0.

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

В §3.2 определяются множества функций С1, Za^ Zь, семейство множеств функций 6 и устанавливается критерий полноты для функциональной системы (Р, {о, у}) в терминах этих множеств. Далее, с использованием этого результата строятся множества функций £), I)1 и А'1, являющиеся единственными минимальными по включению порождающими множествами для функциональных систем (Т7, {о}), (^1,{о}) и (^1,{о,у}) соответственно. Основные результаты главы 3 могут быть сформулированы следующим образом.

Теорема 3 (теорема 3.3.18). Пусть А С .Р. Замыкание мноэюеетва А относительно операций {о, у} совпадает с Р тогда и только тогда, когда Сп С А и найдется С Е такое, что С С Л,

Теорема 4 (теорема 3.4.3). Пусть АСЕ. Замыкание мноэюеетва А относительно операций {о} совпадает с Р тогда и только тогда, когда ОСА.

Теорема 5 (теорема 3.5.6). Пусть А С Р1. Замыкание мноэюеетва А относительно операций {о} совпадает с И1 тогда и только тогда, когда Я1 С А.

Теорема 6 (теорема 3.6.6). Пусть А С Р1. Замыкание множества А относительно операций {о, у} совпадает с Р1 тогда и только тогда, когда К1 С А.

В главе 4 устанавливается критерий полноты для множества 9Л^(2) -множества двухместных ограниченно селекторных функций, монотонных относительно ф, где ф является частично упорядоченным множеством типа башня высоты п (п > 3) с максимальным элементом. Отметим, что из теоремы 1 следует, что класс 9Л® не является конечно порожденным, поэтому представляется интересным получение критериев полноты для мно-

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

В §4.1 вводятся множества одноместных функций и рассматри-

вается множество Г, которое состоит из упорядоченных пар одноместных функций, таких, что первый элемент пары принадлежит множеству а второй — множеству Далее определяются отображения до и д\, которые каждой функции из множества сопоставляет функцию из множеств .Р< и соответственно. После этого определяется отображение д : —> Г, которое каждой двухместной функции / из множества Ш® ставит в соответствие пару одноместных функций (до(/), Затем на множествах Е> определяются операции Фо и Ф1, являющиеся обобщениями операции свертки (см. главу 3). Далее на множестве Г рассматриваются операции специального вида 0 и Ф, определенные следующим образом:

(/о, /1) <8> (до, д\) = (/о о д0, /1 о д1), Ф((/о,Л), (90,91), (¿оА)) - (Фо(/о^о,Ло),Ф1(/ь5ьМ)-

Операции <8) и Ф интересны тем, что позволяют в некотором смысле сводить изучение вопросов порождения двухместных функций из множества Ш® к изучению порождения множества Р относительно этих операций. А именно, показывается, что замыкание произвольного множества А С 9Л®(2) содержит множество 9Л^(2) тогда и только тогда, когда замыкание множества д(А) и {е} относительно операций (2) и Ф совпадает с Р, где е — тождественная функция на множестве Р. В §4.2 устанавливается критерий полноты для системы (Р,{<8>,Ф}) в терминах свойств пар функций и порождения множеств Р> относите