- Asked 2/12
- 2069 Poush · 4 marks
- 2070 Magh · 1 mark
Horn clause
Short answer
A Horn clause is a disjunction of literals with at most one positive literal, equivalent to an implication (fact, rule, or query). They allow efficient linear-time inference and form the basis of logic programming like Prolog.
What is a Horn clause?
A Horn clause is a clause (a disjunction of literals) that contains at most one positive literal.
General form: ¬P1 ∨ ¬P2 ∨ ... ∨ ¬Pn ∨ Q
This is logically equivalent to the implication (P1 ∧ P2 ∧ ... ∧ Pn) → Q, i.e. "IF P1 and P2 and ... and Pn THEN Q".
Types of Horn clauses
| Type | Form | Example |
|---|---|---|
| Fact (unit clause) | Exactly one positive literal, no negative | Parent(Ram, Sita) |
| Rule (definite clause) | One positive literal and one or more negative | ¬Parent(x,y) ∨ ¬Parent(y,z) ∨ Grandparent(x,z) |
| Goal / query | No positive literal | ¬Grandparent(Ram, z) |
In Prolog these are written as grandparent(X,Z) :- parent(X,Y), parent(Y,Z).
Importance
- Inference with Horn clauses (forward and backward chaining, SLD resolution) is efficient: for propositional Horn clauses entailment is decided in time linear in the size of the knowledge base.
- They are the basis of logic programming (Prolog) and rule-based expert systems.
- Not every sentence can be a Horn clause; for example the disjunction A ∨ B (two positive literals) is not Horn.
✓ Answer checked by Claude Opus 5.5 (high effort)