Klauzula Horna

Klauzula Rogu jest logicznym rozszczepieniem literówek, gdzie co najwyżej jedna z nich jest pozytywna, a wszystkie inne negatywne. Nazwa pochodzi od Alfreda Horna, który opisał je w artykule w 1951 roku.

Klauzula Rogowa z dokładnie jedną dosłownością dodatnią jest klauzulą ostateczną; klauzula ostateczna bez dosłowności ujemnej jest czasami nazywana "faktem", a klauzula Rogowa bez dosłowności dodatniej jest czasami nazywana klauzulą celu. Te trzy rodzaje klauzuli rogu są zilustrowane w poniższym przykładzie:

klauzula określona: ¬ p ∨ ¬ q ∨ ⋯ ∨ ¬ t ∨ u ¬displaystyle \neg p\neg q \neg q \vee \neg t\neg t\vee u} $\neg p\lor \neg q\vee \cdots \vee \neg t\vee u$

Fakt: u {\i1}Style u{\i1} $u$

klauzula o celu:

W przypadku nieprzysposobienia, wszystkie zmienne w klauzuli są w sposób dorozumiany powszechnie określone ilościowo, z zakresem całej klauzuli. Tak więc, na przykład:

¬ human ( X ) ∨ mortal ( X ) {\i1} {\i1}displaystyle {\i1}neg {\i1}text{\i1}(X){\i1}lor {\i1}(X){\i1} $\neg {\text{human}}(X)\lor {\text{mortal}}(X)$

oznacza:

∀ X ( ¬ ludzki ( X ) ∨ śmiertelny ( X ) ) {\i1}Styl stylistyczny {\i0} {\i1}dla wszystkich X(\i0}(X){\i0}(X)){\i0} $\forall X(\neg {\text{human}}(X)\lor {\text{mortal}}(X))$

co jest logicznie równoznaczne z:

∀ X ( człowiek ( X ) → śmiertelny ( X ) ) . {\i1}(X){\i1}{\i1}{\i1}wszystkim X(X){\i0}(tekst ludzki){\i0}(X){\i1}(tekst nieśmiertelny){\i0}(X)). } $\forall X({\text{human}}(X)\rightarrow {\text{mortal}}(X)).$

Klauzule rogów odgrywają podstawową rolę w logice konstrukcyjnej i obliczeniowej. Są one ważne w zautomatyzowanym twierdzeniu udowadniającym poprzez rozwiązywanie pierwszego rzędu, ponieważ rozwiązywanie dwóch klauzul Rogu samo w sobie jest klauzulą Rogu, a rozwiązywanie klauzuli celu i klauzuli ostatecznej jest klauzulą celu. Te wła¶ciwo¶ci klauzul rogowych mog± prowadzić do większej efektywno¶ci w udowodnieniu twierdzenia (reprezentowanego jako negacja klauzuli celu).

Klauzule rogowe są również podstawą programowania logicznego, gdzie powszechnie pisze się konkretne klauzule w formie implikacji:

( p ∧ q ∧ ⋯ ∧ t ) → u {\i1}displaystyle (p\i0}wedge qwedge \i0}cdots \i0}rightarrow u} $(p\wedge q\wedge \cdots \wedge t)\rightarrow u$

W rzeczywistości, rozdzielczość klauzuli celu z określoną klauzulą w celu stworzenia nowej klauzuli celu jest podstawą reguły wnioskowania rezolucji SLD, używanej do implementacji programowania logicznego i języka programowania Prolog.

W programowaniu logicznym konkretna klauzula zachowuje się jak procedura redukcji celów. Na przykład, klauzula Horn napisana powyżej zachowuje się jak procedura:

by pokazać ci styl u $u$ , pokazać styl p $p$ i pokazać styl q i ⋯. $\cdots$ i pokazują styl t $t$ .

Aby podkreślić to wsteczne użycie klauzuli, często jest ona zapisana w formie odwrotnej:

u ← ( p ∧ q ∧ ⋯ ∧ t ) {\i0} {\i1}Style uleftarrow (p\i0}landia q \i0}landia t) $u\leftarrow (p\land q\land \cdots \land t)$

W Prologu jest to napisane jako:

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

Zapis w Prologu jest w rzeczywistości niejednoznaczny, a termin "klauzula celu" jest czasami również używany niejednoznacznie. Zmienne w klauzuli celu mogą być odczytywane jako uniwersalnie lub egzystencjalnie określone ilościowo, a wyprowadzanie "fałszywych" może być interpretowane albo jako wyprowadzanie sprzeczności, albo jako wyprowadzanie udanego rozwiązania problemu, który ma być rozwiązany.

Van Emden i Kowalski (1976) badali teoretyczne właściwości modelu klauzul Horna w kontekście programowania logiki, pokazując, że każdy zestaw zdefiniowanych klauzul D posiada unikalny minimalny model M. Wzór atomowy A jest logicznie implikowany przez D wtedy i tylko wtedy, gdy A jest prawdziwe w M. Wynika z tego, że problem P reprezentowany przez egzystencjalnie kwantyfikowane połączenie dodatnich liter jest logicznie implikowany przez D wtedy i tylko wtedy, gdy P jest prawdziwe w M. Minimalna semantyka modelu klauzul Horna jest podstawą stabilnej semantyki modelu programów logicznych.

Klauzule Propositional Horn są również interesujące w złożoności obliczeniowej, gdzie problem znalezienia przypisania wartości true w celu połączenia klauzul Propositional Horn true jest problemem typu P-complete (w rzeczywistości rozwiązywalnym w czasie liniowym), czasami nazywanym HORNSAT. (Nieograniczony boolejski problem satysfakcji jest jednak problemem NP-complete). Zadawalalność klauzul Horna pierwszego rzędu jest niezdecydowana.

Pytania i odpowiedzi

P: Co to jest klauzula rogowa?

O: Klauzula Horna to logiczna dysjunkcja literałów, gdzie co najwyżej jeden z literałów jest pozytywny, a wszystkie pozostałe są negatywne.

P: Kto pierwszy je opisał?

O: Alfred Horn opisał je po raz pierwszy w artykule z 1951 roku.

P: Co to jest klauzula definitywna?

A: Klauzula Horna z dokładnie jedną literą dodatnią jest nazywana klauzulą definitywną.

P: Co to jest fakt?

A: Klauzula definitywna bez literałów ujemnych jest czasami określana jako "fakt".

P: Co to jest klauzula celu?

A: Klauzula rogowa bez literału dodatniego jest czasami nazywana klauzulą celu.

P: Jak działają zmienne w przypadkach niepropozycyjnych?

O: W przypadku niepropozycyjnym, wszystkie zmienne w klauzuli są domyślnie uniwersalnie kwantyfikowane z zakresem całej klauzuli. Oznacza to, że odnoszą się do każdej części wypowiedzi.

P: Jaką rolę odgrywają klauzule Horna w logice konstrukcyjnej i obliczeniowej? O: Klauzule Horna odgrywają ważną rolę w zautomatyzowanym dowodzeniu twierdzeń przez rozwiązywanie pierwszego rzędu, ponieważ resolvent dwóch klauzul Horna lub między jedną klauzulą celu i jedną klauzulą definitywną może być wykorzystany do zwiększenia wydajności przy dowodzeniu czegoś reprezentowanego jako negacja klauzuli celu. Są one również wykorzystywane jako podstawa języków programowania logicznego, takich jak Prolog, gdzie zachowują się jak procedury redukcji celów.