Введение
Многозначные логики появились в 20-х годах XX века в работах Поста и Лукасевича. Несколько позднее было предложено ещё несколько многозначных логик, таких как логика Бочвара, логики Гёделя, логика Клини. Интересный библиографический экскурс в многозначные логики можно найти в [7]. Изобретение этих логик было мотивировано разными задачами. Так, Лукасевич и Бочвар исходили из философских предпосылок, вводя третье значение в свои логики для формализации неполного или противоречивого знания; Пост и Гёдель руководствовались более техническими соображениями, когда обобщали классическую логику в n-значных системах; Клини же просто искал удобный формализм для анализа понятия частично определённой рекурсивной функции. Однако все эти логики объединяет важная отличительная особенность: в них ме-татеоретически заложена концепция, которую называют истинностной функциональностью. Согласно ей, всякое высказывание имеет некоторое значение истинности, и это значение может быть однозначно вычислено некоторой заранее определённой функцией по значениям входящих в это высказывание подвысказываний. Так, в случае конъюнкции А А В высказываний А и В искомой функцией будет некоторая функция /л от значения А и значения В.
Если логика истинностно-функциональна, это непосредственно означает существование метода вычисления значения истинности для любого высказывания, записанного на языке этой логики. В этом состоит привлекательная в техническом смысле сторона многозначных логик: по любой формуле можно легко сказать, что она «значит». Сохраняется ли эта при-
влекательность многозначных логик в теории вывода? К сожалению, нет, поскольку с ростом числа истинностных значений растёт и то внимание, которое им приходится уделять, а в это время падает эффективность рассуждений.
Что же в таком случае делать, если возникают задачи, требующие многозначного решения? Отказаться от истинностной функциональности и : перейти в другую концепцию? Как следует из данной работы, этого делать не нужно, поскольку полученные в ней результаты позволяют эффективно строить выводы, оставаясь в рамках концепции многозначности.
Степень разработанности проблемы. В нашей стране было получено большое количество результатов в области многозначных логик. Среди них можно особо отметить следующие: вычисление Яблонским всех пред-полных классов функций для трехзначной логики Поста в 1954 году, а также нескольких классов для случая к ^ 4 значений в 1958 году; доказательство существования А;-значных замкнутых классов функций, не имеющих конечного базиса, для к > 2, найденное Яновым и Мучником в 1959 году (см. [30]); определение функциональных свойств логик Лукасевича Финном [4] в 1970 году; получение метода аксиоматизации произвольных конечнозначных логик Аншаковым и Рычковым [1] в 1982 году; установление Карпенко [9] связи импликации Лукасевича с классами простых чисел в 1999 году; построение Косовским и Тишковым [17] секвенциальных исчислений для классов конечнозначных логик в 2000 году. Также можно указать оригинальное доказательство полноты бесконечнозначной логики Лукасевича относительно реляционных семан-тик с тернарным отношением достижимости, полученное Васюковым в [88]. За рубежом многозначная логика в наше время является сложной разветвлённой отраслью науки. Многие работы общетеоретического характера публикуются не отдельными авторами, а коллективами авторов, например, статья по секвенциальным исчислениям с метками для конечнозначных логик [36] или монография по алгебраическим основаниям многозначных логик [46].
Актуальность темы диссертации. Сегодня для бесконечнозначных
логик не существует хорошо обоснованной теории доказательств, хотя для конечнозначных логик табличные исчисления без сечений были построены ещё Руссо [80] в 1967 году. Некоторые исчисления для бесконечнозначных логик Лукасевича всё лее определяются в литературе, например, Агуц-цоли и Чиабаттони [31] в 2000 году строят секвенциальное исчисление для бесконечнозначной логики, опирающееся на идею Мундичи о сводимо- сти проблемы разрешимости с бесконечнозначной логики на подходящий класс конечнозначных логик, и, следовательно, основанное на исчисле- ниях для конечнозначных логик. В 2001 году Софрони-Стоккерманс [85] предложила метод доказательства теорем для большого класса многознач-ных логик, основанный на теореме представления алгебр истинностных значений. Кроме своей эффективности, этот метод интересен ещё и тем, что в нём посредством структур Крипке устанавливается соответствие между многозначными и модальными логиками. К сожалению, метод [85] неприменим к ряду широко распространённых бесконечнозначных логик. Данный метод исследован в диссертации, и на основе этого исследования сделан вывод о возможности его обобщения на класс бесконечнозначных логик на основе подходящей теоремы представления алгебр истинностных значений.
Цель диссертационного исследования — формирование единого подхода к теории вывода многозначных логик на основе изучения их семантик и исчислений.
Предмет исследования — это логические семантики различных видов, логические исчисления для многозначных логик, теории, в которых формализована концепция многозначности, и модели таких теорий.
Методы исследования. В работе используется логическая техни- ка, как традиционная, например, секвенциальные логические исчисления, так и нетрадиционная: исчисления с «отмеченными формулами», S-классификация замкнутых классов функций многозначных логик, дуальные многозначным семантикам топологические модели. Автором работы вводится оригинальный метод на основе исчисления резолюций для доказательства теорем в многозначных логиках с линейно упорядоченными
множествами истинностных значений.
Структура и объём работы. Диссертация состоит из введения, семи глав, заключения, приложения и списка литературы.
В первой главе — «Истинностно-функциональные семантики» — осуществляется содержательное философское истолкование концепции истинностной функциональности, лежащей в основе явления многознач-л ности. Раскрывается понятие истинностно-функциональной семантики,
приводятся наиболее распространённые варианты таких семантик, и среди них: семантика голосования, семантика сходства, семантика рисков, семантика допустимости, семантика приближений.
Во второй главе — «Формализация многозначных логик» — даются строгие определения понятий многозначной теории вывода, таких как: логика высказываний, логика первого порядка, абстрактная алгебра, логический вывод, формула с метками, логическое исчисление (секвенциальное, табличное, гильбертовское, резолютивное).
Третья глава — «Функциональный анализ многозначных логик»
— содержит изложение основных результатов анализа и классификации функций многозначных логик в классе функций га-значных логик Поста.
; Приводятся определения замкнутых и .^-замкнутых классов функций
многозначных логик, а также критерии полноты и ^-полноты для этих классов. Даётся предикатная характеризация ^-замкнутых классов по Марченкову.
Четвёртая глава — «Метод резолюций для смешанной логики Поста»
— посвящена исследованию так называемой смешанной логики Поста PostL, предложенной Косовским и Тишковым [17], и обобщающей в своём исчислении свойства класса исчислений всех n-значных логик Поста. В
1^. этой главе автором строится корректное исчисление резолюций в духе [35]
для смешанной логики Поста.
В пятой главе — «Теорема Чена» — впервые на русском языке даётся полное оригинальное доказательство теоремы Чена о полноте бесконечнозначной логики Лукасевича относительно многообразия MV-алгебр.
Шестая глава — «Метод резолюций на основе теоремы представления дистрибутивных решёток с операторами» — освещает проблематику представления алгебр многозначных логик и знакомит с методом поиска доказательства теорем многозначных логик, основанном на результате [83]. В данной главе мы исследуем теорию вывода многозначных логик с алгебраической точки зрения. Результатом исследования является формулировка критерия применимости к произвольной многозначной логике предложенного в [85] метода резолюций на основе теоремы представления Пристли для дистрибутивных решёток с операторами.
В седьмой главе — «Эффективное доказательство теорем в логиках Лукасевича» — приводятся некоторые оптимизационные методы доказательства теорем в логиках Лукасевича. В частности, для бесконеч-нозначной логики Лукасевича L^o даётся метод (см. [37]), основанный на теореме Мак-Нотона [19].
В заключении показано, из каких вспомогательных результатов и посылок следуют основные результаты работы. Приводятся научно значи-мые следствия из основных результатов и общего содержания работы. В особенности указывается на открывающуюся перспективу создания общей "1' теории вывода для большого класса логик, основанных на дистрибутивных решётках или полурешётках с оператором резидуации, т.е. для нечёткозначных логик (включая логики Лукасевича) и релевантных ло- гик.
В приложении доказывается вложимость произвольного пропозиционального немодального гильбертовского исчисления в исчисление резолюций с одноместными предикатами и приводится пример, иллюстрирующий подобное вложение: доказательство рефлексивности импликации в аксиоматической системе {B,C,W,Ki,X3}, рассмотренной в [7], с помощью программы автоматического поиска доказательства теорем OTTER. Таким образом доказано, что данная система аксиом является аксиоматизацией импликативного фрагмента классической логики высказываний.
Обозначения используются стандартные. Выражение, заключённое в фигурные скобки { и }, обозначает множество. Запись {х : Р] читается
8
?
как «множество таких элементов х, для которых выполняется условие Р». Выражение вида [х,у], если не оговорено иное, обозначает числовой отрезок от х до у включая сами х и у. Запись [х, у) обозначает отрезок от х до у, включая х, но исключая у. Используются операции, определённые на (частично) упорядоченных множествах: тахМ — максимальный элемент множества М, rainM — минимальный элемент множества М, infM — наибольшая нижняя грань, или инфимум, множества М, sup М — наименьшая верхняя грань, или супремум, множества М. Множества натуральных, целых, рациональных и действительных чисел обозначаются, соответственно, N, Z, Q и R. Множество подмножеств заданного множества М будет обозначаться как V(M). Для определения функций используется запись вида / : X —? Y, которая читается как «функция /, отображающая множество X на множество У». Иногда функции могут задаваться на разных частях области определения, и тогда условные выражения для каждой части области определения объединяются фигурной скобкой. Выражение хп является сокращением
п раз
для х х • • • х х, причём п — это неотрицательное целое, ах — это разновидность умножения или конъюнкции.
Принимаются обозначения, доопределяемые в конкретных контекстах: Form — множество всех формул (языка данной логики), Var — множество всех переменных, Term — множество всех термов. Для предикатных констант в первопорядковой логике и для пропозициональных переменных употребляются символы P,Q,R,Pi,Qt,Rt,...; для произвольных формул — А, В, С, А\, Вх, Ci,... Как правило, количество аргументов предикатных и функциональных констант не указывается. Обозначения могут быть нестандартными, если это способствует более лёгкому чтению текста.
Предпошлём теперь формализованным изысканиям краткое содержательное истолкование смысла истинностных значений многозначных логик.
Возьмём такое упорядочение истинности (или упорядочение уверенности) на множестве истинностных значений {0,1}, которое сопоставляет О
т т
JL
JL
Рис. 1: Упорядочение истинности, упорядочение знания и решетка ЧЕТВЕРКА.
с наименьшей истинностью, или уверенностью, а 1 — с наибольшей. Будем писать F вместо 0 и Т вместо 1, как в левой части рисунка 1.
Совершенно иная интерпретация истинностных значений, принятая в исследованиях искусственного интеллекта и программировании, — это упорядочение знания (или упорядочение информации), где 0 означает отсутствие знания, а 1 — всезнание. Будем писать А. вместо 0 и Т вместо 1, см. центральную часть рисунка 1. С философской точки зрения, в интерпретации этого типа находит своё отражение эпистем,ологическая неопределённость.
Полезно иметь оба упорядочения в многозначной логике одновременно. Вслед за работой [38] вообразим, что у нас есть множество распределенных агентов, работающих над одной проблемой. Каждый агент дает двухзначный ответ из множества {T,F}, упорядоченного по истинности. А что делать, если какой-то агент не дал ответа, или же разные агенты дали разные ответы? В первой ситуации мы ничего не знаем, а поэтому должны взять истинностное значение ±; во втором случае мы берем значение Т, чтобы смоделировать общее, даже противоречивое знание. Уникально определенные значения F и Т находятся в середине. В результате получается решетка алмаза знания, изображенная в правой части рисунка 1. Эта решетка вместе с порожденными ей многозначными логиками исследуется в многочисленных статьях, начиная возможно с Лукасевича [67, 18], который считал получающуюся логику модальной, осуществляя попытку создания модели аристотелевской модальной силлогистики. Лукасевич
10
т
V
JL Рис. 2: Семизначная решетка для моделирования транзисторов MOS.
рассматривал импликацию, полученную с помощью резидуации точной нижней грани решетки, а также с помощью нескольких одноместных связок для добавления/удаления/перестановки истинных значений. Они оба, и в [18], и в [38], используют отрицание, которое переставляет JL и Т, F и Т. Решетка алмаза знания в частности удобна для передачи паранепро-тиворечивого знания, т.е. для осуществления вывода в противоречивых ситуациях [38].
Решетка знания становится решеткой алмаза знания, если повернуть ее на 90 градусов против часовой стрелки. Получается, что такие пересекающиеся решетки, где присутствуют оба вида упорядочения одновременно, могут быть обобщены из четырехзначного случая, см., например, [54].
Истинностные значения иногда мотивируются областями применения и имеют технический, а не логический смысл. Вот пример, взятый из [62]: у транзистора MOS на входе и выходе уровень сигнала разный из-за физического эффекта деградации. Эта ситуация моделируется семизначной логикой с N = {F,T,F',T',T,T',±} и порядком < изображенным на рис. 2. Значения Т и F соответствуют полным сигналам, тогда как F' и Т" соответствуют деградированным сигналам. В неисправной контактной схеме сигналы могут столкнуться в узле,
11
давая результирующие сигналы Т и Т'. Значение JL соответствует неподключенным узлам («отсутствие сигнала»). При данных условиях узел, в котором встречаются два сигнала жиг/, вычисляется просто как точная верхняя грань в решетке индуцированной порядком ^. Заметим, что у нас есть две решетки алмаза знания, соединенных вершинами друг друга. Транзисторы MOS моделируются пропозициональными связками в логике, чья семантика определяется техническими характеристиками специфических транзисторов. В статье Эсакиа [28] была дана естественная алгебраическая характеризация этой логики с помощью т.н. булевых каскадов. Получающаяся логика является суперинтуиционистской, она удовлетворяет ослабленному закону Пирса.
В заключение упомянем о двух применениях многозначной логики в философских аргументах: первое — это парадокс кучи и его разрешение в логике Лукасевича. Парадокс может быть запёчатлён в следующей импровизированной аксиоматической системе:
(А) Одна крупинка песка не является кучей.
(Bt) Добавляя одно зернышко песка к i зернышкам, которые еще не куча, кучу не получим.
(С) 100000 зернышек песка являются кучей.
Утверждения (A), (Bj)i^99999 и (С) классически противоречивы. Изменение размера (В{) до, скажем, кучи из 27000 зерен выглядит неправдоподобно, так же как и выбрасывание (А) либо (С). В логике Лукасевича можно разрешить данный парадокс допустив, что
I
меньше истины. Довольно частое применение (В,;) истощает «доверие», 4г заложенное в заключении, и таким образом разрешает парадокс.
Более важным является результат Хайека и Париса [60] о формализации парадокса лжеца (задаваемого, например, предложением «Это предложение ложно.») на базе логики Лукасевича, с применением многозначного предиката истинности. Показано, что идея использования многозначного предиката приводит к непротиворечивому определению
12
истинностного предиката в арифметике Пеано, которое, как известно, невозможно в классической логике. Интересно, что арифметика моясет оставаться классической, и только определение истины должно быть многозначным.
13
Глава 1
Истинностно-функциональные
семантики
В этой главе мы представим некоторые основные варианты семантик, обеспечивающих принцип истинностной функциональности многозначных логиках. Этот принцип является основным во всех многозначных логиках без исключения. Согласно нему, всякое высказывание имеет некоторое значение своей истинности, и это значение может быть более или менее однозначно вычислено некоторой заранее определённой функцией по значениям входящих в это высказывание подвысказываний. Так, в случае конъюнкции А А В высказываний А и В искомой функцией будет некоторая функция /Л от значения А и значения В. Разумеется, пока истинностная функциональность не подтверждена семантическими построениями, она является не принципом, а лишь допущением, подтверждение которого является целью главы.
Введём функцию w(A), где w : Form —> [О,1], возможно с различными индексами, для обозначения той степени, в которой А истинно. В качестве области значений этой функции используется интервал действительных чисел включительно от 0 до 1. Выражение w(A) = 1 обозначает, что А истинно в наивысшей возможной степени, тогда как w(A) = О, обозначает что А не истинно ни в какой степени. Функция w берётся как субъективная оценка, т.е. свойство некоторого познающего агента,
14
которого мы называем а, и там, где желательно подчеркнуть это обстоятельство, используется запись wa вместо w.
Будем называть ги(А) истинностно-функциональной, если при всех А, В G Form
«/(-.А) = Uw(A)), w(AaB) = /ЛЦЛ),ш(В)), w(AvB) = /v(w(A),w(S)),
для некоторых функций /_ : [0,1] —> [0,1] и /A,/v •' [0,1]2 —>• [0,1]. Наибольший интерес представляют такие выборы функций /_,, /Л, /v, которые сделаны независимо от функции w, так как на практике допущение истинностной функциональности используется тогда, когда хотят определить значение ги{А) сложного высказывания А по значениям его пропозициональных переменных w(Pi),... ,w(Pn), т.е. возникает обратная ситуация, в которой /Л и другие функции выбираются в зависимости от w.
Среди функций /-,, /л и /v, используемых в литературе, существует три особенно популярных подборки:
(1.1)
fl(x, y) = max{0, x + y-l},
(1.2)
(1.3)
Мы будем называть связки, соответствующие функциям, входящим в данные подборки, связками первого, второго и третьего типа.
15
В литературе по многозначным логикам довольно часто встречаются следующие два подхода к трактовке функции оценки w(A). В первом из них w(A) предназначается для оценки, в какой мере А истинно, отсюда w(A) есть некоторый уровень истинности высказывания А. Типичным примером здесь будет уровень, относительно которого истинно высказывание, что
Рыночный тип экономики — прогрессивный.
При этом множество истинностных значений меняется с классического, состоящего из 1 (абсолютно истинно) и 0 (абсолютно ложно) на неклассическое — интервал [0,1], отражающий неточность, или, как ещё говорят; нечёткость признака «прогрессивный». Во всех случаях, когда нужно выразить это понятие меры истинности, значения w{A) называются значениями истинности.
Во втором распространённом подходе w(A) обозначает мнение агента а об истинности А, или его уверенность в А. Здесь подразумевается, что А на самом деле истинно или ложно, но каково оно в действительности, а. не знает, а только предполагает. Отсюда, во всех случаях, когда нужно выразить это понятие уверенности, значения w(A) называются значениями мнения.
Разумеется, допущение истинностной функциональности не ограничивается только этими трактовками, существует множество иных подходов. Тем не менее в этой главе, равно как и в данной работе в целом, мы ограничимся только этими двумя. Далее мы рассмотрим различные типы семантик, предложенные в литературе, и которые уместны этих рамках. Важно также подчеркнуть тот факт, что это часто будет требовать переинтерпретирования оригинальных авторских идей для встраивания их в наши жёсткие рамки, что возможно не входило в намерения авторов, поэтому мы снабжаем читателя необходимыми ссылками на оригинальные работы.
16
§1 Семантика голосования
Семантика голосования была описана в [70]. Идея этой семантики состоит в том, что истинностные значения, присваевыемые агентом а, суммируют предпочтения большой группы (возможно воображаемых) избирателей. Точнее, предположим, что агент имеет доступ к некоторому множеству М избирателей, каждый из которых с необходимостью должен проголосовать однозначно «за» или «против» утверждений вида «А истинно».
В этом случае функция wa может быть определена как
wa{A) = \{v G М : v{A) = 1}| ¦ \М\
-1
где v(A) = 1 (v(A) = 0) обозначает «v голосует за утверждение (соответственно, против утверждения), что А истинно».
Это толкование истинностного значения, которое агент ее присваивает высказыванию А, выглядит привлекательно и, более того, может быть с успехом применено на практике. Например, а может собрать (или лишь представить) 100 человек и попросить каждого из них выразить своё согласие или несогласие с тем, что рыночный тип экономики — прогрессивный; доля ответивших согласием будет взята в качестве истинностного значения этого утверждения.
В частности, если ответы избирателей совместны в том смысле, что для любого из них, например, v, верно
0, (1.4)
v(A Л В) = 1 ф=ф v(A) = 1 и v(B) = 1, (1.5)
v{A\JB) = \ <^> v(A) = 1 или v{B) = 1, (1.6)
тогда wa является просто вероятностной функцией (т.е. функцией, вычисляющей вероятность, с которой произвольный избиратель проголосует «за»). Это означает, что wa удовлетворяет условиям определения вероятностной функции w : Form —у [0,1] для А,В€ Form (см. [70], стр.
17 |
