This is an archive of an inactive wiki and cannot be modified.

What is "Horn Logic"

Contributed by IgorMozetic (in progress)

Since the RIF charter mentions "Horn Logic" several times, this is an attempt to define the term more precisely.

I propose to define "Horn Logic" as a formal language, which has a corresponding inference procedure, thus forming a formal system together. The formal language allows to express rules (and facts), and queries. The inference procedure computes answers to queries from rules (and facts).

The formal language to express rules is that of "definite program" [1] or "logic program" [2, 3] as defined in the Logic Programming community (and "definite goal" [1] or "query" [2] for queries, respectively). There is no need to repeat the precise syntax here, just some highlights: no negation in rules' conditions, no existentially quantified variables, function symbols are allowed as arguments.

The "Horn Logic" language has declarative semantics defined by the least (or minimal) Herbrand model [1]. The language can express any computable function (or simulate the universal Turing machine) and is therefore undecidable. E.g., checking whether a set of Horn rules implies a fact is undecidable. In the presence of function symbols, terms of arbitrary depth can be constructed and thus the Herbrand model may be infinite.

Apart from the declarative, model-theoretic semantics, the "Horn Logic" language has also a procedural semantics. It is defined by an inference procedure called SLD-resolution (Linear resolution with Selection function for Definite clauses [1]). SLD-resolution is a sound and complete inference procedure, meaning that declarative and procedural semantics coincide. However, due to undecidability, SLD-resolution might not terminate (when the Herbrand model is infinite and the query is not a logical consequence of the rules). The SLD-refutation procedure is underspecified in the sense that it leaves open the order in which atoms in the body are selected and the order in which clauses are tried. To guarantee soundness and completness, the following conditions have to be met:

What is a "subset of standard Prolog"

By "standard Prolog" we indicate an operational computer language, as defined by the ISO standard. The ISO standard is apparently not freely available, but we found the following references to the pre-final draft [4, 5].

By a "subset of standard Prolog" we mean a language which allows only user-defined predicates in the body of a Horn clause (no cut, negation, built-ins, meta- or extra-logical predicates).

In relation to "Horn Logic" a "subset of standard Prolog" is a logic program with clauses ordered sequentialy, and atoms in the body ordered from left-to-right. "Standard Prolog" systems implement a deterministic resolution procedure in which the leftmost atom in the body is selected, and clauses are tried in the order in which they were specified. Such implementation of SLD-resolution in "standard Prolog" system does not preserve its completeness.

[1] J.W. Lloyd, Foundations of Logic Programming, Springer-Verlag, 1987.

[2] L. Sterling, E. Shapiro, The Art of Prolog, MIT Press, 1994.

[3] E. Dantsin, T. Eiter, G. Gottlob, A. Voronkov, Complexity and Expressive Power of Logic Programming, ACM Computing Surveys 33 (3), pp. 374-425, Sep. 2001.