Хорновский дизъюнкт
Клаузула Хорна - это логическая дизъюнкция букв, где в большинстве случаев один из букв является положительным, а все остальные - отрицательным. Она названа в честь Альфреда Хорна, который описал их в статье в 1951 году.
Оговорка Хорна с одним положительным литералом - это определенная оговорка; определенная оговорка без отрицательных литералов иногда называется "фактом"; а оговорка Хорна без положительного литерала иногда называется пунктом цели. Эти три вида пунктов Horn проиллюстрированы в следующем пропозиционном примере:
определённое положение: ¬ p ∨ ¬ q ∨ ⋯ ¬ t ∨ u {\displaystyle \neg \neg p\lor \neg q\vee \cdots \vee \neg t\vee u} 
факт: u {\displaystyle u} 
целевая оговорка: ¬ p ∨ ¬ q ∨ ⋯ ∨ ¬ t {\displaystyle \neg \neg p\lor \neg q\vee \cdots \vee \neg t} 
В непроизводственном случае все переменные в клаузуле имплицитно универсально подсчитываются с охватом всего клаузула. Так, например:
¬ человеческий (X) ∨ смертный (X) {\displaystyle \neg {\text{human}}(X) \lor {\text{mortal}}(X) } 
означает:
∀ X ( ¬ человеческий (X) ∨ смертный (X) ) {\displaystyle \forall X(\neg {\text{human}}(X)\lor {\text{mortal}}(X))} 
что логически эквивалентно:
∀ X ( human ( X ) → mortal ( X ) ) . {\displaystyle \forall X({\text{human}}(X)\rightarrow {\text{mortal}}(X)). } 
Роговые клаузулы играют основную роль в конструктивной и вычислительной логике. Они важны в автоматической теореме, доказываемой разрешением первого порядка, потому что разрешение двух клаузул Хорна само по себе является клаузулой Хорна, а разрешение клаузулы цели и определенной клаузулы - клаузулой цели. Эти свойства клаузул Хорна могут привести к большей эффективности в доказательстве теоремы (представляемой как отрицание клаузулы цели).
Оговорки Horn также являются основой логического программирования, где принято писать определенные пункты в виде подтекста:
(p ∧ q ∧ ⋯ ∧ t) → u {\displaystyle (p\wedge q\wedge \cdots \wedge t)\rightarrow u} 
На самом деле, разрешение целевого пункта с определенным пунктом для создания нового целевого пункта является основой правила разрешения SLD умозаключений, используемого для реализации логического программирования и языка программирования Prolog.
В логическом программировании определенное условие ведет себя как процедура снижения цели. Например, написанное выше выражение Horn ведет себя как процедура:
чтобы показать u {\displaystyle u} , show p {\displaystyle p}
и show q {\displaystyle q}
и ⋯ {\displaystyle \cdots } 
и показать t{\displaystyle t}
.
Чтобы подчеркнуть это обратное использование пункта, его часто пишут в обратной форме:
u ← ( p ∧ q ∧ ⋯ ∧ t ) {\displaystyle u\leftarrow (p\land q\land \cdots \land t)} 
В Прологе это написано как:
u:- p, q, ..., t.Нотация Пролога на самом деле неоднозначна, а термин "пункт цели" иногда также используется неоднозначно. Переменные в пункте цели могут быть истолкованы как универсальные или экзистенциально квантифицированные, а выведение "ложных" может быть истолковано как выведение противоречия или как выведение успешного решения решаемой проблемы.
Ван Эмден и Ковальский (1976) исследовали модельные теоретические свойства клаузул Хорна в контексте логического программирования, показав, что каждое множество определённых клаузул D имеет уникальную минимальную модель M. Атомная формула A логически подразумевается D, если и только если A верна в M. Из этого следует, что задача P, представленная экзистенциально квантифицированным соединением положительных литералов, логически подразумевается D, если и только если P верна в M. Минимальная модельная семантика клаузул Хорна является основой стабильной модельной семантики логических программ.
Пропозиционные положения Горна представляют интерес и в вычислительной сложности, где проблема нахождения истинного значения задания для того, чтобы сделать верным сочетание проекционных положений Горна - это Р-задача (на самом деле разрешимая в линейном времени), иногда называемая Горнасатом. (Однако неограниченная Булева проблема удовлетворительности является NP-завершенной задачей). Удовлетворительность клаузул первого порядка неосуществима.
Вопросы и ответы
В: Что такое клаузула Хорна?
О: Клауза Хорна - это логическая дизъюнкция литералов, в которой как минимум один из литералов является положительным, а все остальные - отрицательными.
В: Кто впервые описал их?
О: Альфред Хорн впервые описал их в статье в 1951 году.
В: Что такое определенная клауза?
О: Клауза Хорна с ровно одним положительным литералом называется определенной клаузой.
В: Что такое факт?
О: Определенная клауза без отрицательных литералов иногда называется "фактом".
В: Что такое целевая клауза?
О: Роговая клауза без положительного литерала иногда называется клаузой цели.
В: Как работают переменные в непропозициональных случаях?
О: В непропозициональном случае все переменные в клаузе неявно универсально квантифицированы с областью применения всей клаузы. Это означает, что они применяются к каждой части высказывания.
В: Какую роль играют формулы Хорна в конструктивной логике и вычислительной логике? О: Клаузы Хорна играют важную роль в автоматизированном доказательстве теорем методом разрешения первого порядка, поскольку резольвента между двумя клаузами Хорна или между одной целью и одной определенной клаузой может быть использована для создания большей эффективности при доказательстве чего-либо, представленного как отрицание его целевой клаузы. Они также используются в качестве основы для языков логического программирования, таких как Prolog, где они ведут себя как процедуры сокращения целей.
