Horn klauzule - Horn clause

v matematická logika a logické programování, a Horn klauzule je logický vzorec konkrétní formy podobné pravidlu, která mu dává užitečné vlastnosti pro použití v logickém programování, formální specifikace, a teorie modelů. Klauzule Horn jsou pojmenovány pro logika Alfred Horn, kteří poprvé poukázali na jejich význam v roce 1951.^[1]

Definice

Horn klauzule je doložka (A disjunkce z literály ) s nejvýše jedním pozitivním, tj. nezrušený, doslovně.

Naopak disjunkce literálů s maximálně jedním negovaným literálem se nazývá a doložka o dvojím klaksonu.

Horn klauzule s přesně jedním kladným literálem je a určitá klauze nebo a přísná klauze Horn;^[2] definitivní klauze bez negativních literálů se někdy nazývá a jednotková klauze,^[3] a jednotková klauze bez proměnných se někdy nazývá a skutečnost;^[4] a Hornova klauze bez pozitivního literálu se někdy nazývá a doložka o cíli (všimněte si, že prázdná věta skládající se z žádných literálů je klauzule cíle). Následující tři typy Hornových klauzulí jsou ilustrovány níže propoziční příklad:

V non-propoziční případ, všechny proměnné^{[poznámka 2]} v klauzuli jsou implicitně všeobecně kvantifikováno přičemž rozsahem je celá klauzule. Například:

¬ člověk(X) ∨ smrtelný(X)

znamená:

∀X (¬ člověk(X) ∨ smrtelný(X) )

což je logicky ekvivalentní:

∀X ( člověk(X) → smrtelný(X) )

Význam

Horn klauze hrají základní roli v konstruktivní logika a výpočetní logika. Jsou důležité v automatizované dokazování věty podle rozlišení prvního řádu, protože rozpouštědlo dvou Hornových klauzulí je sama Hornovou klauzí a resolvence cílové klauze a definitivní klauze je klauzule cíle. Tyto vlastnosti Hornových klauzí mohou vést k větší efektivitě při dokazování věty (představované jako negace klauzule o cíli).

Zajímavé jsou také propoziční klauzule výpočetní složitost. Problém nalezení přiřazení hodnoty pravdy k uskutečnění konjunkce výrokových Hornových vět je a P-kompletní problém, řešitelný v lineární čas,^[5] a někdy volal HORNSAT. (Neomezený Booleovský problém uspokojivosti je NP-kompletní problém však.) Splnitelnost Hornových klauzulí prvního řádu je nerozhodnutelný.^{[Citace je zapotřebí ]}

Logické programování

Hornovy doložky jsou rovněž základem logické programování, kde je běžné psát určité věty ve tvaru implikace:

(p ∧ q ∧ ... ∧ t) → u

Ve skutečnosti je řešení cílové klauze s definitivní klauzí k vytvoření nové cílové klauzule základem Rozlišení SLD pravidlo odvození, které se používá k implementaci logické programování v programovacím jazyce Prolog.

V logickém programování se určitá klauzule chová jako postup snižování cíle. Například klauzule Horn napsaná výše se chová jako procedura:

ukázat u, ukázat p a ukázat q a ... a ukázat t.

Aby se zdůraznilo toto obrácené použití klauze, je často psáno v obrácené formě:

u ← (p ∧ q ∧ ... ∧ t)

v Prolog toto se píše jako:

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

v logické programování a datalog, výpočet a vyhodnocení dotazu se provádí vyjádřením popření problému, který má být vyřešen, jako klauzule cíle. Například problém řešení existenciálně kvantifikované konjunkce pozitivních literálů:

∃X (p ∧ q ∧ ... ∧ t)

je reprezentován negací problému (popřením, že má řešení) a jeho reprezentací v logicky ekvivalentní formě klauzule cíle:

∀X (Nepravdivé ← p ∧ q ∧ ... ∧ t)

v Prolog toto se píše jako:

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

Řešení problému znamená odvození rozporu, který představuje prázdná klauzule (nebo „false“). Řešením problému je substituce termínů za proměnné v klauzuli cíle, které lze vyvodit z důkazu rozporu. Tímto způsobem jsou brankové klauze podobné spojovací dotazy v relačních databázích a logika klauze Horn je ekvivalentní ve výpočetní síle a univerzální Turingův stroj.

Prologova notace je ve skutečnosti nejednoznačná a termín „klauzule cíle“ se někdy také používá nejednoznačně. Proměnné v klauzuli cíle lze číst jako univerzálně nebo existenčně kvantifikované a odvození „false“ lze interpretovat buď jako odvození rozporu, nebo jako odvození úspěšného řešení problému, který má být vyřešen.

Van Emden a Kowalski (1976) zkoumali modelové teoretické vlastnosti Hornových klauzulí v kontextu logického programování a prokázali, že každá sada definitivních klauzí D má jedinečný minimální model M. Atomový vzorec A logicky implikuje D kdyby a jen kdyby A je pravda v M. Z toho vyplývá, že problém P reprezentovaný existenciálně kvantifikovanou spojkou pozitivních literálů logicky implikuje D kdyby a jen kdyby P je pravda v M. Minimální modelová sémantika Hornových klauzí je základem pro stabilní sémantika modelu logických programů.^[6]

Poznámky

Reference