Конструктивные отрицания и паранепротиворечивость тема диссертации и автореферата по ВАК РФ 01.01.06, доктор физико-математических наук Одинцов, Сергей Павлович

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

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

1 Введение

1 Reductio ad absurdum

2 Минимальная логика. Синтаксис и семантика.

3 Логика классической опровержимости

3.1 Свойство максимальности логики Le

3.2 Изоморфы логики Le.

4 Класс расширений минимальной логики

4.1 Расширения логики Le'.

4.1.1 Интуиционистские и негативные напарники расширений логики Le'.

4.2 Интуиционистские и негативные напарники расширений минимальной логики.

4.2.1 Негативные напарники как логики противоречий

4.3 Три размерности класса Par.

5 Адекватная алгебраическая семантика для расширений минимальной логики

5.1 Логика Гливенко.

5.2 Представление j-алгебр.

5.3 Логики Сегерберга и их семантика.

5.4 Семантика Крипке для паранепротиворечивых расширений логики

6 Негативно эквивалентные логики

6.1 Определения и простейшие свойства.

6.2 Логики, негативно эквивалентные промежуточным

6.3 Классы негативной эквивалентности.

6.4 Структура Л1П+ с точностью до негативной эквивалентности

7 Абсурдность как унарный оператор

7.1 Введение.

7.2 Ье и модальная логика Лукасевича.

7.3 Парадокс минимальной логики и обобщенная абсурдность

7.4 А- и С-представления.

7.4.1 Определения и первые результаты.

7.4.2 Логика СМ*

7.4.3 Логика Сета Р1.

II Сильное отрицание

8 Различные виды семантики для паранепротиворечивой логики Нельсона

8.1 Логики N4 и N4"'" и их простейшие свойства.

8.2 Семантика Фиделя.

8.3 Твист-структуры.

8.3.1 Вложение логики N3 в N4.

8.4 Ж-Решетки.

8.5 Многообразие К4-решеток.

8.6 Логика N41 и N^-penieTKH.

9 N41-PemeTKH

9.1 Структура N41-peineTOK

9.2 Гомоморфизмы и подпрямо неразложимые N41-peiiieTKM

10 Класс расширений логики N

10.1 Ш41 и lnt+.

10.2 Структура решетки ¿N41.

10.3 Избыточные и нормальные напарники. ф 10.4 Структура решеток £N4C и £N4XC.

10.5 Теоремы переноса для класса К41-расширений

Глава

Введение диссертации (часть автореферата) на тему «Конструктивные отрицания и паранепротиворечивость»

Как следует непосредственно из названия, проблематика данной работысочетает концепции паранепротиворечивости и конструктивной логики.Поэтому в самом начале мы скажем несколько слов о двух упомянутыхконцепциях. Паранепротиворечивые логики — это такие логики, которые допускают противоречивые, но нетривиальные теории, т.е. логики,позволяющие осуществлять нетривиальные выводы из противоречивогомножества гипотез. Логики, в которых все противоречивые теории тривиальны, будут называться избыточными (столь вольным способом мыпереведем уже устоявшийся английский термин explosive, ввиду того,что дословный перевод, "взрывающийся", обладает степенью экспрессиичрезмерной для научного текста). Отмеченное свойство паранепротиворечивых логик позволяет использовать их в разнообразных ситуациях,когда приходится иметь дело с феноменами, имеющими отношение, в тойили иной степени, к логическому понятию противоречивости. К числу тагких ситуаций мы можем отнести следующие: накопление информации вкомпьютерных базах данных; различные научные теории; законы и иныеюридические документы; описание фантастических (и иных несуществующих) объектов; описание контрафактических ситуаций и т.д. Для первого знакомства с проблематикой паранепротиворечивости можно порекомендовать обзор Г. Приста [65], появившийся во втором издании4Handbook of Philosophical logic. Изучение феномена паранепротиворечивости может быть основано на различных философских нредпосылках(см., например, [66]). Мы отметим лишь один фундаментальный аснектисследований в области паранепротиворечивости, прекрасно выраженный Д. Нельсоном. В работе [60, с.209] Д. Нельсон отмечает: "Как вклассической, так и в интуиционистской логике все противоречия эквивалентны. Это делает в принципе невозможным рассмотрение подобных сущностей в математике. Мне не ясно, действительно ли необходимастоль радикальная позиция в отношении противоречия." Отвергая принцип "противоречие влечет все что угодно" (еж contraditione quodlibet), паранепротиворечивая логика позволяет изучать феномен противоречиясам по себе. Именно этот формально логический аспект паранепротиворечивости будет в центре внимания представленного исследования.Обратимся теперь к конструктивной логике. Довольно часто конструктивная логика отождествляется с формализацией интуиционистской логики, предложенной А. Рейтингом [40]. Однако смысл этого понятиязначительно шире. Конструктивная логика — это логика конструктивной математики, логика, ориентированная на работу с универсумом конструктивных математических объектов. Общим для различных вариантов конструктивной математики является отказ от использования концепции актуальной бесконечности и признание существования только таких объектов, которые построены на основе концепции потенциальнойосуществимости. Различные способы понимания последней концепциидают начало различным направлениям конструктивной математики (см.,например, [2]) и, соответственно, различным вариантам конструктивнойлогики. В любом случае, переход от классической логики к конструктивной сопровождается изменением смысла логических связок. Например, А.А. Марков [5] следующим образом определяет конструктивнуюдизъюнкцию: "Конструктивному пониманию существования математи^ ческого объекта соответствует конструктивное понимание дизъюнкций— предложений вида " Р или Q". Такое предложение тогда считаетсяустановленным, когда хотя бы одно из предложений Р, Q установленокак верное." Разумеется, данное понимание дизъюнкции не позволяетпризнать закон исключенного третьего и приводит к отказу от классической логики. В рамках конструктивной логики сформировались двеважнейшие концепции отрицания, которые и рассматриваются в даннойдиссертации. При этом стоит оговорится, что наши исследования носят^ классический, а не конструктивный характер.Каким же образом понимается отрицание в контексте конструктивной логики? Есть два основных подхода. Во-первых, начиная с работЛ.Э.Я. Брауера отрицание утверждения Р, -пР, понимается как сокрэгщение утверждения "предположение Р ведет к противоречию". Заметим,что такое понимание отрицания хорошо согласуется с концепцией паранепротиворечивости, так как оно вовсе не предполагает принципа ехcontradictione quodlibet, влекущего за собой тривиализацию противоречивых теорий. Первый вариант формализации интуиционистской логики,предложенный А.Н. Колмогоровым [1] еще в 1925 году, был паранепро^ тиворечивым. В этой работе Колмогоров резонно замечает, что принципех contradictione quodlibet (в форме -ip —^ [р —*^ q)) появился тольков формальном представлении классической логики и не используется вобычной математической практике. Тем не менее, А. Рейтинг был уверен,что использование ех contradictione quodlibet допустимо в интуиционистских рассуждениях, и добавил аксиому -ip—*{p—*q)K своему вариантуLi интуиционистской логики [40]. Только в 1937 году И. Иоганссон [43]вновь поставил под вопрос использование ех contradictione quodlibet вконструктивных рассуждениях и предложил систему, которая стала впоследствии называться логикой Иоганссона или минимальной логикой.Ш Обозначим эту логику Lj. Аксиоматика Lj получается вычеркиванием ехcontradictione quodlibet из стандартного списка аксиом интуиционистской- логики, иными словами, имеет место соотношение Li = Lj + {-ip —* (р —*q)}.B [43] Иоганссон доказал, что многие свойства отрицания, доказуемые в логике Рейтинга Li, сохраняются и в его системе Lj. Фактически,Иоганссон вернулся к Колмогоровскому варианту интуиционистской логики. Точнее, {—^, -•}-фрагмент логики Lj совпадает с пропозициональным фрагментом системы Колмогорова [1]. А.Н. Колмогоров рассматри^ вал логику первого порядка, но в языке, который содержит только дветпропозициональных связки, импликацию и отрицание.К сожалению, логика Lj в течение долгого времени находилась вневнимания специалистов по паранепротиворечивости. Традиционно этомотивировалось следующим "паранепротиворечивым парадоксом" логики Lj. Хотя формально логика Lj не является избыточной, т.е. допускает нетривиальные противоречивые теории, мы можем доказать в Lj длялюбых формул (риф, чтоЭто означает, что связка отрицания теряет смысл в противоречивых Ljтеориях, поскольку в таких теориях доказуемо отрицание любой формулы. Таким образом, противоречивые Lj-теории — это, по существу, позитивные теории. Следует отметить, что исследования в области паранепротиворечивости в течение долгого времени были направлены на поиск"наиболее естественной системы" паранепротиворечивой логики (см. [42,с. 147]), в наибольшем объеме сохраняющей свойства классической логики. Что привело, впрочем, к созданию достаточно экзотических логик.В известной логике Н. Да Косты, например, нельзя определить логическую связку, обладающую свойствами конгруэнции, что делает весьмапроблематичным развитие математики над такой логикой. Поэтому в носледнее время все большее внимание уделяется изучению параненротиворечивых аналогов известных логических систем. И в этом отношениилогика Иоганссона Lj безусловно заслуживает внимания как параненротиворечивый аналог интуиционистской логики Li.Перейдем ко второму главному подходу к понятию отрицания в конструктивной логике, концепции сильного отрицания. Отметим, что именно сильное отрицание является действительно конструктивным.Теперь несколько слов об обозначениях рассматриваемых логик. Логику с сильным отрицанием и ее паранепротиворечивый вариант Нельсон обозначал N и N (см. [59, 9]). В системе обозначений М. Дана [32]эти логики получают имена N и BNi, соответственно. Мы же будем следовать иной традиции, наиболее распространенной в данное время (см.,например, [88]), и обозначать избыточную логику Нельсона через N3, апаранепротиворечивую логику Нельсона через N4. Эти обозначения связаны с семантикой Крипке для данных логик, которая была разработанадля N 3 Р.Томасоном [83] и Р. Роутли [75]. Как и в случае интуиционистской логики, N3-mKajibi — это предпорядки. Однако ввиду того, что верификация и фальсификация трактуются в N3 независимо, N3-мoдeлиимеют две оценки, v'^ для верификации и v для фальсификации, с дополнительным условием v^{p) П v{p) — 0, т.е. атомное утверждение неможет верифицироваться и фальсифицироваться одновременно. Опуская это условие, мы получим семантику для N4. Нетрудно проверить(см. [72]), что пара оценок {v'^^v) может быть заменена многозначнойоценкой, трех-значной (true, false, neither) для N3 и четырех-значной(true, false, neither, both) для N4. Именно это определяет выбор обозначений для данных логик.Разумеется, логика N4 более привлекательна с прикладной точки зрения, так как она позволяет работать с противоречивой информацией.Кроме того, она может быть использована для разрешения некоторыхизвестных логических парадоксов (см. [87]). В то же время, ее изучению было уделено несравненно меньше внимания, чем избыточной N3. Вчастности, семантические исследования N4 ограничиваются семантикойКрипке. Отсутствует какая-либо специфическая информация о классеК4-расширений, за исключением сведений о классе расширений логикиN3. Стоит отметить, что последний класс изучался достаточно интенсивно ( см.[39, 48, 77, 78, 79]).Итак, имеются две избыточные логики Li и N3, и их паранепротиворечивые аналоги Lj и N4. В диссертации установлено, что Li точновкладывается в Lj, а N 3 точно вкладывается в N4. Таким образом,отказ от аксиомы избыточности не приводит к потере выразительныхвозможностей логики. Здесь встает вопрос о том, какими новыми вы10разительными возможностями обладают логики Lj и N4 по сравнениюс избыточными Li и соответственно N3, а также насколько регулярноустроен этот набор новых возможностей? В настояш;ей работе мы постараемся дать ответ на этот вопрос исследуя решетки расширений логикLj и N4.Изучение классов расширений различных логик таких, например, какинтуиционистская логика Li (см., например, [22]), нормальная модальная логика К 4 [36, 37] и т.д., играет чрезвычайно важную роль в развитии современной логики. В первой части диссертации представлен первый опыт систематического изучения решетки расширений паранепротиворечивой логики, а именно логики Lj. Установлена важная черта,отличающая класс Lj-расширений от классов расширений избыточныхлогик Li и К4. Класс Jhn имеет нетривиальную и интересную глобальную структуру (он трехмерный, в некотором смысле), что позволяет свести его описание, до определенной степени, к хорошо изученным классампромежуточных и позитивных логик. Точнее, класс Jhn является дизъюнктным объединением трех классов: класса промежуточных логик Int,который содержит только избыточные логики; класса Neg, состоящего изнегативных логик, т.е. логик с вырожденным отрицанием, содержащихсхему -ip; и класса Par собственно паранепротиворечивых расширепийлогики Lj, содержащего все логики, не попавшие в первые два класса.Jhn = Int и Neg и Par.Заметим, что негативные логики дефинициально эквивалентны позитивным.Для любой логики L е Par, можно определить ее интуиционистский напарник Lint (негативный напарник Ь^ед) как наименьшую логику из класса Int (соответственно, из класса Neg), содержашую логикуL. Имеются сильные трансляции (т.е. трансляции, сохраняющие отно11шение следования) логик Lint и Lmg в исходную паранепротиворечивуюлогику L. Логика Lint может быть получена также присоединением ехcontradicUone quodlibet к L. Таким образом, упомянутая трансляция логики Lint показывает, что обычные избыточные рассуждения моделируются в паранепротиворечивой логике. В то же время, как было отмеченовыше, важным преимуществом паранепротиворечивых логик являетсявозможность различать противоречия, которые не эквивалентны другдругу. В случае класса Lj-расширений структура противоречий паранепротиворечивой логики L эксплицируется в виде формальной системы,а именно, в виде ее негативного напарника Li^ ep- Сильная трансляция логики Lneg в L может быть задана посредством оператора противоречияС((/?) := (fi А -чр. Поэтому логика Lneg действительно может рассматриваться как логика противоречий логики L.Мы завершим исследование класса Jhn изучением отношения негативной эквивалентности между логиками из Jhn. Логики Li,L2 € Jhnнегативно эквивалентны, если они имеют одно и то же негативное отношение следования, т.е. X hij -ly?, если и только если X \-i^ -мр длялюбых множества формул X и формулы у?. Негативная эквивалентностьлогик из класса Lj эквивалентна также утверждению, что эти логикиимеют то же самое семейство противоречивых множеств формул. С конструктивной точки зрения эти факты означают, что две негативно эквивалентные логики имеют одинаковые концепции отрицания и противоречия.В заключительной главе первой части диссертации мы предложимспособ преодолеть вышеупомянутый парадокс минимальной логики. Этобудет сделано заменой константы JL на унарный оператор абсурдностии последующим определением отрицания как редукции к такой12обобщенной абсурдности:Идея подобного определения возникает из сравнения оператора противоречия в логике классической опровержимости КарриЬе [28], наибольшем паранепротиворечивом расширении минимальной логики, и онератора необходимости в модальной логике Лукасевича L [52, 53]. Мы докажем, что один из модальных парадоксов логики L в точности соответствует тому факту, что оператор абсурдности является константой, какв Le. Более того, оказывается, что в некоторых хорошо известных системах наранепротиворечивых логик отрицание может быть задано именноэтим способом. Например, в логике CLuN Д. Батенса [13, 14] и в максимальной паранепротиворечивой логике Сета Р^ [80, 67] отрицание можетбыть представлено как сведение к унарному оператору абсурдности.Бо второй части диссертации исследуется решетка расширений паранепротиворечивой логики Нельсона. Здесь существенную роль играет нетолько интерес к логике Нельсона как альтернативной формализацииинтуиционистской логики, но и желание нроверить, применим ли к этому новому объекту нодход, разработанный в первой части работы? Иответ на этот вопрос является положительным, хотя будет обнаруженотакже существенное отличие структур решеток расширений минимальной логики и паранепротиворечивой логики Нельсона.Б связи с паранепротиворечивой логикой Нельсона возникает вопрос,в каком языке следует рассматривать эту логику. Избыточная логикаКЗрассматривается обычно в языке (V, Л, —>•, , -i) с символами для двухотрицаний, сильного и интуиционистского -I. Причем интуиционистское отрицание, вообще говоря, излишне, так как может быть определеночерез сильное. При переходе к паранепротиворечивой логике N4 интерпретация -1 не ясна, поэтому кажется естественным рассматривать язык13с единственным отрицанием . Такой вариант паранепротиворечивойлогики Нельсона мы будем обозначать N4. Тем не менее, как мы увидим, присутствие в языке интуиционистского отрицания наряду с сильным естественно и желательно. Консервативное расширение логики N4в языке (V, Л, —>, , 1) с дополнительными аксиомами для константы ±будет обозначаться N4"^. Интуиционистское отрицание определяется вN4'^' обычным образом, -чр :=(/?—> ±.Для изучения класса £^N4 (£^N4^) расширений логики Нельсона N 4(N4'^) необходима адекватная алгебраическая семантика. Нужно найти определяющее логику N 4 (N4"^) многообразие алгебр такое, что существует дуальный изоморфизм между решеткой подмногообразий данного многообразия и решеткой К4(М4''")-расширений. Для избыточнойлогики N 3 такую семантику задает многообразие N3-peшeтoк, которое достаточно хорошо изучено [69, 34, 35, 39, 77, 78, 86]. N4-peшeтки,введенные автором в [116], определяют семантику этого типа для логики N4. Алгебраическая семантика для N4"'' задается N4"''-peшeткaми,естественной модификацией К4-решеток. Интересная особенность N 4 ( HN4•'•)-peшeтoк состоит в том, что они имеют целый фильтр выделенныхзначений.Нреимуш;ество языка с интуиционистским отрицанием становится явным, когда мы начинаем исследование класса К4''"-расширений. Его строение суш,ественно отличается от строения класса Jhn. Прежде всего, вотличие от Jhn, содержаш;его целый подкласс Neg противоречивых логик, логика N4"^ не имеет нетривиальных противоречивых расширений.Несмотря на то, что логика N4"*" паранепротиворечива, она допускаеттолько локальные противоречия. Присоединение к N4"^ противоречиякак схемы формул имеет своим результатом тривиальную логику. Тем неменее, класс £^ N4"^ " разбивается на подклассы избыточных, нормальных14логик и логик обш,его вида. Это разбиение отражает локальную струк'Щ' туру противоречий в К4''"-моделях и подобно разбиению класса Jhn наподклассы промежуточных, негативных и собственно паранепротиворечивых логик. Именно присутствие в языке константы _L позволяет определить класс нормальных логик, соответствуюш,ий классу негативныхлогик в решетке Lj-расширений.Заметим, что отношение негативной эквивалентности, играюш,ее важную роль при изучении класса расширений минимальной логики, вырождается при переходе к К4-расширениям. Два расширения логики^ N4 (N4''") негативно эквивалентны, если и только если они равны.Опишем теперь более точно структуру диссертации. Глава 2 содержит определения важнейших логик из класса Jhn и необходимые сведения об алгебраической семантике и семантике Крипке для расширенийминимальной логики. Глава 3 посвящена логике классической опровержимости, наибольшему паранепротиворечивому расширению логики Lj,играющему ключевую роль в исследовании класса Lj-расширений.В главе 4 мы исследуем логику Le' = Lj + {± V (± —>• р)} и доказываем, что класс расширений этой логики совпадает с классом всехвозможных пересечений промежуточных и негативных логик. Более то* го, каждая логика L, расширяющая Le', имеет единственное представление в виде пересечения промежуточной логики Li и негативной логики L2. Логику Li (соответственно, L2) мы назовем интуиционистским (соответственно, негативным) напарником логики L. Далее, понятия интуиционистского и негативного напарников обобщаются на классвсех Lj-расширений. При этом класс Par собственно паранепротиворечивых Lj-расширений разбивается на попарно непересекающиеся семейм\ ства Spec{Li,L2), состоящие из всех логик имеющих логики Li и L2 вкачестве своих интуиционистского и, соответственно, негативного напар15НИКОВ. Каждое из семейств Spec{Li, L2) образует интервал в решетке Par'Щ" с наибольшей точкой Х/хПЬг. Таким образом, изучение структуры классаJhn сводится к изучению интервалов вида Spec{Li,L2).Следующая глава посвящена нахождению удобного представления j алгебр, которое позволяло бы определять положение различных логиквнутри интервалов Spec{Li,L2)- Эффективность полученного представления демонстрируется его применением к многочисленным расширениям минимальной логики, рассматривавшимся К. Сегербергом [76].В главе 6 мы вводим отношение =пед негативной эквивалентности ло^ гик и, модифицировав технику формул Янкова, доказываем, что решетка Spec{Li^ L2)/ =пед изоморфна интервалу 5j?ec(Lk, L2). Мы покажемтакже, что каждый интервал Spec{Li,L2) содержит бесконечно многоклассов негативной эквивалентности, а в Jhn имеется континуум различных классов негативной эквивалентности.Последняя глава первой части диссертации, глава 7, посвящена изучению унарного оператора абсурдности.Глава 8 начинает вторую часть диссертации, носвященную сильному отрицанию. В первом параграфе определяются два варианта паранепротиворечивой логики Нельсона. Логика N 4 определяется в языке^ (V, Л, —^ , ) , где — символ для сильного отрицания, а логика N4"*" —в языке (V, Л, —*, , -L) с дополнительной константой ±. При этом N4"''— консервативное расширение как N4, так и интуиционистской логики.Избыточная логика N 3 получается присоединением к N4 аксиомы избыточности "^ р —^ {р -^ q)- Причем, полагая ± : = {ро —> ро) можнодоказать в N3 дополнительные аксиомы логики N4""".Во втором параграфе логика N4 характеризуется с помощью структур Фиделя [35]. Это непосредственное обобщение результата М. Фиделяиз [35] для логики N3. Структуры Фиделя представляют собой импли16кативные решетки с выделенным семейством одноместных нредикатов.В третьем параграфе семантика N4 задается с номощью твист-структур над импликативными решетками (см. [34, 86]). Причем теорема нолноты следует из доказанной здесь же эквивалентности структур Фиделяи твист-структур. Твист-структура — это алгебраическая система, задаваемая на декартовом квадрате импликативной решетки. Причем онерации этой структуры согласованы на первой координате с операциямиимнликативной решетки и "скручены" на второй.Далее, в 4-м параграфе устанавливается, что класс алгебр изоморфных твист-структурам допускает теоретико-решеточное определение. Введен класс N4-peшeтoк. Доказано, что всякая твист-структура являетсяК4-решеткой, а всякая N4-pemeTKa Л изоморфна твист-структуре надДх,, импликативной решеткой, определяемой как фактор-решетка Л поконгруэнции специального вида. Откуда следует, что N4 характеризуется N4-решетками.В следуюш,ем параграфе доказывается, что К4-решетки образуютмногообразие VN4) И устанавливается дуальный решеточный изоморфизммежду решеткой £^N4 расширений логики N 4 и решеткой подмногообразий многообразия VN4В заключительном параграфе главы 8 ранее полученные результаты переносятся на логику N4"'' и решетку ее расширений ^N4"^. Приэтом твист-структуры определяются над алгебрами Рейтинга и для любой N4"^ •-peшeтки Л фактор-структура Atxi также будет алгеброй Рейтинга. Назовем Д<, базисной алгеброй N4"'"-peшeтки Л. В главе 9 развиты начала алгебраической теории N4•'•-peшeтoк в объеме, необходимом для исследования решетки расширений логики N4"*". Вчастности получено представление N4•'•-peшeтoк в виде алгебр Рейтинга с выделенными фильтром и идеалом. Определена пара сопряженных17функторов между категориями N4''"-pemeT0K и алгебр Рейтинга. Доказано, что если гомоморфизм базисных алгебр может быть поднят HaN4''"решетки, то это делается единственным образом. Показано, что конгруэнции на N4"'"-penieTKe находятся во взаимно однозначном соответствиис импликативными фильтрами. Установлен изоморфизм решеток конгруэнции N4"^-peшeтки и ее базисной алгебры. Как следствие, описаныподрямо неразложимые К4'''-решетки как решетки с подпрямо неразложимой базисной алгеброй. В терминах описанного выше представлениясформулирован критерий вложимости и описаны фактор-алгебры N4"*"решеток.В заключительной 10-й главе изучается строение решетки N4'^-pacширений, при этом обнаруживается несомненное сходство со строениемкласса расширений минимальной логики. Хотя различия в строении этихдвух классов логик также существенны. Первое из этих отличий состоитв том, что N4"^ не содержит противоречивых нетривиальных расширений. Минимальная же логика имеет целый класс противоречивых расширений, изоморфный классу расширений позитивной логики.В главе исследованы связи между логикой L, расширяюш,ей N4"^, иее интуиционистским фрагментом. В решетке £^ N4"^ " расширений логикиN4 определены подклассы избыточных логик Ехр, нормальных логикNor и логик общего вида Gen, играющие роль аналогичную классам Int,Neg и Par в решетке расширений минимальной логики. Исследованы связи между классами Ехр, Nor и Gen с помощью определения избыточныхи нормальных напарников для логик из класса Gen.Даны первые приложения развитой теории решетки К4"''-расширений.Во-первых, полностью описана решетка расширений логики N4"''С, получающейся присоединением аксиомы Даммета к N4'''. Доказано, чтовсе ее расширения разрешимы и конечно аксиоматизирумы, а по произ18вольной формуле можно определить, какое расширение логики N4"'"Cона аксиоматизирует.Во-вторых, описаны табличные, предтабличные логики и логики, обладаюш;ие интерполяционным свойством Крейга в решетке расширенийлогики N4'''.19# Часть IReductio ad absurdum20Глава 2Минимальная логика. Синтаксис исемантика.в первой части диссертации, посвященной минимальной логике, мы будем рассматривать логики и дедуктивные системы, сформулированныев следующих языках.:= {л, V, -^}, £^ := £+ U {_L}, Г := £+ UРасширения минимальной логики допускают эквивалентные представления в языках С^ и Логикой мы называем множество формул, замкнутое относительноправил подстановки и modus ponens. Как правило, мы будем задаватьлогики как множества теорем дедуктивных систем Гильбертовского типа с правилами подстановки и modus ponens. Поэтому для задания логики будет достаточно перечислить ее аксиомы. Если L — логика, а X —множество формул в том же самом языке, тоЬ-\-Х обозначает наименьшую логику, содержащую L и X. Символом + будем обозначать такжеоперацию взятия точной верхней грани в решетках логик. ОтношениеX \-L (р означает, что формула tp может быть получена из элементов Xи L с помощью правила modus ponens.Обозначим через ^* тривиальную логику, т.е. множество всех формул21языка £*, * е {+, -L,Определим ряд важнейших логик. Отметим, что при выборе обозначений мы следовали монографии В. Раутенберга [72].2. Для любых мнооюества формул X С ^-^ и формулы (р е J^-^ верноX hyx ip, если и только если р{Х) h^j- p{ip).Более того, Lj^ \- ср *-^ ^p{v^) ^ля любой формулы ip.иТаким образом, определенные выше трансляции сохраняют дедуктивные свойства, а последовательное применение двух трансляций дает формулу, эквивалентную исходной. Ввиду этих фактов мы может свободно23переходить от языка £-*• к языку СГ и обратно. В дальнейшем мы опускаем индексы в обозначении минимальной логики и не будем уточнятьс какой из ее версий мы работаем в данный момент. Точно также мыбудем поступать и с расширениями минимальной логики.

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

1. Колмогоров А. Н. О принципе tercium поп datur // Матем. сборник. - 1925. - Т. 32, № 4. - С. 646-667.

2. Кушнер Б.А. Конструктивная математика // Математическая энциклопедия, т.2 / Ред. А. Виноградов. Москва: Советская энциклопедия, 1977. - С. 1042-1046.

3. Максимова J1.JI. Предтабличные суперинтуицонистские логики // Алгебра логика. 1972. - Т. И, № 5. - С. 552-570.

4. Максимова JI.J1. Теорема Крейга в суперинтуционистских логиках и амальгамируемые многообразия псевдобулевых алгебр / / Алгебра логика. 1977. - Т. 16, № 6. - С. 643-681.

5. Марков A.A. О конструктивной математике // Тр. ИМ им. Стек-лова. 1962. - Т. 67. - С. 8-14.

6. Самохвалов К.Ф. Относительно конструктивные системы // Выч. системы. Вып. 124. - Новосибирск, 1988. - С. 99-113.

7. Янков В.А. Об отношении между выводимостью в интуиционистском пропозициональном исчислении и конечными импликативны-ми структурами // Докл. АН СССР. 1963. - Т. 151, № 6. - С. 12931294.

8. Янков В.А. Построение последовательности сильно независимых суперинтуиционистских пропозициональных исчислений.// Докл. АН СССР. 1968. - Т. 181. - С. 1035-1037.

9. Almukdad A., Nelson D. Constructible falsity and inexact predicates 11 J. Symb. Log. 1984. - Vol. 49, No. 1. - P. 231-233.

10. Alves E.H., Sette A.M. On the equivalence between some systems of non-classical logic // Bull. Sect. Log., Univ. Lodz, Dep. Log. 1996. -Vol. 25, No. 2. - P. 68-72.

11. Avron A. On an implication connective of RM // Notre Dame J. Formal Logic. 1986. - Vol. 27, No. 2. - P. 201-209.

12. Avron A. Natural 3-valued logics: characterization and proof theory. // J. Symb. Log. 1991. - Vol. 56, No. 1. - P. 276-294.

13. Batens D. A completeness proof method for extensions of the implicational fragment of the propositional calculus // Notre Dame J. Formal Logic. 1980. - Vol. 21, No. 3. - P. 509-517.

14. Batens D. Paraconsistent extensional propositional logics // Log. Anal., Nouv. Ser. 1980. - Vol. 23 - P. 195-234.

15. Batens D., De Clercq K., Kurtonina N. Embedding and interpolation for some paralogies. The propositional case // Rep. Math. Logic. -1999. Vol. 33. - P. 29-44.

16. Belnap N.D. A useful four-valued logic // Modern Uses of Multiple-Valued Logic / Eds. G. Epstein and M.J. Dunn. Oriel Press, 1977. -P. 7-37.

17. Belnap N.D. How computer should think // Contemporary Aspects of Philosophy / Ed. G.Ryle. Oriel Press, 1977. - P. 30-56.

18. Borceux F. Handbook of Categorical Algebra 1, Basic Category Theory.- Cambridge: Cambridge University Press, 1994 345 p.

19. Burris S, Sankappanavar H.P. A course in universal algebra. Graduate Texts in Math. 78, N.Y.: Springer, 1981 - 276 p.

20. Chagrov A., Zakharyaschev M. The undecidability of disjunction property of propositional logics and other related problems //J. Symb. Log. 1999. - Vol. 58, No. 3. - P. 967-1003.

21. Chagrov A., Zakharyaschev M. Modal logic. Oxford: Clarendon Press, 1997 - 605 p.

22. Cignoli R. The class of Kleene algebras satisfying interpolation preperty and Nelson algebras // Algebra Univers. 1986. - Vol. 23, No. 3. -P. 262-292.

23. Curry H.B. On the definition of negation by a fixed proposition in the inferential calculus // J. Symb. Log. 1952. - Vol. 17, No. 1. - P. 98104.

24. Curry H.B. The system LD, // J. Symb. Log. 1952. - Vol. 17, No. 1.- P. 35-42.

25. Curry H.B. Foundations of mathematical logic. N.Y.: McGrow-Hill Book Company, 1963. - 408 p.

26. Dosen K. Negative modal operators in intuitionistic logic // Publ. Inst. Math., Nouv. Ser. 1984. - Vol. 35(49). - P. 15-20.

27. Dosen K. Negation as a modal operator // Rep. Math. Logic. 1986.- Vol. 20. P. 15-28.

28. Dosen K. Negation in the light of modal logic // What is Negation?/Eds. D. Gabbay, H. Wansing. Dordrecht: Kluwer, 1999. P. 77-86.

29. Dunn J.M. Partiality and its Dual // Stud. Log. 2000. - Vol. 66, No. 1. - P. 5-40.

30. Dunn J.M., Meyer R.K. Algebraic completeness results for Dummett's LC and its extensions // Z. Math. Logic Grundl. Math. 1971. -Vol. 17, No. 2. - P. 225-230.

31. Fidel M.M. An algebraic study of a propositional system of Nelson // Mathematical Logic, Proc. of the First Brasilian Conference, Campinas 1977. Lect. Notes Pure Appl. Math. 39, 1978. - P. 99-117.

32. Fidel M.M. An algebraic study of logic with constructive negation // Proc. of the Third Brazilian Conf. on Math. Logic, Recife 1979. 1980.- P. 119-129.

33. Fine K. Logics containing K4. I // J. Symb. Log. 1974. - Vol. 39, No. 1. - P. 31-42.

34. Fine K. Logics containing K4. II // J. Symb. Logic. 1985. - Vol. 50, No. 3. - P. 619-651.

35. Font J.M., Hajek P. On Lukasiewicz's four-valued modal logic // Stud. Log. 2002. - Vol. 70, No. 2. - P. 157-182.

36. Goranko V. The Craig interpolation theorem for propositional logics with strong negation // Stud. Log. 1985. - Vol. 44, No. 3. - P. 291317.

37. Heyting A. Die formalen Regeln der intuitionistischen Logik 11 Sitzungsber. Akad. Berlin. 1930. - P. 42-56.

38. Heyting A. Intuitionism. An introduction. Amsterdam: North-Holland, 1971. - 150 p.

39. Jaskowski S. Propositional calculus for contradictory deductive systems // Stud. Log. 1969. - Vol. 24. - P. 143-157.

40. Johansson I. Der Minimalkalkül, ein reduzierter intuitionistischer Formalismus // Compos. Math. 1937. - Vol. 4. - P. 119-136.

41. Kanger S. A note on partial postulate sets for propositional logic // Theoria. 1955. - Vol. 21, No. 1. - P. 99-104.

42. Karpenko A.S. Two three-valued isomorphs of classical propositional logic and their combinations // First World Congress on Paraconsistency, Abstracts, Ghent, 1997. P. 92-94.

43. Kolmogoroff A. Zur Deutung der intutionistischen Logik // Math. Z. -1932 Vol. 35. - P. 58-65.

44. Körner S. Experience and Theory. London: Kegan Paul, 1966. - 250 p.

45. Kracht M. On extensions of intermediate logics by strong negation // J. Philos. Log. 1998. - Vol. 27, No. 1. - P. 49-73.

46. Kripke S.A. Distinguished constituents (abstract) //J. Symb. Log. -1959. Vol. 24, No. 4. - P. 323.50. von Kutschera F. Ein verallgemeinerter Widerlegungsbegriff für Gentzenkalküle // Arch Math. Logic. 1969. - Vol. 12, No. 2. - P. 104118.

47. Loparic A., da Costa N.C.A. Paraconsistency, paracompleteness and induction // Log, Anal. Nouv. Ser. 1986. - Vol. 113. - P. 73-80.

48. Lukasiewicz J. A system of modal logic // J. Comput. Systems. Vol. 1.- P. 111-149.

49. Lukasiewicz J. Aristotle's syllogistic from the standpoint of modern formal logic. Oxford: Clarendon Press, 1951 - 141 p.

50. Lukasiewicz J. Selected works. Amsterdam, North-Holland, 1970. -405 p.

51. Maksimova L.L. On maximal intermediate logics with the disjunction property // Stud. Log. 1986. - Vol. 45, No. 1. - P. 69-75.

52. Mendelson E. Introduction to mathematical logic, 2nd edition. N.Y.: D. Van Nostrand Company, 1979. - 328 p.

53. McKay C.M. On finite logics // Indag. Math., New Ser. 1967. -Vol. 29, No. 3. - P. 363-365.

54. Miura S. A remark on the intersection of two logics // Nagoja Math. J.- 1966. Vol. 26, No. 2. - P. 167-171.

55. Nelson D. Constructible falsity // J. Symb. Log. 1949. - Vol. 14, No. 1. - P. 16-26.

56. Nelson D. Negation and separation of concepts // Constructivity in mathematics. Amsterdam: Notrh-Holland, 1959. - P. 208-225.

57. Ono H. Kripke models and intermediate logics // Publ. Res. Inst. Math. Sci. 1971. - Vol. 6. - P. 461-476.

58. Porte J. The fi-system and the L-system of modal logic // Notre Dame H J. Formal Logic. 1979. - Vol. 20, No. 4. - P. 915-920.

59. Porte J. Lukasiewicz's L-modal system and classical refutability // Log. Anal. Nouv. Ser. 1984. - Vol. 27. - P. 87-92.

60. Priest G. Paraconsistent logic // Handbook of Philosophical Logic, Vol.6, 2nd edition / Eds. Gabbay D., Guenter. H. Dordrecht: Kluwer, 2002. - P. 287-393.

61. Paraconsistent logic. Essays on the inconsistent / Eds. Priest G., Routley R., Norman J. München: Philosophia Verlag, 1989. - 716 p.

62. Pynko A.P. Algebraic study of Sette's maximal paraconsistent logic // Stud. Log. 1995. - Vol. 54, No. 1. - P. 89-128.

63. Pynko A.P. Functional completeness and axiomatizability within Belnap's four-valued logic and its expansions //J. Appl. Non-Class. Log. 1999. - Vol. 9, No. 1. - P. 61-105.

64. Rasiowa H. TV-lattices and constructive logic with strong negation // Fundam. Math. 1958. - Vol. 46, No. 1. - P. 61-80.

65. Rasiowa H. Algebraische Charakterisierung der intuitionistischen ^ Logik mit starker Negation // Constructivity in mathematics / Ed.Heyting A. Amsterdam: Noth-Holland, 1959. - P. 234-240.

66. Rasiowa H. An algebraic approach to non-classical logics. Amsterdam: North-Holland, 1974. - 403 p.

67. Rautenberg W. Klassische und nichtclassische Aussagenlogik. -Braunschweig: Vieweg, 1979. 362 p.

68. Rescher N. Many-valued Logic. N.Y.,1969. - 359 p.

69. Robinson T.T. Independence of two nice sets of axioms for the propositional calculus //J. Symb. Log. 1968. - Vol. 33, No. 2. -P. 265-270.

70. Routley R. Semantical analyses of propositional systems of Fitch and Nelson // Stud. Log. 1974. - Vol. 33, No. 3. - P. 283-298.

71. Segerberg K. Propositional logics related to Heyting's and Johansson's // Theoria. 1968. - Vol. 34, No. 1. - P. 26-61.

72. Sendlewski A. Some investigations of varieties of AMattices // Stud. Log. 1984. - Vol. 43, No. 3. - P. 257-280.

73. Sendlewski A. Nelson algebras through Heyting ones // Stud. Log. -1990. Vol. 49, No. 1. - P.106-126.

74. Sendlewski A. Axiomatic extensions of the constructive logic with strong negation and disjunction property // Stud. Log. 1995. -Vol. 55, No. 3. - P. 377-388.

75. Sette A.M. On the propositional calculus P1 // Math. Jap. 1973. -Vol. 18, No. 3. - P. 173-180.

76. Smiley T. On Lukasiewicz's L-modal system // Notre Dame J. Formal Logic. 1961. - Vol. 2, No. 3. - P. 149-153.

77. Suzuki N.-Y. Constructing a continuum of predicate extensions of each intermediate propositional logics // Stud. Log. 1995. - Vol. 54, No. 2. - P. 173-198.

78. Thomason R. A semantical study of constructive falsity // Z. Math. Logik Grundl. Math. 1969. - Vol. 15, No. 3. - P. 247-257.

79. Thomason S.K. Reduction of Second-order Logic to Modal Logic. Z. Math. Logik Grundl. Math. 1975. - Vol. 21, No. 2. -P. 107-114.

80. Urbas I. A note on "Carnot's logic" // Bull. Sect. Logic., Univ. Lodz, Dep. Log. 1994. - Vol. 23, No. 3. - P. 118-125.

81. Vakarelov D. Notes on N-lattices and constructive logic with strong negation // Stud. Log. 1977. - Vol. 36, No. 1-2. - P. 109-125.

82. Wansing H. Semantics-based nonmonotonic inference // Notre Dame J. Formal Logic. 1995. - Vol. 36, No. 1. - P. 44-54.

83. Wansing H. Negation // The Blackwell Guide to Philosophical Logic / Ed. Goble L. Cambridge: Basil Blackwell Publishers, 2001. - P. 415436.

84. Wansing H. Diamonds are a Philosopher's Best Friends //J. Philos. Log. 2002. - Vol. 31, No. 6. - P. 591-612.

85. Wojtylak P. Mutual interpretability of sentential logic.I // Rep. Math. Logic. 1981. - Vol. 11. - P. 69-89.

86. Wojtylak P. Mutual interpretability of sentential logic.II // Rep. Math. Logic. 1981. - Vol. 12. - P. 51-66.

87. Woodruff P.W. A note on JP' 11 Theoria. 1970. - Vol. 36, No. 2. -P. 183-184.

88. Wronski A. The degree of completeness of some fragments of the intuitionistic propositional logic // Rep. Math. Logic. 1974. - Vol. 2.- P. 55-62.

89. Wroiiski A. On the cardinalities of matrices strongly adequate for the intuitionistic propositional logic // Rep. Math. Logic. 1974. - Vol. 3.- P. 67-72.Работы автора по теме диссертации

90. Одинцов С.П. О связи относительно конструктивных систем с традиционными подходами // Выч. системы. 1989. - Вып. 129. -Новосибирск, 1989. - С. 172-182.

91. Одинцов С.П. Пропозициональные относительно конструктивные системы // Выч. системы. 1997. - Вып. 158. - Новосибирск, 1997.- С. 110-126.

92. Одинцов С.П. Изоморфы логики классической опровержимости и их обобщения // Труды научно-исследовательского семинара Логического центра Института философии РАН / Ред. Смирнова Е.Д.- Москва, 1998. С. 48-61.

93. Одинцов С.П. Паранепротиворечивые расширения минимальной логики и их логики противоречий // Смирновские чтения, 2-я международная конференция/ Ред. Смирнова Е.Д. Москва, 1999. -С. 58-60.

94. Одинцов С.П. О негативно эквивалентных расширениях минимальной логики и их логиках противоречий // Логические исследования / Ред. Карпенко A.C. Москва: Наука, 2000. - С. 119-127.

95. Одинцов С.П. О логиках Сегерберга // Выч. системы. 2001. -Вып. 168. - Новосибирск, 2001. - С. 19-52.

96. Одинцов С.П. О парадоксе минимальной логики // Выч. системы.- 2001. Вып. 168. - Новосибирск, 2001. - С. 53-60.

97. Одинцов С.П. Алгебраическая семантика и семантика Крипке для расширений минимальной логики // Логические исследования Электронный ресурс]. 1999, Том 2. - Режим доступа: http://www.logic.ru/LogStud/02/No2-06.html.

98. Одинцов С.П. Теоремы переноса для расширений паранепротиво-речивой логики Нельсона // Алгебра и логика 2006. - Т. 45, №4 -С. 409-435.

99. Одинцов С.П. О расширениях логики Нельсона, удовлетворяющих аксиоме Даммета // Сиб. матем. журнал 2007. - Т. 48, №1. -С. 144-161.

100. Одинцов С.П. Об одном обобщении принципа reductio ad absurdum // Вестник НГУ, Серия: матем., мех. и информатика. 2006. - Т. 6, Вып. 3. - С. 62-87.

101. Одинцов С.П. Решетка расширений минимальной логики // Математические труды 2006. Т. 9, №2. - С. 60-108.

102. Odintsov S.P. Maximal paraconsistent extension of Johansson logic // First World Congress on Paraconsistency, Abstracts. Ghent,1997. -P. 111-113.

103. Odintsov S.P. Maximal paraconsistent extension of Johansson logic // Log. Anal., Nouv. Ser. 1998. - Vol. 161/163. - P. 107-120.

104. Odintsov S.P. On j-algebras and j-frames // International Maltsev conference on mathematical logic, Abstracts. Novosibirsk, 1999. -P. 101-102.

105. Odintsov S.P. Representation of j-algebras and Segerberg's logics // Log. Anal., Nouv. Ser. 1999. - Vol. 165/166. - P. 81-106.

106. Odintsov S.P. Negation as Absurdity in Paraconsistent Setting //II World Congress on Paraconsistentcy, Juquehy, Brazil, 2000:Abstracts. Campinas, 2000. - P. 94-95.

107. Odintsov S.P. On the Structure of Paraconsistent Extensions of Johansson's Logic (extended abstract) // CLE-e-printsElectronic resource. 2002. - Vol. 2, No. 7. - Mode of access: & ftp:logica.cle.unicamp.br/pub/e-prints/Odintsov.ps.

108. Odintsov S.P. On the embedding of Nelson's logics // Bull. Sect. Log., Univ. Lodz, Dep. Log. 2002. - Vol. 31, No. 4. - P. 241-250.

109. Odintsov S.P. Logic of classical refutability and class of extensions of minimal logic // Log. Log. Philos. 2002. - Vol. 9. - P. 91-107.

110. Odintsov S.P. Semantical characterization of Nelson's paraconsistent logic // Smirnov Readings, 4th International Conference / Ed. Karpenko A.S. Moscow, 2003. - P. 86-87.

111. Odintsov S.P. Algebraic semantics for paraconsistent Nelson's Logic // J. Log. Comput. 2003. - Vol. 13, No. 4. - P. 453-468.

112. Odintsov S.P. "Reductio ad absurdum" and Lukasiewicz's modalities // Log. Log. Philos. 2003. - Vol. 11. - P. 149-166.

113. Odintsov S.P. On representation of N4-lattices // Stud. Log. 2004. - Vol. 76, No. 3. - P. 385-405.

114. Odintsov S.P. Negative equivalence of extensions of minimal logic // Stud. Log. 2004. - Vol. 76, No. 3. - P. 417-442.

115. Odintsov S.P. On the structure of paraconsistent extensions of Johansson's logic // J. Appl. Log. 2005. - Vol. 3, No. 1. - P. 4365.

116. Odintsov S.P. The Class of Extensions of Nelson Paraconsistent Logic // Stud. Log. 2005. - Vol. 80, No. 2-3. - P. 291-320.