Fórmula de Harrop

En la lógica intuicionista , las fórmulas de Harrop , llamadas así en honor a Ronald Harrop, son la clase de fórmulas definidas inductivamente de la siguiente manera: ^{[1] [2] [3]}

• Las fórmulas atómicas son de Harrop, incluida la falsedad (⊥);
• ${\displaystyle A\cuña B}$Harrop proporciona y son;${\estilo de visualización A}$${\estilo de visualización B}$
• ${\estilo de visualización \neg F}$es Harrop para cualquier fórmula bien formada ;${\estilo de visualización F}$
• ${\displaystyle F\rightarrow A}$es Harrop siempre que sea, y es cualquier fórmula bien formada;${\estilo de visualización A}$${\estilo de visualización F}$
• ${\displaystyle \paratodos xA}$Harrop lo proporciona .${\estilo de visualización A}$

Al excluir la disyunción y la cuantificación existencial (excepto en el antecedente de implicación), se evitan los predicados no constructivos , lo que tiene beneficios para la implementación informática.

Las fórmulas de Harrop también se comportan bien en un contexto constructivo. Por ejemplo, en la aritmética de Heyting , las fórmulas de Harrop satisfacen una equivalencia clásica que no se cumple generalmente en la lógica constructiva: ^[1]${\displaystyle {\mathsf {HA}}}$

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

Sin embargo, existen enunciados que son independientes, es decir, enunciados simples para los que no se puede demostrar el término medio excluido . De hecho, si bien la lógica intuicionista demuestra que para cualquier , la disyunción no será Harrop. $Estilo de visualización: Pi__{1}$${\displaystyle {\mathsf {PA}}}$${\displaystyle \paratodos xA}$${\displaystyle {\mathsf {HA}}}$${\displaystyle \neg \neg (P\lor \neg P)}$${\estilo de visualización P}$

En la programación lógica se utiliza una definición más compleja de las fórmulas hereditarias de Harrop como una generalización de las cláusulas de Horn y constituye la base del lenguaje λProlog . Las fórmulas hereditarias de Harrop se definen en términos de dos (a veces tres) conjuntos recursivos de fórmulas. En una formulación: ^[4]

• Las fórmulas atómicas rígidas, es decir, constantes o fórmulas , son hereditarias (Harrop);${\estilo de visualización r}$${\displaystyle r(t_{1},...,t_{n})}$
• ${\displaystyle A\cuña B}$es hereditario Harrop proporcionado y son;${\estilo de visualización A}$${\estilo de visualización B}$
• ${\displaystyle \paratodos xA}$es hereditario Harrop siempre es;${\estilo de visualización A}$
• ${\displaystyle G\rightarrow A}$es hereditario Harrop siempre que sea rígidamente atómico, y es una G -fórmula.${\estilo de visualización A}$${\estilo de visualización G}$

Las fórmulas G se definen de la siguiente manera: ^[4]

• Las fórmulas atómicas son G -fórmulas, incluyendo la verdad (⊤);
• ${\displaystyle A\cuña B}$es una fórmula G proporcionada y son;${\estilo de visualización A}$${\estilo de visualización B}$
• ${\estilo de visualización A\vee B}$es una fórmula G proporcionada y son;${\estilo de visualización A}$${\estilo de visualización B}$
• ${\displaystyle \paratodos xA}$es una fórmula G proporcionada es;${\estilo de visualización A}$
• ${\displaystyle \existe xA}$es una fórmula G proporcionada es;${\estilo de visualización A}$
• ${\displaystyle H\rightarrow A}$es una fórmula G proporcionada , y es hereditaria Harrop.${\estilo de visualización A}$${\estilo de visualización H}$

Las fórmulas de Harrop fueron introducidas alrededor de 1956 por Ronald Harrop e independientemente por Helena Rasiowa . ^[2] Se utilizan variaciones del concepto fundamental en diferentes ramas de las matemáticas constructivas y la programación lógica .

• Realizabilidad