Сложность множества тавтологий и некоторых родственных ему множеств

• Автор: Ганичева, Антонина Валериановна
• Шифр специальности: 01.01.06
• Научная степень: Кандидатская
• Год защиты: 1983
• Место защиты: Калинин
• Количество страниц: 119 c. : ил

ГЛАВА I. Мера сложности множества тавтологий и некоторых других множеств формул

§1. Необходимое условие ограниченности меры контекстности функцией порядка о(Со$?о£.п)

§2. Мера правой контекстности для множества тавтологий при двоичном кодировании

§3. Мера контекстности и мера правой контекстности

для множества тавтологии при унарном кодировании

§4. Сигнализирующая времени для множества тавтологий и множества выполнимых формул

ГЛАВА 2. Множества Ыист., (Хиет,^, 01^,01 ист. у &-'м

и подклассы класса языков, распознаваемого детерминирование за полиномиальное время

§1. Хорновские тавтологии

§2. О принадлежности множеств формул исчисления выс- с называний классам: $пм,

ГЛАВА 3. Место множества тавтологий и родственных множеств в низших классах примитивно-рекусивных множеств
§1. Рудиментарность множества тавтологий и некоторых
других множеств
§2. Изословарность
§3. Б -рудиментарность
/ А
ГЛАВА 4. О принадлежности множеств (Хн> 01н и
некоторых подмножеств множества 01цст классу индексных языков
§Г. Основные определения
§2. Структура квазисовершенных дизыэктивных нормаль-ных форм
§3. Множества &н, &н - индексные языки
ЗАКЛЮЧЕНИЕ
УКАЗАТЕЛЬ ОСНОВНЫХ ОБОЗНАЧЕНИЙ И СОКРАЩЕНИЙ
Литература г..

Множество тавтологий - исключительно важный объект исследования в математической логике. В настоящее время одно из главных направлений теории алгоритмов - изучение сложности алгоритмов и вычислений. Первоначально основная проблема заключалась в исследовании вопроса:"Существует алгоритм или нет?", а теперь центр тяжести переместился к вопросу о строении алгоритмов и процессов их работы. С этой точки зрения интересно посмотреть на классические объекты математической логики - такие, как множество тавтологий. Это связано с тем, что тавтологии, как недавно lit выяснилось, - удобный модельный объект для переборной задачи; тем самым изучение этого множества может позволить пролить некоторый свет на возможные подходы к решению этой задачи.
Цель данной работы заключается в исследовании свойств множества тавтологий и родственных множеств: множества выполнимых формул, множества хорновских тавтологий, множества формул, состоящего из всех представлений конечного числа булевых функций.
Эти множества издавна привлекали к себе внимание благодаря удивительной красоте структуры и возможности анализировать на на их основе законы и возможности логических заключений. Уже у Аристотеля была идея составлять сложные рассуждения, последовательно производя простые элементарные шаги, не зависящие от природы объектов, о которых идет речь. Дальнейшее развитие эта идея получила, в частности, у Лейбница, Буля, Гильберта. Сравнительно недавно, в 60-х годах, С.Кук lit доказал, что множество тавтологий, равно как и множество выполнимых формул, , является хорошим модельным объектом для переборной задачи.

Интересный результат о множестве тавтологий получен Г.С.Цейтиным /2 / ,* им введены некоторые величины, характеризующие сложность вывода, и установлен ряд соотношений между ними. М.В.Ломковская /3 / установила, что множество выполнимых формул (с бесконечным списком переменных) принадлежит классу Я -языков.
В настоящей работе рассматривается множество тавтологий и родственные ему множества формул исчисления высказываний с конечным и бесконечным списком переменных элементарных высказываний. В случае конечного числа переменных используется алфавит 7, а1 0.п,),(]. Множество тавтологий в этом
алфавите обозначается через 01ист , множество выполнимых формул - через 01^Ъ1П , множество формул, каждая из которых равносильна некоторой формуле данного конечного множества М -через (Хм . Для бесконечного списка переменных рассматриваются два способа кодирования: унарное, при котором переменная кодируется цепочкой а 11...[ и используется алфавит 3, 7,а, /,),(] , и двоичное - а.;_ кодируется цепочкой аР , где Р - двоичная запись числа I , и используется алфавит В={&, У,3,7, О, 0,1,),(}‘£ При двоичном (унарном) кодировании мы пользуемся следующими обозначениями для множеств: (Мг1Ст(С31г;сгп')-множество тавтологий, 0ЦЫП (01'&ып) - множество выполнимых
формул, 01н(ан) - множество хорновских тавтологий, 01 м
(О- множество формул, состоящее из всех представлений булевых функций из конечного множества М.
Для всех этих множеств в данной работе установлено их место в иерархии примитивно-рекурсивных множеств, получены оценки для ряда широко распространенных мер сложности, рассмот-

Определение 2.1.9. /42/ Линейное множество 5-]1П имеет размерность т. , если 5 содержится в аффинном многообразии размерности т и не содержится в аффинном многообразии размерности т
Нетрудно показать, что пересечение линейных множеств с нулевым предпериодом является линейным множеством с нулевым предпериодом, Т.е. П I- V 7 ••• 7 1-(ы1г..,о(гп) для некоторого
1=1 1 периода оС1?..., оСт
Утверждение 2.1.1. /41/ Пусть !_[_ = Ь (оСо^сС,^ о^. )
(14К) - линейные множества и 1~;с 7ЧП (16 I 4 к).

Положим П сс^,). Тогда существует
конечное множество СсК такое, что
Д Ь(оСо);о<,и,)...,о4^;)ь)вс1/с1(Сь} о4( <*т).
Положим 5(к)={('ц, ьк, 117 ^еЖ^К)
и для любой координаты из последних к координат найдется ей равная среди первых К координат}.
Пу С ТЬ й — ■£( 11, 12 I ^ , 11, 12,) > • • 7 Ь к) 11} £ N , 1 6 j ^ К } . Утверждение 2.1.2. /42/ Множество 5 нельзя представить в виде конечного объединения линейных множеств, каждое из которых имеет размерность к-1 или меньшую.
п.З . Пусть а1 обозначает .аа . а
_ , (К) f И 1-2 L L« ji Jо Jk
Рассмотрим множество L -а1 clz ... ака1 а.
где ls£N (1S К), а,, ..., ак - попарно различные символы и для любого вхождения цепочки ctJss (l&S^K) из числа последних к вхождений цепочек найдется вхождение
цепочки ар (16(^6 к) среди к первых вхождений цепочек
a£(l^t£K) такое, что | CLJSS | =] СХа |)
{к)
Лемма 2.I.I. Множество L можно представить в виде пересече-