Semántica de lógica de predicados

Ejemplo 1

Sea $\mathcal{F} \stackrel{\mathrm{def}}{=} \{i\}$ y $\mathcal{P} \stackrel{\mathrm{def}}{=} \{R, F\}$, donde $i$ es una constante, $F$ un símbolo de predicado con un argumento y $R$ un símbolo de predicado con dos argumentos.

Un modelo $\mathcal{M}$ contiene un conjunto de elementos concretos $A$, como estados de un programa de computadora.

Las interpretaciones $i^{\mathcal{M}}$, $R^{\mathcal{M}}$ y $F^{\mathcal{M}}$ pueden ser un estado inicial, una relación de transición entre estados y un conjunto de estados finales, respectivamente.

Ejemplo 2

Sea $\mathcal{F} \stackrel{\mathrm{def}}{=} \{e, \cdot\}$ y $\mathcal{P} \stackrel{\mathrm{def}}{=} \{\leq\}$, donde $e$ es una constante, $\cdot$ es una función con dos argumentos y $\leq$ es un predicado que necesita dos argumentos también. Escribimos $\cdot$ y $\leq$ en notación infija como en

$$(t_1 \cdot t_2) \leq (t \cdot t).$$

El modelo $\mathcal{M}$ define $A$ como las cadenas binarias, incluyendo la cadena vacía, que denotamos por $\varepsilon$. La interpretación $e^{\mathcal{M}}$ es $\varepsilon$, $\cdot^{\mathcal{M}}$ es la concatenación de palabras, $\leq^{\mathcal{M}}$ como la relación de prefijos de palabras.

¿Es $\forall x \left( (x \leq x \cdot \varepsilon) \land (x \cdot \varepsilon \leq x) \right)$ cierta?

• ⇒ Sí

• ¿Es $\exists y \forall x\, (y \leq x)$ cierta?
• ⇒ Sí

• ¿Es $\forall x \exists y\, (x\leq y)$ cierta?
• ⇒ Sí

¿Es $\forall x \forall y \forall z \left( (x \leq y) \rightarrow (x \cdot z \leq y \cdot z) \right)$ cierta?

• ⇒ No

• ¿Es $\neg \exists x \forall y \left( (x \leq y) \rightarrow (y \leq x) \right)$ cierta?
• ⇒ Sí

• La demostración formal de las fórmulas universales para las cadenas suele proceder por inducción estructural

Ejemplo 3

Considere los enunciados:

$$\def\arraystretch{1.5} \begin{array}{lll} \varphi_1 &\stackrel{\mathrm{def}}{=}& \forall x\, P(x,x)\\ \varphi_2 &\stackrel{\mathrm{def}}{=}& \forall x\, \forall y\, (P(x,y) \rightarrow P(y,x))\\ \varphi_3 &\stackrel{\mathrm{def}}{=}& \forall x\, \forall y\, \forall z\, ((P(x,y) \wedge P(y,z)) \rightarrow P(x,z)) \end{array}$$

Encuentre tres relaciones binarias $P$, cada una satisfaciendo solo dos de estas propiedades.

Considere los enunciados:

$$\def\arraystretch{1.5} \begin{array}{lll} \varphi_1 &\stackrel{\mathrm{def}}{=}& \forall x\, P(x,x)\\ \varphi_2 &\stackrel{\mathrm{def}}{=}& \forall x\, \forall y\, (P(x,y) \rightarrow P(y,x))\\ \varphi_3 &\stackrel{\mathrm{def}}{=}& \forall x\, \forall y\, \forall z\, ((P(x,y) \wedge P(y,z)) \rightarrow P(x,z)) \end{array}$$

el universo $A$ como los números enteros, y

$$P=\{(n,m)\,|\,\ |n-m|\leq 1\}$$

• Se satisfacen $\varphi_1$ y $\varphi_2$, pero no $\varphi_3$.

Considere los enunciados:

$$\def\arraystretch{1.5} \begin{array}{lll} \varphi_1 &\stackrel{\mathrm{def}}{=}& \forall x\, P(x,x)\\ \varphi_2 &\stackrel{\mathrm{def}}{=}& \forall x\, \forall y\, (P(x,y) \rightarrow P(y,x))\\ \varphi_3 &\stackrel{\mathrm{def}}{=}& \forall x\, \forall y\, \forall z\, ((P(x,y) \wedge P(y,z)) \rightarrow P(x,z)) \end{array}$$

el universo $A$ como Bart, Lisa y Maggie Simpson, y

$$P(x,y): \text{``$x$ es hermano(a) de }y\text{''}$$

• Se satisfacen $\varphi_2$ y $\varphi_3$, pero no $\varphi_1$.

Considere los enunciados:

$$\def\arraystretch{1.5} \begin{array}{lll} \varphi_1 &\stackrel{\mathrm{def}}{=}& \forall x\, P(x,x)\\ \varphi_2 &\stackrel{\mathrm{def}}{=}& \forall x\, \forall y\, (P(x,y) \rightarrow P(y,x))\\ \varphi_3 &\stackrel{\mathrm{def}}{=}& \forall x\, \forall y\, \forall z\, ((P(x,y) \wedge P(y,z)) \rightarrow P(x,z)) \end{array}$$

el universo $A$ como los enteros, y

$$P(p,q): \text{``$p$ divide a $q$''}$$

• Se satisfacen $\varphi_1$ y $\varphi_3$, pero no $\varphi_2$.

Ejemplo 4

Considere $\varphi \stackrel{\mathrm{def}}{=} \forall x\forall y Q(g(x,y),g(y,y),z)$, donde $Q^{(3)}$ y $g^{(2)}$. Encuentre $\mathcal{M}$ y $\mathcal{M}'$ con ambientes respectivos $l$ y $l'$ tales que $\mathcal{M}\models_l\varphi$ y $\mathcal{M}'\cancel\models_{l'}\varphi$.

$\forall x \forall y Q(g(x,y), g(y,y), z)$ depende de los valores de $z$. Elegimos $A$ como $\mathbb{Z}$, $g^{\mathcal{M}}(n, m)=n-m$, y $(p,q,r)$ está en $Q^{\mathcal{M}}$ si y solo si $r$ es el producto de $p$ por $q$. $\, g(y,y)$ se interpreta como $0$ y nuestra fórmula afirma que $0$ es igual al valor de $z$. Para $l(z) \stackrel{\mathrm{def}}{=} 0$ la fórmula se cumple, mientras que para $l'(z) \stackrel{\mathrm{def}}{=} 1$ es falsa.

Ejemplo 5

Suponiendo que una y sólo una de las siguientes oraciones es verdadera, ¿cuál es?

1. Hay un mexicano que no es guapo
2. Javier es mexicano
3. No todos los mexicanos son guapos
4. Hay por lo menos un mexicano
5. Javier es mexicano y es guapo

Ejemplo 5

Suponiendo que una y sólo una de las siguientes oraciones es verdadera, ¿cuál es?

1. Hay un mexicano que no es guapo
2. Javier es mexicano
3. No todos los mexicanos son guapos
4. Hay por lo menos un mexicano ← Respuesta
5. Javier es mexicano y es guapo