Posterior: Campos algebraicos Arriba: Cálculo de predicados Anterior: Sintaxis básica del cálculo

Semántica básica del cálculo de predicados

Veamos el concepto de modelo o interpretación de una teoría de primer orden.

Definición 2.1   Sea $L=\mbox{\it Sig}\cup\mbox{\it SL}$ un alfabeto para una teoría de primer orden, con signatura $\mbox{\it Sig}=\mbox{\it Cte}\cup\mbox{\it Fun}\cup\mbox{\it Rel}$. Una INTERPRETACIÓN para $L$, o una -ESTRUCTURA, es un conjunto $M$ junto con una correspondencia $\overline{\cdot}$ definida en $\mbox{\it Sig}$ tal que

1. Toda constante corresponde a un elemento en $M$:
   
   $$\xi\in\mbox{\it Cte}\ \Rightarrow\ \overline{\xi}\in M$$
   
   

2. Todo símbolo de función de aridad $n$ corresponde a una función $M^n\to M$:
   
   $$f^n_j\in\mbox{\it Fun}\ \Rightarrow\ \overline{f^n_j}:M^n\to M$$
   
   

3. Todo símbolo de relación de aridad $n$ corresponde a una relación de aridad $n$, es decir a un subconjunto en $M^n$:
   
   $$R^n_j\in\mbox{\it Rel}\ \Rightarrow\ \overline{R^n_j}\subset M^n.$$
   
   

Diremos que la pareja $\mathfrak{M}=(M,\overline{\cdot})$ es la interpretación o la $L$-estructura.

Naturalmente, si se tiene una interpretación se puede interpretar a los términos y a las fórmulas del lenguaje.

Definición 2.2   Sea $L=\mbox{\it Sig}\cup\mbox{\it SL}$ un alfabeto para una teoría de primer orden, y sea $\mathfrak{M}=(M,\overline{\cdot})$ una interpretación. La INTERPRETACIÓN DE UN TÉRMINO será bien un elemento de $M$ o una función definida en alguna potencia cartesiana de $M$, según el término sea o no cerrado. Explícitamente, para cada término $\xi$ en $L$, definimos su interpretación $\overline{\xi}$ de manera recursiva:

1. Si $\xi=c$ es una constante, entonces $\overline{\xi}=\overline{c}$:
   
   $$\xi=c\ ,\ c\in\mbox{\it Cte}\ \Rightarrow\ \overline{\xi}=\overline{c}.$$
   
   

2. Si $\xi=x$ es una variable, entonces $\overline{\xi}$ es la función identidad en $M$:
   
   $$\xi=x\ ,\ x\in\mbox{\it Var}\ \Rightarrow\ \overline{\xi}:M\to M, m\mapsto m.$$
   
   

3. Si $\xi$ es un término compuesto, entonces $\overline{\xi}$ es la composición de las interpretaciones de sus componentes:
   
   $$\xi=f^n_j(\xi_1,\ldots,\xi_n)\ ,\ f^n_j\in\mbox{\it Fun}\ \Ri... ...xi}=\overline{f^n_j}(\overline{\xi_1},\ldots,\overline{\xi_n}).$$
   
   

Así pues, para cada término $\xi$, $\overline{\xi}$ es una función $M^k\to M$ donde $k$ es el número de variables que aparecen en $\xi$. Recordamos que un enunciado es una fórmula bien formada sin variables libres.

Definición 2.3   Sea $\mathfrak{M}=(M,\overline{\cdot})$ una interpretación de un alfabeto $L=\mbox{\it Sig}\cup\mbox{\it SL}$. Veamos ahora cómo se interpreta a los enunciados.

Enunciados atómicos.

Sea $R^i_j\in\mbox{\it Rel}$ un símbolo variable y sean $\xi_1,\ldots,\xi_i$ términos sin variables libres. Se dice que el átomo $R(\xi_1,\ldots,\xi_i)$ es VÁLIDO en $\mathfrak{M}$, y se escribe $\mathfrak{M} \models R(\xi_1,\ldots,\xi_i)$, si $(\overline{\xi_1},\ldots,\overline{\xi_i})\in\overline{R}$.

Enunciados negados.

Sea $\phi=\neg \psi$ un enunciado cuyo conectivo principal es la negación. Entonces definimos:

$$\mathfrak{M} \models \phi\ :\Leftrightarrow\ \mathfrak{M} \not \models \psi.$$

Enunciados que son conjunciones.

Sea $\phi=\psi\land\chi$ un enunciado cuyo conectivo principal es la conjunción. Entonces definimos:

$$\mathfrak{M} \models \phi\ :\Leftrightarrow\ \left(\mathfrak{... ...models \psi\right)\ \&\ \left(\mathfrak{M} \models \chi\right).$$

Enunciados que son disyunciones.

Sea $\phi=\psi\lor\chi$ un enunciado cuyo conectivo principal es la disyunción. Entonces definimos:

$$\mathfrak{M} \models \phi\ :\Leftrightarrow\ \left(\mathfrak{... ... \psi\right)\ \mbox{o}\ \left(\mathfrak{M} \models \chi\right).$$

Enunciados que son implicaciones.

Sea $\phi=\psi\rightarrow\chi$ un enunciado cuyo conectivo principal es la implicación. Entonces definimos:

$$\mathfrak{M} \models \phi\ :\Leftrightarrow\ \left[\;\left(\m... ...\ \Rightarrow\ \left(\mathfrak{M} \models \chi\right)\;\right].$$

Enunciados que son equivalencias.

Sea $\phi=\psi\leftrightarrow\chi$ un enunciado cuyo conectivo principal es la equivalencia. Entonces definimos:

$$\mathfrak{M} \models \phi\ :\Leftrightarrow\ \left[\;\left(\m... ...\ \Rightarrow\ \left(\mathfrak{M} \models \chi\right)\;\right].$$

Enunciados cuantificados universalmente.

Sea $\phi=\forall x\, \psi(x)$ un enunciado, donde $\psi(x)$ es una fórmula en la que sólo la variable $x$ aparece libre. Para cada término $\xi$ en donde no aparezca $x$, denotemos por $\psi(x\leftarrow \xi)$ al enunciado que resulta de $\psi$ al sustituir la variable $x$ por $\xi$. Entonces definimos:

$$\mathfrak{M} \models \phi\ :\Leftrightarrow\ \mbox{\begin{min... ...$, $\mathfrak{M} \models \psi(x\leftarrow \xi)$.\end{minipage}}$$

Enunciados cuantificados existencialmente.

Sea $\phi=\exists x\, \psi(x)$ un enunciado, donde $\psi(x)$ es una fórmula en la que sólo la variable $x$ aparece libre. Entonces definimos:

$$\mathfrak{M} \models \phi\ :\Leftrightarrow\ \mbox{\begin{min... ...$, $\mathfrak{M} \models \psi(x\leftarrow \xi)$.\end{minipage}}$$

Por ejemplo, los axiomas lógicos y los de reescritura, tales como aparecen en la definición 3.1.7, son válidos en cualquier interpretación de un alfabeto propio de una teoría de primer orden.

Definición 2.4   Si $\Phi$ es un conjunto de enunciados en un alfabeto $L$ y $\mathfrak{M}$ es una $L$-estructura, diremos que $\mathfrak{M}$ es un MODELO de $\Phi$, y escribiremos $\mathfrak{M} \models \Phi$, si toda fórmula en $\Phi$ es válida en $\mathfrak{M}$, i.e.

$$\phi\in\Phi\ \Rightarrow\ \mathfrak{M} \models \phi.$$

Así, por ejemplo, si $\mbox{\rm Ax}_{\mbox{\scriptsize\it Log}}(L)$ es la colección de axiomas lógicos y $\mbox{\rm Ax}_{\mbox{\scriptsize\it RE}}(L)$ la de axiomas de reescritura, entonces, según la observación precedente, cualquiera que sea la $L$-estructura $\mathfrak{M}$ se tiene $\mathfrak{M} \models \mbox{\rm Ax}_{\mbox{\scriptsize\it Log}}(L)\cup \mbox{\rm Ax}_{\mbox{\scriptsize\it RE}}(L)$. Veamos ejemplos de modelos para colecciones particulares de axiomas no-lógicos.

Posterior: Campos algebraicos Arriba: Cálculo de predicados Anterior: Sintaxis básica del cálculo