Horn-Formel
Eine Hornklausel ist eine logische Disjunktion von Literalen, wobei höchstens eines der Literale positiv und alle anderen negativ ist. Sie ist nach Alfred Horn benannt, der sie 1951 in einem Artikel beschrieben hat.
Ein Hornsatz mit genau einem positiven Literal ist ein definitiver Satz, ein definitiver Satz ohne negative Literale wird manchmal als "Faktum" bezeichnet, und ein Hornsatz ohne positives Literal wird manchmal als Zielsatz bezeichnet. Diese drei Arten von Hornsätzen werden im folgenden Satzbeispiel veranschaulicht:
Dauerklausel: ¬ p ∨ ¬ q ∨ ⋯ ∨ ¬ t ∨ u {\displaystyle \neg p\lor \neg q\vee \cdots \vee \neg t\vee u} 
Tatsache: u {\darstellungsstil u} 
Zielklausel: ¬ p ∨ ¬ q ∨ ⋯ ∨ ¬ t {\displaystyle \neg p\oder \neg q\vee \cdots \vee \neg t} 
Im nicht-stellungsbezogenen Fall werden alle Variablen in einem Satz implizit universell mit dem Geltungsbereich des gesamten Satzes quantifiziert. So wird zum Beispiel
¬ Mensch ( X ) ∨ sterblich ( X ) {\neg {\Text}}(X)}oder {\Text}(X){\sterblich}(X)} 
steht für:
∀ X ( ¬ Mensch ( X ) ∨ sterblich ( X ) ) Anzeigestil \für alle X(\neg {\neg }Text{\mensch}(X)}oder {\Text{\terblich}(X))} 
was logisch gleichbedeutend ist mit:
∀ X ( Mensch ( X ) → sterblich ( X ) ) . {\Darstellungsstil \für alle X({\Text{Mensch}}(X){\Rechtspfeil {\Text{Sterben}}(X)). } 
Hornsätze spielen eine grundlegende Rolle in der konstruktiven Logik und Berechnungslogik. Sie sind wichtig beim automatisierten Theorembeweis durch Auflösung erster Ordnung, denn das Resolvent zweier Hornklauseln ist selbst eine Hornklausel, und das Resolvent einer Zielklausel und einer Definitivklausel ist eine Zielklausel. Diese Eigenschaften von Hornklauseln können zu größeren Effizienzgewinnen beim Beweis eines Theorems (dargestellt als die Negation einer Zielklausel) führen.
Hornsätze sind auch die Grundlage der logischen Programmierung, wo es üblich ist, bestimmte Sätze in Form einer Implikation zu schreiben:
( p ∧ q ∧ ⋯ ∧ t ) → u {\Anzeigestil (p\Keil q\Keil \Punkte \Keil t)\Rechtspfeil u} 
Tatsächlich ist die Auflösung einer Zielklausel mit einer definitiven Klausel zur Erzeugung einer neuen Zielklausel die Grundlage der Inferenzregel der SLD-Resolution, die zur Implementierung der logischen Programmierung und der Programmiersprache Prolog verwendet wird.
In der logischen Programmierung verhält sich ein definitiver Satz wie ein Zielreduktionsverfahren. Beispielsweise verhält sich der oben beschriebene Hornsatz als Prozedur:
um u {\displaystyle u} , p {\displaystyle p} 
und q {\displaystyle q} 
und ⋯ {\displaystyle \cdots } anzuzeigen 
und zeigen t {\Anzeigestil t} 
.
Um diesen rückwärtsgerichteten Gebrauch der Klausel zu betonen, wird sie oft in der rückwärtsgerichteten Form geschrieben:
u ← ( p ∧ q ∧ ⋯ ∧ t ) {\Anzeigestil u\linker Pfeil (p\land q\land \cdots \land t)} 
Im Prolog wird dies geschrieben als:
u :- p, q, ..., t.Die Prolog-Notation ist eigentlich mehrdeutig, und der Begriff "Zielklausel" wird manchmal auch mehrdeutig verwendet. Die Variablen in einem Zielsatz können als universell oder existentiell quantifiziert gelesen werden, und die Ableitung "falsch" kann entweder als Ableitung eines Widerspruchs oder als Ableitung einer erfolgreichen Lösung des zu lösenden Problems interpretiert werden.
Van Emden und Kowalski (1976) untersuchten die modelltheoretischen Eigenschaften von Hornsätzen im Kontext der Logikprogrammierung und zeigten, dass jeder Satz definitiver Sätze D ein eindeutiges Minimalmodell M besitzt. Eine atomare Formel A wird logisch durch D impliziert, wenn und nur wenn A in M wahr ist. Daraus folgt, dass ein Problem P, das durch eine existentiell quantifizierte Konjunktion positiver Literale repräsentiert wird, logisch durch D impliziert wird, wenn und nur wenn P in M wahr ist.
Propositional-Horn-Klauseln sind auch bei der rechnerischen Komplexität von Interesse, wo das Problem, Wahrheitswertzuweisungen zu finden, um eine Konjunktion von Propositional-Horn-Klauseln wahr zu machen, ein P-komplettes Problem ist (das tatsächlich in linearer Zeit lösbar ist), das manchmal HORNSAT genannt wird. (Das uneingeschränkte Boolesche Erfüllbarkeitsproblem ist jedoch ein NP-komplettes Problem). Die Erfüllbarkeit von Horn-Klauseln erster Ordnung ist unentscheidbar.
Fragen und Antworten
F: Was ist eine Horn-Klausel?
A: Eine Horn-Klausel ist eine logische Disjunktion von Literalen, bei der höchstens eines der Literale positiv ist und alle anderen negativ sind.
F: Wer hat sie zuerst beschrieben?
A: Alfred Horn beschrieb sie erstmals 1951 in einem Artikel.
F: Was ist eine definite Klausel?
A: Eine Horn-Klausel mit genau einem positiven Literal wird als definite Klausel bezeichnet.
F: Was ist ein Faktum?
A: Eine definite Klausel, die keine negativen Literale enthält, wird manchmal als "Fakt" bezeichnet.
F: Was ist eine Zielklausel?
A: Eine Horn-Klausel ohne ein positives Literal wird manchmal als Zielklausel bezeichnet.
F: Wie funktionieren die Variablen in nicht-propositionalen Fällen?
A: Im nicht-propositionalen Fall sind alle Variablen in einer Klausel implizit universell quantifiziert und gelten für die gesamte Klausel. Das bedeutet, dass sie für jeden Teil der Aussage gelten.
F: Welche Rolle spielen Horn-Klauseln in der konstruktiven Logik und der Computerlogik? A: Horn-Klauseln spielen eine wichtige Rolle beim automatisierten Theorembeweis durch Auflösung erster Ordnung, da die Auflösung zwischen zwei Horn-Klauseln oder zwischen einer Ziel- und einer definitiven Klausel verwendet werden kann, um eine größere Effizienz beim Beweis von etwas zu erreichen, das als Negation seiner Zielklausel dargestellt wird. Sie werden auch als Grundlage für logische Programmiersprachen wie Prolog verwendet, wo sie sich wie Zielreduktionsverfahren verhalten.
