Н.К.Косовский
УРОВНЕВЫЕ ЛОГИКИ
(результаты доложены 6 июня 1994 г.)
Статья посвящена описанию уровневых логик, изучению их общих на-
чальных свойств и изложению их естественных приложений.
Длительное влияние моего научного руководителя дипломной работы
и кандидатской диссертации Н.А.Шанина, значительный период своей жиз-
ни занимавшегося углублением финитарного понимания математических ут-
верждений, придало мне смелость ввести в этой статье оценочно уровне-
вую интерпретацию утверждений самого различного вида. В наше время
трудно удивить кого-либо ещё одной логикой или целым классом логик.
Тем не менее класс логик, описываемых в настоящей статье, является
весьма полезным как в традиционных областях применения классической
логики, так и в новых облястях применения нечётких (непрерывных) ло-
гик, восходящих к Р.Мак-Нотону [1] и Л.Заде [2]. Предлагаемые логики
позволяют получать те же результаты в математической психологии отно-
сительно сознания человека, что и гамма-алгебра Левефра, введённая
для моделирования подсознательных (интуитивных) процессов мышления
человека [3], [4].
Можно ввести операцию объединения конечного числа уровневых ло-
гик, результат которой будет опять уровневой логикой. Результат тако-
го объединения будет содержать в себе в качестве подструктуры каждую
логику, являющуюся членом этого объединения. В частности поэтому в
настоящей статье выдвигается предположение, что каждый человек при
честном убеждении других в своей правоте использует одну из уровневых
логик. При этом чем более разнообразны люди, которых ему приходится
убеждать, тем обширнее множество логических значений, которое он ис-
пользует.
Парадоксальное логическое значение в уровневой логике имеют лю-
бые парадоксы, например, парадокс лжеца.
В уровневой логике кроме материальной импликации может использо-
ваться уровневая импликация, т.е. естественное линейное упорядочение
логических значений. Тогда правило, что из лжи следует всё что угод-
но, превращается в правило, что из лжи следует ложь такого же или ме-
ньшего уровня, а также парадоксальные утверждения и истинные утверж-
дения. Отмечаем, что парадоксальное значение отличается от ложного.
За последний век было предложено значительное количество самых
разнообразных логик. Многие из них имеют только чисто теоретическое
или математическое значение. В большинстве случаев обучение математи-
ческой логике лиц, не специализирующихся в этой области, ограничива-
ется классической двузначной логикой, являющейся простейшей уровневой
логикой без парадоксального значения. Логика Лукасевича, многозначные
логики Поста и логика Гетмановой являются слегка изменёнными уровне-
выми логиками (см., например, [5]).
Уровневую логику удобно применять при анализе аксиоматических
систем, присвоив сериям аксиом или схемам аксиом разных уровней дос-
товерности (истинности). Тогда в рамках одного исчисления можно со-
единить несколько классических исчислений, например, геометрию без
знаменитой аксиомы о параллельных с традиционной геометрией. Эти два
классических исчисления выделяются на основе неотрицательных оценок
уровней утверждений (обычная геометрия) и максимальной положительной
оценке уровня утверждений (геометрия без аксиомы о параллельных).
Аналогичным образом можно использовать различные оценки для пос-
тулатов различных наук, соединив несколько наук в единую систему. По-
скольку из ложного утверждения следует, согласно уровневой имплика-
ции, любое утверждение, оценка (или уровень) которого больше, то оце-
нки постулатов различных наук можно расположить по частоте изменяемо-
сти их постулатов. Например, можно предложить, чтобы логические зна-
чения у постулатов наук возрастали бы в следующей последовательности:
социология, психология, философия, другие гуманитарные науки, естест-
венные науки, начинающиеся биологией и заканчивающиеся химией, физи-
кой, математикой и, наконец, математической логикой.
Уровневая логика может использовать все рациональные числа из
замкнутого симметричного относительно нуля множества рациональных чи-
сел (но наибольший интерес, по мнению автора, представляет уровневая
логика, в которой используются все рациональные числа). Такое множе-
ство рациональных чисел назовём множеством логических значений уров-
невой логики. Для многих приложений непрерывной логики [6] этого впо-
лне достаточно.
Атомарная формула представляет собой логическую константу или
пропозициональную переменную с индексами. Среди этих индексов могут
быть термы, построенные обычным образом из имён объектов предметной
области, из переменных для них (предметных переменных) и различных
функторов для функций над этой предметной областью.
Логические значения конъюнкции и дизъюнкции вычисляются соответ-
ственно посредством вычисления минимума и максимума логических значе-
ний аргументов. Операция отрицания Лукасевича соответствует одномест-
ному минусу. Материальная импликация (X=>Y) имеет логическое значение
МАХ(-[X],[Y]), где [X], [Y] - логические значения X и Y соответствен-
но. Материальная импликация истинна тогда и только тогда, когда посы-
лка ложна или заключение истинно. Традиционным образом можно опреде-
лить и эквивалентность.
Кванторы являются обобщением коньюнкции и дизъюнкции. Логическое
значение выражения (cущ)x А равно супремуму логических значений А при
всех х. Логическое значение выражения (люб)х А равно инфимуму логиче-
ских значений А при всех х.
Все логические значения, большие нуля, являются истинными или
достоверными (большей или меньшей степени (или уровня) достовернос-
ти). Все логические значения, меньшие нуля, являются ложными. Логиче-
ское значение, равное нулю, называется парадоксальным. В логике Гет-
мановой парадоксальным значением является 1/2. Соответственно истин-
ными являются значения, большие 1/2, а ложными - значения, меньшие
1/2. При этом логическое значение отрицания вычисляется по более сло-
жной формуле.
Представляют интерес предикаты, которые могут быть более или
менее достоверными. Примером такого предиката может служить двумест-
ный предикат "больше" (логическое значение равно разности его аргуме-
нтов).
Под секвенцией понимаем последовательность правильно построенных
формул, разделённых стрелкой (знаком секвенции).
Аксиомы имеют следующий вид:
Г1 Р Г2 -> Г3 Р Г4 ,
Г1 -> Г2 Е Г3 ,
Г1 -Е Г2 -> Г3 ,
где Г1, Г2, Г3, Г4 - конечные (быть может пустые) списки формул, Р -
формула, Е - неотрицательное число (логическая константа).
Правила вывода для логических связок и кванторов определяются
как в традиционном исчислении предкатов с обратимыми правилами введе-
ния логических связок как в антецедент, так и в сукцедент секвенции
(для кванторов тоже можно использовать обратимые правила введения их
как в антецедент, так и в сукцедент). Дополнительно используется тра-
диционное правило сокращения повторения (см, например, [7]).
Понятие вывода, выводимой секвенции, выводимой формулы определя-
ются как обычно.
Легко доказываются следующие теоремы.
ТЕОРЕМА 1. Во всякой уровневой логике аксиомы не являются ложны-
ми. Во всякой уровневой логике заключения правил не являются ложными,
если посылки этих правил не являются ложными.
ТЕОРЕМА 2. Всякая пропозициональная формула, логическое значение
которой в любой уровневой логике не меньше нуля, выводима в этом ис-
числении.
ТЕОРЕМА 3. Всякая пропозициональная формула без логических конс-
тант, не являющаяся ложной ни в какой уровневой логике, является вы-
водимой тогда и только тогда, когда она является тавтологией класси-
ческого исчисления высказываний.
ТЕОРЕМА 4. Нет пропозициональных формул без логических констант,
являющихся истинными хоть в одной уровневой логике, имеющей парадо-
ксальную константу.
Если ограничиться следующим базисом: (МАХ, -(одноместный), sup),
то достаточно следующих аксиом и правил вывода для пропозиционального
исчисления.
Аксиомы:
МАХ(Г,Е) >= Е ,
МАХ(Г1,А,Г2,-А) >= |[А]| >= 0 .
Правила рефлексивности и транзитивности нестрогого неравенства,
перестановки и снятия двойного минуса:
МАХ(Г,-Х) >= Н
МАХ(Г,X,Y) >= Н МАХ(Г,-Y) >= Н
-------------------- ---------------------
МАХ(Г,МАХ(X,Y)) >= Н МАХ(Г,-МАХ(X,Y)) >= H
Для предикатного исчисления достаточно добавить правило сокраще-
ния повторения и два правила с традиционными ограничениями на формулу
А, переменные Х, В и терм Т:
X X
МАХ(Г,[A] ) >= Н МАХ(Г,-[A] ) >= Н
T T
------------------ -------------------
МАХ(Г, sup A) >= Н МАХ(Г, -sup A) >= Н
X Х
Отметим, что правила предикатного исчисления ранее не предлага-
лись для уровневых логик, отличных от классической двузначной логики.
Используемую сигнатуру можно расширять, например, за счёт введе-
ния не рассматривавшегося ранее в уровневых логиках уровневого услов-
ного выражения следующего вида:
(if [A] >= 0 then B else C).
Это выражение, по мнению автора, более удобно записывать в виде
(-- А ; В -- С --).
Логическое значение выражения (-- А ; В -- С --) совпадает с В,
если А >= 0 и совпадает с С, если А < 0. При многократном использова-
нии уровневого условного предложения
(-- А1 ; В1 -- (-- А2 ; В2 --(-- ...(--Аn ; Bn -- C)-- ...--)--)--)
внутренние круглые скобки вместе с двумя минусами у каждой скобки мо-
жно опустить. В результате получится выражение
(-- Ai ; Bi -- A2 ; B2 --...--An ; Bn -- C --).
Секвенциальные правила для уровневого условного предложения бу-
дут существенно сложнее. Для получения заключения
МАХ(Г, (-- А ; В -- С --)) >= Е
необходимы следующие три посылки:
МАХ(Г,В,С) >= Е ,
[A] >= 0 or MAX(Г,С) >= Е ,
-[A] > 0 or MAX(Г,В) >= Е .
В связи с этим все предшествующие правила необходимо будет про-
дублировать для строгого неравенства, добавив правило
Е > Н
------------
МАХ(Г,Е) > Н
и аксиомы вида Г(Е>Н) и Г(Е>=Н) для тех рациональных констант Е и Н,
для которых строгое неравенство имеет место. Здесь Г - конечный спи-
сок неравенств, возможно пустой. При этом теперь любая секвенция рас-
ширяется до дизъюнкции строгих и нестрогих неравенств.
Для уровневого условного выражения с минусом достаточно однопо-
сылочного правила
МАХ(Г, (-- А ; (-В) -- (-С) --)) >= Е
-------------------------------------
МАХ(Г, -(-- А ; В -- С --)) >= Е
Возможно дальнейшее расширение сигнатуры уровневой логики с по-
мощью введения уровневой импликации от А к В, логическое значение ко-
торой совпадает с -[A] + [B], поэтому для неё не будет специально
вводиться новый символ.
Алгорифм установления выводимости пропозициональных формул на
основе секвенциального исчисления с обратимыми правилами (см., напри-
мер, [ ]) принадлежит некоторому классу функций из ЕХР-LIN-TIME, т.е.
вычислим при некотором С за 2^(C*k) шагов, где k - длина пропозицио-
нальной формулы, детерминированной машиной Тьюринга. В рамках того же
класса функций можно получить алгорифм установления выводимости про-
позициональных формул в расширенной сигнатуре уровневой логики. Более
точно, устанавливается следующая теорема.
ТЕОРЕМА 5. Универсальная элементарная теория строгих и нестрогих
неравенств с рациональными коэффициентами над рациональными числами
разрешима алгорифмом из класса ЕХР-LIN-TIME.
Доказательство. Секвенция представляет собой последовательность
строгих и нестрогих неравенств. По-прежнему имеет место правило пере-
становки членов секвенции, изменения знака неравенства при умножении
на -1. Разрешаются обычные правила переноса слагаемых в линейных не-
равенствах и приведение подобных членов.
Поскольку выражение МАХ(Г) >= 0 можно представлять себе как сек-
венцию формул вида "член последовательности Г больше или равен нуля",
то все сформулированные в этой статье правила и аксиомы по существу
сохраняются. Добавляются аксиомы вида Г(А <= Е1)(А > Е2) и вида
Г(А<=Е1)(А>Е2), где А - линейное выражение, Е1 и Е2 - рациональные
числа такие, что Е2 <= Е1.
Дополнительные аксиомы, кроме этих двух, ввести потребуется, по-
скольку из геометрических соображений ясно, что многомерные полупро-
странства будут давать в объединении всё пространство, только если
будет выполнено следующее.
Если секвенция содержит нестрогие неравенства, то следует прове-
рить, не является ли она аксиомой первых двух добавленных типов с то-
чностью до перестановки. В противном случае, если секвенция с точнос-
тью до перестановки имеет вид Г(АE1), то выражаем одну пере-
менную через другие в уравнении А=Е1 и подставляем вместо неё полу-
ченное выражение во все члены секвенции. Этот процесс подстановки по-
вторяем, пока имеются члены секвенции вида (АE). Тавтологич-
ность так полученной секвенции эквивалентна тавтологичности прежней.
Если наша секвенция всё же не имеет ни одного из перечисленных
видов, то её тавтологичность эквивалентна тавтологичности секвенции,
полученной заменой всех нестрогих неравенств на строгие.
Если секвенция содержит только строгие неравенства, то она явля-
ется дополнительной аксиомой тогда и только тогда, когда это может
быть установлено с помощью методов решения задачи линейного програм-
мирования, ибо отрицание дизъюнкции строгих линейных неравенств будет
системой нестрогих линейных неравенств.
По существу, здесь описан алгорифм проверки тавтологичности на
рациональных числах систем нестрогих и строгих линейных неравенств с
целочисленными коэффициентами. Дело в том, что система линейных нера-
венств с некоторыми строгими неравенствами может содержать меньшее
число решений по сравнению с системой с теми же неравенствами, но за-
менёнными на нестрогие. Только на границах множества решений могут
отличаться. Границы же проверяются дополнительными аксиомами первых
двух типов.
Классические конъюнкции, в том числе и находящиеся под отрицани-
ем, вводятся согласно традиционным обратимым секвенциальным правилам
отрицания атомарных формул, являющихся неравенствами, получаемыми с
помощью замены знаков неравенства.
Таким образом можно получить следующую дедуктивную систему.
Аксиомами являются такие секвенции, которые являются последова-
тельностями строгих или нестрогих линейных неравенств, система из от-
рицаний которых не имеет решений в рациональных числах.
Распознавание этих аксиом может быть осуществлено методами ли-
нейного программирования.
Правилами вывода являются правила перестановки членов секвенции,
перестановки слагаемых и добавления нулевых слагаемых в линейных вы-
ражениях, приведения подобных членов, снятия двойного минуса, измене-
ния знака неравенства при умножении на (-1) обеих частей неравенства.
Кроме этого, для максимума вводится правило
Г(Р+А >= 0)(Р+В > 0)
--------------------
Г(Р+МАХ(А,В) >= 0)
и такое же правило - для строгого неравенства, а также
Г(Р+А >= 0)
Г(Р+В >= 0)
--------------------
Г(Р-МАХ(А,В) >= 0)
и такое же правило - для строгого неравенства.
Для уровневого условного выражения достаточно следующих правил:
Г(Р+В >= 0)(Р+С >= 0) Г(Р+В > 0)(Р+С > 0)
Г(А >= 0)(С >= 0) Г(А >= 0)(С > 0)
Г(-А > 0)(В >= 0) Г(-А > 0)(В > 0)
----------------------------- ----------------------------
Г(Р+(-- А ; В -- С --)) >= 0) Г(Р+(-- А ; В -- С --)) > 0)
и правила
Г(Р+(-- А ; (-В) -- (-С) --) >= 0)
----------------------------------
Г(Р+-(-- А ; В -- С --) >= 0)
и такое же правило - для строгого неравенства.
Все эти правила являются обратимыми, что существенно упрощает
поиск вывода. (В это исчисление могут быть введены и предикатные пра-
вила, как это уже было сделано выше.)
ТЕОРЕМА 6. Алгорифм установления выводимости в этом исчислении
принадлежит классу EXP-LIN-TIME.
Описанный алгорифм установления выводимости формул рассматрива-
емого исчисления принадлежит требуемому классу, поскольку имеет
структуру, в общем совпадающую с традиционным алгорифмом установле-
ния выводимости пропозициональных формул в секвенциальном пропозици-
ональном исчислении с обратными правилами.
Отметим, что если в уровневой логике ограничиться конечным чис-
лом логических значений, то появится больше тавтологичных пропози-
циональных формул, чем в предложенной системе. При этом, чем меньше
число логических значений, тем больше появляется новых тавтологичных
пропозициональных формул в расширенной логике.
Например, в двузначной логике тавтологична следующая формула:
MIN(|-X1+X2|, |-X2+X3|, |-X3+X1|) <= 0
( Напомним, что |X| ~ MAX(X,-X) ). При увеличении числа логических
значений та формула, конечно, будет опровержима.
Возможно расширение множества значений уровневой логики до мно-
жества всех вещественных чисел, производимое в рамках конструктивного
направления в математике. В этом случае вещественное число задаётся
полиномом с целыми коэффициентами и интервалом, для которого, соглас-
но теореме Штурма, выполняется критерий единственности вещественого
корня на этом интервале. Так задаваемые вещественные числа можно
складывать, вычитать и, что более существенно, проверять на равен-
ство их друг с другом с помощью алгорифмов. Предлагаемое расширение
конструктивно, в то время как дальнейшее расширение до непрерывной
логики [6] не является таковым.
В этом случае возможно применение такого расширения уровневой
логики в геометрических задачах на прямой, на плоскости, в простран-
стве и т.д.
Возможно дальнейшее расширение множества алгебраических чисел до
такого множества конструктивных вещественных чисел (FR-конструктов),
для которого дополнительно имеется алгорифм проверки нестрогого нера-
венства между любыми двумя числами из этого множества. Такой алгорифм
позволит решать линейные уравнения обычным для традиционной математи-
ки способом.
Логическое значение одноместного предиката принадлежности точки
лучу на прямой может иметь значение вида Х-Х0, где Х0 - координата
вершины луча, Х - координата точки, являющейся аргументом.
Логическое значение одноместного предиката принадлежности точки
отрезку [X0,Y0] на прямой имеет логическое значение вида MIN(X-X0,
X-Y0), где Х - координата точки, являющейся аргументом.
Логическое значение одноместного предиката принадлежности точки
с координатами (X,Y) какой-либо геометрической фигуре на плоскости
может задаваться минимумом расстояния до границы, взятого со знаком
"+", если точка находится внутри фигуры, и взятого со знаком "-",
если точка находится вне этой фигуры. Согласно известной теореме из
геометрии, непрерывная замкнутая линия делит плоскость на две части:
внутреннюю и внешнюю.
Аналогичное определение можно ввести и для принадлежности точки
телу в пространстве.
Тем самым удаётся точно формализовать деление некоторых утверж-
дений на более и менее истинные.
Основные идеи настоящей работы докладывались на секции логики
тысячного заседания семинара "Алгебра и логика" в Новосибирске 3 мар-
та 1994 г.