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

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

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

Синтаксис логики по умолчанию [ править ]

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

{\frac {\mathrm {Prerequisite:Justification} _{1},\dots ,\mathrm {Justification} _{n}}{\mathrm {Conclusion} }}

Согласно этому умолчанию, если мы считаем, что $Предпосылка$ истинна, и каждый $\mathrm {Justification} _{i}$ для $i=1,\dots ,n$ согласуется с нашими текущими убеждениями, нас заставляют поверить, что $вывод$ верен.

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

Примеры [ править ]

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

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

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

W=\{\mathrm {Bird} (\mathrm {Condor} ),\mathrm {Bird} (\mathrm {Penguin} ),\neg \mathrm {Flies} (\mathrm {Penguin} ),\mathrm {Flies} (\mathrm {Bee} )\}

.

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

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

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

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

Ограничения [ править ]

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

Семантика логики по умолчанию [ править ]

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

\left\langle \left\{{\frac {\mathrm {Republican} (X):\neg \mathrm {Pacifist} (X)}{\neg \mathrm {Pacifist} (X)}},{\frac {\mathrm {Quaker} (X):\mathrm {Pacifist} (X)}{\mathrm {Pacifist} (X)}}\right\},\left\{\mathrm {Republican} (\mathrm {Nixon} ),\mathrm {Quaker} (\mathrm {Nixon} )\right\}\right\rangle

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

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

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

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

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

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

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

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

Привлечение [ править ]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Переводы [ править ]

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

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

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

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

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

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

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

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

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

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

Сложность [ править ]

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

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

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

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

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

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

Реализации [ править ]

Четыре системы, реализующие логику по умолчанию: ДеРеС ^{[ постоянная мертвая ссылка ]}, Рентгеновский , GADeL. Архивировано 6 апреля 2007 г. в Wayback Machine и Catala .

См. также [ править ]

Ссылки [ править ]

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

Внешние ссылки [ править ]

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