| Horn Clause |
Article Index for Horn |
Shopping Clause |
Website Links For Horn |
Information AboutHorn Clause |
| CATEGORIES ABOUT HORN CLAUSE | |
| logic in computer science | |
|
The following is an example of a (definite) Horn clause: : Such a formula can be rewritten in the following form, which is more common in logic programming and similar fields: : The relevance of Horn clauses to theorem proving by First-order Resolution is that the resolution of two Horn clauses is a Horn clause. Moreover, the resolution of a goal clause and a definite clause is again a goal clause. In Automated Theorem Proving , this can lead to greater efficiencies in proving a theorem (represented as a goal clause). In fact, Prolog is a programming language based on Horn clauses (Prolog also includes constructs such as the ''cut'' that cannot be easily expressed in logic). Horn clauses are also critical in Computational Complexity , where the problem of finding a set of variable assignments to make a conjunction of Horn clauses true is a P-complete problem, sometimes called HORNSAT . This is P's version of the Boolean Satisfiability Problem , a central NP-complete problem. The name "Horn clause" comes from the logician Alfred Horn , who first pointed out the significance of such clauses in 1951, in the article "On sentences which are true of direct unions of algebras", Journal of Symbolic Logic, 16, 14-21. |
|
|