Стабильная семантика модели

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

Мотивация

Исследования декларативной семантики отрицания в логическом программировании были мотивированы тем фактом, что поведение разрешения SLDNF — обобщения разрешения SLD, используемого Прологом при наличии отрицания в телах правил — не полностью соответствует таблицам истинности, известным из классическая пропозициональная логика . Рассмотрим, например, программу

$p$

$r\leftarrow p,q$

$s\leftarrow p,\operatorname {not} q.$

Учитывая эту программу, запрос p будет успешным, поскольку программа включает p как факт; запрос q завершится неудачно, поскольку он не встречается в заголовке ни одного из правил. Запрос r также завершится неудачей, поскольку единственное правило с r в заголовке содержит подцель q в своем теле; как мы видели, эта подцель не достигается. Наконец, запрос s завершается успешно, поскольку каждая из подцелей p , $\operatorname {not} q$ удается. (Последнее удается, потому что соответствующая положительная цель q не удается.) Подводя итог, поведение разрешения SLDNF в данной программе может быть представлено следующим присваиванием истинности:

п	д	р	с
Т	Ф	Ф	Т. ​

С другой стороны, правила данной программы можно рассматривать как пропозициональные формулы, если отождествить запятую с союзом $\land$, символ $\operatorname {not}$ с отрицанием $\neg$и соглашаемся лечить $F\leftarrow G$ как следствие $G\rightarrow F$ написано наоборот. Например, последнее правило данной программы является с этой точки зрения альтернативным обозначением пропозициональной формулы

$p\land \neg q\rightarrow s.$

Если мы вычислим значения истинности правил программы для присвоения истинности, показанного выше, то мы увидим, что каждое правило получает значение T . Другими словами, это задание является моделью программы. Но у этой программы есть и другие модели, например

п	д	р	с
Т	Т	Т	Ф. ​

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

Отношение к немонотонной логике

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

Синтаксис автоэпистемической логики использует модальный оператор , который позволяет нам различать то, что истинно, и то, что известно. Михаил Гельфонд [1987] предложил прочитать $\operatorname {not} p$ в теле правила как " $p$ не известно», и понимать правило с отрицанием как соответствующую формулу автоэпистемической логики. Семантику устойчивой модели в ее базовой форме можно рассматривать как переформулировку этой идеи, избегающую явных ссылок на автоэпистемическую логику.

В логике по умолчанию значение по умолчанию похоже на правило вывода , за исключением того, что оно включает, помимо своих посылок и заключения, список формул, называемых обоснованиями. Дефолт можно использовать для получения заключения при условии, что его обоснования согласуются с тем, что известно на данный момент. Николь Бидуа и Кристин Фруадево [1987] предложили рассматривать отрицаемые атомы в своде правил как оправдания. Например, правило

$s\leftarrow p,\operatorname {not} q$

можно понимать как значение по умолчанию, которое позволяет нам получить $s$ от $p$ предполагая, что $\neg q$ является последовательным. Семантика стабильной модели использует ту же идею, но не относится явно к логике по умолчанию.

Стабильные модели

В приведенном ниже определении стабильной модели, воспроизведенном из [Гельфонд и Лифшиц, 1988], используются два соглашения. Во-первых, истинное присвоение идентифицируется с набором атомов, которые получают T. значение Например, истинностное задание

п	д	р	с
Т	Ф	Ф	Т. ​

отождествляется с множеством $\{p,s\}$. Это соглашение позволяет нам использовать отношение включения множества для сравнения истинностных присвоений друг с другом. Наименьшее из всех заданий на истинность $\emptyset$ тот, который делает каждый атом ложным; наибольшее истинное присвоение делает каждый атом истинным.

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

$\operatorname {even} (0)$

$\operatorname {even} (s(X))\leftarrow \operatorname {not} \operatorname {even} (X)$

понимается как результат замены X в этой программе основными членами

$0,s(0),s(s(0)),\dots .$

всеми возможными способами. Результатом является бесконечная наземная программа.

$\operatorname {even} (0)$

$\operatorname {even} (s(0))\leftarrow \operatorname {not} \operatorname {even} (0)$

$\operatorname {even} (s(s(0)))\leftarrow \operatorname {not} \operatorname {even} (s(0))$

$\dots$

Определение

Пусть P — набор правил вида

$A\leftarrow B_{1},\dots ,B_{m},\operatorname {not} C_{1},\dots ,\operatorname {not} C_{n}$

где $A,B_{1},\dots ,B_{m},C_{1},\dots ,C_{n}$ являются основными атомами. Если P не содержит отрицания ( $n=0$ в каждом правиле программы), то по определению единственной устойчивой моделью P является его модель, минимальная относительно включения множества. (Любая программа без отрицания имеет ровно одну минимальную модель.) Чтобы распространить это определение на случай программ с отрицанием, нам понадобится вспомогательное понятие редукции, определяемое следующим образом.

Для любого набора I основных атомов сокращение P путем относительно I - это набор правил без отрицания, полученный из P сначала отбрасывания каждого правила, такого, что хотя бы один из атомов ⁠ $C_{i}$⁠ в своем теле

$B_{1},\dots ,B_{m},\operatorname {not} C_{1},\dots ,\operatorname {not} C_{n}$

принадлежит мне , а затем отбрасываю части $\operatorname {not} C_{1},\dots ,\operatorname {not} C_{n}$ из тел всех остальных правил.

Мы говорим, что — стабильная модель P , если I — стабильная модель редукции P относительно I. I (Поскольку редукция не содержит отрицания, ее стабильная модель уже определена.) Как предполагает термин «стабильная модель», каждая стабильная модель P является моделью P .

Пример

Для иллюстрации этих определений проверим, что $\{p,s\}$ это стабильная модель программы

$p$

$r\leftarrow p,q$

$s\leftarrow p,\operatorname {not} q.$

Сокращение этой программы относительно $\{p,s\}$ является

$p$

$r\leftarrow p,q$

$s\leftarrow p.$

(Действительно, поскольку $q\not \in \{p,s\}$, сокращение получается из программы путем отбрасывания части $\operatorname {not} q.$) Стабильная модель редукции: $\{p,s\}$. (Действительно, этот набор атомов удовлетворяет всем правилам редукции и не имеет собственных подмножеств с тем же свойством.) Таким образом, после вычисления стабильной модели редукции мы пришли к тому же набору $\{p,s\}$ с чего мы начали. Следовательно, этот набор является устойчивой моделью.

Проверяем таким же образом остальные 15 наборов, состоящих из атомов $p,q,r,s$ показывает, что у этой программы нет других стабильных моделей. Например, сокращение программы относительно $\{p,q,r\}$ является

$p$

$r\leftarrow p,q.$

Стабильная модель редукции: $\{p\}$, который отличается от набора $\{p,q,r\}$ с чего мы начали.

Программы без уникальной стабильной модели

Программа с отрицанием может иметь много стабильных моделей или не иметь стабильных моделей. Например, программа

$p\leftarrow \operatorname {not} q$

$q\leftarrow \operatorname {not} p$

имеет две стабильные модели $\{p\}$, $\{q\}$. Программа с одним правилом

$p\leftarrow \operatorname {not} p$

не имеет стабильных моделей.

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

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

Свойства семантики стабильной модели

В этом разделе, как и в приведенном выше определении стабильной модели , под логической программой мы понимаем набор правил вида

$A\leftarrow B_{1},\dots ,B_{m},\operatorname {not} C_{1},\dots ,\operatorname {not} C_{n}$

где $A,B_{1},\dots ,B_{m},C_{1},\dots ,C_{n}$ являются основными атомами.

Головные атомы

Если атом A принадлежит стабильной модели логической программы P то A является главой одного из правил P. ,

Минимальность

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

Свойство антицепи

Если I и J — стабильные модели одной и той же логической программы, то не является собственным подмножеством J. I Другими словами, множество устойчивых моделей программы представляет собой антицепь .

NP-полнота

Проверка того, имеет ли программа с конечной основной логикой устойчивую модель, является NP-полной .

Отношение к другим теориям отрицания как неудачи

Завершение программы

Любая стабильная модель конечной базовой программы является не только моделью самой программы, но и моделью ее завершения [Marek and Subrahmanian, 1989]. Обратное, однако, неверно. Например, завершение программы с одним правилом

$p\leftarrow p$

это тавтология $p\leftrightarrow p$. Модель $\emptyset$ этой тавтологии является устойчивой моделью $p\leftarrow p$, но это другая модель $\{p\}$ нет. Франсуа Фаж [1994] нашел синтаксическое условие для логических программ, которое устраняет такие контрпримеры и гарантирует стабильность каждой модели завершения программы. Программы, удовлетворяющие его условию, называются жесткими .

Фанчжэнь Линь и Ютин Чжао [2004] показали, как сделать завершение нежесткой программы более сильным, чтобы исключить все ее нестабильные модели. Дополнительные формулы, которые они добавляют к завершению, называются формулами цикла .

Хорошо обоснованная семантика

Хорошо обоснованная модель логической программы делит все основные атомы на три набора: истинные, ложные и неизвестные. Если атом верен в хорошо обоснованной модели $P$ то оно принадлежит каждой стабильной модели $P$. Обратное, как правило, неверно. Например, программа

$p\leftarrow \operatorname {not} q$

$q\leftarrow \operatorname {not} p$

$r\leftarrow p$

$r\leftarrow q$

имеет две стабильные модели, $\{p,r\}$ и $\{q,r\}$. Несмотря на то $r$ принадлежит им обоим, его значение в обоснованной модели неизвестно .

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

Сильное отрицание

Представление неполной информации

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

В контексте логического программирования эта идея приводит к необходимости различать два вида отрицания — отрицание как неудачу , рассмотренное выше, и сильное отрицание , которое здесь обозначается $\sim$. Следующий пример, иллюстрирующий разницу между двумя видами отрицания, принадлежит Джону Маккарти . Школьный автобус может пересекать железнодорожные пути при условии отсутствия приближающегося поезда. Если мы не обязательно знаем, приближается ли поезд, то правило, использующее отрицание как неудачу,

${\hbox{Cross}}\leftarrow {\hbox{not Train}}$

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

${\hbox{Cross}}\leftarrow \,\sim {\hbox{Train}}.$

Там написано, что переходить дорогу можно, если мы знаем , что поезд не приближается.

Согласованные стабильные модели

Чтобы включить сильное отрицание в теорию стабильных моделей, Гельфонд и Лифшиц [1991] допустили каждое из выражений $A$, $B_{i}$, $C_{i}$ в правиле

$A\leftarrow B_{1},\dots ,B_{m},\operatorname {not} C_{1},\dots ,\operatorname {not} C_{n}$

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

Альтернативный подход [Феррарис и Лифшиц, 2005] рассматривает сильное отрицание как часть атома и не требует каких-либо изменений в определении устойчивой модели. В этой теории сильного отрицания мы различаем атомы двух видов, положительные и отрицательные , и предполагаем, что каждый отрицательный атом является выражением формы ${\sim }A$, где $A$ является положительным атомом. Набор атомов называется когерентным , если он не содержит «дополнительных» пар атомов. $A,{\sim }A$. Когерентные устойчивые модели программы идентичны ее непротиворечивым множествам ответов в смысле [Гельфонд и Лифшиц, 1991].

Например, программа

$p\leftarrow \operatorname {not} q$

$q\leftarrow \operatorname {not} p$

$r$

${\sim }r\leftarrow \operatorname {not} p$

имеет две стабильные модели, $\{p,r\}$ и $\{q,r,{\sim }r\}$. Первая модель является последовательной; второй нет, потому что он содержит как атом $r$ и атом ${\sim }r$.

Предположение о закрытом мире

Согласно [Гельфонд и Лифшиц, 1991], предположение о замкнутом мире для предиката $p$ можно выразить правилом

$\sim p(X_{1},\dots ,X_{n})\leftarrow \operatorname {not} p(X_{1},\dots ,X_{n})$

(отношение $p$ не выполняется для кортежа $X_{1},\dots ,X_{n}$ если нет доказательств того, что это так). Например, стабильная модель программы

$p(a,b)$

$p(c,d)$

$\sim p(X,Y)\leftarrow \operatorname {not} p(X,Y)$

состоит из 2 положительных атомов

$p(a,b),p(c,d)$

и 14 отрицательных атомов

$\sim p(a,a),{\sim }p(a,c),\dots$

т. е. сильные отрицания всех других положительных основных атомов, образованных из $p,a,b,c,d$.

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

Программы с ограничениями

Семантика устойчивой модели была обобщена на многие виды логических программ, помимо наборов «традиционных» правил, обсуждавшихся выше, — правил вида

$A\leftarrow B_{1},\dots ,B_{m},\operatorname {not} C_{1},\dots ,\operatorname {not} C_{n}$

где $A,B_{1},\dots ,B_{m},C_{1},\dots ,C_{n}$ являются атомами. Одно простое расширение позволяет программам содержать ограничения — правила с пустым заголовком:

$\leftarrow B_{1},\dots ,B_{m},\operatorname {not} C_{1},\dots ,\operatorname {not} C_{n}.$

Напомним, что традиционное правило можно рассматривать как альтернативную запись пропозициональной формулы, если мы отождествляем запятую с союзом $\land$, символ $\operatorname {not}$ с отрицанием $\neg$и соглашаемся лечить $F\leftarrow G$ как следствие $G\rightarrow F$ написано наоборот. Чтобы распространить это соглашение на ограничения, мы идентифицируем ограничение с отрицанием формулы, соответствующей его телу:

$\neg (B_{1}\land \cdots \land B_{m}\land \neg C_{1}\land \cdots \land \neg C_{n}).$

Теперь мы можем распространить определение стабильной модели на программы с ограничениями. Как и в случае с традиционными программами, для определения устойчивых моделей мы начинаем с программ, не содержащих отрицания. Такая программа может быть непоследовательной; тогда мы говорим, что у него нет устойчивых моделей. Если такая программа $P$ тогда последовательно $P$ имеет уникальную минимальную модель, и эта модель считается единственной стабильной моделью $P$.

Далее с помощью редуктов определяются стабильные модели произвольных программ с ограничениями, формируемые так же, как и в случае традиционных программ (см. определение стабильной модели выше). Набор $I$ атомов — это стабильная модель программы $P$ с ограничениями, если сокращение $P$ относительно $I$ имеет стабильную модель, и эта стабильная модель равна $I$.

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

Ограничения играют важную роль в программировании набора ответов , поскольку добавление ограничения в логическую программу $P$ влияет на сбор стабильных моделей $P$ очень простым способом: он исключает стабильные модели, нарушающие ограничение. Другими словами, для любой программы $P$ с ограничениями и любым ограничением $C$, стабильные модели $P\cup \{C\}$ можно охарактеризовать как устойчивые модели $P$ которые удовлетворяют $C$.

Дизъюнктивные программы

Основная статья: Дизъюнктивный журнал данных

В дизъюнктивном правиле головкой может быть дизъюнкция нескольких атомов:

$A_{1};\dots ;A_{k}\leftarrow B_{1},\dots ,B_{m},\operatorname {not} C_{1},\dots ,\operatorname {not} C_{n}$

(точка с запятой рассматривается как альтернативное обозначение дизъюнкции $\lor$). Традиционные правила соответствуют $k=1$и ограничения на $k=0$. Чтобы распространить семантику стабильной модели на дизъюнктивные программы [Гельфонд и Лифшиц, 1991], мы сначала определяем, что в отсутствие отрицания ( $n=0$ в каждом правиле) устойчивыми моделями программы являются ее минимальные модели. Определение редукции для дизъюнктивных программ остается таким же, как и раньше . Набор $I$ атомов является устойчивой моделью $P$ если $I$ представляет собой стабильную модель сокращения $P$ относительно $I$.

Например, набор $\{p,r\}$ является устойчивой моделью дизъюнктивной программы

$p;q$

$r\leftarrow \operatorname {not} q$

потому что это одна из двух минимальных моделей редукции

$p;q$

$r.$

В приведенной выше программе есть еще одна стабильная модель: $\{q\}$.

Как и в случае с традиционными программами, каждый элемент любой устойчивой модели дизъюнктивной программы $P$ является головным атомом $P$, в том смысле, что это происходит в голове одного из правил $P$. Как и в традиционном случае, устойчивые модели дизъюнктивной программы минимальны и образуют антицепь. Проверка того, имеет ли конечная дизъюнктивная программа стабильную модель, заключается в следующем. $\Sigma _{2}^{\rm {P}}$-полный [Эйтер и Готтлоб, 1993].

Стабильные модели множества пропозициональных формул

Правила, и даже дизъюнктивные правила , имеют довольно особую синтаксическую форму, по сравнению с произвольными пропозициональными формулами . Каждое дизъюнктивное правило по сути является импликацией, так что его антецедент (тело правила) представляет собой соединение литералов , а его консеквент (голова) — это дизъюнкция атомов. Дэвид Пирс [1997] и Паоло Феррарис [2005] показали, как распространить определение стабильной модели на наборы произвольных пропозициональных формул. Это обобщение имеет применение при программировании множеств .

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

Общее определение стабильной модели

Согласно [Феррарис, 2005], редукция пропозициональной формулы $F$ относительно набора $I$ атомов - это формула, полученная из $F$ путем замены каждой максимальной подформулы, которая не удовлетворяется на $I$ с логической константой $\bot$ (ЛОЖЬ). Сокращение ​ набора $P$ пропозициональных формул относительно $I$ состоит из редукций всех формул из $P$ относительно $I$. Как и в случае с дизъюнктивными программами, мы говорим, что множество $I$ атомов является устойчивой моделью $P$ если $I$ минимальна (относительно включения множеств) среди моделей редукции $P$ относительно $I$.

Например, сокращение множества

$\{p,p\land q\rightarrow r,p\land \neg q\rightarrow s\}$

относительно $\{p,s\}$ является

$\{p,\bot \rightarrow \bot ,p\land \neg \bot \rightarrow s\}.$

С $\{p,s\}$ является моделью редукции, а соответствующие подмножества этого набора не являются моделями редукции, $\{p,s\}$ является устойчивой моделью данного набора формул.

Мы видели это $\{p,s\}$ также является устойчивой моделью той же формулы, записанной в обозначениях логического программирования, в смысле исходного определения . Это пример общего факта: применительно к набору традиционных правил (формул, соответствующих) определение стабильной модели согласно Феррарису эквивалентно исходному определению. То же самое верно, в более общем плане, для программ с ограничениями и для дизъюнктивных программ .

Свойства общей семантики стабильной модели

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

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

$p\lor \neg p$

имеет две стабильные модели, $\emptyset$ и $\{p\}$. Последний не является минимальным и является надстройкой первого.

Проверка того, имеет ли конечный набор пропозициональных формул устойчивую модель, - это $\Sigma _{2}^{\rm {P}}$-полный , как и в случае дизъюнктивных программ .

См. также

• Программирование набора ответов
• Логическое программирование
• Отрицание как неудача

Ссылки

• Бидуа, Н.; Фруадево, К. (1987). «Минимализм включает в себя логику и ограничения по умолчанию». Материалы: Симпозиум по логике в информатике , Итака, Нью-Йорк, 22-25 июня 1987 г. Издательство Компьютерного общества IEEE. стр. 89–97. ISBN  978-0-8186-0793-6 . 87CH2464-6.
• Эйтер, Т.; Готтлоб, Г. (1993). «Результаты о сложности дизъюнктивного логического программирования и приложения к немонотонной логике» . ILPS '93: Материалы международного симпозиума 1993 года по логическому программированию . МТИ Пресс. стр. 266–278. ISBN  978-0-262-63152-5 .
• ван Эмден, М.; Ковальски, Р. (1976). «Семантика логики предикатов как языка программирования» (PDF) . Журнал АКМ . 23 (4): 733–742. CiteSeerX   10.1.1.64.9246 . дои : 10.1145/321978.321991 . S2CID   11048276 .
• Фагес, Ф. (1994). «Состоятельность пополнения Кларка и существование устойчивых моделей» . Журнал методов логики в информатике . 1 : 51–60. CiteSeerX   10.1.1.48.2157 .
• Феррарис, П. (2005). «Множества ответов для пропозициональных теорий» . Логическое программирование и немонотонное рассуждение. ЛПНМР 2005 . Конспекты лекций по информатике. Том. 3662. Спрингер. стр. 119–131. CiteSeerX   10.1.1.129.5332 . дои : 10.1007/11546207_10 . ISBN  978-3-540-31827-9 .
• Феррарис, П.; Лифшиц, В. (2005). «Математические основы программирования множества ответов» . Мы им покажем! Очерки в честь Дова Габая . Публикации Королевского колледжа. стр. 615–664. CiteSeerX   10.1.1.79.7622 .
• Гельфонд, М. (1987). «О стратифицированных автоэпистемических теориях» (PDF) . AAAI'87: Материалы шестой Национальной конференции по искусственному интеллекту . стр. 207–211. ISBN  978-0-934613-42-2 .
• Гельфонд, М.; Лифшиц, В. (1988). «Семантика стабильной модели для логического программирования» . Материалы Пятой Международной конференции по логическому программированию (ICLP) . МТИ Пресс. стр. 1070–80. ISBN  978-0-262-61054-4 .
• Гельфонд, М.; Лифшиц, В. (1991). «Классическое отрицание в логических программах и дизъюнктивных базах данных» . Компьютеры нового поколения . 9 (3–4): 365–385. CiteSeerX   10.1.1.49.9332 . дои : 10.1007/BF03037169 . S2CID   13036056 .
• Хэнкс, С.; Макдермотт, Д. (1987). «Немонотонная логика и временная проекция» . Искусственный интеллект . 33 (3): 379–412. дои : 10.1016/0004-3702(87)90043-9 .
• Лин, Ф.; Чжао, Ю. (2004). «ASSAT: вычисление наборов ответов логической программы решателями SAT» (PDF) . Искусственный интеллект . 157 (1–2): 115–137. дои : 10.1016/j.artint.2004.04.004 . S2CID   514581 .
• Марек, В.; Субраманиан, В.С. (1989). «Взаимосвязь между семантикой логической программы и немонотонными рассуждениями». Логическое программирование: материалы шестой международной конференции . МТИ Пресс. стр. 600–617. ISBN  978-0-262-62065-9 .
• Пирс, Д. (1997). «Новая логическая характеристика устойчивых моделей и наборов ответов» (PDF) . Немонотонные расширения логического программирования . Конспект лекций по искусственному интеллекту. Том. 1216. стр. 57–70. дои : 10.1007/BFb0023801 . ISBN  978-3-540-68702-3 .
• Райтер, Р. (1980). «Логика рассуждений по умолчанию» (PDF) . Искусственный интеллект . 13 (1–2): 81–132. дои : 10.1016/0004-3702(80)90014-4 .