---
title: "Horn clause"
subject: "Artificial Intelligence"
chapter: 4
key: "semester_6/artificial_intelligence:horn-clause"
source: https://www.bctengineer.com/q/semester_6/artificial_intelligence/horn-clause
site: BCT Engineering
---

# Horn clause

Artificial Intelligence · Chapter 4: Knowledge Representation, Inference & Reasoning

- Asked in: 2069 Poush, 4 marks; 2070 Magh, 1 marks (asked 2 times)
- Video: [Horn Clause in Artificial Intelligence | Horn Clause In Artificial Intelligence With Example](https://www.youtube.com/watch?v=htidfFH7nUs) — Pywix Classes
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_6/artificial_intelligence/horn-clause
- Whole chapter: https://www.bctengineer.com/md/semester_6/artificial_intelligence/chapter-4

## Question

What is a 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.

## Answer

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.

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. What is a Horn clause?
   A. A clause with at most one positive literal
   B. A clause with at least two positive literals
   C. A clause with only negative literals and a quantifier
   D. A conjunction of clauses
   Answer: A. A Horn clause is a disjunction of literals with at most one positive literal. (Key point: Definition)

2. ¬P1 ∨ ¬P2 ∨ Q is equivalent to which statement?
   A. (P1 ∨ P2) → Q
   B. (P1 ∧ P2) → Q
   C. Q → (P1 ∧ P2)
   D. ¬Q → P1
   Answer: B. It is the rule IF P1 and P2 THEN Q. (Key point: Implication form)

3. Which clause is NOT a Horn clause?
   A. Parent(Ram, Sita)
   B. ¬Parent(x,y) ∨ ¬Parent(y,z) ∨ Grandparent(x,z)
   C. A ∨ B
   D. ¬Grandparent(Ram, z)
   Answer: C. A ∨ B has two positive literals. (Key point: Non-Horn example)

4. Why are Horn clauses important?
   A. They allow efficient inference and are the basis of Prolog and rule-based systems
   B. They can express every sentence
   C. They avoid the need for facts
   D. They make inference exponential
   Answer: A. Propositional Horn entailment is linear time, and they underlie logic programming. (Key point: Importance)