автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.17, диссертация на тему:Алгоритмы выводимости в рациональнозначных логиках для представления знаний

Введение.

ГЛАВА 1. Бескванторные (универсальные) теории линейных неравенств

§1.1 Полиномиальные алгоритмы проверки совместности в рациональных и целых числах систем строгих и нестрогих линейных неравенств.

§1.2 Определение бескванторных (универсальных) теорий линейных неравенств

§1.3 Построение секвенциальных исчислений для двух бескванторных теорий линейных неравенств.

§1.4 Специфические правила вывода в^ис^щ^рениях ИС^ и Ц^.

§1.5 Бескванторные теории и

§1.6 Бескванторные теории и ш;.зз

§1.7 Добавление сортов для конечных множеств.

§1.8 Выполнимость формул в теориях линейных неравенств.

ГЛАВА 2. Плюралистическая логика и смешанные логики Поста и Лукасевича

§2.1 Введение

§2.2 Внутренняя сигнатура.

§2.3 Предикатные формулы.

§2.4 Интерпретация формул

§2.5 Вложение рассматриваемых логик в двузначную

§2.6 Секвенциальные исчисления для вводимых логик.

§2.7 Правила вывода для внутренних формул

Работа посвящена изучению свойств выводов в логиках, впервые введенных в 1995 году Н.К. Косовским [9] и задуманных как как новые логики для представления многоагентных экспертных знаний. В начальный период накопления многоагентных экспертных знаний описание многих областей исследования начинается с лингвистического освоения полученных результатов. Вслед за этим наступает период накопления знаний лингвистического характера. В конце концов выясняется противоречивость некоторых сведений, которую в это время не удается устранить: традиционная двузначная логика может оказаться неприменимой, поскольку в ней из противоречия следует все что угодно. При пополнении или изменении базы многоагентных экспертных знаний также существуют такие моменты времени, когда в ней находятся неполные или противоречивые знания. Именно на этих стадиях функционирования базы многоагентных экспертных знаний могут стать полезными логики конечнозначных предикатов, представленные в настоящей работе. Особенно это относится к плюралистической логике, так как она позволяют оперировать с противоречиями различной силы, например, один "за" и один "против", или десять "за" и десять "против", или сто "за" и сто "против".

При изучении любой новой области используются и знания из других областей, устоявшиеся в различной степени, которым удобно придавать дополнительные логические значения. Поскольку новые логические- значения приходится вводить не ограниченное заранее число раз, нецелесообразно применять широко известные традиционные логики, например конечнозначные логики Поста [39], а лучше пользоваться предлагаемой смешанной логикой Поста [11], имеющей, в частности, неограниченное число сортов переменных для любой конечнозначной логики Поста. Более устоявшиеся истинные значения предикатов будут иметь большие величины логических зна5 чений. Впрочем, такую логику рациональнее использовать для описания неполных баз экспертных знаний. Для описания не только неполных, но и противоречивых баз знаний более предпочтительны как плюралистическая, так и эвристическая логики, являющиеся расширениями смешанной логики Поста.

Разработанный аппарат позволяет ввести и рассмотреть смешанную логику Лу-касевича. Однако, введение в этой логике дополнительной особой импликации существенно усложняет секвенциальное исчисление и вряд ли крайне необходимо при записи результатов начальных исследований во многих областях.

В диссертации рассмотрены логики с разными областями значений предикатов: рациональные числа и их подмножества: симметричный конечный набор рациональных чисел из промежутка, множества {—1,1} и {—1,0,1}, а также варианты, когда в одной формуле содержатся предикаты с логическими значениями из разных множеств. Введены многозначные предикатные формулы, и, что является новой идеей, в язык введена возможность сравнения значений предикатных формул. Для этого над многозначными формулами надстроена двузначная логика сравнений, в которой формулы являются неравенствами в обычном их понимании. Одним из первых докладов по такой логической системе был сделан на Первом Российском Философском конгрессе в 1997 году [12]. Далее в эти логики введена и многоагентность, когда значением предиката является кортеж чисел фиксированной размерности.

История логик, являющихся предшественниками вводимых в диссертации, начинается с 20-х годов нашего века, когда появились логики Поста [39]. Эти многозначные логики определялись на наборах целых чисел. Затем появилась логика Лукасевича Ьк0 (см. [26, 35]), ее значениями были все рациональные числа из отрезка [0,1]. Но до второй половины нашего столетия все еще были сомнения являются ли многозначные логики полезным для практики оформления научных исследований направлением или это всего лишь интересное чисто математическое упражнение для ума. В 60-х годах появилась нечеткая логика Заде [42], которая нашла широкое применение начиная с 6

70-х годов, когда появились первые базы знаний в экспертных системах. Нечеткость удалось формализовать за счет обобщения связи между объектом и его характеристикой, введения функции принадлежности, действующей на множество вещественных чисел из отрезка [0,1]. Появилась возможность формально выразить степень обладания объекта некоторым свойством. (Моделирование нечетких утверждений при помощи рассматриваемых в диссертации логик опубликовано в [32]). Затем в 1991 году Л.И. Волгин и В.И. Левин [3, 4] предложили непрерывные логики, также многозначные, определенные на вещественном отрезке.

Рассматриваемые в диссертации логики также позволяют учитывать нечеткость. Но в них есть несомненные удобства, которыми не обладают предшествующие системы. Используются рациональные числа, которые более удобно представлять в памяти компьютера, чем вещественные. Более того, предикаты могут принадлежать лишь конечным сортам, чего на практике оказывается вполне достаточно. В то же время использование вещественных чисел в логиках затруднено с онтологической точки зрения, поскольку они сами нуждаются в логическом обосновании. Кроме того, вещественные числа точно непредставимы в компьютере.

Один из вариантов плюралистической логики, плюралистическая логика двухмерных кортежей, является также обобщением четырехзначной логики с логическими константами "истина", "ложь", "неизвестно" и "противоречиво" [2]. При этом необходимо пользоваться специальным видом отрицания, как комбинации двух логических связок. Такая логика более удобна для исследовательских изменяемых баз экспертных знаний, (включая неполные и противоречивые знания), чем паранепротиворечи-вые логики [28].

По-видимому, впервые в 1960 г. В.И. Шестаков [24] использует отрицательную константу (—1) для интерпретации логической константы "ложь". В исчислении рассматриваются три константы "истина", "ложь" и "не определено". Указывается на возможность преобразования такого трехзначного исчисления высказываний в любое 7 с-значное исчисление, где к > 3 и значения симметричны относительно нуля (с. 343). Результат такого преобразования даже для бесконечной логики предложил независимо Чанг [27] в 1963 г.

Изучение многозначных логик Поста с точки зрения алгебры и теоретической кибернетики отражено в учебных пособиях А.И. Мальцева [17] и C.B. Яблонского [25], включающих, в частности, некоторые результаты исследований A.A. Мучника и Ю.И. Янова [18].

Статья [41] рассматривает логику, использующую значения "истина", "ложь" и "не определено". Эта логика почти совпадает с трехзначной смешанной логикой Лукасевича.

Другая трехзначная логика, со значениями "истина", "ложь" и "совсем неизвестно", предлагается в работе [37].

В книге С. А. Гинзбурга [5], излагается бесконечнозначная или непрерывная логика для приложений в автоматике, например для анализа некоторых нелинейных электрических цепей. Автор считает, что значение истинности не может быть иррациональным числом (с. 5). В то же время на с. 8 в качестве основы дальнейшего изложения для логических значений рассматривается сегмент вещественных чисел, использованный П.С. Новиковым как пример булевой алгебры [19]. На с. 15 уточняется, что, как правило, в дальнейшем речь будет идти о симметричном относительно нуля сегменте.

Тесно связана с вероятностной логикой логика антонимов, которая для интерпретации логических значений вместо линейной функции использует обратную функцию, степень двух и двоичный логарифм [30], что может существенно усложнить вычисления.

Содержание работы. Глава 1 служит идейной основой доказательств теорем в последующих главах. Она содержит основной математический аппарат для доказательства теорем и посвящена общим формулировкам, связанным с бесквантор8 ными, обычно называемыми универсальными, теориями линейных неравенств. Последние являются подтеориями элементарной теории линейного порядка, для которой А.Р. Мейером [36] (см. также [20]) доказана неэлементарная цо Кальмару нижняя оценка для теории линейно упорядоченных множеств (на основе аксиом \/ху{х < у У у < х) и Ух yz(x z)).

Неравенства рассматриваются для предикатных формул с многосортными переменными. Для каждого сорта будет использоваться своя бесконечная серия предметных переменных с номерами, но все сорта переменных будут включены в самый первый, на котором и задаются все функции и предикаты сигнатуры. Часть результатов, представленных в этой главе имеется в публикациях [13, 10, 14, 16], а также [33].

Бескванторной (универсальной) теорией в сигнатуре S, обозначаемой UTh(S), будем называть множество бескванторных предикатных формул, для которых истинна интерпретация их замыканий по всеобщности, т. е. результатов вставки перед ними кванторов всеобщности по всем предметным переменным, входящим свободно в эти формулы. Предикатные формулы строятся обычным образом с использованием функций, предикатов, констант из сигнатуры S с переменными для носителей, определенных в сигнатуре S.

В первой главе рассматриваются следующие универсальные теории линейных неравенств.

1. Теория супер линейных неравенств UQ:

UTh(Q; |Q,\{Хх.с ■ х + с0 : с <Е Q}, A®.abs(a;), Xab.a + Ь, Xab. max(a, b), Xabc.ií 0 < a then b else с fi, Aa.(0 < a)), где Q — множество всех рациональных чисел, числитель и знаменатель которых записан в позиционной системе счисления; |Q — перечень всех рациональных чисел; |{Ах.с ■ х + с0 : с £ Q} — перечень всех одноместных линейных функций; abs— функция вычисления абсолютной величины; +,тах — двухместные функ9 ции. Имеется трехместная функция для записи условных выражений. Последним в сигнатуре UQ записан одноместный предикат неотрицательности аргумента.

2. Целочисленная теория супер линейных неравенств UZ. Сигнатура UZ отличается от сигнатуры UQ тем, что первая строчка заменяется на следующую:

UTh(Z; |Z, |{Аж.с • х + с0 : с £ Z}, A.x.abs(a;), где Z — множество всех целых чисел.

3. Теория UZ2, отсутствует многократное сложение, коэффициенты при переменных равны ±1:

UTh(Z; |Z, А а. — а, Аж.аЬз(ж), Xab. тах(а, 6), Xabc.ií 0 < a then b else с fi, Ла.(0 < а), \ab.(0 < а + Ь)).

4. Теория UQ — расширение UQ на кортежи из п элементов:

UTh(Qn; |Qn, |{Ах.с ■ х + с0 : с G Q}, Ax.abs(a;),

Хх. \ ж, Xab.a + 6, Xab. max(a, b), Xabc.ií 0 < a then b else с fi, Aa.(0 < a)),

5. Теория UZ -- расширение UZ на кортежи из n элементов:

UTh(Zn; |Zn, |{Aх.с • ж + c0 : с G Q}, Аж.аЬв(ж),

Хх. \ х, Xab.a + b, Xab. max(a, b), Xabc.ií 0 < a then b else с fi, Aa.(0 < a)),

6. Теория UZ

2 •

UTh(Zn; |Zn, Хх. \ x, Xa. — a, Аж.аЬз(ж), Xab.a + b, Xab. max(a, 6),

Xabc.ii 0 < a then b else с fi, Aa.(0 < a), Xab.(0 < a + b)).

Для всех указанных теорий строятся исчисления для чистых секвенций. Исчисления обладают свойством обратимости всех правил, которое облегчает поиск вывода.

10

В этой же главе доказаны следующие теоремы о сложности вывода в этих исчислениях. Все теории, для которых существуют полиномиальные алгоритмы распознавания аксиом, разрешимы алгоритмом из класса ВТ1МЕ(2Сп1°ё?г). Для теорий 11(5 и ЦСГ можно воспользоваться, например, алгоритмом Хачияна, для теорий и Шп2 алгоритм разработан автором. Используя секвенциальные алгоритмы разрешимости и опираясь на оценки длины записи решений задачи целочисленного линейного программирования, можно дать и верхние оценки для теорий ХЗЪ и \}Ъп. Но такая оценка превысит экспоненту в степени полином четвертой степени, что является неприемлемым для практических целей. Поэтому, без уточнения оценок, в диссертации указывается, что такие алгоритмы ИР-трудны и принадлежат классу РЗРАС'Е. В рассматриваемых в последующих главах логиках эти теории не используются.

Для теории линейных неравенств и теории ПС^, содержащей не более двух слагаемых в неравенстве, удается понизить верхнюю оценку сложности вывода до 2Сп если в каждом неравенстве используется не более одной переменной (второе слагаемое, или оба слагаемых являются константами, или в неравенства только одно слагаемое).

Доказана теорема о том, что добавление сортов, то есть конечных носителей, не повысит верхних оценок сложности вывода во всех теориях.

В заключение главы доказана Л^Р-полнота задачи выполнимости всех рассматриваемых теорий линейных неравенств.

В главе 2 представлены три логики: плюралистическая логика, смешанная логика Поста и смешанная логика Лукасевича. Глава содержит необходимые определения и построение секвенциальных исчислений для чистых секвенций, а также теоремы о семантической обоснованности исчислений.

Плюралистическая логика основана на теории ТЩ™, но содержит лишь не более двух слагаемых в неравенстве. Особую семантику имеет ее подлогика — эвристическая логика, в которой кортежи содержат по два элемента. В эвристической

11 логике первым элементом можно считать основное мнение, вторым — мнение оппозиции. Подлогика плюралистической логики — эвристическая логика — рассмотрена в публикации [15].

Смешанная логика Лукасевича основана на теории Это единственная из рассматриваемых логик, в которой формулы могут содержать более двух слагаемых.

Наконец, смешанная логика Поста является самой простой для реализации. В ней содержится наименьшее количество логических связок из рассмотренных логик и алгоритм распознавания аксиом для нее самый простой. Каждое неравенство многозначных предикатных формул содержит не более двух предикатных формул и фактически, как и в плюралистической логике, призвано сравнить две предикатные формулы.

Глава 3 посвящена изучению свойств введенных логик. Формулируются и доказываются теоремы о возможности перестройки любого вывода в вывод с чистыми переменными (напомним, в исчислениях рассматриваются только чистые выводы), о допустимости некоторых правил, верхние оценки сложности выводов, связь с классической логикой.

В первом параграфе доказана допустимость правила добавления, правила сокращения повторения, правила подстановки и обратных правил. Доказано, что все эти правила являются неудлиняющими, что позволило пользоваться ими в дальнейшем при доказательствах методом возвратной математической индукции.

Второй параграф посвящен сложению неравенств. Привычный для взгляда математика результат сложения двух неравенств в которых присутствует одна и та же переменная, но с противоположным знаком, для рассматриваемых логик оказывается аналогом важнейшей теоремы об устранении сечения в двузначной логике.

Следующие правила допустимы в плюралистической логике, смешанной логике Поста и смешанной логике Лукасевича.

ДДО <А + В) д2(0 < С + ~>В)

Д!Д2(0 < А + С)

1. А х о А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М.: Мир, 1978. 536 с.

2. Б е л н а п Н., С т и л Т. Логика вопросов и ответов. М.: Прогресс, 1981. 288 с.

3. Во лгинЛ.И., Л евинВ.И. Непрерывные логики, теория и применение. Таллинн, 1991. 210 с.

4. ВолгинЛ.И. Непрерывная логика и ее схемотехнические применения: 5 лекций по курсу "Логические основы и модели нейронных сетей". Ульяновск: УлГТУ, 1996. 107 с.

5. Г и н з б у р г С. А. Математическая непрерывная логика и изображение функций: Библиотека по автоматике. Вып. 274. М.: Энергия, 1968. 136 с.

6. ГэриМ., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982. 416 с.

7. К л и н и С. К. Введение в метаматематику. М.: Иностранная литература, 1957. 526 с.

8. К о с о в с к и й Н. К. Элементы математической логики и ее приложения к теории субрекурсивных алгоритмов. Л.: Изд-во Ленингр. гос. ун-та, 1981. 192 с.

9. Косовский Н. К. Уровневые логики// Записки науч. семинаров Петербург, отд. Мат. ин-та РАН. Т. 220. 1995. С. 72-82.

10. К о с о в с к и й Н. К. Полиномиальные алгоритмы для разрешимости некоторых систем линейных неравенств// Дискретный анализ и исследование операций. Т. 2, N3. Новосибирск: Ин-т математики, 1995. С. 76.100

11. КосовскийН.К, ТишковА. В. Естественное упорядочение значений утверждений логики Поста// Современная логика: проблемы теории, истории и применения в науке. СПб: Изд-во С.-Петербург, гос. ун-та, 1996. С. 30-32.

12. К о с о в с к и й Н. К., Т и ш к о в А. В. Две логические теории сравнений// Тезисы Первого Российского Философского Конгресса. Т. 3. СПб: Изд-во С.-Петербург, гос. ун-та, 1997. С. 191-194.

13. К о с о в с к и й Н. К., Т и ш к о в А. В. Градуируемые логические значения для представления знаний// Исследования по конструктивной математике и математической логике X. Записки научных семинаров ПОМИ. Т. 241. 1997. С. 135-149.

14. К о с о в с к и й Н. К., Т и ш к о в А. В. Секвенциальное исчисление для сравнения условий различной степени достоверности// Мат. вопр. кибернетики. Вып. 7. 1998. М.: Наука, Физматлит. С. 213-226.

15. К о с о в с к и й Н. К., Т и ш к о в А. В. О сложности некоторых бескванторных теорий// Материалы IX межгосударственной школы-семинар а "Синтез и сложность управляющих систем" , декабрь 1998. М.: Изд-во мех.-мат. ф-та МГУ. 1999. С. 44.

16. М а л ь ц е в А. И. Итеративные алгебры Поста. Новосибирск: Изд-во Новосибирского гос. ун-та, 1976. 100 с.

17. М у ч н и к А. А., Янов Ю. И. О существовании fc-значных замкнутых классов,не имеющих конечного базиса// Докл. АН СССР, Т. 127, N1, 1969. С. 44-46.' !iö. к о в и к о в П. С. Элементы математЙческой логики. М.: Наука, 1973. 100 с.101

18. Р а б и н М. Разрешимые теории. Справочная книга по математической логике. М.: Наука, 1982. Т. 3. С. 77-111.

19. Сх рейвер А. Теория линейного и целочисленного программирования. М.: Мир, 1991. 702 с.

20. X а ч и я н Л.Г. Полиномиальные алгоритмы в линейном программировании// Журн. вычислит, математики и мат. физики. 1980. N1. С. 51-68.

21. Шевченко В. Н. Качественные вопросы целочисленного программирования. М.: Наука, 1995. 190 с.

22. Я б л о н с к и й С. В. Введение в дискретную математику. М.: Наука, 1986. 384 с.

23. В е a v е г s С. Automated Theorem Proving for Lukasiewicz Logics// Studia Logica 52. 1993. P. 183-196.

24. С h a n g С. C. Logic with positive and negative truth values// Acta Philosophica Fennica, 1963, Fasc. XVI. P. 19-39.28. d e С о s t a N. C. A. On the theory of inconsistent formal systems// Notre Dame J. of Form. Logic, 1974. Vol. XV, N4. P. 497-510.

25. F a g i n R., H a 1 p e r n J. Y., M e g i d d о N. A logic for reasoning about probabilities// Proc. 3rd IEEE Symp. on Logic in Сотр. Sci. 1998. P 271- 291.

26. G о 1 о t a Y. Y. On a certain formalization of antonyms logic,// Fuzzy sets and systems. Vol. 45. 1992. P. 335-340.102

27. K a r ra a r k a r N. A new polynomial-time algorithm for linear programming// Proc. Sixteenth Arm. ACM Symp. on Theory of Computing. N. Y.: The Association for Computer Machinery, 1984. P. 302-311.

28. K o s s o v s k i N. K., T i s h k o v A. V. Mathematical reasoning for fuzzy propositions// Intern, conf. on Informatics and Control. Proceedings. Vol. 2, St. Petersburg, 1997. P. 522-529.

29. Kossovski N.K., T i s h k o vA.V. Weak theory of linear inequalities with integer coefficients and variables// 14th days of weak arithmetic. 1997. http://logic.pdmi.ras.ru/ jafl4 / participants.html

30. Kossovski N.K., T i s h k o v A.V., Iaroslavski V.V. The propositional n- Agent Logic// Proc. 19th International Workshop of Central and Eastern Europe on Multi-Agent Systems. St.Petersburg, 1999. P. 331-333.

31. L u k a s i e w i c z J., T a r s k i A. Unter suchungen über den Aussagen Kalkul// Comptesreudus des séances de la Société des Sciences et des lettres. CI. III, 23(1930). P. 3050.

32. M c y e r A. R. The inherent complexity of ordered sets// Proc. of the International Congress of Math. Vancouver, 1974, Canadian Math. Congress, 1975. P. 477-482.

33. O b e i d N. Three valued logic and monotonie reasoning// Computer and Artificial Intellegence. Vol. 15, N6. 1996. P. 509-530.

34. O r e v k o v V. Complexity of proofs and their transformations in axiomatic theories. American Mathematical Society, Translations of Mathematical Monographs. Vol. 128. 1993.

35. P o s t E.L. Introduction to a general theory of elementary proposition// American J. of Math. 1921. Vol.43, N3. P. 163-185.

36. Renegar J. A polynomial-time algorithm, based on Newton's method for linear programming// Ivíath. Sci. Res. Institute. Berkley. Preprint 07118-86, .Juñe 1986.103

37. You J., YuanL. A Three-valued semantics for deductive databases and logic programs// J. Comput. and Syst. Sci. 1994. 49. P. 334-361.

38. Z a d e h L. A. Fuzzy Sets// Informational Control. 1965. N8. P. 338-353.