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). Recibe su nombre en honor a Jacques Herbrand .

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

El universo de Herbrand

Definición

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

1. El universo de Herbrand de un lenguaje de primer orden L ^σ , es el conjunto de todos los términos básicos de L ^σ . Si el lenguaje no tiene constantes, entonces se extiende 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 los lenguajes de primer orden también hablamos simplemente del universo Herbrand del vocabulario σ .
2. El universo de Herbrand de una fórmula cerrada en 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 de Herbrand de L ^σ (o σ ) es { c , f ( c ), g ( c ), f ( f ( c )), f ( g ( c )), g ( f ( c )), g ( g ( c )), ...}.

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

Estructura de Herbrand

Una estructura Herbrand interpreta términos sobre un universo 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 solo si

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

Observaciones

1. U es el universo Herbrand de σ .
2. Una estructura de Herbrand que es un modelo de una teoría T se denomina 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 , ...}
• f → f , f → f , ...
• c → c

Base de Herbrand

Además del universo, definido en el § Universo de Herbrand, y del término denotaciones, definido en el § Estructura de Herbrand, la base de Herbrand completa la interpretación al denotar los símbolos de relación.

Definición

Una base de Herbrand es el conjunto de todos los átomos fundamentales cuyos términos de argumento 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 ), ...}

Véase 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.