Оговорка о роге - Horn clause

В математическая логика и логическое программирование, а Оговорка о роге представляет собой логическую формулу определенной формы, подобной правилу, которая придает ей полезные свойства для использования в логическом программировании, формальная спецификация, и теория моделей. Роговые предложения названы в честь логика Альфред Хорн, которые впервые указали на их значение в 1951 г.^[1]

Определение

Оговорка Хорна - это пункт (а дизъюнкция из литералы ) с не более чем одним положительным, т.е. незащищенный, букв.

И наоборот, дизъюнкция литералов с одним отрицательным литералом называется оговорка о двух рогах.

Предложение Хорна с ровно одним положительным литералом - это определенная статья или строгая оговорка Рога;^[2] определенное предложение без отрицательных литералов иногда называют пункт о единице,^[3] а единичное предложение без переменных иногда называют факт;^[4] а предложение Хорна без положительного литерала иногда называют целевое положение (обратите внимание, что пустое предложение, не содержащее литералов, является целевым предложением). Эти три вида предложений Хорна проиллюстрированы ниже. пропозициональный пример:

	Форма дизъюнкции	Последствия форма	Читайте интуитивно как
Определенная оговорка	¬п ∨ ¬q ∨ ... ∨ ¬т ∨ ты	ты ← п ∧ q ∧ ... ∧ т	предположить, что, если п и q и и т все держатся, тогда также ты держит
Факт	ты	ты	предположить, что ты держит
Пункт о цели	¬п ∨ ¬q ∨ ... ∨ ¬т	ложный ← п ∧ q ∧ ... ∧ т	покажи это п и q и и т все держатся [примечание 1]

в непреклонный случай, все переменные^{[заметка 2]} в предложении неявно универсально определяемый со сферой действия всего пункта. Так, например:

¬ человек(Икс) ∨ смертный(Икс)

означает:

∀X (¬ человек(Икс) ∨ смертный(Икс) )

что логически эквивалентно:

∀X ( человек(Икс) → смертный(Икс) )

Значимость

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

Пропозициональные предложения Горна также представляют интерес в вычислительная сложность. Проблема нахождения присвоений значений истинности, чтобы сделать конъюнкцию пропозициональных предложений Хорна истинной, является P-полный проблема, решаемая в линейное время,^[5] и иногда называли HORNSAT. (Неограниченный Проблема логической выполнимости является НП-полный проблема, однако.) Выполнимость предложений Горна первого порядка неразрешимый.^{[нужна цитата ]}

Логическое программирование

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

(п ∧ q ∧ ... ∧ т) → ты

Фактически, решение целевого пункта с определенным предложением для создания нового целевого пункта является основой Разрешение SLD правило вывода, используемое для реализации логическое программирование на языке программирования Пролог.

В логическом программировании определенное предложение ведет себя как процедура приведения к цели. Например, предложение Horn, написанное выше, ведет себя как процедура:

показывать ты, Показать п и показать q и ... и показать т.

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

ты ← (п ∧ q ∧ ... ∧ т)

В Пролог это записывается как:

u: - p, q, ..., t.

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

∃Икс (п ∧ q ∧ ... ∧ т)

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

∀Икс (ложный ← п ∧ q ∧ ... ∧ т)

В Пролог это записывается как:

: - п, д, ..., т.

Решение проблемы сводится к получению противоречия, которое представлено пустым предложением (или «ложным»). Решение проблемы - замена переменных в целевом предложении терминами, которые можно извлечь из доказательства противоречия. Таким образом, целевые предложения похожи на конъюнктивные запросы в реляционных базах данных, а логика предложения Хорна по вычислительной мощности эквивалентна универсальная машина Тьюринга.

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

Ван Эмден и Ковальски (1976) исследовали теоретико-модельные свойства предложений Хорна в контексте логического программирования, показывая, что каждый набор определенных предложений D имеет уникальную минимальную модель M. Атомарная формула А логически подразумевается D если и только если А верно в M. Отсюда следует, что проблема п представленное экзистенциально количественной конъюнкцией положительных литералов, логически подразумевается D если и только если п верно в M. Семантика минимальной модели предложений Хорна является основой для семантика стабильной модели логических программ.^[6]

Примечания

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