En la 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 los 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 básicos de L σ . Si el lenguaje no tiene constantes, entonces el lenguaje se amplía agregando una nueva constante arbitraria.
- El universo de Herbrand es infinito numerable 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 Herbrand de una fórmula cerrada en Skolem forma normal F , es el conjunto de todos los términos sin variables, que pueden ser construidos utilizando los símbolos de función y las constantes de F . Si F no tiene constantes, entonces F se amplía 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 ( g ( c )), ...}.
Observe que los símbolos de relación no son relevantes para un universo Herbrand.
Estructura de la marca
Una estructura de Herbrand interpreta términos sobre un universo de Herbrand .
Definición
Deje S ser una estructura , con σ vocabulario y universo U . Sea T el conjunto de todos los términos sobre σ y T 0 el subconjunto de todos los términos libres de variables. Se dice que S es una estructura Herbrand iff
- U = T 0
- f S ( t 1 , ..., t n ) = f ( t 1 , ..., t n ) para cada símbolo de función n -aria f ∈ σ y t 1 , ..., t n ∈ T 0
- c S = c para toda constante c en σ
Observaciones
- U es el universo Herbrand de σ.
- Una estructura de Herbrand que es un modelo de una teoría T , se llama el modelo de Herbrand de T .
Ejemplos de
Para un símbolo constante cy 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 el universo de Herbrand , y el término denotaciones, definido en la 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 de tierra cuyos términos de argumento son el universo de Herbrand.
Ejemplos de
Para un símbolo de relación binaria R , obtenemos con los términos de arriba:
{ R ( c , c ), R ( fc , c ), R ( c , fc ), R ( fc , fc ), R ( ffc , c ), ...}
Ver también
Notas
Referencias
- Ebbinghaus, Heinz-Dieter ; Flum, Jörg; Thomas, Wolfgang (1996). Lógica matemática . Springer . ISBN 978-0387942582.