Содержание к диссертации
стр
ВВЕДЕНИЕ 3
ПЛАВА I. Мера сложности множества тавтологий и некоторых
других множеств формул ',.. 12
1. Необходимое условие ограниченности меры кон-
текстноети функцией порядка о(Сод.од.п) ....... 15
2. Мера правой контекстности для множества тавтоло
гии при двоичном кодировании ., ZH
3. Мера контекстности и мера правой контекстности
для множества тавтологии при унарном кодировании Зт
4. Сигнализирующая времени для множества тавтологий
и множества выполнимых формул 43
ГЛАВА 2. МНОЖеСТВа Оіиспь, Ot'uom, ОіИ7 6і'н, С%ст > &«П* Оін, Ot'M
и подклассы класса языков, распознаваемого детерминиро
вание за полиномиальное время .;..1, 'Л. ^
1. Хорновские тавтологии .......................... 48
2. О принадлежности множеств формул исчисления вые- с
называний классам &пи, ^ *с ? &кс 5Ь
ГЛАВА 3. Место множества тавтологий и родственных множеств
в низших классах примитивно-рекусивных множеств 64
1. РудиментарностЬ) множества тавтологий и некоторых
других множеств . V. ." і 64
2. Изословарность ; 76
3. S -рудиментарность *. 79
ГЛАВА 4. О принадлежности множеств (%$ып> ОСн, (Хы и
некоторых подмножеств множества Оіцст. классу индексных
языков 85
Г. Основные определения ; Л&5
2'. Структура квазисовершенных дизьюктивных нормаль-
ных форм оу
3. Множества OL,gtin7 (Хн, &'н - индексные языки.. 101
ЗАКЛЮЧЕНИЕ ...105
УКАЗАТЕЛЬ ОСНОВНЫХ ОБОЗНАЧЕНИЙ И СОКРАЩЕНИЙ... 106
v .но
Введение к работе
Множество тавтологий - исключительно важный объект исследования в математической логике. В настоящее время одно из главных направлений теории алгоритмов - изучение сложности алгоритмов и вычислений. Первоначально основная проблема заключалась в исследовании вопроса:"Существует алгоритм или нет?", а теперь центр тяжести переместился к вопросу о строении алгоритмов и процессов их работы. С этой точки зрения интересно посмотреть на классические объекты математической логики - такие, как множество тавтологий. Это связано с тем, что тавтологии, как недавно 111 выяснилось, - удобный модельный объект для переборной задачи; тем самым изучение этого множества монет позволить пролить некоторый свет на возможные подходы к решению этой задачи.
Цель данной работы заключается в исследовании свойств множества тавтологий и родственных множеств: множества выполнимых формул, множества хорновских тавтологий, множества формул, состоящего из всех представлений конечного числа булевых функций.
Эти множества издавна привлекали к себе внимание благодаря удивительной красоте структуры и возможности анализировать на на их основе законы и возможности логических заключений. Уже у Аристотеля была идея составлять сложные рассуждения, последовательно производя простые элементарные шаги, не зависящие от природы объектов, о которых идет речь. Дальнейшее развитие эта идея получила, в частности, у Лейбница, Буля, Гильберта. Сравнительно недавно, в 60-х годах, С.Кук /1 / доказал, что множество тавтологий, равно как и множество выполнимых формул, . является хорошим модельным объектом для переборной задачи.
Интересный результат о множестве тавтологий получен Г.С.Цейтиным /2 / ; им введены некоторые величины, характеризующие сложность вывода, и установлен ряд соотношений между ними. М.В.Ломковская /3 / установила, что множество выполнимых формул (с бесконечным списком переменных) принадлежит классу Я -языков.
В настоящей работе рассматривается множество тавтологий и родственные ему множества формул исчисления высказываний с конечным и бесконечным списком переменных элементарных высказываний. В случае конечного числа переменных используется алфавит В ={&,V,, 7, cij,...,Un',),(}. Множество тавтологий в этом
алфавите обозначается через 0L,m » множество выполнимых
к ист
формул - через @lg,bm , множество формул, каждая из которых равносильна некоторой формуле данного конечного множества М -через 01 дд . Для бесконечного списка переменных рассматриваются два способа кодирования: унарное, при котором переменная Q*t кодируется цепочкой а 11 .1 и используется алфавит В ={&,V, =>, 7, Q ,/,),( J , и двоичное - Q^ кодируется цепочкой аР , где Р - двоичная запись числа I , и используется алфавит В={&, V,3, A 0,0,1,),(] При двоичном (унарном) кодировании мы пользуемся следующими обозначениями для множеств: Ol-ucm (Aucm) ~ множество тавтологий, 0U {(Х\ ) - множество выполнимых формул, 6lH(0t'H) - множество хорновских тавтологий, 01 м (OLflJ- множество формул, состоящее из всех представлений булевых функций из конечного множества М.
Для всех этих множеств в данной работе установлено их место в иерархии примитивно-рекурсивных множеств, получены оценки для ряда широко распространенных мер сложности, рассмот-
рен вопрос о принадлежности перечисленных множеств известным подклассам класса языков, распознаваемого детерминированной машиной Тьюринга за полиномиальное время; доказано, что мно-жества Oig^ , біи, &н - индексные языки, a Ct^.^ содержит бесконечно много неиндексных языков.
В теории формальных грамматик и языков важное место занимает вопрос об устройстве "механизма", позволяющего НС-грамматике с использованием контекста порождать не бесконтекстные языки С fil ,/5/, /6/,//7). В работах Ф.Й.Бранденбурга (/8/ , 131 , 110/ ) детально изложен один из способов исследования этого механизма, связанный с системой предков и потомков в цепочке; введены меры, которые можно интерпретировать как "меры небесконтекстности" языка. Среди них важнейшие - мера контекстности и мера правой контекстности, которые, в отличие от таких распространенных мер сложности, как время и емкость, характеризуют внутреннюю структуру вывода. Мера контекстности определяется как максимальная длина цепочек-предков для каждого вхождения символа в выводимую цепочку, определение меры правой контекстности получается из определения меры контекстности наложением некоторого ограничения на вывод.
Эти меры сложности использованы автором для характериза-
ции множеств: 0iucm, Ot'ucnt » 1ът » ^ &ып > ^м » й'м .
В первом параграфе первой главы доказано необходимое условие мажорируемости меры контекстности функций, по порядку меньшей totU ^0^ Отсюда получена нижняя оценка меры контекстности для множеств 0tuctn , (51 м > OL
ист і Во втором параграфе для названных множеств при двоичном кодировании доказано, что их мера правой контекстности не мо-
жет быть ограничена сверху функцией, по порядку меньшей п.
В третьем параграфе для этих же множеств при унарном кодировании переменных установлено, что их мера контекстности не может быть ограничена сверху функцией, по порядку, меньшей 1оогп. Кроме того, в этом параграфе рассмотрены множества 0iucfn и 0(gb)n представляющие собой соответственно множество тавтологий и множество выполнимых формул при унарном кодировании переменных, причем для каждой формулы выполняется условие: 8къК, где К - число вхождений различных элементарных переменных высказываний в формулу,п- число вхождений всех высказываний в формулу. Как следует из доказательства теоремы С.Кука в /I/, аналогичные множества при двоичном кодировании являются моделями для пере-борной задачи. Для $исти (Х^ установлено, что мера их контекстности и мера правой контекстности ограничена сверху функцией log ti, кроме того, мера правой контекстности для (ХисП1 не может быть ограничена сверху функцией, по порядку меньшей og2n.
Одной из центральных задач теории сложности вычислений
является установление для любого НС-языка оценки времени рас
познавания детерминированной или недетерминированной машиной
Тьюринга и времени порождения НС-грамматикой. Для множеств
01 ист і ^ист, Цып, ист , 1л бьт эта задача
особенно актуальна в связи с известной проблемой, о связи между детермированными и недетермированными вычислениями за полином-ное время /I/. Поэтому в следующем параграфе рассмотрен вопрос
о сигнализирующей времени для перечисленных множеств. Установці ^ і лено, что при унарном кодировании множества (ЙисгцИ 0(gblnраспознаются детермированной машиной Тьюринга за время 2 9 п.
Этот результат особенно интересен тем, что он является
первым примером, когда оценки сложности для двоичного и унарного кодирования не совпадают.
Для двоичного кодирования доказано, что нижней оценкой времени распознания детерминированной машиной Тьюринга для 0t^ln является функций пг7\а. о(гьа) служит нижней оценкой времени порождения НС-грамматикой для множеств СХЦСт и 0(м.
Вторая глава посвящена вопросу о принадлежности множеств
Н і ^ uctn ,
01 km известным подклассам класса языков, распознаваемого детерминированной машиной Тьюринга за полиномиальное время.
Установлено, что множество хорновских тавтшогий нельзя представить в виде пересечения конечного числа КС-языков.Этот результат особенно интересен в связи с тем, что, как нетрудно показать, это множество можно распознавать детерминированно за время п3 на одноленточной машине Тьюринга и за линейное время на вычислительных устройствах типа РАМ.
В настоящее время известно много классов языков,строго промежуточных между классом НС-языков и классом КС-языков; эти классы введены и подробно изучены в ряде работ многих авторов. Наиболее сложными и мало изученными почти для всех этих классов языков типов задач являются задачи о времени распознавания детерминированными (недетерминированными) автоматами из различных классов автоматов множеств данного класса. В /19/ доказано, что языки,принадлежащие классу простых матричных языков (Збпм/20/), классу языков, порождаемых грамматиками Касаи степени n (dK/2l/ ), классу языкяв, порождаемых линейными КС-грамматиками с нерегулярным языком управления (І^./22/),
классу векторных языков/23/ , распознаются детерминированной машиной Тьюринга за полиномиальное время. Поэтому естест-венно возникает вопрос о принадлежности множеств CXucm(6luctn), ^Ьып^Ьып) » 01м(&м) ?тим классам. Для классов ^6Пм , ^ кс » "^к автором получен отрицательный ответ на этот вопрос, что является еще одним доводом в пользу известной гипотезы С.Кука о нераспознаваемости множеств 0tucm и Otfebm детерминированно за полиномиальное время.
В то же время для множества тавтологий с конечным списком переменных доказано, что это множество является КС-языком (теорема А.А.Мучника) и, следовательно, распознается детерминированной машиной Тьюринга за время п3 . Этот результат рас-пространен на множества Olgbm и 0LM .
В третьей главе получен новый результат о месте множеств
QLuctn , Cl'ticm , -Ььт> &Ььт > &м » Оі'м В иерархии классов языков, промежуточных между НС-языками и бесконтекстными. Среди этих классов одним из важнейших и интереснейших является класс рудиментарных множеств, введенный Раймондом Смальяном ЦЧI .
Доказано, что все перечисленные множества рудиментарны, но не 5 -рудиментарны (по Смальяну), и не являются изословар-ными (изословарные множества рассмотрены Н.К.Косовским).
Результат о принадлежности названных множеств классу рудиментарных предикатов интересен в теоретическом и прикладном аспектах в связи с тем, что, как показано в /2 5/ , рудиментарные предикаты вычисляются на простейших (абстрактных) вычислительных устройствах, очень похожих на реальные вычислительные устройства типа цифровых вычислительных машин.
Как уже было сказано, в настоящее время известно много классов НС-языков, содержащих класс контекстно-свободных языков. Один из наиболее интересных и важных классов этого рода - класс индексных языков kxo/Z&L Он замкнут относительно многих важных операций над языками и образует абстрактное семейство языков /27/.
Четвертая глава посвящена исследованию вопроса о принадлеж-ности множеств Oiiun, Оіи > (%н > а rtifiie некоторых важных подмножеств множества (Лист С Oi'ucm. ) классу индексных языков.
Класс индексных языков довольно широк, a /Z8/ установлено необходимое условие принадлежности шожества этому классу. Но по этому условию примеры неиндексных языков получаются в основном однотипными: безотносительно к структуре множеств важна изме-няющаяся по закону / длина слов. Первый интересный пример неиндексного языка был приведен в работе М.И.Фишера /Z9/, Это множество $(ап)т\п= /,2,...",m-i :-Ц Автором получено обобщение этого результата и доказано существование бесконечной последовательности неиндексных языков, представляющих собой множество формул в так называемой квазисовершенной дизъюнктивной нормальной форме (к.с.д.н.ф.), имеющих красивую и довольно богатую
СТРУКТУРУ И СОДержащИХСЯ В МНОЖеСТВе (Хисті ОІ'ист » Оіп , (%*)
ото существенно более сложный пример (в настоящее время единственный известный пример такого рода) неиндексных языков.
Что же касается множества выполнимых формул, то здесь автором усилен результат М.В.Ломковской и показано, что множество выполнимых формул принадлежит классу составных языков, являющемуся собственным подклассом класса индексных языков по Ахо и класса N -языков (в терминологии М.В.Ломковской),
Рассмотренные множества находят широкое применение (теоретического и прикладного характера) в качестве модельных объектов для ряда задач. Так множество &н общеупотребительно для описания релейно-контактных схем в случаях, когда нужно реализовать все возможные прохождения тока через цепь при данных условиях.
Рассмотренные множества используются при описании функционирования автоматов, в эвристическом программировании при организационном переооре, когда строится граф "решений" и поиск доказательства сводится к нахождению оптимального пути-в графе.
При распознавании образов задачи описания сложных сигналов при наличии помех часто сводятся к задаче отыскания кратчайшего пути в графе, т.е. переборной задаче.
В экономических задачах, описываемых при помощи иерархи-
ЧЄСКИХ СИСТеМ, Также ИСПОЛЬЗУЮТСЯ МНОЖеСТВа Oiucm, Otfan. ,0(м.
Так, при построении модели решения такой глобальной задачи, как задача о взаимодействии экономических интересов отдельных личностей, коллективов и общества в целом, как было показано автором в /53/, успешное функционирование данной системы формально описывается при помощи' тавтологий.
Множество хорновских тавтологий является хорошей моделью для задачи идентификации цепочек символов при редактировании текстов, поиске данных.
Поэтому исследование сложности этих множеств представляет интерес. Полученные в работе теоретические результаты, связанные с установлением ряда важных свойств рассмотренных множеств, могут найти практическое применение при решении многих прикладных задач.
Основными результатами, полученными автором являются:
Получено необходимое условие ограниченности меры контекстнос-ти функцией, меньшей по порядку, чем У)ОгШгп,Втот результат представляет для теории формальных языков самостоятельный интерес. При помощи необходимого условия доказано, что мера контекст-ности для множеств $uctn> $uem7 ЙМ| 0lM не может быть ограничена сверху функцией, меньшей по порядку, чем U}QzloQzh. .
Установлено, что для 0fucm и 0ім мера правой контекстности является максимальной, а при унарном кодировании - не может быть ограничена сверху функцией по порядку меньшей ш2и
Определено место множества тавтологий и родственных множеств в иерархии примітивно - рекурсивных множеств: доказано, что
$ucm, &исгн< ^L*, &||ыМ Йм, ^м рудиментарны.
4. Доказано, что любое подмножество множества тавтологий в
квазисовершенной дизъюнктивной нормальной форме, содержащее
формулы, зависящие от любого числа различных элементарных пере
менных высказываний, не принадлежит классу индексных языков.
Результаты диссертации докладывались на семинаре по математической логике в Ленинградском отделении Математического института АН СССР, а также неоднократно докладывались на семинарах по математической логике в Калининском государственном университете.
По теме диссертации опубликовано шесть работ /30/ - /35/.
В заключение хочу принести свою глубокую признательность моему учителю А.В.Гладкому, под влиянием которого сложились мои взгляды и интересы в области математики.
