23 Evaluacion semantica de formulas (valores de verdad)

Llamamos signatura al conjunto $\displaystyle\Sigma$ formado por todos los simbolos de funcion y predicado (incluyendo los de constante y proposicion atomica).

Sea $\displaystyle\Sigma$ una signatura. Llamamos interpretacion definida sobre $\displaystyle\Sigma$ a un par $\displaystyle(D,I)$ donde:

•  
  ​

  $\displaystyle D$ es un conjunto no vacio, llamado el dominio de la interpretacion.

•  
  ​

  $\displaystyle I$ es la funcion interpretacion que asocia a cada elemento de $\displaystyle\Sigma$ un objeto matematico como se describe a continuacion:

  • •
    ​

    A cada simbolo de constante $\displaystyle c\mapsto$ un elemento del dominio $\displaystyle c^{\prime}\in D$.

  • •
    ​

    A cada simbolo de funcion $\displaystyle f$ de aridad $\displaystyle n\geq 1\mapsto$ una funcion $\displaystyle f^{\prime}:D^{n}\to D$.

  • •
    ​

    A cada simbolo de predicado $\displaystyle P$ de aridad $\displaystyle n\geq 1\mapsto$ una relacion $\displaystyle n$-aria $\displaystyle P^{\prime}\subseteq D^{n}$.

Dado el conjunto de simbolos de variable, llamamos asignacion a una funcion $\displaystyle A$ que asocia:

•  
  ​

  A cada simbolo de variable $\displaystyle x\mapsto$ un elemento del dominio $\displaystyle x^{A}\in D$.

Vamos a asociar, de forma recursiva, a cada termino $\displaystyle t$ un elemento del dominio $\displaystyle t^{I,A}\in D$.

•  
  ​

  Si $\displaystyle c$ es un simbolo de constante $\displaystyle\Rightarrow(c)^{I,A}\coloneqq c^{I}$

•  
  ​

  Si $\displaystyle x$ es un simbolo de variable $\displaystyle\Rightarrow(x)^{I,A}\coloneqq x^{A}$

•  
  ​

  Si $\displaystyle f$ es un simbolo de funcion de aridad $\displaystyle n\geq 1$ y $\displaystyle t_{1},t_{2},\ldots,t_{n}$ son terminos $\displaystyle\Rightarrow(f(t_{1},t_{2},\ldots,t_{n}))^{I,A}\coloneqq f^{I}(t^{I,A}_{1},t^{I,A}_{2},\ldots,t^{I,A}_{n})$.

Vamos a asociar, de forma recursiva, a cada formula $\displaystyle\varphi$ un valor de verdad $\displaystyle\varphi^{I,A}\in\{0,1\}$

•  
  ​

  $\displaystyle(\top)^{I,A}\coloneqq 1$

•  
  ​

  $\displaystyle(\perp)^{I,A}\coloneqq 0$

•  
  ​

  Si $\displaystyle p$ es un simbolo de proposicion atomica $\displaystyle\Rightarrow(p)^{I,A}\coloneqq p^{I}$

•  
  ​

  Si $\displaystyle P$ es un simbolo de predicado de aridad $\displaystyle n\geq 1$ y $\displaystyle t_{1},t_{2},\ldots,t_{n}$ son terminos $\displaystyle\Rightarrow$

  $$\displaystyle(P(t_{1},t_{2},\ldots,t_{n}))^{I,A}\coloneqq\begin{dcases}1\text{ si }(t^{I,A}_{1},t^{I,A}_{2},\ldots,t^{I,A}_{n})\in P^{I}\\ 0\text{ en caso contrario}\end{dcases}$$
•  
  ​

  Si $\displaystyle t_{1},t_{2}$ son terminos $\displaystyle\Rightarrow$

  $$\displaystyle((t_{1}=t_{2}))^{I,A}=\begin{dcases}1\text{ si }t^{I,A}_{1}=t^{I,A}_{2}\\ 0\text{ en caso contrario}\end{dcases}$$
•  
  ​

  Si $\displaystyle\varphi$ es una formula $\displaystyle(\varphi)^{I,A}$ se define como en proposicional: …

•  
  ​

  Si $\displaystyle\varphi,\psi$ son formulas …

•  
  ​

  Si $\displaystyle\varphi$ es una formula y $\displaystyle x$ es simbolo de variable $\displaystyle\Rightarrow$

  $$\displaystyle(\forall x\varphi)^{I,A}\coloneqq\begin{dcases}1\text{ si }\varphi^{I,A[x/d]}=1\text{ para todos los elementos }d\in D\\ 0\text{ en caso contrario}\end{dcases}$$

  $$\displaystyle(\exists x\varphi)^{I,A}\coloneqq\begin{dcases}1\text{ si }\varphi^{I,A[x/d]}=1\text{ para algun elemento }d\in D\\ 0\text{ en caso contrario}\end{dcases}$$