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

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИМЕНИ М В ЛОМОНОСОВА

МЕХАНИКО-МАТЕМАТИЧЕСКИЙ ФАКУЛЬТЕТ

На правах рукописи УДК 519 716

Дудакова Ольга Сергеевна

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

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

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

Москва - 2007

003071760

Работа выполнена на кафедре дискретной математики механико-математического факультета Московского государственного университета им М В Ломоносова

Научный руководитель Официальные оппоненты.

Ведущая организация

доктор физико-математических наук,

профессор А. Б Угольников

доктор физико-математических наук,

профессор В Б Алексеев,

кандидат физико-математических наук,

доцент В А Стеценко.

Казанский государственный университет

Защита диссертации состоится 18 мая 2007 г в 16 ч 15 мин на заседании диссертационного совета Д 501 001 84 в Московском государственном университете им M В Ломоносова по адресу 119992, ГСП-2, Москва, Ленинские горы, МГУ, механико-математический факультет, аудитория 14-08

С диссертацией можно ознакомиться в библиотеке механико-математического факультета МГУ (Главное здание, 14 этаж).

Автореферат разослан 18 апреля 2007 г

Ученый секретарь диссертационного совета Д 501 001.84 в МГУ доктор физико-математических наук, профессор

В H Чубариков

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

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

В теории функций многозначной логики важное место занимают задачи классификационного характера Одной из наиболее естественных и хорошо изученных классификаций является разбиение множества Рк всех функций fc-значной логики на классы, замкнутые относительно операции суперпозиции Все замкнутые классы функций двузначной логики были описаны Э Постом1, который показал, что число таких классов счетно

Несмотря на то, что многозначные логики во многом похожи на двузначную, имеют место и принципиальные различия К их числу относится пример континуального семейства замкнутых классов в Р* при к > 3, приведенный в работе Ю И Янова и А А Мучника2. Континуальность семейства всех замкнутых классов при к > 3 приводит к значительным трудностям при их изучении К настоящему времени изучены только некоторые семейства замкнутых классов в Рк К числу таких семейств относятся предполные классы функций Из теоремы А В Кузнецова3 следует, что при любом к > 2 в Рк существует конечное число предполных классов При к — 3 описание всех предполных классов было получено С В Яблонским4 Отдельные семейства предполных в P¡- классов при к > 4 были найдены С. В Яблонским, В В Мартынюком, Ло Чжу-Каем и другими исследователями. Полное описание предполных классов в Рк было получено И. Розенбергом5, который выделил шесть семейств

1 Post Е L Introduction to a general theory of elementary propositions // Amer J Math 1921 43, №3 P 163-185

Post E t The two-valued iterative systems of mathematical logic // Annals of Math Studies Princeton Univ Press 1941 5

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

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

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

5Rosenberg I G Uber die funktionale Vollständigkeit in den mehrwertigen Logiken // Rozpr CSAV MPV 1970 80 P 3-93

предполных классов6 классы самодвойственных функций — классы типа F, классы линейных функций — классы типа L, классы функций, сохраняющих разбиения множества Ек = {0,1, .., к — 1} — классы типа Е, классы функций, сохраняющих центральные отношения — классы типа С, классы функций, сохраняющих сильно голоморфные прообразы /t-адических элементарных отношений — классы типа В, и классы функций, монотонных относительно частично упорядоченных множеств с наименьшим и наибольшим элементами — классы типа О

Одной из наиболее важных проблем, связанных с семействами замкнутых классов функций многозначной логики, является задача о конечной порожденности, то есть задача о выразимости всех функций из замкнутого класса формулами над некоторым конечным множеством функций, принадлежащих этому же классу Из результатов Поста следует, что каждый замкнутый класс булевых функций имеет конечный базис В многозначных логиках этот результат не имеет места для любого к>ЗвРк существуют замкнутые классы как со счетным базисом, так и не имеющие базиса К настоящему времени отсутствует полное описание всех конечно-порожденных классов функций многозначной логики даже для семейства предполных классов. Д Лау7 показала, что любой предполный класс в Рк из семейств Р, L, Е, С и В порождается конечным числом функций Для предполных классов всех функций, монотонных относительно частично упорядоченных множеств (классов из семейства О) этот результат верен, вообще говоря, лишь при к < 7 Г. Тардошем8 приведен пример такого частично упорядоченного множества из восьми элементов, что предполный класс всех функций, монотонных на этом множестве, не имеет конечного базиса

К настоящему времени получен ряд достаточных условий конечной порожденности предполных классов монотонных функций В частности, из интерполяционной теремы К Бейкера и А Пиксли9 следует, что если в замкнутом классе содержится мажоритарная функция, то класс является конечно-порожденным. В работе Я. Деметровича, JI. Ханнака и JL Ро-

вВ диссертации используются обозначения из книги Яблонский С В , Гаврилов Г П, Набебип А А Предпалные классы в многозначных логиках M Изд-во МЭИ, 1997 142 с

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

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

8 Tardos G A not finitely generated maximal clone of monotone operations// Order 1986 3 P 211218

9Baker К, Foley A Polynomial interpolation and the Chinese remainder theorem for algebraic systems // Math Z 1975 143 P 165-174

няи10 приводится следующее условие предполный класс всех функций, монотонных на частично упорядоченном множестве V, имеет конечный базис, если множество V представляется в виде С\/С, где С — решетка, а 1С — выпуклое подмножество С, не содержащее наименьшего и наибольшего элементов С (отсюда, например, следует конечная порожден-ность классов функций, монотонных относительно решеток и линейно упорядоченных множеств) Этими же авторами показано11, что условие представимости множества V в виде С \ К эквивалентно отсутствию в множестве V четверки элементов а, Ь, с, d, таких, что а,Ь < с, элементы а и Ь не имеют точной верхней грани и элементы с и d не имеют точной верхней грани Доказательство конечной порожденное™ класса монотонных функций, приведенное в этих работах, опирается на существование в классе мажоритарных функций Отметим, что условие существования мажоритарных функций в классе не является необходимым для конечной порожденности этого класса даже для замкнутых классов булевых функций Примеры частично упорядоченных множеств, таких что классы всех функций, монотонных относительно этих множеств, являются конечно-порожденными, но не содержат мажоритарных функций, приведены в работе Я Деметровича и JI Роняй12, однако эти классы не являются предполными.

Цель работы

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

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

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

wDemetrovtcs X, Hannák L, Rânyat L Near unanimity functions and partial orderings // Proc 14 ISMVL, Manitoba. 1984 P 52-56

11 Demetrovtcs J, Hannák L , Rânyat L On algebraic properties of monotone clones // Order 1986 3 P 219-225

12Demetrovocs J, Rânyat L Algebraic properties of crowns and fences // Preprint, MTA SZTAK11

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

Все результаты работы являются новыми В диссертации получены следующие основные результаты

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

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

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

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

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

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

Апробация результатов

Результаты диссертации докладывались на семинаре "Функции многозначной логики и смежные вопросы" под руководством профессоров С Б Гашкова и А Б Угольникова (2005, 2006 гг.), на семинаре "Синтез и сложность управляющих систем" под руководством академика РАН О Б Лупанова (2006 г), на семинаре "Математические вопросы кибернетики" под руководством профессора О. М Касим-Заде (2007 г.), на VII Международной конференции "Дискретные модели в теории управляющих систем" (Покровское, март 2006 г), на XXVIII Конференции молодых ученых механико-математического факультета МГУ (апрель

2006 г), на научной конференции "Ломоносовские чтения" (Москва, МГУ, апрель 2006 г) на XVI Международной школе-семинаре "Синтез и сложность управляющих систем" (Санкт-Петербург, июнь 2006 г)

Публикации

Основные результаты диссертации опубликованы в 4 работах, список которых приведен в конце автореферата

Структура и объем работы

Диссертация состоит из введения, трех глав и списка литературы Полный объем диссертации — 107 страниц, список литературы содержит 48 наименований

Содержание работы

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

В первой главе приводятся основные определения, доказывается ряд свойств частично упорядоченных множеств специального вида, а также некоторые свойства монотонных функций и отображений В частности, определяются понятия ширины частично упорядоченного множества, минимальной верхней грани, точной верхней грани и точной верхней грани второго порядка пары элементов Шириной частично упорядоченного множества V называется максимальное число попарно несравнимых элементов этого множества Семейство всех частично упорядоченных множеств ширины два с наименьшим и наибольшим элементами обозначается через А2 Пусть а и 6 — несравнимые элементы множества V Элемент с называется верхней гранью элементов а и Ь, если выполняется неравенство с> а, Ь Верхняя грань с элементов а и Ъ называется минимальной веросней гранью этих элементов а и Ь, если ни для какого х не выполняются неравенства а,Ь < х < с Минимальная верхняя грань с элементов а и 6 называется точной верхней гранью этих элементов, если для любой верхней грани х элементов а и Ь выполняется неравенство х > с Элемент е называется точной верхней гранью второго порядка элементов о и Ь, если элементы а и Ь имеют две минимальные верхние грани с и й, и е является точной верхней гранью элементов си д, Точная

верхняя грань и точная верхняя грань второго порядка элементов а и Ь обозначаются через sup(o, b) и sup2(a, b) соответственно

Во второй главе устанавливается достаточное условие существования конечного базиса в классе Л4р всех функций, монотонных относительно некоторого частично упорядоченного множества V ширины два с наименьшим и наибольшим элементами Рассматривается семейство А^, состоящее из всех таких множеств V € Аг, что для любой пары несравнимых элементов аи5вР существует либо sup(o, b), либо sup2(a, b) В параграфе 2 1 устанавливается ряд соотношений для элементов произвольного множества V £ А^ В параграфе 2.2 определяются операторы ф и тр специального вида, и доказывается ряд свойств этих операторов. В параграфе 2 3 рассматриваются отображения /' : Q' —> V, где Q' — некоторое подмножество произвольного частично упорядоченного множества Q, а V — произвольное множество из семейства А^, и с помощью операторов фиф, определенных в предыдущем параграфе, задается доопределение отображения /' на множество Q! Основным результатом параграфа 2.3 является теорема о необходимых и достаточных условиях существования монотонного доопределения отображения /' Q' —> V на множество Q (теорема 2 3 1) В параграфе 2 4 на основе полученного критерия существования монотонного доопределения не всюду определенного отображения доказана теорема (теорема 2 4.1) о существовании в классе М-р, где V € некоторой мажоритарной функции, число переменных которой зависит только от мощности множества V. Из этого результата с помощью теоремы Бейкера и Пиксли получено утверждение о конечной порожденности класса М-р для любого множества V из семейства А^ (теорема 2.4 2).

В третьей главе доказывается критерий конечной порожденности класса всех функций, монотонных относительно множеств ширины два с наименьшим и наибольшим элементами В параграфе 3 1 приводится семейство А^ частично упорядоченных множеств ширины два, которым соответствуют предполные классы монотонных функций, не имеющие конечного базиса Основной результат параграфа 3 1 сформулирован в теореме 3.11 Для доказательства используется предложенный в диссертации метод, который является обобщением метода Тардоша13 на случай множеств произвольной мощности Рассматривается некоторое множе-

13 Tardes G A not finitely generated maximal clone of monotone operations // Order 1986 3 P 211218

б

ство V е /4 , для каждого значения п > 4 строится множество ТЬр,п наборов элементов множества V и устанавливается ряд свойств наборов из этого множества С помощью этих свойств показывается, что при всех значениях к < | множество 72-я,« сохраняется всеми функциями из класса М-р, зависящими от к переменных Далее, показывается, что существует функция /(х\, ,Х2п) € М-р, которая не сохраняет множество 71-р<п В параграфе 3 2 на основе результатов предыдущего параграфа и главы 2 приводится критерий конечной порожденности класса М-р, где V — произвольное частично упорядоченное множество ширины два с наименьшим и наибольшим элементами (теорема 3 2 1) На основе теоремы 3 2 1 получен критерий конечной порожденности классов монотонных функций в терминах существования в этих классах мажоритарных функций (теорема 3 2 2). Кроме того, из теоремы 3.2.1 следует существование полиномиального алгоритма для распознавания конечной порожденности соответствующих классов монотонных функций (теорема 3 2 3)

Благодарности

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

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

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

2 Дудакова О С О свойствах предполных классов монотонных функций /г-значной логики // Труды VII Международной конференции "Дискретные модели в теории управляющих систем" (Покровское, 4-6 марта 2006 г) М. МАКС Пресс 2006 С. 107-113

3 Дудакова О С Семейства предполных классов монотонных функций в Рк, не имеющих конечного базиса // Труды XXVIII Конференции молодых ученых механико-математического факультета

МГУ (10-15 апреля 2006 г.) М Изд-во ЦПИ при мех -матем фаг культете МГУ. 2006 С 55-59

4 Дудакова О С О конечной порожденное™ некоторых семейств предполных классов монотонных функций &-значной логики // Материалы XVI Международной школы-семинара "Синтез и сложность управляющих систем "(Санкт-Петербург, 26-30 июня 2006 г). М.. Изд-во мех -матем. факультета МГУ 2006. С 35-37.

Издательство ЦПИ при механико-математическом факультете МГУ им М В Ломоносова Подписано в печать// ОЦ, О? Формат 60x90 1/16 Уел печ л 0,5

Тираж 100 экз Заказ {9

Введение

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

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

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

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

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

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

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

2.3 Теорема о существовании монотонного доопределения не всюду определенного отображения.

2.4 Существование монотонной мажоритарной функции и достаточное условие конечной порожденности класса М-р.

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

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

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

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

В теории функций многозначной логики важное место занимают задачи классификационного характера. Одной из наиболее естественных и хороню изученных классификаций является разбиение множества Рвсех функций А'-значпой логики па классы, замкнутые относительно операции суперпозиции (см. [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].

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.