Horno išlyga

Horno išlyga - tai loginė literalų disjunkcija, kurioje ne daugiau kaip vienas iš literalų yra teigiamas, o visi kiti - neigiami. Ji pavadinta Alfredo Horno, kuris 1951 m. aprašė ją straipsnyje, vardu.

Horno išlyga, turinti lygiai vieną teigiamą literatūrą, yra apibrėžta išlyga; apibrėžta išlyga, neturinti neigiamų literatūrų, kartais vadinama "faktu"; o Horno išlyga be teigiamos literatūros kartais vadinama tikslo išlyga. Šias tris Horno klauzulių rūšis iliustruoja šis propozicinis pavyzdys:

apibrėžtasis sakinys: ¬ p ∨ ¬ q ∨ ⋯ ∨ ¬ t ∨ u {\displaystyle \neg p\lor \neg q\vee \cdots \vee \neg t\vee u} $\neg p\lor \neg q\vee \cdots \vee \neg t\vee u$

faktas: u {\displaystyle u} $u$

tikslo sąlyga: ¬ p ∨ ¬ q ∨ ⋯ ∨ ¬ t {\displaystyle \neg p\lor \neg q\vee \cdots \vee \neg t} $\neg p\lor \neg q\vee \cdots \vee \neg t$

Nepropoziciniu atveju visi klaustuko kintamieji yra netiesiogiai visuotinai kvantifikuojami ir apima visą klaustuką. Taigi, pvz:

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

reiškia:

∀ X ( ¬ žmogus ( X ) ∨ mirtingasis ( X ) ) {\displaystyle \forall X(\neg {\tekstas{žmogus}}(X)\lor {\tekstas{mirtingas}}(X))} $\forall X(\neg {\text{human}}(X)\lor {\text{mortal}}(X))$

kuris logiškai lygiavertis:

∀ X ( žmogus ( X ) → mirtingasis ( X ) ) . {\displaystyle \forall X({\text{žmogus}}(X)\rightarrow {\text{mortal}}}(X)). } $\forall X({\text{human}}(X)\rightarrow {\text{mortal}}(X)).$

Konstruktyviojoje logikoje ir skaičiavimo logikoje pagrindinis vaidmuo tenka Horno išlygoms. Jie yra svarbūs automatizuotam teoremų įrodymui taikant pirmosios eilės skiriamąją gebą, nes dviejų Horno išlygų rezolventas pats yra Horno išlyga, o tikslo išlygos ir apibrėžtos išlygos rezolventas yra tikslo išlyga. Dėl šių Horno sąlygos savybių galima efektyviau įrodyti teoremą (pateikiamą kaip tikslo sąlygos paneigimą).

Horno sąlygos taip pat yra loginio programavimo pagrindas, kur įprasta rašyti apibrėžtąsias sąlygas implikacijos forma:

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

Iš tikrųjų tikslo sąlygos išskyrimas su apibrėžta sąlyga, siekiant gauti naują tikslo sąlygą, yra SLD išvedimo taisyklės, naudojamos loginiam programavimui ir programavimo kalbai Prolog, pagrindas.

Loginiame programavime apibrėžtoji sąlyga veikia kaip tikslo redukavimo procedūra. Pavyzdžiui, pirmiau užrašyta Horno sąlyga elgiasi kaip procedūra:

rodyti u {\displaystyle u} $u$ , rodyti p {\displaystyle p} $p$ ir rodyti q {\displaystyle q} ir ⋯ {\displaystyle \cdots } $\cdots$ ir show t {\displaystyle t} $t$ .

Norint pabrėžti šį atvirkštinį sakinio vartojimą, jis dažnai rašomas atvirkštine forma:

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

Prologe tai užrašoma taip:

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

Prologo užrašas iš tikrųjų yra dviprasmiškas, o terminas "tikslo sąlyga" taip pat kartais vartojamas dviprasmiškai. Tikslo sąlygos kintamieji gali būti suprantami kaip visuotinai arba egzistenciškai kiekybiškai apibrėžti, o išvedimas "false" gali būti aiškinamas kaip prieštaravimo išvedimas arba kaip sėkmingo sprendžiamo uždavinio sprendimo išvedimas.

Van Emdenas ir Kowalskis (1976 m.) ištyrė Horno išlygų modelio teorines savybes loginio programavimo kontekste, parodydami, kad kiekviena apibrėžtųjų išlygų aibė D turi unikalų minimalų modelį M. Atominė formulė A logiškai implikuojama D tada ir tik tada, kai A yra teisinga M. Iš to išplaukia, kad problema P, išreikšta egzistenciškai kiekybiškai apibrėžta teigiamų literalų konjunkcija, logiškai implikuojama D tada ir tik tada, kai P yra teisinga M. Horno išlygų minimalaus modelio semantika yra loginių programų stabilaus modelio semantikos pagrindas.

Propoziciniai Horno straipsniai taip pat domina skaičiavimo sudėtingumo srityje, kur uždavinys, kaip rasti tiesos reikšmių priskyrimus, kad propozicinių Horno straipsnių konjunkcija būtų teisinga, yra P pilnas uždavinys (iš tikrųjų išsprendžiamas per tiesinį laiką), kartais vadinamas HORNSAT. (Tačiau neapriboto loginio patenkinamumo problema yra NP-užbaigta problema). Pirmosios eilės Horno sąlygos yra neišsprendžiamos.

Klausimai ir atsakymai

Klausimas: Kas yra rago klaustukas?

A: Horno išlyga - tai loginė literalų disjunkcija, kai ne daugiau kaip vienas iš literalų yra teigiamas, o visi kiti - neigiami.

K: Kas pirmasis juos aprašė?

A: Alfredas Hornas pirmą kartą jas aprašė 1951 m. straipsnyje.

K: Kas yra apibrėžtoji išlyga?

A: Horno išlyga, kurioje yra lygiai vienas teigiamas literalas, vadinama apibrėžtąja išlyga.

K: Kas yra faktas?

A: Apibrėžtinis sakinys, neturintis neigiamų literatalų, kartais vadinamas "faktu".

K: Kas yra tikslo sąlyga?

A: Horno išlyga be teigiamo literalo kartais vadinama tikslo išlyga.

K: Kaip veikia kintamieji nepropoziciniais atvejais?

A: Nepropoziciniu atveju visi kintamieji sąlygoje yra netiesiogiai visuotinai kvantifikuojami, o jų taikymo sritis - visa sąlyga. Tai reiškia, kad jie taikomi kiekvienai teiginio daliai.

Klausimas: Kokį vaidmenį Horno sąlygos atlieka konstruktyviojoje logikoje ir skaičiavimo logikoje? A: Horno sąlygos vaidina svarbų vaidmenį automatizuotame teoremų įrodyme taikant pirmosios eilės rezoliuciją, nes dviejų Horno sąlygų arba tarp vienos tikslo ir vienos apibrėžtos sąlygos rezolventas gali būti naudojamas siekiant didesnio efektyvumo įrodant ką nors, kas pateikiama kaip tikslo sąlygos neiginys. Jos taip pat naudojamos kaip loginio programavimo kalbų, pavyzdžiui, Prologo, pagrindas, kur jos elgiasi kaip tikslų redukcijos procedūros.