📐Horn Logic

NEW

Also known as: Horn Clause Logic, Propositional Horn Clauses

A fragment of first-order logic built from Horn clauses, enabling efficient inference and forming the basis of logic programming.

DESCRIPTION

Horn logic uses clauses with at most one positive literal, supporting linear-time entailment in propositional cases. It underpins Prolog and Datalog, widely used in rule-based systems. Restricted syntax enables efficient resolution strategies. In data systems, Datalog powers recursive queries and integrity rules. Horn logic’s balance of expressiveness and tractability makes it a practical foundation for reasoning and query evaluation.

ALTERNATIVE DEFINITIONS

Wikipedia

A Horn clause is a clause with at most one positive literal; Horn clauses are central to logic programming and Prolog.

Defines clause structure and connection to logic programming.

Source

Stanford Encyclopedia of Philosophy

Logic programming is based on Horn clauses, using resolution as a proof procedure to derive consequences from a program.

Positions Horn clauses as foundational for logic programming.

Source

RELATED TERMS

Rule-Based System Datalog Prolog Resolution Reasoner First-order Logic

COMPETING TERMS

Full First-Order Logic Description Logic

KNOWLEDGE AREAS

Mathematics AI Programming Languages

TARGET AUDIENCE

Data Scientist AI Engineer Software Developer Data Modeler

EXTERNAL SOURCES

• Wikipedia - Horn clause
• ACM - Foundational paper on Datalog
• SWI-Prolog - Prolog system documentation

TOP QUESTIONS

Why is Horn Logic popular in AI and databases?

It provides tractable inference and supports recursion, making it ideal for rule-based systems and recursive queries.

Category: Relevancy

What is the structure of a Horn clause?

A disjunction of literals with at most one positive literal, often written as rules in logic programming.

Category: Explanation

How does Horn Logic relate to Datalog?

Datalog uses Horn clauses without function symbols, enabling efficient, declarative query evaluation.

Category: Example

What are common mistakes with Horn Logic?

Assuming full first-order expressiveness; Horn clauses restrict certain constructs like arbitrary negation and functions.

Category: Mistakes

What risks arise when modeling with Horn Logic?

Over-restriction can prevent capturing complex semantics; conversely, extensions may break tractability.

Category: Risk

How do you implement Horn Logic rules?

Use Prolog or Datalog engines, define predicates and rules, and rely on resolution or semi-naive evaluation.

Category: Requirements

What is a hot topic around Horn Logic?

Combining Datalog with graph databases and incremental evaluation for streaming data.

Category: Topic

How is Horn Logic validated?

Create test cases, ensure rule termination, and check results against expected derivations and invariants.

Category: Management

Where to learn Horn Logic?

Study logic programming texts, Stanford Encyclopedia entries, and practical Prolog/Datalog tutorials.

Category: Learning