Слабо импликативно и комбинаторно селекторные множества тема автореферата и диссертации по математике, 01.01.06 ВАК РФ

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

Иванов Дмитрий Иванович

СЛАБО ИМПЛИКАТИВНО И КОМБИНАТОРНО СЕЛЕКТОРНБ1Е МНОЖЕСТВА

01.01.06 — математическая логика, алгебра и теория чисел

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

Екатеринбург - 2007

003066585

Работа выполнена на кафедре алгебры и математической логики Тюменского государственного университет га,

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

профессор Дёгте в Александр Николаевич

Официальные оппоненты: доктор физико-математических наук,

профессор Попов Владимир Юрьевич

кандидат физико-математических наук, доцент Захаров Сергей Дмитриевич

Ведущая организация: Институт Математики им, С. Л. Соболева

СО РАН, Новосибирск

hjOO

Защита диссертации состоится « 23 » октября 2007 г. а «/У-я часов на заседании диссертационного совета Д 004.006.03 в Институте математики и механики УрО РАН но адресу: 620219, г. Екатеринбург, ул. С. Ковалевской 16.

С диссертацией можно ознакомиться в библиотеке Института математики и механики УрО РАН.

Автореферат разослан «£Р» Зе*гТл fjL&m г.

Ученый секретарь диссертационного сонет а,

доктор физ.-мат, наук В. В. Кабанов

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы

Диссертация посвящена одному из новых подходов к классификации подмножеств N = {0,1,2, } множества всех целых неотрицательных чисел, который использует булевы функции и эффективную вычислимость Первым, кто заинтересовался этим направлением, был Э Пост [16] Среди рекурсивно перечислимых множеств он определил классы рекурсивных, простых, креативных и мезоичных [11] множеств Позже [10], [12] класс мезоичных множеств был разбит на семейства псевдопростых и псевдокреативных множеств Однако, как пишет в своей монографии X Роджерс [8], "это полезный каталог изученных к настоящему времени типов множеств, но с теоретической точки зрения, несколько произвольный" Другой подход к изучению произвольных подмножеств множества N заключается в их классификации по "сложности" Инструментом для такой классификации служит понятие сводимости, являющееся одним из центральных в теории алгоритмов На интуитивном уровне множество А сводимо к множеству В, если существует алгоритм, который решал бы проблему вхождения элементов для множества А при условии, что есть возможность по мере надобности пользоваться информацией о принадлежности тех или иных чисел из N множеству В Наиболее пристальное внимание было уделено /я-, табличной (//-) и тьюринговой (Г -) сводимостям, введенных также Э Постом Среди рекурсивно перечислимых множеств т - лолные (креативные [15]) являются наиболее "сложными", а рекурсивные, для которых существует эффективная процедура распознавания принадлежности к ним любого числа из N, наиболее "простыми" Вопрос о существовании относительно Т - сводимости множеств, промежуточных по сложности, получили название проблемы Поста Она была положительно решена независимо Р Фридбергом [13] и А А Мучником [7]. Что касается сводимостей, промежуточных между

т - и tt - сводимостями, то основными оказались еще пять Ьщ -ограниченная «-сводимость с нормой 1, с-конъюнктивная, d -дизъюнктивная, р - позитивная и /-линейная [1], [9] Важные результаты о соотношениях между этими сводимостями были получены А Н Дегтевым [2], [3], [4]

В работе [14] К Джокуш ввел понятие полурекурсивного множества, именно, подмножество А множества N называется полурекурсивным, если существует двуместная общерекурсивная функция (ОРФ) / такая, что

МУуХЛ*. у) е к Л A (z(x) V х(у)) = 1« /U, у)*А),

где % ~ характеристическая функция множества А По аналогии А Н Деггев определил понятие (3-комбинаторных [5] множеств, а именно, множество А называется р -комбинаторным, где Р ~ произвольная и-местная булева функция, при условии р{х, ,х)= х, если существует «-местная общерекурсивная функция /, такая что

(Vxb ,xnX/S(x(x,), ,*(*„))= 1<=>/(хj, ,x„)eA)

Оказалось, что число различных классов ^-комбинаторных множеств равно семи

Если потребовать, чтобы ОРФ f была селекторной, т е (v*b ,x„Xf(xh ,xn)<s{xx, ,*„}),

то придем к определению понятия р -селекторного [5] (р-комбинаторно-селекторного (Р-КС)) множества Выяснилось, что число различных классов Р -селекторных множеств всего три класс всех рекурсивных, класс всех полурекурсивных и класс всех подмножеств V

Далее, если в определении /?-комбинаторно-селекторного множества эквивалентность заменить на импликацию, то получим определение /?-ымпликативно-селекторного (р-ИС) множества [6], множество А

4

называется уЗ-импликативно-селекторным, если существует «-местная селекторная ОРФ / такая, что

Пусть т> 1, семейство всех Рт+\ -ИС множеств, где

Рт+1= & [xlvx^)

1</< ]<т+\

Центральным результатом статьи [6] является следующая теорема если /3-БФ такая, что {¡(х, ,х) = х, то семейство /3-ИС множеств совпадает с

одним из ¡7^т\ т > 1 или причём имеют место строгие включения

^с^с сИ")с с»

Обобщением данных понятий послужили работы [17] и [18], где в определении в качестве / используется селекторная частично-рекурсивная функция (ЧРФ), т е такая, что

(V*!, ,хп^/{хь ,х„)4=>/(хь ,х„)е{хь ,*„}),

где /(х], ,хп)1 означает, что значение /(.*], ,хп) определено

Именно, множество А с. N называется слабо /? -нмпликативно-селекторным (слабо /3-ИС), где /? - я-местная булева функция, если существует «-местная частично-рекурсивная функция / такая, что

(Ухь ,х„)(р(х(хД ,х(хп)) = 1^>/(хъ ,х„)еАп{хи ,дг„}>

Далее, множество А называется слабо /3-комбинаторно-селекторным множеством (слабо р-КС). если существует и-местная ЧРФ ( такая, что

«Х^Ь Ь >*яН=>/(*1> -хп)^{х1> >*„}),

При этом в обоих определениях функцию / называют соответствующей множеству А

Обозначим через К(0) (Riß)) класс слабо ß-WZ (соответственно /?-КС) множеств, считая размерностью K(ß) ( R{ß)) число существенных переменных булевой функции ß Назовём функцию ß допустимой, если ß* 0,1 и ß(ö, ,0)= 0 Кроме того, будем рассматривать БФ ß с точностью до перестановки переменных Рассмотрению именно этих классов множеств и посвящена настоящая диссертация

Цель работы

При написании диссертационной работы были поставлены следующие цели во-первых, описать классы K{ß) и R(ß) для произвольных БФ ß, во-вторых, выяснить соотношения между этими классами по включению

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

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

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

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

- полностью описаны все классы слабо ß-ИС множеств, размерность которых не превосходит трех, как и монотонных слабо /?-ИС множеств размерности не выше четырех, и выяснены соотношения между ними по включению (теоремы 111 и 112) В частности, классов монотонных слабо ß-ИС множеств оказалось бесконечно много (теорема 113),

- полностью описаны все классы слабо ¡3-ИС множеств для линейных и самодвойственных (размерности не выше четырех) БФ ¡3 и выяснены соотношения между ними по включению (теоремы 1 4 1 и 1 4 2),

- полностью описаны все классы размерности 3 слабо /?-КС множеств как для монотонных, так и для немонотонных БФ ¡3 и выяснены соотношения между ними по включению Этот результат также обобщен для случая БФ произвольной размерности (теоремы 2 2 1 и 2 2 2)

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

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

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

Изложенные в диссертации результаты были представлены на международной конференции, посвященной 200-летию Казанского государственного университета (Казань, 2-9 июня 2004 года), а также на межрегиональных конференциях "Современные математические методы и информационные технологии в образовании" (Тюмень, 14-16 апреля 2005 года, 18 апреля 2007 года) Кроме того, полученные результаты регулярно докладывались на заседаниях кафедры алгебры и математической логики Тюменского государственного университета По результатам работы автор выступал с докладом в Уральском государственном университете на семинаре "Алгебраические системы" (Екатеринбург, 8 февраля 2007 год)

Публикации

Основные результаты диссертации опубликованы в семи работах, список которых приведен в конце автореферата [17-23] Результаты первых трех из них получены в соавторстве с научным руководителем А Н Дегтевым

Структура диссертации

Текст диссертации состоит из оглавления, введения, двух глав, объединяющих 6 параграфов, заключения и списка литературы Библиография включает 38 наименований Общий объем диссертации составляет 73 страницы

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

В главе 1 изучаются слабо ¡3 -импгшкативно селекторные множества, где /3- допустимая БФ В § 1 1, с использованием определенной техники, выписаны все допустимые БФ, зависящие от двух и трёх переменных (с точностью до их перестановок) Их оказалось 4 и 34 соответственно В § 1 2 описаны с точностью до включения все классы K(j3) слабо /3-ИС множеств для допустимых БФ, размерность которых не превосходит трех Центральным результатом данного параграфа является

ТЕОРЕМА 12 1 [18] Каждый класс К{/3) слабо импликативно-селекторных множеств, размерность которого не превосходит трех, совпадает с одним из классов

причем К Q с: К-^ с^с Кц и а К\ с. и все включения строгие

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

K0 = K(xvy), К] = К(ху v xz v yz),

К4 = К(х),

Полученный результат можно изобразить в виде диаграммы включений классов К(р)

§ 1 3 посвящён изучению классов слабо /?-ИС множеств монотонных БФ, размерность которых не выше четырёх Доказана следующая

ТЕОРЕМА 13 2 [21] Если /3 - монотонная булева функция и К{0) имеет размерность не выше четырех, то К{0) совпадает с одним из классов К(х V у), К(ху V хг V у г), К(и(ху V хг V уг) V хуг), К{х), и

К{х\/ у)а К(ху V лг V уг)с К(и{ху V хг V у:) V хуг)с К{х),

причем все включения строгие

Что же касается булевых функций произвольной размерности, доказывается, что классов монотонных слабо /3-ИС множеств существует:

бесконечно много Обозначим класс всех слабо 8т -импликативно

селекторных множеств, где

8т = V {хчх1г' х>т1 для т>\ 1<;]«2< <1т<т+1

С использованием метода приоритета доказана ТЕОРЕМА 13 1 К^1"^ а для т>2

Наконец, в § 1 4 получены результаты для произвольных линейных и самодвойственных БФ, размерность которых не выше четырех Они отражены в следующих двух теоремах

ТЕОРЕМА 141 [19] Если ß - допустимая линейная булева функция, то класс K(ß) совпадает с одним из классов К(х v у), к(ху v ху\ К(х), и

К(х v у) а К^ку v ху)с К{х), причем все включения строгие

ТЕОРЕМА 142 [19] Класс самодвойственных слабо имплшативно селекторных множеств размерности не выше четырех совпадает с одним из классов К{х v у), К(ху v xzv yz), К(х), и

K(xv у) с. К(ху v xz v yz) с К(х), причем включения везде строгие

В главе 2 изучаются слабо ß-KC, множества В § 2 I рассматриваются классы, порожденные монотонными БФ Вначале получен ответ для тех БФ, размерность которых не превышает трех Затем этот результат был обобщен для БФ произвольной размерности и доказана

ТЕОРЕМА 2 1 1 [22] Если ß - монотонная булева функиия, то R(ß) содержится в одном из следующих классов R(х v у), R(xy vjcv yz), R(xy), R(x), и

r(x v у) с r{xy v xz v yz)cz r(xy) с r(x). причем включения везде строгие

В случае немонотонных БФ (§ 2 2) оказалось, что если а -немонотонная БФ, то всякое слабо а-КС множество имеет рекурсивно перечислимое дополнение После рассмотрения всевозможных случаев БФ получен следующий результат

ТЕОРЕМА 2 2 1 [22] Если ß - немонотонная булева функция, то класс R{ß) совпадает или с классом всех рекурсивных множеств, или с классом всех полурекурсивных множеств с рекурсивно-перечисчимыми дополнениями или с классом всех множеств, имеющих рекурсивно-перечислимые дополнения

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

[1] БулиткоВ К Сводимости чинейными по Жегалмну таблицами //Сиб мат журнал,-! 980,-Т 21,-№3,-С 23-31

[2] Дегтев А Н Сравнение линейной сводимости с другими сводимостями табличного типа // Алгебра и логика,-1982,-Т 21,-№ 5, С -511-529

[3] Дегтев А Н Соотношения между степенями табличного типа //Алгебра и логика,-1983,-Т 22,-№ 1,-С 35-52

[4] Дегтев А Н Соотношения между сводимостями табличного типа //Алгебра и логика,-1983,-Т 22,-№ 3,-С 243-259

[5] Дегтев А Н Рекурсивно-комбинаторные свойства подмножеств натуральных чисел //Алгебра и логика,-1990,-Т 29,-№ 3,-С 303314

[6] Дегтев А Н Импликативно-сечекторные множества II Алгебра и логика,-1996,-Т 35,-№2,-С 145-153

[7] Мучник А А Неразрешимость проблемы сводимости теории алгоритмов //ДАН СССР, 1956,-Т 108,-С 194-197

[8] Роджерс X Теория рекурсивных функций и эффективная вычислимость Пер с англ-М Мир,-1972

[9] Селиванов В Л Об одном классе сводимостей в теории рекурсивных функций // Вероятностные методы и кибернетика,-1982,-Т 18,-С. 83-100

[10] Успенский В А Несколько замечаний о перечислимых множествах // Z Math Logic Grundlag Math ,-1957,-№3,-С 157170

[11] Dekker J С Е Two notes on recursively enumerable sets // Proc Amer Math Soc ,-1953,-№4,-P 495-501

[12] Dekker J С E, Myhill J Some theorems on classes of recursively enumerable sets II Trans Amer Math Soc,-1958,-V 89,-P 25-59

[13] Friedberg R M Two recursively enumerable sets of uncomparable degrees of unsolvability II Proc Nat Acad Sci ,-1957,-V 43,-P 236238

[14] Jockusch С G Semirecurcive sets and positive reducibility II Trans Amer Math Soc,-1968,-V 131,-№2,-P 420-436

[15] Myhill J Creative sets HZ Math Logic Grundlag Math ,-1955,-V l,-№ 2,-P 97-108

[16] Post E L Recursively enumerable sets of positive integers and their decision problem II Bull Amer Math Soc ,-1944,-V 50,-№ 5,-P 284-316

Работы автора по теме диссертации

[17] Дегтев А Н, Иванов Д И Слабо комбинаторно-селекторные множества //Алгебра и логика,-1998,-Т-37, № 6,-С 627-636

[18] Дегтев А Н, Иванов Д И Слабо импликативно-селекторные множества размерности 3 II Дискретная математика,-1999,-Т 11,-№ 3,-С 126-132

[19] Дегтев А Н, Иванов Д И О классах линейных и самодвойственных слабо импликативно-селекторных множествах И Вестник ТюмГУ,-2004,- № 4,-С. 238-241

[20] Иванов Д И О некоторых вопросах слабо комбинаторно и импликативно сечекторных множеств // Труды Математического центра имени Н И Лобачевского, Казань, Казанское математическое общество,-2004,-Т 23,-С 53-54

[21] Иванов Д И О слабо комбинаторно и импликативно селекторных множествах Межрегиональная конференция "Современные математические методы и информационные технологии в образовании", тезисы докладов, 14-16 апреля 2005 г, Тюмень

[22] Иванов Д И О слабо гшппикативно-селекторных множествах II Известия ВУЗов Математика,-2006,- № 9 (532),-С 29-33

[23] Иванов Д И О слабо комбинаторно-сечекторных множествах // Известия ВУЗов Математика,-2006,- № 11 (534),-С 22-25

Подписано в печать 13 06 2007 Формат 60x84/16 Уел печ л 2 Гарнитура Times Печать ризограф

Тираж 100 экз Зак № 781

***

Типография «Печатник» Тюмень, ул Республики, 148 корп 1/2 Тел (3452) 20-51-13, тел /факс (3452) 32-13-86

ОГЛАВЛЕНИЕ.

ВВЕДЕНИЕ.

ГЛАВА 1. СЛАБО ИМПЛИКАТИВНО-СЕЛЕКТОРНЫЕ МНОЖЕСТВА.

§ 1.1. ДОПУСТИМЫЕ БУЛЕВЫ ФУНКЦИИ ОТ ДВУХ И ТРЁХ ПЕРЕМЕННЫХ.

§ 1.2. ОПИСАНИЕ КЛАССОВ СЛАБО р-ИМПЛИКАТИВНО СЕЛЕКТОРНЫХ

МНОЖЕСТВ РАЗМЕРНОСТИ 3.

§ 1.3. ОПИСАНИЕ КЛАССОВ СЛАБО Р-ИМПЛИКАТИВНО СЕЛЕКТОРНЫХ МНОЖЕСТВ ДЛЯ МОНОТОННЫХ БУЛЕВЫХ ФУНКЦИЙ РАЗМЕРНОСТИ 4.

§ 1.4. ОПИСАНИЕ КЛАССОВ СЛАБО р-ИМПЛИКАТИВНО СЕЛЕКТОРНЫХ

МНОЖЕСТВ ДЛЯ ЛИНЕЙНЫХ И САМОДВОЙСТВЕННЫХ ФУНКЦИЙ.

ГЛАВА 2. СЛАБО КОМБИНАТОРНО-СЕЛЕКТОРНЫЕ МНОЖЕСТВА.

§ 2.1. МОНОТОННЫЕ СЛАБО р-КОМБИНАТОРНО-СЕЛЕКТОРНЫЕ

МНОЖЕСТВА.

§ 2.2. НЕМОНОТОННЫЕ СЛАБО Р-КОМБИНАТОРНО-СЕЛЕКТОРНЫЕ

МНОЖЕСТВА.

Теория алгоритмов зародилась в тридцатых - сороковых годах прошлого столетия благодаря работам А. Тьюринга [30] и С. Клини [22]. В этих работах была доказана эквивалентность различных уточнений понятия вычислимой функции и обоснован известный тезис Чёрча. Другой основополагающей работой в этом направлении принято считать статью Э. Поста [26], опубликованную в 1944 году. В ней обращено внимание на те подмножества N = {0,1,2,.}, элементы которых можно эффективно перечислять, такие подмножества образуют класс рекурсивно-перечислимых множеств (РПМ). Наиболее "простыми" из них являются так называемые рекурсивные множества, для которых имеются алгоритмы, позволяющие правильно отвечать на вопросы о принадлежности к ним любых чисел из N. В этой же статье Э. Пост привёл некоторые примеры нерекурсивных рекурсивно-перечислимых множеств, в частности креативных и простых. Существуют и другие, которые были названы Деккером [15] мезоичными. Классификация РПМ была предпринята Деккером и Майхиллом [16] и Успенским [13], которые разбили класс мезоичных множеств на псевдопростые и псевдокреативные множества. В результате дальнейшего разбиения были получены другие классы. Это широкий список изученных к настоящему времени типов множеств, но с теоретической точки зрения, несколько произвольный.

Один из подходов к изучению свойств РПМ заключается в рассмотрении решётки которую образует семейство всех РПМ вместе с операциями пересечения и объединения множеств. Оказалось, что в решётке £ определены классы рекурсивных, простых, рекурсивно неотделимых и других множеств. Д. Мартин доказал, что класс гиперпростых множеств не определим в этой решётке [27]. В 1983 году была установлена неразрешимость элементарной теории £ [18], [19].

Существенный вклад в изучение решётки £ внесли Р. Фридбергер [17], построивший максимальное множество, и А. Лахлан [25], описавший класс, так называемых гипергиперпростых множеств. Эти множества являются определимыми в решётке Неожиданным оказался результат Харрингтона

29], который доказал определимость в t креативных множеств. Последние успехи в данном направлении отражены в книге Р. Соара [12], который получил важные результаты об автоморфизмах £ [28].

Другой подход к изучению РПМ и произвольных подмножеств множества N заключается в попытке их классификации по "сложности". Инструментом для такой классификации служит понятие сводимости, являющееся одним из центральных в теории алгоритмов. На интуитивном уровне множество А сводимо к множеству В, если существует алгоритм, который решал бы проблему вхождения элементов для множества А при условии, что есть возможность по мере надобности пользоваться информацией о принадлежности тех или иных чисел из N множеству В. В этом случае А оказывается "проще устроено", чем А, или (в определённом смысле) А рекурсивно относительно В. Такая сводимость в наиболее общем виде называется Тыоринговой (Т-) сводимостью.

Наряду с Т - сводимостью уже в 1944 году Э.Пост [26] ввел некоторые специальные виды сводимостей, такие как m - сводимость, табличная (// -) и ограниченная табличная (btt -) сводимости. Именно, множество А т- сводимо к множеству В {А <т В), если существует всюду определенная на N вычислимая функция / такая, что хеЛ<=> f(x)eB для всех xeN. Множество A tt- сводимо к В (А <п В), если существует алгоритм, который для каждого xeN дает набор чисел ^п(х)) и булеву функцию

0х\уи->Уп(х)) такие> что х)[х е А о х[*п(х)]}= l)> где z(0 = Ь если ' и z(0 = ®> если частности, если п(х) для всех д: не больше некоторого фиксированного числа, то говорят, что А btt - сводимо к В. Сводимости, промежуточные по своей силе между т - и tt - сводимостью, были названы сводимостями табличного типа.

Как выяснилось, на множестве всех собственных подмножеств N существуют в точности семь различных основных сводимостей, а именно: m, , с, d, pj,tt [1], [11], где -ограниченная //-сводимость с нормой 1, с - конъюнктивная, й? - дизъюнктивная, р-позитивная и /-линейная сводимости. Каждая сводимость г, если положить А =г В <=> А <г В лВ <г А, разбивает множество подмножеств N на классы эквивалентности, называемые г - степенями. Если г - степень содержит РПМ, то её называют рекурсивно перечислимой г - степенью. Важные результаты о строении верхних полурешёток РП г - степеней [3], а так же о соотношении между различными сводимостями табличного типа [5], [6], [7] были получены А. Н. Дегтевым. Кроме того, решена проблема соотношения между классами г-полных множеств [4] и установлено, что элементарные теории полурешёток Ltt, Ц, Lp, Lj, Lc, Lm и попарно различны [2].

Ещё одна классификация подмножеств множества N была предложена А. Н. Дёгтевым. В работе [20] К. Джокуш ввёл понятие полурекурсивного множества, именно, подмножество А множества N называется полурекурсивным, если существует двуместная общерекурсивная функция (ОРФ) / такая, что

Vx)(Vy)(/(x, у) е {х, л (*(*) v Х(у)) =1<* f(x, у) е А), где х - характеристическая функция множества А. По аналогии А. Н. Дёгтев определил понятие /?-комбинаторных [8] множеств, а именно, множество А называется -комбинаторным, где /?-произвольная «-местная булева функция (БФ), если существует и-местная общерекурсивная функция (ОРФ) / такая что

Щ,.,х„№{х(х11.,х(х„)) = 1 <=> f{xh.,xn)e А), Оказалось, что классы ^-комбинаторных множеств тесно связаны с основными сводимостями табличного типа.

Если потребовать, чтобы ОРФ/была селекторной, т. е. fxh.,xnXf(x\,.,xn)e{xh.,xn}), то придём к определению понятия /3-селекторного [8] (/?-комбинаторно-селекторного (у3-КС)) множества. Выяснилось, что семейство /?-селекторных множеств совпадает либо с семейством всех рекурсивных, либо с семейством всех полурекурсивных множеств, либо с семейством всех подмножеств N.

Далее, если в определении (3-комбинаторно-селекторного множества эквивалентность заменить на импликацию, то получим определение /?-импликативно-селекторного (/? -ИС) множества [10], множество А называется /?-импликативно-селекторным, если существует «-местная селекторная ОРФ/такая, что

Доказано, что если р- БФ, такая, что р(х, х,.,х) = х, то семейство /?-ИС множеств совпадает с одним из F^m\ т> 1, или с причём имеют место строгие включения

F(1)cF(2)c.cFWc.cFW) здесь, F^ - семейство всех d*m+\ -ИС множеств, где d*m+1= & {xiVXj).

1 </'< j<m+\

Обобщением данных понятий послужили работы [32] и [33], где в определении в качестве / используется селекторная частично-рекурсивная функция (ЧРФ), т. е. такая, что где f{x\,.,xn)i означает, что значение f{xi,.,xn) определено.

Именно, множество AqN называется слабо [3-импликативно-селекторным (слабо /3-ИС), где (3 - п-местная булева функция, если существует «-местная частично-рекурсивная функция/такая, что:

Vxjхп Шх{ц),-., zfan)):=1 Ах\>•••>хп)еАп{х\ v. хп}).

При этом функцию/называют соответствующей множеству А.

Далее, множество А называется слабо (3-комбинаторно-селекторным множеством (слабо /3-КС), если существует я-местная ЧРФ/такая, что х„ )(/{х{,., х„) f{x\,., хп) е foхп}); 6)(Vx],., х„ Mz(x 1),., %(хп)) = Ю f{x\,., хп) е А), где х - характеристическая функция множества А. Функция /соответствует множеству А.

Обозначим через К{(3) (R{0)) класс слабо /3-ИС (соответственно (3-КС) множеств, считая размерностью К{(3) {R{0)) число существенных переменных булевой функции (3. Назовём функцию [3 допустимой, если /7*0,1 и /?(0,.,0) = 0.

Данная работа посвящена рассмотрению именно этих классов множеств, при изучении которых были поставлены следующие задачи: во-первых, описать всевозможные классы К((3) и R{0) для произвольных БФ /3; во-вторых, выяснить соотношения между этими классами по включению. Работа состоит из введения, двух глав, объединяющих 6 параграфов, заключения и списка использованной литературы, насчитывающего 38 наименований.

В главе 1 изучаются слабо /?-импликативно селекторные множества, где Р-допустимая БФ. В § 1.1, с использованием определённой техники, выписаны все допустимые БФ, зависящие от двух и трёх переменных (с точностью до их перестановок). В § 1.2 описаны с точностью до включения все классы К(р) слабо P-WC множеств для допустимых БФ, размерность которых не превосходит трёх. Центральным результатом данного параграфа является

ТЕОРЕМА 1.2.1. [33]. Каэ/сдый класс К{0) слабо импликативно-селекторньгх множеств, размерность которого не превосходит трёх, совпадает с одним из классов К0 = К(х v у), К\ = К{ху v xz v yz), Kj = к{ху v ху), К2 = к(хуг v xyz v xyzj, К4 = К{х), причём Kg с К2 с К^ а К4 и Kq с К\ с К^ и все включения строгие.

Полученный результат можно изобразить в виде диаграммы включений классов К{0):

§ 1.3 посвящен изучению классов слабо /?-ИС множеств монотонных БФ, размерность которых не выше четырёх. Доказана следующая

ТЕОРЕМА 1.3.2. [36]. Если /? -монотонная булева функция, и К{0) имеет размерность не выше четырёх, то К(/3) совпадает с одним из классов: К(х v у), К(ху v xz v yz), К(и(ху vxzv yz) v xyz), К(х), и к(х v у) с К{ху V xz v yz) С к{и{ху v xz v yz) v xyz) С к(х), причём все включения строгие.

Кроме того, доказывается, что классов монотонных слабо /?-ИС множеств существует бесконечно много (теорема 1.3.1).

Наконец, в § 1.4 получены результаты для произвольных линейных и самодвойственных БФ, размерность которых не выше четырёх. Они отражены в следующих двух теоремах.

ТЕОРЕМА. 1.4.1. [34]. Если /? - допустимая линейная булева функция, то класс К{0) совпадает с одним из классов: К{х v у), к[ху v ху), К(х), и

К(х v у)с К.{ху v ху)с причем все включения строгие.

ТЕОРЕМА. 1.4.2. [34] Класс самодвойственных слабо импликатнвно селекторных множеств размерности не выше четырёх совпадает с одним из классов: К{х v у), К(ху vxzv yz), К(х\ и

К(х v у) с к(ху v xzv yz) с К{х), причем включения везде строгие.

В главе 2 изучаются слабо /3-КС множества. В § 2.1 рассматриваются классы, порождённые монотонными БФ. Вначале получен ответ для тех БФ, размерность которых не превышает трёх. Затем этот результат был обобщён для БФ произвольной размерности и доказана

ТЕОРЕМА 2.1.1. [37]. Если (3 -монотонная булева функция, то R{P) содержится в одном из следующих классов:

R(x v у), R(xy v xz v yz), R(xy), R(x), и

R(x v у) с R(xy v xzv yz) с R(xy) с причём включения везде строгие.

В случае немонотонных БФ (§ 2.2) оказалось, что если а-немонотонная БФ, то всякое слабо «-КС множество имеет рекурсивно перечислимое дополнение. После рассмотрения всевозможных случаев БФ получен следующий результат:

ТЕОРЕМА 2.2.1. [37]. Если Р - немонотонная булева функция, то класс R{ft) совпадает или с классом всех рекурсивных множеств, или с классом всех полурекурсивных множеств с рекурсивно-перечислимыми дополнениями или с классом всех множеств, имеющих рекурсивно-перечислимые дополнения.

ЗАКЛЮЧЕНИЕ

Таким образом, основными результатами данной работы являются:

1. Найдены все, с точностью до перестановки переменных, допустимые БФ, зависящие от трёх переменных.

2. Полностью описаны все классы слабо /3 -ИС множеств, размерность которых не превосходит трёх, как и монотонных слабо (3-ИС множеств размерности не выше четырёх, и выяснены соотношения между ними по включению (теоремы 1.1.1 и 1.1.2). В частности, классов монотонных слабо /?-ИС множеств оказалось бесконечно много (теорема 1.1.3).

3. Полностью описаны все классы слабо /?-ИС множеств для линейных и самодвойственных (размерности не выше четырёх) БФ /? и выяснены соотношения между ними по включению (теоремы 1.4.1 и 1.4.2).

4. Полностью описаны все классы размерности 3 слабо (3-КС множеств как для монотонных, так и для немонотонных БФ /3 и выяснены соотношения между ними по включению. Этот результат также обобщён для случая БФ произвольной размерности (теоремы 2.2.1 и 2.2.2).

1. Булитко В. К. Сводимости линейными по Жегалкину таблицами И Сиб. мат. журнал,-1980,-Т. 21,-№ 3,-С. 23-31.

2. Дёгтев А. Н. О сводимостях табличного типа в теории алгоритмов. II Успехи мтем. наук,-1979,-Т. 34,-№ 3,-С. 137-168.

3. Дёгтев А. Н. Несколько результатов о верхних полурешётках и т-степенях. II Алгебра и логика,-1979,-Т. 18,-№ 6,-С. 664-679.

4. Дёгтев А. Н. Соотношения между полными множествами. II Известия ВУЗов. Математика,-1981,-№ 5 (228),-С. 50-55.

5. Дёгтев А. Н. Сравнение линейной сводимости с другими сводимостями табличного типа. II Алгебра и логика,-1982,-Т. 21,-№ 5,-С. 51 1-529.

6. Дёгтев А. Н. Соотношения между степенями табличного типа. II Алгебра и логика,-1983,-Т. 22,-№ 1,-С. 35-52.

7. Дёгтев А. Н. Соотношения между сводимостями табличного типа. II Алгебра и логика,-1983,-Т. 22,-№ 3,-С. 243-259.

8. Дёгтев А. Н. Рекурсивно-комбинаторные свойства подмножеств натуральных чисел // Алгебра и логика,-1990,-Т. 29,-№ 3,-С. 303-314.

9. Дёгтев А. Н. Слабые комбинаторно-селекторные свойства подмножеств натуральных чисел. И Алгебра и логика,-1990,-Т. 29,-№ 4,-С. 421-429.

10. Дёгтев А. Н. Импликативно селекторные множества. II Алгебра и логика,-1996,-Т. 35,-№ 2,-С. 145-153.11 .Селиванов В. JI. Об одном классе сводимостей в теории рекурсивных функций II Вероятностные методы и кибернетика,-1982,-Т. 18,-С. 83-100.

11. СоарР. И. Вычислимо перечислимые множества и сводимости: Пер. сангл. Казань: Казанское математическое общество, 2000. И.Успенский В. А. Несколько замечаний о перечислимых множествах // Z.

12. Math. Logic Grundlag. Math.,-1957,-№3,-C. 157-170. Н.Яблонский С. В., Гаврилов Г. П., Кудрявцев В. Г. Функции алгебры логики и классы Поста. М.: Наука, 1966.

13. Dekker J. С. Е. Two notes on recursively enumerable sets. II Proc. Amer. Math. Soc,-1953,-№4,-P. 495-501.

14. Dekker J. С. E., Myhill J. Some theorems on classes of recursively enumerable sets. //Trans. Amer. Math. Soc.,-1958,-V. 89,-P. 25-59.

15. Fridberg R. M. Three theorems on recursive enumerable sets. II J. Symbolic Logic,-1958,-V. 23,-№ 3,-P. 309-316.

16. Harrington L. The undecidability of the lattice of recursively enumerable sets (handwritten notes).

17. Herrmann E. The undecidability of the elementary theory of the lattice of recursively enumerable sets (abstract), In: Frege Conference 1984, Proceedings of the International Conference at Schwerin (GDR), Akademie-Verlag, Berlin, 66-72.

18. Jockusch C. G. Semirecurcive sets and positive reducibility. И Trans. Amer. Math. Soc.,-1968,-V. 131,-№ 2,-P. 420-436.

19. Jockusch C. G., Owings J. C. Weakly semirecurcive sets. HI. Symbolic Logic,-1990,-V. 55,-№ 2,-P. 637-644.

20. Kleene S. C. Recursive predicates and quantifiers. II Trans. Amer. Math. Soc.,-1943,-V. 53,-№ 1,-P. 41-73.

21. Kummer M., Stephan F. Weakly semirecurcive sets and r. e. ordering. II Ann. Pure and Appl. Logic,-1993,-V. 60,-P. 133-150.

22. Lachlan A. N. On the lattice of recursively enumerable sets. II Trans. Amer. Math. Soc,-1968,-V. 130,-№ 1,-P. 1-37.

23. Lachlan A. N. The elementary theory of recursively enumerable sets. II Duke Math. J.,-1968,-V. 35,-№ 1,-P. 123-146.

24. Post E. L. Recursively enumerable sets of positive integers and their decision problem. //Bull. Amer. Math. Soc.,-1944,-V. 50,-№ 5,-P. 284-316.

25. Soare R. I. Automorphisms of the lattice of recursively enumerable sets, Part I: Maximal sets. //Ann. of Math.,-1974,-V. 100,-№1,-P. 80-120.

26. Soare R. I. Automorphisms of the lattice of recursively enumerable sets, Part II: Low sets. II Ann. Math. Logic,-1982,-V. 22,-№ 1,-P. 69-107.

27. Soare R. I. Recursively enumerable sets and degrees. -Berlin: Springer-Verlag.

28. Turing A. M. On computable numbers with an application to the Entschiduns problem II Pros. London Math.,-1936,-V. 32,-№ 3,-P. 230-265.

29. Yates С. E. M. Recursively enumerable sets and retracing functions. II Z. Math. Logic und Grundl.,-1962,-V. 8,-№ 4,-P. 331-345.

30. Работы автора по теме диссертации

31. Дёгтев А. Н., Иванов Д. И. Слабо комбинаторно-селекторные множества. II Алгебра и логика,-1998,-Т. 37,-№ 6,-С. 627-636.

32. Дёгтев А. Н., Иванов Д. И. Слабо импликативно-селекторные мнолсества размерности 3. II Дискретная математика,-1999,-Т. 11,-№ 3,-С. 126-132.

33. Дёгтев А. Н., Иванов Д. И. О классах линейных и самодвойственных слабо импликативно-селекторных множеств. II Вестник ТюмГУ,-2004,-№4,-С. 238-241.

34. Иванов Д. И. О некоторых вопросах слабо комбинаторно и импликативно селекторных множеств. // Труды Математическогоцентра имени Н. И. Лобачевского, Казань, Казанское математическое общество,-2004,-Т. 23,-С. 53-54.

35. Иванов Д. И. О слабо комбинаторно и импликативно селекторных множествах. Межрегиональная конференция "Современные математические методы и информационные технологии в образовании", тезисы докладов, 14-16 апреля 2005 г., Тюмень.

36. Иванов Д. И. О слабо импликативно-селекторных множествах. И Известия ВУЗов. Математика,-2006,-№ 9 (532),-С. 29-33.

37. Иванов Д. И. О слабо комбинаторно-селекторных множествах. II Известия ВУЗов. Математика,-2006,-№ 11 (534),-С. 22-25.