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

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

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

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

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

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

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

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

Примеры

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

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

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

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

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

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

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

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

Ограничения

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

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

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

${\displaystyle \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 }$

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

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

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

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

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

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

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

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

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

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

Скептически настроен

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

Доверчивый

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

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

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

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

Оправдано

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

Краткий

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

Ограниченный

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

Рациональный

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

Осторожный

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

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

Варианты стандартной логики

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

Утвержденные варианты

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

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

Слабые расширения

вместо проверки того, действительны ли предварительные условия в теории, состоящей из базовой теории и последствий примененных значений по умолчанию, предварительные условия проверяются на достоверность в расширении, которое будет сгенерировано; другими словами, алгоритм генерации расширений начинается с предположения теории и ее использования вместо теории фона; то, что получается в результате процесса генерации расширений, на самом деле является расширением только в том случае, если оно эквивалентно теории, предполагаемой вначале. Этот вариант логики по умолчанию в принципе связан с аутоэпистемическая логика, где теория ${\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^{[постоянная мертвая ссылка ]},Рентгеновский снимок иГАДЕЛ

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

• Программирование набора ответов
• Несостоятельная логика
• Немонотонная логика

Рекомендации

• Г. Антониу (1999). Учебник по логике по умолчанию. Опросы ACM Computing, 31(4):337-359.
• М. Кадоли, Ф. М. Донини, П. Либераторе и М. Шаерф (2000). Пространственная эффективность формализмов пропозиционального представления знаний. Журнал исследований искусственного интеллекта, 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). Немонотонная логика: контекстно-зависимые рассуждения. Springer.
• А. Микитюк и М. Трущинский (1995). Ограниченная и рациональная логика по умолчанию. В Труды четырнадцатой международной совместной конференции по искусственному интеллекту (IJCAI'95), страницы 1509-1517.
• П. Николя, Ф. Саубион и И. Стефан (2001). Эвристика для системы логических рассуждений по умолчанию. Международный журнал по инструментам искусственного интеллекта, 10(4):503-523.
• Р. Рейтер (1980). Логика рассуждений по умолчанию. Искусственный интеллект, 13:81-132.
• Т. Шауб, С. Брюнинг и П. Николас (1996). XRay: средство доказательства теорем технологии пролога для рассуждений по умолчанию: описание системы. В Труды тринадцатой международной конференции по автоматическому вычету (CADE'96), страницы 293-297.
• Дж. Уиллер (2004). Логика по умолчанию с ограниченными ресурсами. В Материалы 10-го международного семинара по немонотонным рассуждениям (ЯМР-04), Уистлер, Британская Колумбия, 416-422.
• Г. Уиллер и К. Дамасио (2004). Реализация статистической логики по умолчанию. В Труды 9-й Европейской конференции по логике в искусственном интеллекте (JELIA 2004), Серия LNCS, Springer, страницы 121-133.

внешняя ссылка

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