In logic, and in particular in propositional calculus, a Horn clause is a proposition of the general type Logic (from Classical Greek λόγος (logos), originally meaning the word, or what is spoken, but coming to mean thought or reason) is most often said to be the study of arguments, although the exact definition of logic is a matter of controversy amongst philosophers (see below). ... In mathematical logic the propositional calculus or sentential calculus is a formal deduction system whose atomic formulas are propositional variables. ...

(p and q and ... and t) implies u,

where the number of propositions combined by ands is as large as we like (and may be zero).

This form can be rewritten, assuming we are working within the usual classical logic. The usual expression of the logical conditional as a disjunction is the case of the equivalence of Classical logic identifies a class of formal logics that have been most intensively studied and most widely used. ... In propositional calculus, or logical calculus in mathematics, the logical conditional is a binary logical operator connecting two statements, if p then q where p is a hypothesis (or antecedent) and q is a conclusion (or consequent). ... Logical disjunction (usual symbol or) is a logical operator that results in true if either of the operands is true. ...

p implies u,

with

(not p) or u.

This generalizes to the equivalence of the general Horn clause expression above with

(not p) or ... or (not t) or u.

This form shows that Horn clauses are a subset of those in conjunctive normal form, in which at most one of the terms is a positive literal, and the rest are negated. Horn clauses play a basic role in logic programming and are important for constructive logic. In Boolean logic, Conjunctive Normal Form (CNF) is a method of standardizing and normalizing logical formulas. ... Logic programming is a programming paradigm that is claimed to be declarative (i. ... In the philosophy of mathematics, constructivism asserts that it is necessary to find (or construct) a mathematical object to prove that it exists. ...

The relevance of Horn clauses to theorem proving by first-order resolution is that the resolution of two Horn clauses is a Horn clause. In automated theorem proving, this can lead to greater efficiencies in representation of the clauses on a computer. In fact, Prolog is a programming language constructed entirely out of Horn clauses. In mathematical logic and automated theorem proving, a branch of the traditional artificial intelligence (see GOFAI), resolution is a theorem-proving technique for sentences in propositional logic and first-order logic. ... Automated theorem proving (currently the most important subfield of automated reasoning) is the proving of mathematical theorems by a computer program. ... Prolog is a logic programming language. ...

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. Complexity theory is part of the theory of computation dealing with the resources required during computation to solve a given problem. ... In complexity theory, the complexity class P-complete is a set of decision problems and is useful in the analysis of which problems can be efficiently solved on parallel computers. ... The Boolean satisfiability problem (SAT) is a decision problem considered in complexity theory. ... In complexity theory, the NP-complete problems are the most difficult problems in NP, in the sense that they are the ones most likely not to be in P. The reason is that if you could find a way to solve an NP-complete problem quickly, then you could use...

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.