Бесплатно скачать, заказать диплом, курсовую, диссертацию Допустимые и выводимые правила вывода в нестандартный логикан

У нас уже 21989 рефератов, курсовых и дипломных работ

Сделать закладку на сайт

Заказать диплом, курсовую, диссертацию

Быстрый переход к готовым работам

Мнение посетителей:

Книга жалоб
и предложений

Название	Допустимые и выводимые правила вывода в нестандартный логикан

Количество страниц	100

ВУЗ	МГИУ

Год сдачи	2010

Бесплатно Скачать	23550.doc

Содержание	Содержание ВВЕДЕНИЕ 4 1 ПРЕДВАРИТЕЛЬНЫЕ СВЕДЕНИЯ О ДОПУСТИМЫХ ПРАВИЛАХ ВЫВОДА В НЕСТАНДАРТНЫХ ЛОГИКАХ 19 1.1 Модальные, временные и суперинтуиционистские логики... 19 1.2 Семантика Крипке... 25 1.3 Допустимые и выводимые правила вывода... 32 2 ДОПУСТИМОСТЬ ПРАВИЛ ВЫВОДА ДЛЯ НЕКОТОРОГО КЛАССА 54-ЛОГИК, НЕ ОБЛАДАЮЩИХ СВОЙСТВОМ ВЕТВЛЕНИЯ 35 2.1 Предварительные сведения... 36 2.2 Алгоритмический критерий допустимости правил вывода для некоторого класса 54-логик, не обладающих свойством ветвления... 40 3 ДОПУСТИМОСТЬ ПРАВИЛ ВЫВОДА ДЛЯ ЛОГИКИ С С ОПЕРАТОРОМ "ЗАВТРА" 50 3.1 Предварительные сведения... -51 3.2 Свойства логики С... 53 3.3 Условие допустимости правил вывода в логике С... 57 4 СТРУКТУРНО-ПОЛНЫЕ 54-ЛОГИКИ 66 4.1 Структурно-полные ,54-логики: необходимые предварительные сведения 66 4.2 Описание структурно-полных бЧ-логик ширины 2, порожденных конечным корневым фреймом с двухэлементным первым слоем... 71 4.3 0 ширине структурно-полных табличных 54-логик... -84 ЗАКЛЮЧЕНИЕ 87 У ЛИТЕРАТУРА 89 РАБОТЫ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ 100 ВВЕДЕНИЕ '/' Актуальность темы. Теория нестандартных систем логического вывода сформи- ? ровалась в начале двадцатых-тридцатых годов 20-го века в работах Лукасе- вича, Льюиса, Геделя и Тарского, как результат анализа поведения аксиоматических систем оснований математики и парадоксов материальной импликации. Однако нестандартные логики по сравнению с классической логикой, отличаются большим разнообразием синтаксиса и семантики. Поэтому к концу 20-го века возникло много новых направлений исследований, связанных с применением идей и методов нестандартной логики в программировании, информатике, теории искусственного интеллекта, представлении знаний и других областях знаний (см., например, [40, 41, 54, 80, 83, 99]). ц Большое влияние на становление теории нестандартных систем логического вы- вода оказано классической теорией доказательств, одним из центральных моментов которой являются правила вывода, поскольку от них зависит эффективность доказательств. Первыми работами, непосредственно посвященными изучению правил вывода, были работы Лося (1955), Тарского (1956) и Сушко (1958). При исследовании правил вывода естественно возник вопрос о том какие правила можно присоединять к логическим системам, сохраняя при этом множество доказуемых теорем системы. Такой класс правил, получивших название допустимых правил вывода, был определен П. Лоренценом [71] в 1955 году. Оказалось, что это в точности допустимые правила вывода - правила, относительно которых данная логика замкнута. Несколько ранее проблема допустимых правил вывода для интуиционистской логи-* ки изучалась П.С. Новиковым, который наряду с понятием производного правила х вывода (допустимого правила вывода) рассматривал понятие сильного производного правила вывода. В работе [16] Новиков затронул дедуктивные аспекты производных правил вывода в интуиционистской логике. Вслед за Лоренцсном и Новиковым ! изучением допустимых правил вывода занимался СЮ. Маслов [11, 12, 13], им ис- следовалась возможность применения выводимых и допустимых правил вывода в различных сферах деятельности. В нестандартных логиках, как правило, класс допустимых правил вывода шире класса выводимых правил вывода. Примеры допустимых, но не выводимых правил вывода, были получены Р. Харропом [55], Г.Е. Минцем [14, 15]. Логика, в которой множества допустимых и выводимых правил вывода совпадают, называется структурно-полной. В настоящее время известно, что большинство базисных логик, например, Н, А'4, 6'4, 5'5 и др., не являются структурно-полными. Структурная полнота не является инвариантом заданной логики, она зависит от выбора аксиоматической системы. Однако, во многих распространенных классах логик правила вывода обычно фиксированы и выбор аксиоматической системы зависит от изменения множества аксиом. Для таких классов логик имеет смысл понятие структурной полноты. Поэтому исследования, касающиеся структурной полноты, представляют интерес для многих ученых. Токарз установил структурную полноту некоторых логик Лукасевича [97], Прукнал доказал структурную полноту логики Медведева конечных задач [82], Войтыляк показал, что конечные классы многозначных логик являются структурно-полными [103]. Дзиобяк нашел полное описание локально конечных структурно-полных модальных логик, расширяющих К А [46]. В [29] Циткину удалось описать все наследственно структурно-полные суперинтуиционистские логики, т.е. логики, всякое расширение которых является структурно-полным. Позже Рыбаковым было получено полное описание наследственно структурно-полных мо- дальных логик над К А [89]. А, именно, модальная логика А является наследственно структурно-полной тогда и только тогда, когда А не содержится ни в одной из два-дцати специальных табличных логик. Однако уже для структурно-полных 5"4-логик малой глубины (меньше 5) класс структурно-полных логик шире класса наследственно структурно-полных логик. Поэтому особый интерес представляет описание классов структурно-полных логик над S4, КА. После того как выяснилось, что для большинства нестандартных логик класс допустимых правил шире класса выводимых правил возникли вопросы алгоритмической разрешимости задачи распознавания допустимых правил вывода. Проблема нахождения алгоритма, распознающего допустимость правил вывода в интуиционистской логике была сформулирована в обзоре проблем X. Фридмана [50], родственная проблема существования конечного базиса для допустимых правил этой логики была поставлена А.В. Кузнецовым (см. [50] (проблема 42), [9]). Положительное решение проблемы Кузнецова давало бы и положительное решение проблемы Фридмана. Проблема алгоритмического распознавания допустимости в интуиционистской логике была решена положительно Рыбаковым [18], после чего вопрос о существовании конечного базиса был решен отрицательно так же Рыбаковым [19, 20]. Естественно возник вопрос построения бесконечного базиса, который позже был построен Ием-хофф для интуиционистской логики [59]. Затем Рыбаков построил, также бесконечный, базис для логики SA [91]. Развивая методы, использованные для решения проблемы допустимости для интуиционистской логики, В.В.Рыбаков доказал разрешимость проблемы допустимости правил вывода в таких важных логиках, как (jL, Grz, SA, К А и в некоторых других логиках [21]—[28], [84]-[88]. В частности, была доказана разрешимость проблемы допустимости правил вывода во всех расширены- ях логики S4.3, что является обобщением результата Файна [48] о разрешимости данных логик. На основе техники, разработанной В.В. Рыбаковым, проблема допустимости была решена для различных индивидуальных транзитивных логик (см. например [1, 2, 37, 5]). При решении данных вопросов основным инструментом являлась реляционная семантика (или семантика Крипке, [64, 65]), причем ключевым моментом были специальные модели Крипке - n-характеристические модели. Так, разрешимость проблемы допустимости в логике эквивалентна разрешимости квазиэквациональной теории свободных алгебр многообразия, порожденного этой логикой. С помощью техники, позволяющей представить свободные алгебры из многообразия модальных алгебр ^-характеристическими моделями, была решена проблема распознавания допустимых правил вывода для широкого класса модальных транзитивных логик. Отметим, что описание свободных модальных и псевдобулевых алгебр для многообразий модальных и псевдобулевых алгебр, соответствующих индивидуальным логикам, является распространенной задачей при исследовании нестандартных логик (см. [3, 17, 18, 31, 34, 35]). Особую важность представляло описание свободных алгебр не для индивидуальных многообразий, а для всех многообразий финитно-, аппроксимируемых транзитивных логик, которое и было дано Рыбаковым в [90]. Ранее было отмечено, что ценность допустимых правил вывода заключается в том, что такие правила позволяют нам сократить и упростить выводы в дедуктивной системе заданной логики. Другой причиной, по которой изучаются данные правила вывода, являются различные приложения. Так, в работе Л.Л. Максимовой [74] приведено исследование свойств строгой разрешимости модальных и интуиционистских исчислений, рассмотрена проблема строгой разрешимости проективного свойства Бета над интуиционистским пропозициональным исчислением. Для доказательства строгой разрешимости проективного свойства Бета над интуиционистским пропозициональным исчислением достаточно решить проблему разрешимости по допустимости суперинтуиционистских логик с таким свойством. Максимовой [73] было показано, что существует точно 16 суперинтуиционистских логик, обладающих проективным свойством Бета. Из результатов В.В. Рыбакова [90] следует разрешимость проблемы допустимости для всех логик с таким свойством, кроме логик под номером 9, 13, 15 из полного списка логик с проективным свойством Бета [74]. Несмотря на то, что Рыбаков получил достаточно общий критерий допустимости правил вывода для финитно-аппроксимируемых логик [90], данный критерий не является универсальным, поскольку одним из условий является наличие свойства ветвления ниже к. Так, логика, указанная под номером 9 в полном списке логик с проективным свойством Бета, не обладает свойством ветвления ниже к ни для какого к. Решение проблемы распознавания допустимых правил вывода в данной логике представлено в настоящей диссертационной работе. Также с работой Л.Л.Максимовой [74] связано исследование логики 540»^, не обладающей свойством ветвления, на разрешимость по допустимости правил вывода. Данная задача была решена в [93] и позволила обосновать предположение о строгой разрешимости интерполяционного свойства над логикой S4, которое было выдвинуто в статье Л.Л.Максимовой [74]. Несмотря на глубокую разработку направления допустимых правил вывода, большинство результатов было получено для транзитивных логик. В настоящее время особый интерес представляют нетранзитивные логики, так как основные результаты и техники, использующиеся для исследования допустимых правил вывода в транзитивных логиках, применять непосредственно при изучении допустимых правил вы- вода в нетранзитивных логиках не удаётся. Как было отмечено, при исследовании допустимых правил вывода центральную роль играют n-характеристические модели Крипке: для всякого правила вывода в модальной логике существует конечное, с точностью до изоморфизма, множество n-характеристических моделей Крипке, на элементах которого можно проверять истинность правила, для выяснения его допустимости. Однако при построении n-характеристической модели возникает немало вопросов. На самом деле, построение n-характеристической модели является достаточно ясным только для расширений модальной логики КА и интуиционистской логики. В случае нетранзитивной логики данные модели описаны только для очень малого списка логик, в частности, для К (см., например, [42]). В случае нетранзитивных временных логик описание упомянутых выше моделей представляется еще более сложной задачей. Цель работы. 1. Исследовать на разрешимость по допустимости правил вывода суперинтуиционистскую логику, порожденную классом всех конечных корневых фреймов F, удовлетворяющих условию (xRyk^(yRx)kyRzkyRu) -+ Sv(zRvkuRv), где R - отношение на фрейме F. Положительное решение данной задачи позволяет обосновать предположение о строгой разрешимости проективного свойства Бета над логикой ^1} которое было выдвинуто в статье Л.Л. Максимовой [74]. 2. Исследовать на разрешимость по допустимости логику с оператором "завтра". 3. Получить описание конечных корневых ^-фреймов ширины 2, порождающих структурно-полные логики. Методика исследования. В исследовании применяются общие методы теоретико-модельной и алгебраической семантики для пропозициональных нестандартных логик. Например, метод фильтрации, метод канонических моделей, метод редуцирования правил вывода. А также в исследовании использованы алгоритмический и семантический критерии допустимости правил вывода, критерий структурной полноты логики, некоторые результаты теории модальных напарников суперинтуиционистских логик. Научная новизна. Все результаты, полученные в диссертации, являются новыми и снабжены подробными доказательствами. Результаты совместных работ получены в нераздельном соавторстве. Основные результаты. В диссертации получены следующие основные результаты. 1. Получен алгоритмический критерий распознавания допустимых правил вывода для 5"4-логики Ц2, порожденной классом всех конечных корневых фреймов F, удовлетворяющих условию (хRy&.->(yRx)hyRz&cyRu) —> 3v(zRv&zuRv), где R - отношение на фрейме F. 2. Доказано, что логика /х2 © Grz и суперинтуиционистская логика, порожденная классом всех конечных корневых фреймов F, удовлетворяющих условию (хRyh~>{yRx)hyRzhyRu) —> 3v(zRv&cuRv), где R - отношение на фрейме F, разрешима относительно допустимости правил вывода. 3. Получен алгоритмический критерий распознавания допустимых правил вывода для логики с оператором "завтра". 4. Получены необходимые и достаточные условия того, что S'4-логика A(F) ширины 2, порожденная конечным корневым фреймом без узлов с двухэлементным первым слоем, является структурно-полной. Теоретическая и практическая ценность. Все полученные результаты носят теоретический характер и могут быть использованы в дальнейших исследованиях допустимых правил вывода в нестандартных логиках, а также в таких областях как теория моделей, теория графов и computer science. Апробация работы. Результаты диссертации докладывались на • XXXVII-международной научной студенческой конференции "Студент и научно-технический прогресс"(Новосибирск, 1999), • XXXVIII-международной научной студенческой конференции "Студент и научно-технический прогресс" (Новосибирск,2000), • XXXIX-международной научной студенческой конференции "Студент и научно-технический прогресс"(Новосибирск, 2001), • XL-международной научной студенческой конференции "Студент и научно-технический прогресс"(Новосибирск, 2002), • международной конференции "Ломоносовские чтения" (Москва, 2000), • международной конференции "Логика и приложения", посвященной 60-летию со дня рождения Ю.Л. Ершова (Новосибирск, 2000), • международной конференции "Дифференциальные уравнения и симметрия" (Красноярск, 2000), • международной научной конференции "Молодая наука - XXI веку" (Иваново, 2001), • II Всесибирском конгрессе, посвященному Софьи Ковалевской (Красноярск, 2002), • международной конференции "Алгебра и ее приложения", посвященной 70-летию со дня рождения В.П.Шункова и 65-летию В.М.Бусаркина(Красноярск, 2002), • международной конференции "Мальцевские чтения" (Новосибирск, 2003), • международной конференции "Алгебра, логика и кибернетика", посвященной 75-летию со дня рождения А.И.Кокорина (Иркутск, 2004). Публикации. По теме диссертации опубликовано 22 работы [104]—[125]. Структура и объём работы. Диссертация состоит из введения, четырех глав, заключения и библиографического списка, включающего 103 наименования. Объём работы 103 страницы машинописного текста. Обзор содержания диссертации и полученных результатов. Во введении обосновывается актуальность выбранной в диссертационной работе темы. Даётся краткий обзор теории допустимых правил вывода. Описывается современное состояние вопросов, рассмотренных в диссертационной работе, сформулирован предмет, цель и методы проведения исследования, указаны основные его результаты. Приведены список конференций, на которых была проведена апробация работы, и даётся обзор всех разделов диссертации. В первой главе представлены необходимые сведения о синтаксисе и семантике модальных, суперинтуиционистских и временных логик, а также методика применения n-характеристических моделей в исследованиях допустимых правил вывода. В разделе 1.1 даны необходимые сведения о синтаксисе пропозициональных логик, рассмотрены примеры базисных логических систем. В разделе 1.2 приведены некоторые важные понятия семантики Крипке такие, как фрейм, модель, сгусток, цепь, антицепь, конакрытие и др. В заключении даны необходимые факты из алгебраической семантики для модальных пропозициональных логик: модальной алгебры, истинности формул на алгебрах, связь между алгебраической семантикой и семантикой модели Крипке через ассоциированные алгебры. В разделе 1.3 дается описание n-характеристических моделей Крипке для модальных логик и ряд свойств n-характеристической модели. Приведены критерии допустимости правил вывода и структурной полноты модальных А'4-логик через n-характеристические модели. Во второй главе представлено решение проблемы допустимости правил вывода для модальной 54-логики /i2, порожденной классом всех конечных корневых фреймов F, удовлетворяющих условию (xRyk^(yRx)kyRzkyRu) -> Sv(zRvkuRv), где R - отношение на фрейме F. Данная проблема также решена для модальной логики n2®Grz, откуда следует разрешимость по допустимости суперинтуиционистской логики ^i, порожденной классом всех конечных корневых фреймов F, удовлетворяющих условию (xRyk-^(yRx)kyRzkyRu) -» 3v(zRvkuRv). В разделе 2.1 приведены необходимые сведения, касающиеся связи между модальными и суперинтуиционистскими логиками: определен Т-перевод для формул и правил вывода, сформулировано определение модальных напарников для суперинтуиционистских логик и др. В данном разделе представлены результаты, полученные В.В. Рыбаковым при исследовании проблемы допустимости правил вывода для модальных логик над К4, приведены определения свойства (/-ветвления ниже некоторого к, свойства ветвления ниже некоторого к, свойства реализации возможностей. В конце раздела введены определения, необходимые при исследовании логик /ii, ц2, И2 Ф Grz. Также введена модификация понятия свойства реализации возможностей, которая является важным моментом при исследовании логик /и1? /л2, № Ф Grz. В разделе 2.2 представлено решение проблемы разрешимости по допустимости для логик hi, Ц2, /г2 Ф Grz. Данные логики не обладают свойством ветвления ниже к ни для какого к, наличие которого является одним из условий в алгоритмическом критерии допустимости правил вывода (см. [90], теорема 3.5.2). Однако исследование логики ^2 можно свести к работе над логикой 54.2, которая обладает свойством ветвления ниже 1 и к которой применим алгоритмический критерий допустимости правил вывода (см. [90], теорема 3.5.2). Пользуясь вышеуказанным свойством логики fi2, в данном разделе разработан алгоритмический критерий распознавания допустимости правил вывода в модальных логиках ц2 и fi2®Grz. И ввиду известной связи между модальными и суперинтуиционистскими логиками (см. [90], теорема 3.2.2) получено решение проблемы разрешимости по допустимости для суперинтуиционистской ЛОГИКИ jjLi. Основными леммами раздела 2.2 являются Лемма 2.2. Пусть правило вывода г := ci,... ,а„//? от к переменных не допустимо в логике /л. Тогда существует ц-модель М. := (M,R,S) = (LJ-^i) U где M.j - открытая подмодель модели М. такая, что 3cjVx G M.j(xRcj) и множество висячих вершин модели Л4, удовлетворяющая условиям: (а) подфрейм S\(M) изоморфен подфрейму Si(Ch^(k)); (б) модель М имеет не более, чем 22Г(п) + (1 + 2г^"^)22 -1 сгустков, где п - число подформул правила г; (в) модель Л4 имеет свойство реализации возможностей относительно подформул правила г для каждой антицепи Е, не содержащей висячих вершин, причем если Е - антицепь, не содержащая висячих вершин, и Е С Mj, то существует элемент хе G M.j, для которого выполняется свойство реализации возможностей для антицепи Е; (г) модель Л4 опровергает правило г. Лемма 2.3. Пусть существует pi-модель М., описанная в лемме 2.2. Тогда правило вывода г := ci,... ,ап//? от к переменных не допустимо в логике ц. Из лемм 2.2, 2.3 вытекает главная теорема данного раздела Теорема 2.2. Модальные логики Ц2, \х?. Ф Grz разрешимы относительно допустимости правил вывода. Из теоремы 2.2 получаем Следствие 2.1. Суперинтуиционистская логика р,\, наименьший модальный напарник t(/ui) и наибольший модальный напарник cr(fj,i) логики ц\ над S4 разрешимы относительно допустимости правил вывода. В третьей главе приведены результаты исследований проблемы допустимости правил вывода для временной нетранзитивной логики С с оператором "завтра". В настоящее время особый интерес представляют нетранзитивные логики, так как основные результаты и техники, использующиеся для исследования допустимых правил вывода в транзитивных логиках, применять непосредственно при изучении до- пустимых правил вывода в нетранзитивных логиках не удаётся. Ранее допустимость правила вывода определялась его поведением на верхних слоях специальной n-характеристической модели Крипке [90]. В данной работе свойства правила вывода определяются через его поведение в ограниченной окрестности каждой из точек n-характеристической модели. Эта новая техника используется для доказательства разрешимости по допустимости логики С и ряда других свойств данной логики. В разделе 3.1 определена исследуемая временная нетранзитивная логика С с оператором "завтра", введены необходимые обозначения. Далее даны определения модальной степени формулы и означивания, цепи, цикла. Вводятся определения редуцированного правила, стандартного вида формулы и правила, а также фрейма, порожденного правилом. Приведены результаты, касающиеся связи правила вывода и его редуцированной формы. Основными результатами раздела 3.2 являются построение п-характеристической модели Chc{n) для логики С и описание свойств модели Chc(n). Показано, что в логике С любая формула представима в стандартном виде, а также отмечены некоторые эквивалентности логики ?, необходимые для доказательства дальнейших результатов. Кроме того, определен класс характеристических фреймов для логики С и показано, что логика С является финитно-аппроксимируемой и разрешимой. В разделе 3.3 построен алгоритмический критерий допустимости правил вывода в логике С. При получении данного результата использовался критерий допустимости правил вывода в модальных логиках, основанный на n-характеристических моделях, построенных в разделе 3.2. Основными результатами раздела 3.3 являются Теорема 3.1. Пусть правило вывода sf(r(x0,... ,Xk-i)) не допустимо в логике С. Тогда во фрейме G{r), порождённом правилом г, существует цикл С длины, не превышающей числа элементов G(r), и удовлетворяющий условиям: 1) цикл С содержит элемент Ш{0 такой, что формула Ш{0> входящая в посылку правила sf(r), содержит формулу -^хо, 2) некоторый элемент Uj цикла С является рефлексивным, т.е. ujRgojj. Теорема 3.2. Пусть во фрейме G(r), порождённом правилом г(х0,... ,Xjt-i), существует цикл С, удовлетворяющий условиям 1)-2) теоремы 3.1. Тогда правило sf(r(x0,... , Xk-i)) He допустимо в логике С. В силу конечности посылки правила вывода из теорем 3.1, 3.2 вытекает Теорема 3.3. Модальная логика С разрешима относительно допустимости правил вывода. Пользуясь алгоритмическим критерием допустимости правил вывода в логике ?, не сложно доказать следующую теорему. Теорема 3.4. Логика С не является структурно-полной. В четвертой главе на основе методов, разработанных В.В. Рыбаковым [90], приведено исследование структурно-полных 54-логик. В разделе 4.1 даются необходимые предварительные сведения о структурно-полных логиках, представлены некоторые общие свойства структурно-полных финитно-аппроксимируемых 54-логик. В разделе 4.2 получены необходимые и достаточные условия того, что 54-логика A(F) ширины 2, порожденная конечным корневым фреймом без узлов с двухэлементным первым слоем, является структурно-полной. Основным результатом раздела 4.2 является Теорема 4.1 Логика A(F) ширины 2, порожденная конечным корневым фреймом

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

Цена, в рублях: (при оплате в другой валюте, пересчет по курсу центрального банка на день оплаты)	1425

Скачать бесплатно	23550.doc

Найти готовую работу

ЗАКАЗАТЬ

Обратная связь:

Связаться

Вход для партнеров

Регистрация

Восстановить доступ

Материал для курсовых и дипломных работ

03.11.24 Лексикографический анализ единиц поля

03.11.24 Из истории слова гость и его производных

03.11.24 Семантическое поле гость в русском языке

Архив материала для курсовых и дипломных работ

Ссылки:

Счетчики:

© 2006-2024. Все права защищены.
Выполнение уникальных качественных работ - от эссе и реферата до диссертации. Заказ готовых, сдававшихся ранее работ.