Расширение понятия дедуктивной системы на случай немонотонных рассуждений тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

_ . ВЭСУДАРСТВЕШЫИ КОМИТЕТ РОССИЙСКОЙ ФЕДЕРАЦИИ р Г ^ ^ ПО ВЫСШЕМ/ ОБРАЗОВАНИЮ

МОСКОВСКИЙ ОРДЕНА ТРУДОВОГО КРАСНОГО ЗНАМЕНИ 2 1} 1»0Н ФИЗИКО-ТЕХНИЧЕСКИЙ ИНСТИТУТ

На правах рукописи

Бондаренко Андрей Геннадьевич

РАСШИРЕНИЕ ПОНЯТИЯ ДЕДУКТИВНОЙ.СИСТЕМЫ НА СЛУЧАЙ НЕМОНОТОННЫХ РАССУЖДЕНИИ.

01.01.09 - математическая кибернетика

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

Научный руководитель, д. т. н., академик РАЕН, Д.А.Поспелов.

Москва 1994

Работа выполнена & Московском Ордена Трудового Красного Знамени физико-техническом институте ГК РФ ло Высшему образованию.

Научный руководитель: д. т. н.. академик РАЕН Поспелов Дмитрий Александрович.

Официальные оппоненты:

д. т. н. Вагин Вадим Николаевич,

к. ф-. м. н. Забежайпо Михаил Иванович. *

Ведущая организация (предприятие): •

Институт проблем передачи информации РАН.

Защита состоится " " ивня 1994 года на заседании Специализированного совета К. 063.91.03 Московского физико-технического института по адресу: 141700 Московская обл., г. Долгопрудный, Институтский переулок, дом 9. ■

С диссертацией можно ознакомиться в библеотеке Московского физико-технического института.

Автореферат разослан " " мая 1994 года.

Ученый секретарь

Спг иализированного совета

д. ф-. м. н.

СамьшовсклШ Александр Иванович.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ.

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

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

Отношение выводимости "Н" . в дедуктяаа&х системах обладает свойством монотонности, то есть, для дюбах множеств

- г -

формуя Т, 0 и формулы <р, из ТНр всегда следует Т«Л}>-р. С другой стороны, отношение следования 'V в человеческих рассуждениях не является монотонным: из Т«*р не всегда следует Т1Л]*ф. Часто добавление новой информации 0 в базу знаний Т делает невозможным вывод некоторых утверждений <р, следовавших из старой базы знаний. Для решения данной проблемы в. последнее десятилетие был предложен ряд логических формализмов,' в которых отношение выводимости немонотонно. Обычно, такие формализмы представляли собой модификацию какой-либо монотонной логики (дедуктивной системы) и разрабатывались для решения конкретных классов задач. К концу 80-х годов появились сотни работ, посвященных Ланкой проблеме, и на стыке математической логики, философии и информатики сформировалось целое научное направление, получившее название немонотонной логики. Было предложено большое количество различных формализмов, достаточно сильно различающихся между собой по подходам и используемым понятиям. Возникла необходимость в соотнесении данных подходоб между собой, их систематизации, и построении общей теории немонотонных рассуждений.

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

Рассмотрим некоторые требования, которым должен был бы удовлетворять такой общий подход к формализации немонотонных рассуждений. *

1). Общность: возможность выразить в рамках данного подхода все (или почти все) широко известные немонотонные логики.

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

3). Связь с семантикой: подход должен включать в себя обобщенный семантический формализм, з ранках которого можно было бы выразить известные семантики для немонотонных логик, а такте строить сзмантики для логик, определенных в терминах теории доказательств. Желательно, чтобы данный семантический формализм базировался на некотором расширении понятия теоретико-модальной семантики, используемого в традиционной математической логике.

4). Простота: все базовые понятия предлагаемого подхода должны быть достаточно просты и иметь ясный интуитивный смысл.

Цель диссертационной работы состоит в построении общего подхода к формализации немонотонных рассуждений, удовлетворяющего требованиям 1)-4), а также в рассмотрении возможностей применения данного подхода для решения существующих проблем в области немонотонной логики и формализации рассуждений.

Научная новизна работы. В последние годы было предпринято несколько попыток построения общего подхода к формализации немонотонных т>ассуждений, из которых наиболее перспективными представляются системы аргументов Лина и Шохама, а также немонотонные системы правил Марека, Нероуда и Реммела . Первый подход, хотя и обладает достаточной общностью, не опирается на понятия, традиционные для математической логики, такие как дедуктивная система, вывод, выводимость ит. п., и кроме того, для него не предложено какой-либо семантики. Второй подход можно рассматривать как Некоторое обобщение классической теории вывода, опирающееся на понятие дедуктивной системы, и в этом смысле он сохраняет преемственность, однако, данный подход на обладает достаточной общностью, и кроме того, для него также не предложено никакой семантики.

В настоящей диссертационной работе предлагается новый общий подход к формализации немонотонных рассуждений, Относительно свободный от вышеперечисленных недостатков и удовлетворяющий требованиям 1), 2), 3), 4). В основу Данного подхода легли понятия немонотонной системы и семантической структуры, которые являются расширением понятий дедуктивной системы и теоретико-модельной семантики, используемых в традиционной математической логике. В работе такке рассмотрен ряд примеров по применению предложенного формализма для решения некоторых проблем в области немонотонной логики и формализации человеческих рассуждений.

Практическая значимость. Научные результаты,

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

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

.рассуждений;

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

- в гуманитарных науках, связанных с познанием законов мышления, таких как философская логика, психология мышления и т. п.

Апробация работы. Основные результаты работы докладывались и обсуждались на:

Международной конференции "Теоретиеские аспекты рассуждений о знаниях", (Асиломар, США, 1990);

- Второй Российской конференции по логическому программированию <Санкт-Питербург, 1991);

- Второй международной конфенции по логическому программированию и немонотонным рассуждениям (Лиссабон, Португалия, 1993);

- Научных семинарах ИПС РАН, Мех-мат МГУ, Института философии РАН, Факультета вычислений Императорского колледжа (Лондон, Великобритания).

Публикации. По теме диссертации в настоящее время опубликовано три статьи. ,

Обьем и структура работы. Диссертация состоит из введения, пяти глав, заключения и списка литературы. Работа излогена на 84 страницах машинописного текста.

СОДЕРЖАНИЕ РАБОТЫ.

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

В главе 1 вводятся все базовые понятия предлагаемого в работе подхода, а также исследуются некоторые и,, свойства.

В §1 даются определение немонотонной системы -основного понятия предлагаемого формализма, а также определения немонотонного вывода, расширения, слабой . и сильной немонотонной выводимости.

Немонотонной системой называется всякая четверка <Ь,К,0,С>, где <Ь,И> - некоторая дедуктивная система, в которой предусмотрено понятие непротиворечивого множества формул ( Ь - формальный язык, В - множество правил вывода), В - некоторое множество формул языка I, и С - подмножество 24

Немонотонным выводом формулы <р из множества формул Т в немонотонной системе <Ь,В,0,С> называется всякая последовательность формул «V ••?„»■. в которой каждая следующая формула либо выводится из предыдущих за один шаг в дедуктивной системе <Ь,Е>, либо является элементом множества

Т, либо является элементом множестве Б, причем в этом случае добавление этой формулы в вывод не приводит к противоречию.

Содержательно Ю представляет собой множество формул, которые по-умолчанию считаются истинными. Каждому элементу <р множества 0 можно поставить в соответствие следующее правило умозаключений: "если добавление <р в вывод не приводит к противоречию, то у»". В зависимости от порядка добавления в вывод формул из множества Б из непротиворечивого множества посылок могут, тем не менее, указанным выше способом выводиться противоречащие друг £ругу заключения. В такой ситуации понятие немонотонной выводимости формулы <р из множества фор?'ул Т нецелесообразно определять просто как наличие немонотонного сывода <р из Т, ибо это ведет к возникновению ряда трудностей. В данной работе, как и в ряде других работ по немонотонным -огикам, отношение немонотонной выводимости определяется через понятие расширения.

Множество формул Е называется расширением непротиворечивого множества формул Т, если

(1). Е содержит Т в качестве подмножества;

(2). Е является максимальным по включению непротиворечивым множеством формул, для которых существует немонотонный вывод из Т;

СЗ). Е является элементом множества С.

Формула <р немонотонно-выводима из множества формул Т в слабом смысле (ТН1^), если существует расширение Т, содержащее <р, либо Т не имеет вообще расширений.

- а -

Формула 1Р' немонотонно выводима из множества формул Т в сильном смысле (Т>2¥>), если 9 принадлежит всем расширениям множества Т. ~

Таким образом, множество С вводит некоторые ограничения на понятие расширения, и соответственно, на множество немонотонно-выводимых формул.

В немонотонной системе <1.,й,й,С> множество Б называется множеством истинных по умолчанию формул, а С - множеством допустимых расширений. .

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

Семантической структурой для формального языка I,

называется всякая четверка <М, К <<.<!>. в которой М -

некоторое множество, элементы которого называются

интерпрь гациями; Н=Мх1. - отношение, устанавливающее

истинность формул языка Ь на интерпретациях из множества М;

«=МхМ - некоторое отношение предпс^ядка на множестве м

интерпретаций, и 4=2 .

Отношение "<<" называется отношением предпочтения.

В семантической структуре не все интерпретации равноправны. Одна интерпретация может быть более предпочтительной. чем другая согласно отношению "«", Интерпретации и1 и л2 могут быть также эквивалентны друг другу. Это имеет место, когда одновременно и1«в2 и ш2«иг Каждой интерпретации может быть поставлен в соответствие класс эквивалентных ей интерпретаций.

. Интерпретация и называется предпочтительной моделью множества формул Т, если:

(1) а КГ - в является моделью 7, то есть все формулы из множества Т истинны в в;

(2) в является максимальной согласно отношению предпочтения "«" на множестве всех моделей Т, то есть, для любой в', такой, что в' КГ, из в«п' следует в' «ш;

(3) множество всех моделей Т, эквивалентных интерпретации ш, является элементом множества

Такое множество называется предпочтительным классом моделей для Т.

Множество. 0 в семантической структура, вводящее ряд дополнительных ограничений на понятие предпочтительной модели, называется множеством допустимых предпочтительных классов.

Формула <р называется слабый семантическим следствием множества формул Т, (Ти1*)'. если существует и предпочтительная модель Т, такая, что <р истинна во всех моделях Т, эквивалентных ш, либо множество Т не имеет вообще предпочтительных моделей.

Формула ч> .называется сильным семантическим следствием множества формул Г (ТЬгу>), если <р истинна во всех предпочтительных моделях Т.

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

В §3 устанавливается взаимосвязь между понятиями расширения и немонотонной выводимости с одной стороны, и предпочтительной модели и немонотонного ремантичесхого следования с другой. В частности, формулируется И доказываете., теорема о том, что если между элементами некоторой немонотонной системы 1=<1,Р.,Б,С> и семантической структуры 5=<М, К«,Ч> существует специальное соответствие, определенное в работе, то для любого множества формул Т и формулы <р:

(1) ТН1? в X т. и т. т., когда Т^1»» в Б;

(2) Тв 2 т. и т.т.. когда в Б.

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

- И -

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

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

§1 - немонотонные системы правил Марека, Нероуда и Реммела ; §2 - логика рассуждений по умолчанию Райтера ; §3 - автоэпистемическая логика Мура ;

§4 - семантика стабильных моделей для логических программ Гельфонда и ЛифшиТца ;

§5 - абдуктивные структуры Ковальского и Какаса .

В Главе 3 рассматриваются системы аргументов Липа и Шохама, а также очерчивание Маккарти . В отличив от формализмов, рассматриваемых в предыдущей главе, данные • немонотонные логики не используют идею "неподвижной точки". В §1 показано, каким образом система аргументов- ,

произвольного вида может быть сформулирована в виде эквивалентной ей немонотонной системы.

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

Глава 4 посвящена рассмотрению различных немонотонных модальных логик.

В §1 показано, каким образом немонотонная модальная логика Мак-Дермота может быть сформулирована в виде эквивалентной немонотонной системы.

В §2, опираясь на результаты §3 главы 1, построена семантика для логики Мак-Дермота, и рассмотрена ее содержательная интерпретация.

В §3 рассматривается логика обоснованного знания СК Лина и Шохама. В параграфе показано, каким образом, данная логика, определенная авторами только в терминах семантики, может быть сформулирована в виде немонотонной системы.

В §4 предлагаются две немонотонные двухмодельные логики, аналогичные логике обоснованного знания Лина-Шохама, но обладающие, однако, по сравнение с данной логикой

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

В §5 предлагается еще одна немонотонная двухмодальная логика, которая может бьлъ рассмотрена как математическая модель человеческих рассуждений о знаниях и убеждениях. Для данной логики предложена формальная семантика и рассмотрена ее содержательная интерпретация.

В Главе 5 представлена так-называемая немонотонная ситуационная . логика ИБЬ. Язык, данной логики, являясь расширением языка первого порядка, обладает большой выразительной силой, так, что в нем, в частности, представимы утверждения вида "в ситуации (контексте) Б имеет место утверждение <р", где <р может быть любой, какой угодно сложной, формулой этого же'языка. Указанное свойство позволяет выражать з данном формальном языке достаточно широкий класс предложений естественного языка. В главе показано, что • в немонотонную ситуационную логику ИБЬ можно погрузить некоторые наиболее известные немонотонные формализмы, такие к?" автоэпиотемичес<сая логика , логика рассуждений по умолчанию, немонотонная модальная логика, что открывает широкие возможности использования логики ИБЬ для формализации различных типов человеческих рассуждений.

В §1 описан формальный язых немонотонной ситуационной логики и представлена его теоретико-модельная семантика.

В §2 рассмотрена монотонная аксиоматизация для данной семантики.

В §3 описана немонотонная составляющая логики

§4 посвящен исследованию вопроса применения

немонотонной ситуационной логики для формализации рассуждений по умолчанию.

В §5 рассматривается пример применения логики N51. для формализации рассуждений о действиях, знаниях, убеждениях и речевых актах различных субъектов.

ОСНОВНЫЕ НАУЧНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ.

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

- универсальность, то есть возможность выразить в терминах данного подхода большинство ' существующих немонотонных логик;

преемственность по отношению к традиционной монотонной логике;

- наличие обобщенной немонотонной семантики;

- ..ростота базовых понятий и определений.

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

2. Доказано, что

- немонотонные системы правил Марека, Нероуда и Реммела;

- логиха рассуждений по умолчанию Райтера;

- автоэпистемическая логика Мура;

семантика стабильных моделей для логического ] программирования Гельфонда и Лифшитца;

- абдуктивные структуры Ковальского и Какаса;

- очерчивание Маккарти в пропозициональном случае;

- логика обоснованного знания Лина и Шохама;

- немонотонная модальная логика Мак-Дермота

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

3. Рассмотрен ряд примеров по применению предложенных в диссертационной работе идей и методов для решения ряда проблем в области немонотонной логики и формализации человеческих рассуждений, а именно:

а). Построена новая формальная семантика для немонотонной модальной логики Мак-Дермота, сочетающая в себе простоту и наличие ясной содержательной интерпретации;

б). Предложена новая двухмодальная логика, обладающая рядом преимуществ по сравнению с логикой обоснованного знания Лина-Шохама, рассмотрена возможность применения данной логики для формализации рассуждений по умолчанию;

в). Предложена новая немонотонная логика, моделирующая человеческие рассуждения о знаниях и убеждениях, для этой

логики построена формальная семантика и рассмотрена ее содержательная интерпретация;

г). Построена так называемая немонотонная ситуационная логика, сочетавшая в себе:

- большую выразительную силу, что позволяет выражать в языке данной логики дастаточно широкий класс предложений естественного языка; и

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

Рассмотрен пример применения данной логики для формализации рассуждений о действиях, знаниях, убеждениях и речевых актах различных субъектов.

Основные резуль-. .ты диссертационной работы изложены в следующих публикациях:

1. Бондаренко А. Г. Немонотонный вывод в модальной логике., Сб. Искусственный интеллект - основа новой информационной технологии, ред. Поспелов Д. А., Семенов Н. А., Калинин, 1990.

2. Bondarenko A.C. Abductive systems for non-monotonie reasoning., In: Lecture notes in Artificial Intelligence, v. 34S, Springer Verlag, 1991.

3. Bondarenko A.C., Kowalski R.A., Toni F., An Assumption-basea Framework for Non-Monotonic Reasoning., In: Proc. of The Second International Workshop on Logic Programming and Non-Monotonic Reasoning., MIT Press, Boston, 1993.

H9TU sa^ji -TL^CV* &0-ЗУ).