Horn clause

Horn formulas are an important type of predicate logic formulas. They play a central role in logic programming, and are of importance for the constructive logic. They were named after the logician Alfred Horn U.S..

Definition

Under a clause, also called Disjunktionsterm, is defined as the disjunction

Of literals, each literal is either an atomic term or a negated atomic expression.

A Horn clause is a clause with at most one positive literal, ie with at most one literal whose atomic expression is not negated.

In the special case of propositional logic, a typical Horn clause looks so like this:

In this case, until all atomic expressions ( in this example, there are propositional variables ) negated.

A Horn formula is a conjunctive normal form ( ie a conjunction of disjunctions ), in which each Disjunktionsterm is a Horn clause.

Examples

Representations of Horn clauses

Horn clauses can be according to the rules of propositional logic pose as substantive implications. So true in the simplest case of a Horn clause with two literals known:

By definition may contain a Horn clause exactly one or no non- negated atom. Moreover, it may happen that no literals occur with negated atomic expressions. So there are three basic types of Horn clauses. The following table gives an overview of these three possible forms of a Horn clause, both as a disjunction, as well as implication.

Satisfiability

With the help of the marking algorithm Horn formulas can be tested in polynomial time to satisfiability ( also HORNSAT is P- complete). So you can determine in polynomial time whether a variable assignment ( an assignment of truth values ​​to the occurring in the Horn formula literals ) exists for which the Horn formula is true. In contrast, it is assumed that in general for propositional formulas is no polynomial time algorithm exists (see satisfiability of propositional logic ).

Application

The importance of Horn clauses is in the computer science in automatic closing. Thus, in the programming language Prolog programs are specified as Horn clauses.

Swell

  • HD Ebbinghaus, J. Flum, W. Thomas: Introduction to mathematical logic. Mannheim -Leipzig- Vienna - Zurich; BI -Wiss. Verlag, 1992, ISBN 3-411-15603-1
  • Wolfgang Rautenberg: Introduction to Mathematical Logic. 3rd edition. Vieweg Teubner, Wiesbaden 2008, ISBN 978-3-8348-0578-2 ( http://www.springerlink.com/content/978-3-8348-0578-2/ ).
  • Hans -Peter Tuschik, Helmut Wolter: Mathematical Logic - in brief. Principles, model theory, decidability, set theory. Mannheim -Leipzig- Vienna - Zurich; BI -Wiss. Publishing, 1994, ISBN 3-411-16731-9
399043
de