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

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

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

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

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

{\ displaystyle {\ frac {\ mathrm {Предпосылка: Обоснование} _ {1}, \ dots, \ mathrm {Обоснование} _ {n}} {\ mathrm {Заключение}}}}

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

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

Примеры

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

{\ Displaystyle D = \ left \ {{\ frac {\ mathrm {Bird} (X): \ mathrm {Flies} (X)} {\ mathrm {Flies} (X)}} \ right \}}

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

{\ displaystyle W = \ {\ mathrm {Bird} (\ mathrm {Condor}), \ mathrm {Bird} (\ mathrm {Penguin}), \ neg \ mathrm {Flies} (\ mathrm {Penguin}), \ mathrm {Мухи} (\ mathrm {Bee}) \}}

.

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

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

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

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

Ограничения

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

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

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

{\ displaystyle \ left \ langle \ left \ {{\ frac {\ mathrm {республиканец} (X): \ neg \ mathrm {Pacifist} (X)} {\ neg \ mathrm {Pacifist} (X)}}, { \ frac {\ mathrm {Quaker} (X): \ mathrm {Пацифист} (X)} {\ mathrm {Пацифист} (X)}} \ right \}, \ left \ {\ mathrm {Республиканец} (\ mathrm { Nixon}), \ mathrm {Quaker} (\ mathrm {Nixon}) \ right \} \ right \ rangle}

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

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

T = W         /* current theory */
A = 0         /* set of defaults applied so far */
 
              /* apply a sequence of defaults */
while there is a default d that is not in A and is applicable to T
    add the consequence of d to T
    add d to A
 
              /* final consistency check */
if 
    for every default d in A
        T is consistent with all justifications of d
then
    output T

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

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

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

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

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

Логическое следствие

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

Скептически настроен: формула вытекает из теории по умолчанию, если она вытекает из всех ее расширений;

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

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

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

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

Оправдано: отличается от исходного тем, что значение по умолчанию не применяется, если в результате набор $T$ становится несовместимым с обоснованием применяемого значения по умолчанию;

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

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

Рациональный: аналогична логике с ограничениями по умолчанию, но последствия добавления по умолчанию не учитываются при проверке согласованности;

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

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

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

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

Утвержденные варианты: Утверждение - это пара, состоящая из формулы и набора формул. Такая пара указывает, что $p$ истинно, в то время как формулы предполагались согласованными, чтобы доказать, что $p$ истинно. Теория утверждений по умолчанию состоит из теории утверждений (набора формул утверждений), называемой фоновой теорией, и набора значений по умолчанию, определенных как в исходном синтаксисе. Каждый раз, когда значение по умолчанию применяется к теории утверждений, к теории добавляется пара, состоящая из его следствия и набора обоснований. В следующей семантике используются теории утверждений: ${\ Displaystyle \ langle p: \ {r_ {1}, \ ldots, r_ {n} \} \ rangle}$ ${\ displaystyle r_ {1}, \ ldots, r_ {n}}$

Кумулятивная логика по умолчанию
Приверженность логике предположений по умолчанию
Квази-дефолтная логика

Слабые расширения: вместо проверки того, действительны ли предварительные условия в теории, состоящей из базовой теории и последствий примененных значений по умолчанию, предварительные условия проверяются на достоверность в расширении, которое будет сгенерировано; другими словами, алгоритм генерации расширений начинается с предположения теории и ее использования вместо базовой теории; то, что является результатом процесса генерации расширений, на самом деле является расширением только в том случае, если оно эквивалентно теории, предполагаемой вначале. Этот вариант логики по умолчанию в принципе связан с автоэпистемической логикой , где теория имеет модель, в которой $x$ истинно только потому, что, предполагая истинность, формула поддерживает исходное предположение. ${\ displaystyle \ Box x \ rightarrow x}$ ${\ displaystyle \ Box x}$ ${\ displaystyle \ Box x \ rightarrow x}$

Дизъюнктивная логика по умолчанию: следствием значения по умолчанию является набор формул вместо одной формулы. Каждый раз, когда применяется значение по умолчанию, по крайней мере одно из его последствий выбирается недетерминированно и становится истинным.

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

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

Переводы

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

Сохранение последствий: исходная и переведенная теории имеют одинаковые (пропозициональные) последствия;

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

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

Тот же алфавит: оригинальная и переведенная теории построены на одном алфавите;

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

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

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

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

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

Сложность

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

Наличие расширений: решение о том, имеет ли теория пропозиционального дефолта хотя бы одно расширение, является завершенным; ${\ displaystyle \ Sigma _ {2} ^ {P}}$

Скептическое следствие: решение о том, что теория пропозиционального дефолта скептически влечет за собой пропозициональную формулу, является полным; ${\ displaystyle \ Pi _ {2} ^ {P}}$

Легковерность: решение вопроса о том, действительно ли теория пропозиционального дефолта влечет за собой пропозициональную формулу, - завершено; ${\ displaystyle \ Sigma _ {2} ^ {P}}$

Проверка расширений: решение о том, эквивалентна ли пропозициональная формула расширению пропозициональной теории по умолчанию, является -полным; ${\ displaystyle \ Delta _ {2} ^ {P [\ log]}}$

Проверка модели: решение о том, является ли пропозициональная интерпретация моделью расширения теории пропозиционального дефолта, является завершенным. ${\ displaystyle \ Sigma _ {2} ^ {P}}$

Реализации

Четыре системы, реализующие логику по умолчанию, - это DeReS , XRay , GADeL и Catala .

Смотрите также

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

Шмидт, Чарльз Ф. RCI.Rutgers.edu , Default Logic. Проверено 10 августа 2004 года.
Рамзи, Аллан (1999). UMIST.ac.uk , Логика по умолчанию. Проверено 10 августа 2004 года.
Stanford.edu , Возможные аргументы, Стэнфордская энциклопедия философии .

Languages

In other projects