Harrop formula

In intuitionistic logic, the Harrop formulae, named after Ronald Harrop, are the class of formulae inductively defined as follows:^[1][2][3]

• Atomic formulae are Harrop, including falsity (⊥);
• ${\displaystyle A\wedge B}$ is Harrop provided ${\displaystyle A}$ and ${\displaystyle B}$ are;
• ${\displaystyle \neg F}$ is Harrop for any well-formed formula ${\displaystyle F}$;
• ${\displaystyle F\rightarrow A}$ is Harrop provided ${\displaystyle A}$ is, and ${\displaystyle F}$ is any well-formed formula;
• ${\displaystyle \forall x.A}$ is Harrop provided ${\displaystyle A}$ is.

By excluding disjunction and existential quantification (except in the antecedent of implication), non-constructive predicates are avoided, which has benefits for computer implementation.

Discussion

Harrop formulae are "well-behaved" also in a constructive context. For example, in Heyting arithmetic ${\displaystyle {\mathsf {HA}}}$, Harrop formulae satisfy a classical equivalence not generally satisfied in constructive logic:^[1]

${\displaystyle \neg \neg A\leftrightarrow A.}$

There are however ${\displaystyle \Pi _{1}}$-statements that are ${\displaystyle {\mathsf {PA}}}$-independent, meaning these are simple ${\displaystyle \forall x.A}$ statements for which excluded middle is not ${\displaystyle {\mathsf {HA}}}$-provable. Indeed, while intuitionistic logic proves ${\displaystyle \neg \neg (P\lor \neg P)}$ for any ${\displaystyle P}$, the disjunction wont be Harrop.

Hereditary Harrop formulae and logic programming

A more complex definition of hereditary Harrop formulae is used in logic programming as a generalisation of Horn clauses, and forms the basis for the language λProlog. Hereditary Harrop formulae are defined in terms of two (sometimes three) recursive sets of formulae. In one formulation:^[4]

• Rigid atomic formulae, i.e. constants ${\displaystyle r}$ or formulae ${\displaystyle r(t_{1},...,t_{n})}$, are hereditary Harrop;
• ${\displaystyle A\wedge B}$ is hereditary Harrop provided ${\displaystyle A}$ and ${\displaystyle B}$ are;
• ${\displaystyle \forall x.A}$ is hereditary Harrop provided ${\displaystyle A}$ is;
• ${\displaystyle G\rightarrow A}$ is hereditary Harrop provided ${\displaystyle A}$ is rigidly atomic, and ${\displaystyle G}$ is a G-formula.

G-formulae are defined as follows:^[4]

• Atomic formulae are G-formulae, including truth(⊤);
• ${\displaystyle A\wedge B}$ is a G-formula provided ${\displaystyle A}$ and ${\displaystyle B}$ are;
• ${\displaystyle A\vee B}$ is a G-formula provided ${\displaystyle A}$ and ${\displaystyle B}$ are;
• ${\displaystyle \forall x.A}$ is a G-formula provided ${\displaystyle A}$ is;
• ${\displaystyle \exists x.A}$ is a G-formula provided ${\displaystyle A}$ is;
• ${\displaystyle H\rightarrow A}$ is a G-formula provided ${\displaystyle A}$ is, and ${\displaystyle H}$ is hereditary Harrop.

History

Harrop formulae were introduced around 1956 by Ronald Harrop and independently by Helena Rasiowa.^[2] Variations of the fundamental concept are used in different branches of constructive mathematics and logic programming.

See also

• Realizability

References