Слабо импликативно и комбинаторно селекторные множества

• Автор: Иванов, Дмитрий Иванович
• Шифр специальности: 01.01.06
• Научная степень: Кандидатская
• Год защиты: 2007
• Место защиты: Тюмень
• Количество страниц: 73 с. : ил.

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

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

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

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

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

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

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

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

МНОЖЕСТВА

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

МНОЖЕСТВА
ЗАКЛЮЧЕНИЕ
СПИСОК ЛИТЕРАТУРЫ
Теория алгоритмов зародилась в тридцатых - сороковых годах прошлого столетия благодаря работам А. Тьюринга [30] и С. Клини [22]. В этих работах была доказана эквивалентность различных уточнений понятия вычислимой функции и обоснован известный тезис Чёрча. Другой основополагающей работой в этом направлении принято считать статью
Э. Поста [26], опубликованную в 1944 году. В ней обращено внимание на те подмножества N = {0,1,2,...}, элементы которых можно эффективно перечислять, такие подмножества образуют класс рекурсивно-перечислимых множеств (РПМ). Наиболее “простыми” из них являются так называемые рекурсивные множества, для которых имеются алгоритмы, позволяющие правильно отвечать на вопросы о принадлежности к ним любых чисел из N. В этой же статье Э. Пост привёл некоторые примеры нерекурсивных рекурсивно-перечислимых множеств, в частности креативных и простых. Существуют и другие, которые были названы Деккером [15] мезоичными. Классификация РПМ была предпринята Деккером и Майхиллом [16] и Успенским [13], которые разбили класс мезоичных множеств на псевдопростые и псевдокреативные множества. В результате дальнейшего разбиения были получены другие классы. Это широкий список изученных к настоящему времени типов множеств, но с теоретической точки зрения, несколько произвольный.
Один из подходов к изучению свойств РПМ заключается в
рассмотрении решётки t, которую образует семейство всех РПМ вместе с операциями пересечения и объединения множеств. Оказалось, что в решётке £ определены классы рекурсивных, простых, рекурсивно неотделимых и
других множеств. Д. Мартин доказал, что класс гиперпростых множеств не определим в этой решётке [27]. В 1983 году была установлена
неразрешимость элементарной теории £ [18], [19].
Существенный вклад в изучение решётки £ внесли Р. Фридбергер [17], построивший максимальное множество, и А. Лахлан [25], описавший класс, так называемых гипергиперпростых множеств. Эти множества являются
определимыми в решётке £. Неожиданным оказался результат Харрингтона
[29], который доказал определимость в £ креативных множеств. Последние успехи в данном направлении отражены в книге Р. Соара [12], который
получил важные результаты об автоморфизмах £ [28].
Другой подход к изучению РПМ и произвольных подмножеств множества N заключается в попытке их классификации по “сложности”. Инструментом для такой классификации служит понятие сводимости, являющееся одним из центральных в теории алгоритмов. На интуитивном уровне множество А сводимо к множеству Л, если существует алгоритм, который решал бы проблему вхождения элементов для множества А при условии, что есть возможность по мере надобности пользоваться информацией о принадлежности тех или иных чисел из N множеству В. В этом случае А оказывается “проще устроено”, чем А, или (в определённом смысле) А рекурсивно относительно В. Такая сводимость в наиболее общем виде называется Тыоринговой (Г-) сводимостью.
Наряду с Т - сводимостью уже в 1944 году Э.Пост [26] ввел некоторые специальные виды сводимостей, такие как m - сводимость, табличная [tt -) и ограниченная табличная (btt -) сводимости. Именно, множество А /»-сводимо к множеству В (А <т В), если существует всюду определенная на N вычислимая функция / такая, что х е А <=> f(x)eB для всех xeN. Множество А tt-сводимо к В (А <и В), если существует алгоритм, который

§2.1. МОНОТОННЫЕ СЛАБО (3-КОМБИНАТОРНО-СЕЛЕКТОРНЫЕ МНОЖЕСТВА
Как известно, существует 8 различных монотонных БФ (с точностью до перестановок), отличных от констант, число существенных переменных которых не больше 3: х, ху, х V у, хуг, х V у V г, ху V уг, ху V уг V хг, ху V 2. Выясним, какие классы слабо КС множеств они образуют.
ЛЕММА 2.1.1. Если у получена из булевой функции Р в результате отождествления некоторых переменных или подстановки вместо некоторых переменных константы 0, то Л(/?)с Я{у).
ДОКАЗАТЕЛЬСТВО. Пусть р = р(х{ хп) и А слабо р- КС множество с соответствующей ЧРФ / = р(х хп) и функция у получена из Р в результате переименования переменной хп на хп_, т. е. /(х| х„_і)= р(х хп_,хп_). Покажем, что А будет слабо /-КС множеством С соответствующей ЧРФ ё{х,..;Хп_)~ /{х Хп_,Хп_). Действительно, если у(х(а )>••■> х{ап-))= В т0
)) = )— Лг(«„-1), )) = 1 и тогда
/(^...^„.ьа^еЛп^ ^}, т. е. g(a an_])єAn{al an_]}. Если же у{хМ-,х(ап-і)) = Р{х{а\-,х{ап-),х{ап-))=®, то /(а! аи_|,а#!_і)Т или р{ах ап_х,ап_{]<£ А . Значит или g(a^ ап_і)£ А. Тем самым доказана первая часть леммы.