Horn-Lauseke

Horn-lauseke on logiikan disjunktio, jossa enintään yksi kirjaimista on positiivinen ja kaikki muut ovat negatiivisia. Se on nimetty Alfred Hornin mukaan, joka kuvasi ne artikkelissaan vuonna 1951.

Hornin lauseke, jossa on täsmälleen yksi positiivinen kirjainlause, on definitiivinen lauseke; definitiivistä lauseketta, jossa ei ole negatiivisia kirjaimia, kutsutaan joskus "faktaksi"; ja Hornin lauseketta, jossa ei ole positiivista kirjainta, kutsutaan joskus tavoitelauseeksi. Näitä kolmea Horn-lauseen tyyppiä havainnollistetaan seuraavassa lause-esimerkissä:

määräinen lauseke: ¬ p ¬ q ∨ ⋯ ∨ ¬ t u {\displaystyle \neg p\lor \neg q\vee \cdots \vee \neg t\vee u} {\displaystyle \neg p\lor \neg q\vee \cdots \vee \neg t\vee u}

fact: u {\displaystyle u} {\displaystyle u}

maalilauseke: ¬ p ¬ q ∨ ⋯ ∨ ¬ t {\displaystyle \neg p\lor \neg q\vee \cdots \vee \neg t} {\displaystyle \neg p\lor \neg q\vee \cdots \vee \neg t}

Ei-propositionaalisessa tapauksessa kaikki lausekkeen muuttujat ovat implisiittisesti universaalisti kvantifioituja koko lausekkeen laajuudella. Näin ollen esimerkiksi:

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

tarkoittaa:

X ( ¬ human ( X ) mortal ( X ) ) {\displaystyle \forall X(\neg {\text{human}}(X)\lor {\text{mortal}}(X))} } {\displaystyle \forall X(\neg {\text{human}}(X)\lor {\text{mortal}}(X))}

joka vastaa loogisesti:

X ( ihminen ( X ) → kuolevainen ( X ) ) . {\displaystyle \forall X({\text{human}}(X)\rightarrow {\text{mortal}}(X)). } {\displaystyle \forall X({\text{human}}(X)\rightarrow {\text{mortal}}(X)).}

Horn-lausekkeilla on perustavanlaatuinen asema konstruktiivisessa logiikassa ja laskennallisessa logiikassa. Ne ovat tärkeitä automaattisessa lauseen todistamisessa ensimmäisen järjestyksen resoluution avulla, koska kahden Horn-lauseen resoluutio on itse Horn-lause, ja tavoitelauseen ja lopullisen lauseen resoluutio on tavoitelause. Nämä Horn-lausekkeiden ominaisuudet voivat johtaa suurempaan tehokkuuteen todistettaessa teoreemaa (joka esitetään tavoitelauseen negaationa).

Horn-lausekkeet ovat myös logiikkaohjelmoinnin perusta, jossa on tavallista kirjoittaa määrämuotoisia lausekkeita implikaation muodossa:

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

Tavoitelausekkeen resoluutio lopullisella lausekkeella uuden tavoitelausekkeen tuottamiseksi on itse asiassa logiikkaohjelmoinnin ja ohjelmointikielen Prologin toteuttamisessa käytetyn SLD-resoluution päättelysäännön perusta.

Logiikkaohjelmoinnissa määrittelylauseke käyttäytyy kuin tavoite-reduktiomenettely. Esimerkiksi edellä kirjoitettu Horn-lauseke käyttäytyy kuin menettely:

näyttää u {\displaystyle u}{\displaystyle u} , näyttää p {\displaystyle p}{\displaystyle p} ja näyttää q {\displaystyle q}q ja {\displaystyle \cdots }. {\displaystyle \cdots }ja show t {\displaystyle t} {\displaystyle t}

Tämän lausekkeen taaksepäin suuntautuvan käytön korostamiseksi se kirjoitetaan usein taaksepäin suuntautuvassa muodossa:

u ← ( p q ∧ ∧ ⋯ ∧ t ) {\displaystyle u\leftarrow (p\land q\land \cdots \land t)} {\displaystyle u\leftarrow (p\land q\land \cdots \land t)}

Prologissa tämä kirjoitetaan seuraavasti:

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

Prologin merkintätapa on itse asiassa moniselitteinen, ja myös termiä "tavoitelause" käytetään joskus moniselitteisesti. Tavoitelausekkeen muuttujat voidaan lukea universaalisti tai eksistentiaalisesti kvantifioiduiksi, ja "false"-lausekkeen johtaminen voidaan tulkita joko ristiriidan johtamiseksi tai ratkaistavan ongelman onnistuneen ratkaisun johtamiseksi.

Van Emden ja Kowalski (1976) tutkivat Horn-lausekkeiden malliteoreettisia ominaisuuksia loogisen ohjelmoinnin yhteydessä ja osoittivat, että jokaisella määräisten lausekkeiden joukolla D on ainutkertainen minimimalli M. Atomikaava A on loogisesti implikoitu D:llä, jos ja vain jos A on tosi M:ssä. Tästä seuraa, että ongelma P, jota edustaa positiivisten literaalien eksistentiaalisesti kvantifioitu konjunktio, on loogisesti implikoitu D:llä, jos ja vain jos P on tosi M:ssä. Horn-lausekkeiden minimimallin semantiikka on logiikkaohjelmien stabiilin mallin semantiikka.

Propositionaaliset Horn-lausekkeet ovat kiinnostavia myös laskennallisen kompleksisuuden kannalta, jossa ongelma totuusarvojen löytämiseksi, jotta propositionaalisten Horn-lausekkeiden konjunktio olisi tosi, on P-täydellinen ongelma (itse asiassa ratkaistavissa lineaarisessa ajassa), jota kutsutaan joskus HORNSAT:ksi. (Rajoittamaton Boolen tyydyttävyysongelma on kuitenkin NP-täydellinen ongelma.) Ensimmäisen asteen Horn-lausekkeiden tyydyttävyys on ratkaisematon.

Kysymyksiä ja vastauksia

K: Mikä on sarvilauseke?


V: Horn-lauseke on logiikan disjunktio literaaleista, joissa korkeintaan yksi literaaleista on positiivinen ja kaikki muut ovat negatiivisia.

K: Kuka kuvasi ne ensimmäisenä?


V: Alfred Horn kuvasi ne ensimmäisen kerran vuonna 1951 julkaistussa artikkelissa.

Kysymys: Mikä on definitiivinen lauseke?


V: Hornin lauseketta, jossa on täsmälleen yksi positiivinen literaali, kutsutaan definitiiviseksi lausekkeeksi.

K: Mikä on fakta?


V: Määritelmälausetta, jossa ei ole yhtään negatiivista kirjainta, kutsutaan joskus "faktaksi".

K: Mikä on tavoitelause?


V: Hornin lauseketta, jossa ei ole yhtä positiivista kirjainta, kutsutaan joskus tavoitelauseeksi.

K: Miten muuttujat toimivat ei-propositiotapauksissa?


V: Ei-propositionaalisessa tapauksessa kaikki lausekkeen muuttujat ovat implisiittisesti universaalisti kvantifioituja koko lausekkeen soveltamisalalla. Tämä tarkoittaa, että ne koskevat lausekkeen jokaista osaa.

K: Mikä rooli Hornin lausekkeilla on konstruktiivisessa logiikassa ja laskennallisessa logiikassa? V: Horn-lausekkeilla on tärkeä rooli automaattisessa lauseen todistamisessa ensimmäisen asteen resoluution avulla, koska kahden Horn-lausekkeen resoluutiota tai yhden tavoite- ja yhden määrälausekkeen välistä resoluutiota voidaan käyttää luomaan suurempaa tehokkuutta, kun todistetaan jotakin, joka on esitetty sen tavoite-lausekkeen negaationa. Niitä käytetään myös loogisten ohjelmointikielten, kuten Prologin, perustana, jossa ne käyttäytyvät kuin maalinreduktiomenetelmät.

AlegsaOnline.com - 2020 / 2023 - License CC3