Логика по умолчанию

редактировать

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

Логика по умолчанию может выражать такие факты, как «по умолчанию что-то верно»; Напротив, стандартная логика может только выразить то, что что-то истинно или что-то ложно. Это проблема, потому что в рассуждениях часто используются факты, которые верны в большинстве случаев, но не всегда. Классический пример: «птицы обычно летают». Это правило может быть выражено в стандартной логике либо «все птицы летают», что несовместимо с тем фактом, что пингвины не летают, либо «всеми птицами, которые не являются пингвинами и не страусами и... летают», что требует всех исключения из правил, которые необходимо указать. Логика по умолчанию направлена ​​на формализацию таких правил вывода, как это, без явного упоминания всех их исключений.

Содержание

  • 1 Синтаксис логики по умолчанию
    • 1.1 Примеры
    • 1.2 Ограничения
  • 2 Семантика логики по умолчанию
    • 2.1 Переход
    • 2.2 Альтернативные правила вывода по умолчанию
  • 3 Варианты по умолчанию логика
  • 4 Перевод
  • 5 Сложность
  • 6 Реализации
  • 7 См. также
  • 8 Ссылки
  • 9 Внешние ссылки

Синтаксис логики по умолчанию

Теория по умолчанию пара ⟨W, D⟩ {\ displaystyle \ langle W, D \ rangle}\ langle W, D \ rangle . W - это набор логических формул, называемых фоновой теорией, которые формализуют достоверно известные факты. D - это набор правил по умолчанию, каждое из которых имеет вид:

Предварительное условие: J ustification 1,…, J ustificationn C onclusion {\ displaystyle {\ frac {\ mathrm {Prerequisite: Justification} _ {1}, \ dots, \ mathrm {Justification} _ {n}} {\ mathrm {Conclusion}}}}{\ displaystyle {\ frac {\ mathrm {Предварительное условие: Обоснование} _ {1}, \ dots, \ mathrm {Обоснование} _ {n} } {\ mathrm {Заключение}}}}

В соответствии с этим значением по умолчанию, если мы считаем, что Prerequisite истинно, и каждое из J ustificationn {\ displaystyle \ mathrm {Обоснование} _ {n}}{\ displaystyle \ mathrm {Justification} _ {n}} согласуется с нашими текущими убеждениями, нас заставляют верить, что Заключение верно.

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

Примеры

Правило по умолчанию «птицы обычно летают» формализовано следующим по умолчанию:

D = {B ird (X): F лежит (X) F лежит (X) } {\ displaystyle D = \ left \ {{\ frac {\ mathrm {Bird} (X): \ mathrm {Flies} (X)} {\ mathrm {Flies} (X)}} \ right \}}{\ displaystyle D = \ left \ {{\ frac {\ mathrm {Bird} (X): \ mathrm {Flies} (X)} {\ mathrm {Flies} (X)}} \ ri ght \}}

Это правило означает, что «если X - птица, и можно предположить, что она летает, то мы можем сделать вывод, что она летает». Базовая теория, содержащая некоторые факты о птицах, следующая:

W = {B ird (C ondor), B ird (P enguin), ¬ F lie (P enguin), F lie (B ee)} {\ displaystyle W = \ {\ mathrm {Bird} (\ mathrm {Condor}), \ mathrm {Bird} (\ mathrm {Penguin}), \ neg \ mathrm {Flies} (\ mathrm {Penguin}), \ mathrm {Flies } (\ mathrm {Bee}) \}}{\ displaystyle W = \ {\ mathrm {Bird} (\ mathrm {Condor}), \ mathrm {Bird} (\ mathrm {Penguin}), \ neg \ mathrm {Flies} (\ mathrm {Penguin}), \ mathrm {Мухи} (\ mathrm {Bee}) \}} .

Согласно этому правилу по умолчанию, кондор летает, потому что предварительное условие Bird (Кондор) истинно, а обоснование Flies (Condor) не противоречит тому, что известно в настоящее время. Напротив, Bird (Penguin) не позволяет заключить Flies (Penguin): даже если предварительное условие для Bird (Penguin) по умолчанию истинно, обоснование Flies (Penguin) несовместимо с тем, что известно. Из этой фоновой теории и этого значения по умолчанию нельзя сделать вывод о Bird (Bee), потому что правило по умолчанию позволяет получить только Flies (X) от Bird (X), но не наоборот. Получение антецедентов правила вывода из последствий является одной из форм объяснения последствий и является целью абдуктивного мышления.

Распространенное допущение по умолчанию - то, что не известно как истинное, считается ложным. Это известно как Предположение о закрытом мире и формализовано в логике по умолчанию с использованием значения по умолчанию, подобного следующему, для каждого факта F.

: ¬ F ¬ F {\ displaystyle {\ frac {: { \ neg} F} {{\ neg} F}}}{\ frac {: {\ neg} F} {{\ neg} F}}

Например, компьютерный язык Prolog использует своего рода допущение по умолчанию при работе с отрицанием: если отрицательный атом не может быть доказан как true, то предполагается, что это ложь. Однако обратите внимание, что Prolog использует так называемое отрицание как отказ : когда интерпретатор должен оценить атом ¬ F {\ displaystyle \ neg F}\ neg F , он пытается чтобы доказать, что F истинно, и заключить, что ¬ F {\ displaystyle \ neg F}\ neg F истинно, если это не удается. Вместо этого в логике по умолчанию, значение по умолчанию, имеющее ¬ F {\ displaystyle \ neg F}\ neg F в качестве обоснования, может применяться только в том случае, если ¬ F {\ displaystyle \ neg F}\ neg F соответствует текущим знаниям.

Ограничения

Значение по умолчанию является категориальным или не требует предварительных условий, если оно не имеет предварительных условий (или, что то же самое, его предварительное условие - тавтологический ). Значение по умолчанию является нормальным, если оно имеет единственное обоснование, эквивалентное его заключению. Значение по умолчанию является сверхнормальным, если оно одновременно категорично и нормально. Дефолт считается полунормальным, если все его обоснования влекут за собой его заключение. Теория по умолчанию называется категориальной, нормальной, сверхнормальной или полунормальной, если все содержащиеся в ней значения по умолчанию являются категориальными, нормальными, сверхнормальными или полунормальными соответственно.

Семантика логики по умолчанию

Правило по умолчанию может применяться к теории, если его предусловие вытекает из теории и все его обоснования согласуются с теорией. Применение правила по умолчанию приводит к добавлению его последствий к теории. Затем к полученной теории могут быть применены другие правила по умолчанию. Когда теория такова, что никакое другое значение по умолчанию не может быть применено, теория называется расширением теории по умолчанию. Правила по умолчанию могут применяться в другом порядке, и это может привести к различным расширениям. Пример алмаза Никсона - это теория по умолчанию с двумя расширениями:

⟨{Республика (X): ¬ Пацифист (X) ¬ Пацифист (X), Куакер (X): Пацифист (X) Пацифист (X)}, {республиканец (N ixon), Q uaker (N ixon)}⟩ {\ displaystyle \ left \ langle \ left \ {{\ frac {\ mathrm {Republican} (X): \ neg \ mathrm {Пацифист} (X)} {\ neg \ mathrm {Пацифист} (X)}}, {\ frac {\ mathrm {Квакер} (X): \ mathrm {Пацифист} (X)} {\ mathrm {Пацифист} (X)}} \ right \}, \ left \ {\ mathrm {Республиканец} (\ mathrm {Nixon}), \ mathrm {Quaker} (\ mathrm {Nixon}) \ right \} \ right \ rangle }{\ displaystyle \ left \ langle \ left \ {{\ frac {\ mathrm {республиканец} (X): \ neg \ mathrm {Пацифист} (X)} {\ neg \ mathrm {Пацифист} (X)}}, {\ frac { \ mathrm {Quaker} (X): \ mathrm {Пацифист} (X)} {\ mathrm {Пацифист} (X)}} \ right \}, \ left \ {\ mathrm {Республиканец} (\ mathrm {Nixon}), \ mathrm {Quaker} (\ mathrm {Nixon}) \ right \} \ right \ rangle}

Поскольку Никсон одновременно является республиканцем и квакером, могут применяться оба значения по умолчанию. Однако применение первого значения по умолчанию приводит к выводу, что Никсон не пацифист, поэтому второй вариант по умолчанию неприменим. Таким же образом, применяя второе значение по умолчанию, мы получаем, что Никсон - пацифист, поэтому первое значение по умолчанию не применимо. Таким образом, эта конкретная теория по умолчанию имеет два расширения: одно, в котором пацифист (Никсон) является истинным, а второе, в котором пацифист (Никсон) ложно.

Исходная семантика логики по умолчанию была основана на фиксированной точке функции. Ниже приводится эквивалентное алгоритмическое определение. Если значение по умолчанию содержит формулы со свободными переменными, считается, что оно представляет собой набор всех значений по умолчанию, полученных путем присвоения значения всем этим переменным. По умолчанию α: β 1,…, β n γ {\ displaystyle {\ frac {\ alpha: \ beta _ {1}, \ ldots, \ beta _ {n}} {\ gamma}}}{\ frac {\ alpha: \ beta _ {1}, \ ldots, \ beta _ {n}} {\ gamma}} применимо к теории высказываний T, если T ⊨ α {\ displaystyle T \ models \ alpha}T \ models \ alpha и все теории T ∪ {β i} {\ displaystyle T \ чашка \ {\ beta _ {i} \}}T \ cup \ {\ beta _ {i} \} согласованы. Применение этого значения по умолчанию к T приводит к теории T ∪ {γ} {\ displaystyle T \ cup \ {\ gamma \}}T \ cup \ {\ gamma \} . Расширение может быть сгенерировано с помощью следующего алгоритма:

T = W / * текущая теория * / A = 0 / * набор значений по умолчанию, примененных до сих пор * / / * применение последовательности значений по умолчанию * / в то время как есть значение d по умолчанию, которого нет в A и применимо к T, добавить следствие d к T добавить d к A / * окончательная проверка согласованности * / ifдля каждый d по умолчанию в AT согласуется со всеми обоснованиями d, затем output T

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

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

⟨{: A (b) ¬ A (b)}, ∅⟩ {\ displaystyle \ left \ langle \ left \ {{\ frac {: A (b)} {\ neg A (b)}} \ right \}, \ emptyset \ right \ rangle}\ left \ langle \ left \ {{\ frac {: A (b)} {\ neg A (b)}} \ right \}, \ emptyset \ right \ rangle

Поскольку A (b) {\ displaystyle A (b)}A (b) согласуется с теорией фона, можно применить значение по умолчанию, что приведет к заключению, что A (b) {\ displaystyle A (b)}A (b) ложно. Однако этот результат подрывает предположение, которое было сделано для применения первого дефолта. Следовательно, у этой теории нет расширений.

В обычной теории по умолчанию все значения по умолчанию являются нормальными: каждое значение по умолчанию имеет вид ϕ: ψ ψ {\ displaystyle {\ frac {\ phi: \ psi} {\ psi}}}{\ frac {\ phi: \ psi} {\ psi}} . Нормальная теория по умолчанию гарантированно имеет хотя бы одно расширение. Кроме того, расширения нормальной теории по умолчанию несовместимы, т.е. несовместимы друг с другом.

Entailment

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

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

Таким образом, пример теории алмаза Никсона имеет два расширения: одно, в котором Никсон является пацифистом, и тот, в котором он не пацифист. Следовательно, ни Пацифист (Никсон), ни ¬ Пацифист (Никсон) не подразумеваются скептически, в то время как оба они подразумеваются доверчиво. Как показывает этот пример, легковерные последствия теории дефолта могут противоречить друг другу.

Альтернативные правила вывода по умолчанию

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

Обоснованный
отличается от исходного тем, что значение по умолчанию не применяется, если в результате набор T становится несовместимым с обоснованием применяемого значения по умолчанию;
Краткий
значение по умолчанию применяется только в том случае, если его последствия еще не вытекают из T (точное определение более сложное, чем это; это только основная идея);
Ограниченный
значение по умолчанию применяется только в том случае, если набор, состоящий из теоретической основы, обоснований всех примененных значений по умолчанию и последствий всех примененных значений по умолчанию (включая этот), согласован;
Rational
аналогично логике с ограничениями по умолчанию, но последствия добавления по умолчанию не учитываются при проверке согласованности;
осторожные
значения по умолчанию, которые могут применяться, но конфликтуют друг с другом (например, в примере с бриллиантом Никсона), не применяются.

Выровненная и ограниченная версии правила вывода назначают по крайней мере расширение для каждого значения по умолчанию t теория.

Варианты логики по умолчанию

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

Варианты утверждения
Утверждение - это пара ⟨p: {r 1,…, rn}⟩ {\ displaystyle \ langle p: \ {r_ {1}, \ ldots, r_ { n} \} \ rangle}\ langle p: \ {r_ {1}, \ ldots, r_ {n} \} \ rangle состоит из формулы и набора формул. Такая пара указывает, что p истинно, в то время как формулы r 1,…, rn {\ displaystyle r_ {1}, \ ldots, r_ {n}}r_ {1}, \ ldots, r_ {n} считались непротиворечивыми, чтобы доказать, что p правда. Теория утверждений по умолчанию состоит из теории утверждений (набора формул утверждений), называемой фоновой теорией, и набора значений по умолчанию, определенных как в исходном синтаксисе. Всякий раз, когда к теории утверждений применяется значение по умолчанию, к теории добавляется пара, состоящая из его следствия и набора обоснований. В следующей семантике используются теории утверждений:
  • Кумулятивная логика по умолчанию
  • Приверженность к предположениям логика по умолчанию
  • Квази-стандартная логика
Слабые расширения
вместо проверки того, предварительные условия действительны в теории, состоящей из базовой теории и последствий примененных значений по умолчанию, предварительные условия проверяются на соответствие в расширении, которое будет сгенерировано; другими словами, алгоритм генерации расширений начинается с предположения теории и ее использования вместо теории фона; то, что является результатом процесса генерации расширений, на самом деле является расширением только в том случае, если оно эквивалентно теории, предполагаемой в начале. Этот вариант логики по умолчанию в принципе связан с автоэпистемической логикой, где теория ◻ x → x {\ displaystyle \ Box x \ rightarrow x}\ Box x \ rightarrow x имеет модель, в которой x истинно только потому, что при условии, что ◻ x {\ displaystyle \ Box x}\ Box x истинно, формула ◻ x → x {\ displaystyle \ Box x \ rightarrow x}\ Box x \ rightarrow x поддерживает исходное предположение.
Дизъюнктивная логика по умолчанию
последствием использования по умолчанию является набор формул вместо одной формулы. Каждый раз, когда применяется значение по умолчанию, по крайней мере одно из его последствий выбирается недетерминированно и становится истинным.
Приоритеты по умолчанию
относительный приоритет значений по умолчанию может быть явно указан; среди значений по умолчанию, применимых к теории, может быть применен только один из наиболее предпочтительных. Некоторая семантика логики по умолчанию не требует явного указания приоритетов; скорее, более конкретные значения по умолчанию (те, которые применимы в меньшем количестве случаев) предпочтительнее менее конкретных.
Статистический вариант
статистический вариант по умолчанию - это значение по умолчанию с прикрепленной верхней границей частоты его ошибок; другими словами, предполагается, что правило по умолчанию является неправильным правилом вывода не чаще, чем в той части случаев, когда оно применяется.

Переводы

Теории по умолчанию могут быть переведены в теории в других логиках и наоборот. Были рассмотрены следующие условия переводов:

Последствия- Сохранение
исходная и переведенная теории имеют одинаковые (пропозициональные) последствия;
Верный
это условие имеет только смысл при переводе между двумя вариантами логики по умолчанию или между логикой по умолчанию и логикой, в которой существует концепция, аналогичная расширению, например, модели в модальной логике ; перевод является достоверным, если существует сопоставление (обычно, взаимное соответствие) между расширениями (или моделями) исходной и переведенной теорий;
Модульный
перевод из логики по умолчанию в другую логику является модульным, если значения по умолчанию и базовая теория могут быть переведены отдельно; более того, добавление формул к базовой теории приводит только к добавлению новых формул к результату перевода;
Same-Alphabet
исходная и переведенная теории построены на одном алфавите;
Полиномиальное
время выполнения перевода или размер созданной теории должны быть полиномиальными по сравнению с размером исходной теории.

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

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

  • классическая логика высказываний;
  • автоэпистемическая логика;
  • логика пропозициональной логики по умолчанию, ограниченная полунормальными теориями;
  • альтернативная семантика логики по умолчанию;
  • ограничение.

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

Сложность

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

Существование расширений
, определяющих, является ли пропозициональная теория по умолчанию имеет по крайней мере одно расширение: Σ 2 P {\ displaystyle \ Sigma _ {2} ^ {P}}\ Sigma _ {2} ^ {P} -complete;
Скептический вывод
определение того, является ли пропозициональный теория по умолчанию скептически влечет за собой пропозициональную формулу is Π 2 P {\ displaystyle \ Pi _ {2} ^ {P}}\ Pi _ {2} ^ {P} -complete;
Доверчивый вывод
Решить, правдоподобно ли теория пропозиционального дефолта влечет за собой пропозициональную формулу, является Σ 2 P {\ displaystyle \ Sigma _ {2} ^ {P}}\ Sigma _ {2} ^ {P} -complete;
Проверка расширений
Решение о том, эквивалентна ли пропозициональная формула расширению пропозициональной теории по умолчанию: Δ 2 P [log] {\ displaystyle \ Delta _ {2} ^ {P [\ log]}}{\ displaystyle \ Delta _ {2} ^ {P [\ log]}} -полный;
Проверка модели
определение того, является ли пропозициональная интерпретация моделью расширением пропозициональной теории по умолчанию является Σ 2 P {\ displaystyle \ Sigma _ {2} ^ {P}}\ Sigma _ {2} ^ {P} -complete.

Реализации

Три системы, реализующие значение по умолчанию логики: DeReS, XRay и GADeL

См. также

Ссылки

  • Г. Антониу (1999). Учебник по логике по умолчанию. ACM Computing Surveys, 31 (4): 337-359.
  • М. Кадоли, Ф. М. Донини, П. Либераторе и М. Шаэрф (2000). Пространственная эффективность формализмов пропозиционального представления знаний. Журнал исследований искусственного интеллекта, 13: 1-31.
  • P. Холевинский, В. Марек и М. Трущинский (1996). Система рассуждений по умолчанию DeReS. В Трудах Пятой Международной конференции по принципам представления и рассуждения знаний (KR'96), страницы 518-528.
  • J. Дельгранде и Т. Шауб (2003). О связи между стандартной логикой Рейтера и ее (основными) вариантами. В Седьмой Европейской конференции по символическим и количественным подходам к рассуждению с неопределенностью (ECSQARU 2003), страницы 452-463.
  • J. П. Дельгранде, Т. Шауб и У. К. Джексон (1994). Альтернативные подходы к логике по умолчанию. Искусственный интеллект, 70: 167-237.
  • G. Готтлоб (1992). Результаты о сложности для немонотонных логик. Journal of Logic and Computing, 2: 397-425.
  • G. Готтлоб (1995). Преобразование логики по умолчанию в стандартную автоэпистемическую логику. Журнал ACM, 42: 711-740.
  • T. Имелински (1987). Результаты перевода значений по умолчанию в окружность. Искусственный интеллект, 32: 131-146.
  • Т. Янхунен (1998). О взаимопереводимости автоэпистемической логики, логики по умолчанию и приоритета, а также параллельного описания. В материалах Шестого Европейского семинара по логике в искусственном интеллекте (JELIA'98), страницы 216-232.
  • T. Янхунен (2003). Оценка влияния полунормальности на выразительность дефолтов. Искусственный интеллект, 144: 233-250.
  • H. Кибург Э. и Ч. Тэн (2006). Немонотонная логика и статистический вывод. Вычислительный интеллект, 22 (1): 26-51.
  • стр. Либераторе и М. Шаэрф (1998). Сложность проверки модели для пропозициональной логики по умолчанию. В материалах тринадцатой Европейской конференции по искусственному интеллекту (ECAI'98), страницы 18–22.
  • W. Лукашевича (1988). Соображения по поводу логики по умолчанию: альтернативный подход. Вычислительный интеллект, 4 (1): 1-16.
  • W. Марек и М. Трущински (1993). Немонотонная логика: контекстно-зависимые рассуждения. Спрингер.
  • А. Микитюк и М. Трущинский (1995). Ограниченная и рациональная логика по умолчанию. В материалах четырнадцатой международной совместной конференции по искусственному интеллекту (IJCAI'95), страницы 1509-1517.
  • P. Николя, Ф. Саубион и И. Стефан (2001). Эвристика для системы логических рассуждений по умолчанию. Международный журнал по инструментам искусственного интеллекта, 10 (4): 503-523.
  • R. Рейтер (1980). Логика рассуждений по умолчанию. Искусственный интеллект, 13: 81-132.
  • Т. Шауб, С. Брюнинг и П. Николас (1996). XRay: средство доказательства теорем технологии пролога для рассуждений по умолчанию: описание системы. В материалах тринадцатой Международной конференции по автоматизированному дедуктивному переводу (CADE'96), страницы 293-297.
  • G. Уиллер (2004). Логика по умолчанию с ограниченными ресурсами. В материалах 10-го Международного семинара по немонотонному мышлению (NMR-04), Уистлер, Британская Колумбия, 416-422.
  • G. Уиллер и К. Дамасио (2004). Реализация статистической логики по умолчанию. В материалах 9-й Европейской конференции по логике в искусственном интеллекте (JELIA 2004), серия LNCS, Springer, страницы 121-133.

Внешние ссылки

Последняя правка сделана 2021-05-17 11:19:23
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте