Слабо импликативно и комбинаторно селекторные множества тема диссертации и автореферата по ВАК РФ 01.01.06, кандидат физико-математических наук Иванов, Дмитрий Иванович

• Иванов, Дмитрий Иванович
• кандидат физико-математических наук
• 2007

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

ОГЛАВЛЕНИЕ.

ВВЕДЕНИЕ.

ГЛАВА 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).

Список литературы диссертационного исследования кандидат физико-математических наук Иванов, Дмитрий Иванович, 2007 год

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.