Оговорка о роге - 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]

Примечания

  1. ^ Как в разрешение теоремы доказательство интуитивно понятные значения "показать φ" и "предполагать ¬φ" являются синонимами (косвенное доказательство ); они оба соответствуют одной и той же формуле, а именно. ¬φ. Таким образом, механический инструмент доказательства должен поддерживать только один набор формул (предположений), а не два набора (предположения и (под) цели).
  2. ^ Имена компонентов формулы различаются между Логика высказываний и Логика первого порядка. Атомарная формула - это просто пропозициональная переменная в первом, тогда как во втором он состоит из предикатного символа и, соответственно, многих термины, каждый из которых может содержать переменные домена. Здесь подразумеваются доменные переменные.

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

  1. ^ Хорн, Альфред (1951). «О предложениях, истинных о прямых союзах алгебр». Журнал символической логики. 16 (1): 14–21. Дои:10.2307/2268661. JSTOR  2268661.
  2. ^ Маковски (1987). «Почему формулы Хорна имеют значение в компьютерных науках: исходные структуры и общие примеры» (PDF). Журнал компьютерных и системных наук. 34 (2–3): 266–292. Дои:10.1016/0022-0000(87)90027-4.
  3. ^ Басс, Сэмюэл Р. (1998). «Введение в теорию доказательств». В Сэмюэле Р. Бассе (ред.). Справочник по теории доказательств. Исследования по логике и основам математики. 137. Эльзевир Б.В. С. 1–78. Дои:10.1016 / S0049-237X (98) 80016-5. ISBN  978-0-444-89840-1. ISSN  0049-237X.
  4. ^ Лау и Орнаги (2004). "Определение композиционных единиц для правильной разработки программ в вычислительной логике". Конспект лекций по информатике. 3049: 1–29. Дои:10.1007/978-3-540-25951-0_1. ISBN  978-3-540-22152-4.
  5. ^ Доулинг, Уильям Ф .; Галье, Жан Х. (1984). "Линейные алгоритмы времени для проверки выполнимости пропозициональных формул Хорна". Журнал логического программирования. 1 (3): 267–284. Дои:10.1016/0743-1066(84)90014-1.
  6. ^ van Emden, M. H .; Ковальский, Р.А. (1976). «Семантика логики предикатов как языка программирования» (PDF). Журнал ACM. 23 (4): 733–742. CiteSeerX  10.1.1.64.9246. Дои:10.1145/321978.321991.