Estructura de Herbrand

Estructura sobre un vocabulario definido únicamente por propiedades sintácticas.

En lógica de primer orden , una estructura de Herbrand S es una estructura sobre un vocabulario σ que se define únicamente por las propiedades sintácticas de σ . La idea es tomar las cadenas de símbolos de los términos como sus valores, por ejemplo, la denotación de un símbolo constante c es simplemente " c " (el símbolo). Lleva el nombre de Jacques Herbrand .

Las estructuras de Herbrand juegan un papel importante en los fundamentos de la programación lógica . ^[1]

universo Herbrand

Definición

El universo de Herbrand sirve como universo en la estructura de Herbrand .

1. El universo Herbrand de un lenguaje de primer orden L ^σ , es el conjunto de todos los términos fundamentales de L ^σ . Si el lenguaje no tiene constantes, entonces el lenguaje se amplía agregando una nueva constante arbitraria.

   • El universo de Herbrand es contablemente infinito si σ es contable y existe un símbolo de función de aridad mayor que 0.
   • En el contexto de las lenguas de primer orden también hablamos simplemente del universo Herbrand del vocabulario σ .
2. El universo Herbrand de una fórmula cerrada en la forma normal de Skolem F es el conjunto de todos los términos sin variables que se pueden construir utilizando los símbolos de función y las constantes de F. Si F no tiene constantes, entonces F se extiende agregando una nueva constante arbitraria.

   • Esta segunda definición es importante en el contexto de la resolución computacional .

Ejemplo

Sea L ^σ , un lenguaje de primer orden con el vocabulario

• símbolos constantes: c
• símbolos de función: f (·), g (·)

entonces el universo Herbrand de L ^σ (o σ ) es { c , f ( c ), g ( c ), f ( f ( c )), f ( g ( c )), g ( f ( c )), g ( gramo ( c )), ...}.

Observe que los símbolos de relación no son relevantes para un universo de Herbrand.

Estructura de Herbrand

Una estructura de Herbrand interpreta términos sobre un universo de Herbrand .

Definición

Sea S una estructura , con vocabulario σ y universo U. Sea W el conjunto de todos los términos sobre σ y W ₀ el subconjunto de todos los términos libres de variables. Se dice que S es una estructura de Herbrand si y así

1. U = W ₀
2. f ^S ( t ₁ , ..., t _n ) = f ( t ₁ , ..., t _n ) para cadasímbolo de función n -aria f ∈ σ y t ₁ , ..., t _n ∈ W ₀
3. c ^S = c para cada constante c en σ

Observaciones

1. U es el universo de Herbrand de σ .
2. Una estructura de Herbrand que es un modelo de una teoría T se llama modelo de Herbrand de T.

Ejemplos

Para un símbolo constante c y un símbolo de función unaria f (.) tenemos la siguiente interpretación:

• U = { c , fc , ffc , fffc , ...}
• fc → fc , ffc → ffc , ...
• c → c

base de herbrand

Además del universo, definido en § Universo de Herbrand, y las denotaciones de términos, definidas en § Estructura de Herbrand, la base de Herbrand completa la interpretación denotando los símbolos de relación.

Definición

Una base de Herbrand es el conjunto de todos los átomos fundamentales cuyos términos argumentales son elementos del universo de Herbrand.

Ejemplos

Para un símbolo de relación binaria R , obtenemos con los términos anteriores:

{ R ( c , c ), R ( fc , c ), R ( c , fc ), R ( fc , fc ), R ( ffc , c ), ...}

Ver también

• teorema de herbrand
• Herbrandización
• Interpretación de Herbrand

Notas

1. "Semántica de Herbrand".

Referencias

• Ebbinghaus, Heinz-Dieter ; Flum, Jörg; Thomas, Wolfgang (1996). Lógica Matemática . Saltador . ISBN 978-0387942582.