Horn clause

• 1. Introduction

  ›

  Horn clauses sit at the crossroads of mathematical logic and computer science, and their story begins with a logician named Alfred Horn, who first identified their significance in 1951. At first glance, a Horn clause is a modest thing: a disjunction of literals with at most one positive, unnegated literal. But that single constraint turns out to carry enormous consequences for how computers can reason, prove theorems, and solve problems.

  What makes a logical formula with a simple structural rule so powerful that entire programming languages are built around it? And what connects a piece of formal mathematics from the 1950s to the modern logic programming language Prolog? Those are the questions this documentary will explore.

• 2. Anatomy of a Clause

  ›

  Alfred Horn drew a boundary around a specific family of logical formulas, and understanding where that boundary falls is what separates Horn clauses from the broader universe of logic. Every Horn clause is a disjunction of literals, meaning a list of statements connected by "or", with the restriction that at most one of those statements is positive, or unnegated.

  Within that family, three distinct subtypes carry different logical roles. A definite clause carries exactly one positive literal, functioning as a rule: if certain conditions hold, then a conclusion follows. A fact is a special case of a definite clause with no negative literals at all, asserting that something is simply true. A goal clause carries no positive literal, and it represents a problem to be solved or a statement to be shown false.

  The empty clause, which contains no literals at all, is itself a goal clause, and it is equivalent to the value false. On the other side of the family sits the dual-Horn clause, which inverts the constraint: a disjunction of literals with at most one negated literal, rather than at most one positive one. Keeping these distinctions clear matters, because the computational payoff of Horn clauses depends entirely on which subtype is in play.

• 3. Theorem Proving and Efficiency

  ›

  Horn clauses play a basic role in automated theorem proving by first-order resolution, and their value there comes from a clean algebraic property: the resolvent of two Horn clauses is itself a Horn clause. This closure property matters in practice, because it keeps the set of formulas the prover must track structurally simple throughout the search.

  When proving a theorem using Horn clauses, the goal clause carries the negation of the theorem to be established. The prover then checks whether assuming that negation leads to a contradiction. If it does, the original theorem must hold. This approach means a mechanical proving tool needs to maintain only one set of formulas, the assumptions, rather than juggling two separate collections of assumptions and subgoals. The resolvent of a goal clause and a definite clause is always another goal clause, so the prover never drifts outside the Horn clause family during its search.

  In computational complexity, the satisfiability problem for propositional Horn clauses carries its own name: HORNSAT. The problem of finding truth-value assignments that make a conjunction of propositional Horn clauses true is P-complete and solvable in linear time. That stands in stark contrast to the unrestricted Boolean satisfiability problem, which is NP-complete, meaning no known algorithm can solve it efficiently in the general case.

• 4. Algebra and Model Theory

  ›

  Universal algebra gives Horn clauses a different name and a different frame. In that setting, definite Horn clauses are generally called quasi-identities, and classes of algebras definable by a set of quasi-identities carry the label quasivarieties. Quasivarieties enjoy some of the good properties that belong to the more restrictive notion of a variety, which is an equational class, while allowing a broader range of structures.

  From a model-theoretic perspective, Horn sentences are significant because they are exactly those sentences preserved under reduced products, up to logical equivalence. In particular, Horn sentences are preserved under direct products. The model-theoretic side also connects to logic programming through work by Van Emden and Kowalski in 1976. They showed that every set of definite clauses D has a unique minimal model M, and that an atomic formula A is logically implied by D if and only if A is true in that minimal model M. The minimal model semantics of Horn clauses later became the basis for the stable model semantics of logic programs, a framework that extended the reach of Horn clause logic into richer reasoning systems.

• 5. Logic Programming and Prolog

  ›

  In logic programming, definite clauses take on a procedural character that moves them from pure mathematics into computation. A definite clause written in implication form behaves as a goal-reduction procedure: to establish that u holds, reduce the problem to establishing that p, q, and t all hold. Prolog encodes this directly in its notation, where the clause is written as "u :- p, q,..., t."

  The resolution of a goal clause with a definite clause to produce a new goal clause is the foundation of SLD resolution, the inference rule used in Prolog's implementation. A goal clause in logic programming represents the negation of a problem to be solved; the problem itself is an existentially quantified conjunction of positive literals. Prolog's notation, which writes this as ":- p, q,..., t.", carries an intentional ambiguity: the same expression can be read as stating the problem or as stating the denial of the problem, and both readings are correct.

  Solving the problem amounts to deriving the empty clause, which in Prolog notation is equivalent to deriving ":- true." The solution is a substitution of terms for the variables in the top-level goal clause, and that substitution can be extracted from the resolution proof. Used this way, goal clauses are similar to conjunctive queries in relational databases. Horn clause logic is equivalent in computational power to a universal Turing machine, which means the restricted form of logic Horn clauses occupy is in fact fully general for computation.