Horn-Klausul er

En Horn-klausul er en logisk disjunktion af bogstaver, hvor højst én af bogstaverne er positiv, og alle de andre er negative. Den er opkaldt efter Alfred Horn, som beskrev dem i en artikel i 1951.

En Horn-klausul med præcis én positiv literal er en bestemt klausul; en bestemt klausul uden negative literaler kaldes nogle gange en "kendsgerning"; og en Horn-klausul uden en positiv literal kaldes nogle gange en målklausul. Disse tre typer af Horn-klausuler illustreres i følgende eksempel med en sætning:

bestemt sætning: ¬ p ∨ ¬ q ∨ ⋯ ∨ ∨ ¬ t ∨ u {\displaystyle \neg p\lor \neg q\vee \cdots \vee \neg t\vee u}

faktum: u {\displaystyle u}

målsætningsklausul: ¬ p ∨ ¬ q ∨ ∨ ⋯ ∨ ¬ t {\displaystyle \neg p\lor \neg q\vee \cdots \vee \neg t}

I det ikke-propositionelle tilfælde er alle variabler i en sætning implicit universelt kvantificeret med hele sætningen som anvendelsesområde. Således kan f.eks:

¬ menneske ( X ) ∨ dødelig ( X ) {\displaystyle \neg {\text{human}}(X)\lor {\text{mortal}}(X)}

står for:

∀ X ( ¬ menneske ( X ) ∨ dødelig ( X ) ) {\displaystyle \forall X(\neg {\text{human}}(X)\lor {\text{mortal}}(X))}

hvilket logisk set svarer til:

∀ X ( menneske ( X ) → dødelig ( X ) ) . {\displaystyle \forall X({\text{human}}(X)\rightarrow {\text{mortal}}(X)). }

Horn-sætninger spiller en grundlæggende rolle i konstruktiv logik og beregningslogik. De er vigtige i automatiseret sætningsafprøvning ved hjælp af førsteordensopløsning, fordi resolventen af to Horn-klausuler i sig selv er en Horn-klausul, og resolventen af en målklausul og en bestemt klausul er en målklausul. Disse egenskaber ved Horn-klausuler kan føre til større effektivitet i bevisførelsen af en sætning (repræsenteret som negationen af en målklausul).

Horn-klausuler er også grundlaget for logisk programmering, hvor det er almindeligt at skrive definitte klausuler i form af en implication:

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

Faktisk er opløsningen af en målklausul med en bestemt klausul for at frembringe en ny målklausul grundlaget for SLD-opløsningsreglen, som anvendes til at implementere logisk programmering og programmeringssproget Prolog.

I logisk programmering opfører en bestemt klausul sig som en målreduktionsprocedure. F.eks. opfører Horn-klausulen, som er skrevet ovenfor, sig som proceduren:

at vise u {\displaystyle u} , vise p {\displaystyle p} og vise q {\displaystyle q} og ⋯ {\displaystyle \cdots } og show t {\displaystyle t}

For at understrege denne bagudvendte anvendelse af sætningen skrives den ofte i bagudvendt form:

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

I Prolog skrives dette som:

Prolog-notationen er faktisk tvetydig, og udtrykket "målklausul" bruges også nogle gange tvetydigt. Variablerne i en målklausul kan læses som universelt eller eksistentielt kvantificerede, og afledning af "false" kan enten fortolkes som afledning af en modsigelse eller som afledning af en vellykket løsning af det problem, der skal løses.

Van Emden og Kowalski (1976) undersøgte de modelteoretiske egenskaber ved Horn-klausuler i forbindelse med logisk programmering og viste, at hvert sæt af definitive klausuler D har en unik minimal model M. En atomformel A er logisk impliceret af D, hvis og kun hvis A er sand i M. Det følger heraf, at et problem P repræsenteret ved en eksistentielt kvantificeret konjunktion af positive bogstaver er logisk impliceret af D, hvis og kun hvis P er sand i M. Den minimale modelsemantik for Horn-klausuler er grundlaget for den stabile modelsemantik for logiske programmer.

Propositionelle Horn-klausuler er også interessante inden for kompleksitet, hvor problemet med at finde sandhedsværditildelinger, der gør en konjunktion af propositionelle Horn-klausuler sande, er et P-komplet problem (der faktisk kan løses i lineær tid), undertiden kaldet HORNSAT. (Det ubegrænsede Boolske tilfredsstillelsesproblem er imidlertid et NP-komplet problem). Tilfredsheden af Horn-klausuler af første orden er ikke til at afgøre.

Spørgsmål og svar

Spørgsmål: Hvad er en hornstilling?

Sp: Hvem beskrev dem først?

Sp: Hvad er en bestemt klausul?

Spørgsmål: Hvad er et faktum?

Spørgsmål: Hvad er en målsætningsklausul?

Spørgsmål: Hvordan fungerer variabler i ikke-propositionelle tilfælde?

Søg efter bogstav