Harrop Formula¶

An intuitionistic formula built so disjunctions and existential quantifiers occur only in negative positions, yielding a stable, computationally disciplined fragment and inspiring hereditary-Harrop logic programming.

Version: v3 · 2026-09-19 · History
Domain-specific #: 1982
Domain group: Formal Sciences
Origin domain: Mathematics
Subdomain: Intuitionistic Logic → Mathematics
Aliases: Harrop formulae, Harrop formulas, Harrop sentence

Core Idea¶

A Harrop formula is an intuitionistic formula with no positive occurrence of disjunction or existential quantification. One standard first-order grammar includes atomic formulas and falsity; closes under conjunction and universal quantification; and permits \(B\to H\) whenever the consequent \(H\) is Harrop while the antecedent \(B\) is arbitrary. Negation \(\neg B\) is included as \(B\to\bot\). Harrop introduced the fragment while studying disjunction and existence properties of intuitionistic systems.

The polarity condition—not the mere absence of the symbols \(\lor\) and \(\exists\)—is decisive: those constructors may occur inside an implication antecedent, where polarity is reversed.

How would you explain it like I'm…

No faithful explanation at this level. A five-year-old version collapses into 'a sentence with no or-words or some-words'. That is the symbol-absence misconception: such words are allowed inside the 'if' part of an implication, where polarity is reversed.

No Secret-Choice Promises

In logic, people write statements using pieces like 'and', 'or', 'if...then', 'for all', and 'there is some'. A Harrop formula is a statement whose promised result never says 'this OR that' or 'there is SOME thing' without saying which. The tricky part: 'or' and 'some' are allowed inside the 'if' part of an if-then, because there they work the opposite way — they describe what you are given, not what you promise. So you can't just check whether the words appear; you have to check where they appear.

Positively Disjunction-Free Formulas

A Harrop formula is a formula of intuitionistic logic with no positive occurrence of disjunction (∨) or existential quantification (∃). One standard grammar starts with atomic formulas and falsity (⊥), and allows conjunction and universal quantification. It also allows B → H whenever H is Harrop, even if the antecedent B is anything at all. Negation ¬B counts as B → ⊥, so it is always Harrop. The key point is polarity: ∨ and ∃ may appear inside an antecedent, because the antecedent of an implication has reversed polarity. Harrop introduced this fragment while studying the disjunction and existence properties of intuitionistic systems.

In intuitionistic logic, a Harrop formula is one in which disjunction and existential quantification have no positive occurrences. A first-order grammar is: H ::= atomic | ⊥ | H ∧ H | ∀x H | B → H, where B ranges over arbitrary formulas. Negation ¬B is defined as B → ⊥ and is therefore Harrop for any B. Polarity is what matters: in B → H the antecedent sits in negative position, so ∨ and ∃ may appear there freely. In the consequent or at top level they are excluded. Simply checking that the symbols ∨ and ∃ do not appear is therefore the wrong test, because it would reject legitimate formulas like (A ∨ C) → D. Harrop defined this class while investigating when intuitionistic systems have the disjunction and existence properties.

Scope of Application¶

Harrop formulas appear in constructive proof theory, conservation and disjunction/existence-property arguments, normalization, realizability, arithmetic, proof search, and program extraction. Related hereditary Harrop formulas extend Horn-clause programming with embedded implications, universal goals, and higher-order structure; they underlie languages such as \(\lambda\)Prolog.

Clarity¶

State the base logic, grammar, treatment of truth and falsity, definition of negation, free-variable policy, and whether “Harrop” or “hereditary Harrop” is intended. Check syntactic polarity on the given parse tree rather than rewriting by semantic equivalence. Qualify stability results by the surrounding intuitionistic theory.

Manages Complexity¶

The restriction suppresses positive choices and positive witness production in assumptions or conclusions where they would obstruct deterministic proof behavior. Its recursive grammar yields a linear syntax-tree membership test and supports proof-search phases with fewer branching forms. The hereditary extension separates program clauses from goals so operational proof search remains aligned with intuitionistic provability.

Abstract Reasoning¶

Parse the formula under the declared grammar.
Assign the root positive polarity.
Preserve polarity through conjunction and quantifiers.
Reverse polarity in an implication antecedent and preserve it in the consequent.
Reject \(\lor\) or \(\exists\) at positive positions.
Or derive membership directly from the inductive Harrop clauses.
Distinguish syntactic membership from provable equivalence.
Apply only the proof-theoretic consequences justified by the base theory.

Knowledge Transfer¶

The portable pattern is restrict choice-producing constructors by polarity so a logical fragment gains stronger operational and proof-theoretic behavior. It transfers to focused proof systems and executable specification languages. The proposed immediate parent is Formal System.

Relationships to Other Abstractions¶

Current abstraction Harrop Formula Domain-specific

Parents (1) — outgoing typed relations

Harrop Formula is a kind of Formal System Prime

Formal System is the broader abstraction this entry instantiates.

Hierarchy paths (2) — routes to 2 parentless roots

Harrop Formula → is a kind of Formal System → presupposes Formalization → presupposes Representation → presupposes Abstraction

Show alternative path (1)

Neighborhood in Abstraction Space¶

Harrop Formula sits in a sparse region of the domain-specific corpus (82^nd percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.

Family — Unclustered & Miscellaneous (2769 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-10-25