23 Evaluacion semantica de formulas (valores de verdad)

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

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

• •
  ​

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

• •
  ​

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

  • –
    ​

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

  • –
    ​

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

  • –
    ​

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

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

• •
  ​

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

Sean $\Sigma$ una signatura, $(D,I)$ una interpretacion definida sobre $\Sigma$ y $A$ una asignacion.

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

• •
  ​

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

• •
  ​

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

• •
  ​

  Si $f$ es un simbolo de funcion de aridad $n\geq 1$ y $t_{1},t_{2},\ldots,t_{n}$ son terminos $\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})$.

Sean $\Sigma$ una signatura, $(D,I)$ una interpretacion definida sobre $\Sigma$ y $A$ una asignacion.

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

• •
  ​

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

• •
  ​

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

• •
  ​

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

• •
  ​

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

  $$(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 $t_{1},t_{2}$ son terminos $\Rightarrow$

  $$((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 $\varphi$ es una formula $(\varphi)^{I,A}$ se define como en proposicional: …

• •
  ​

  Si $\varphi,\psi$ son formulas …

• •
  ​

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

  $$(\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}$$

  $$(\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}$$