Semántica de lógica de predicados

Lógica Computacional, Fac. Ciencias, UNAM. Noé Hernández

El valor de verdad de una fórmula en lógica de predicados depende de la elección específica del universo, de los valores de los términos, y del significado de los símbolos de predicados y de función involucrados, esto constituye un modelo.

Lógica Computacional, Fac. Ciencias, UNAM. Noé Hernández

Ejemplo 1

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

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

Las interpretaciones iMi^{\mathcal{M}}, RMR^{\mathcal{M}} y FMF^{\mathcal{M}} pueden ser un estado inicial, una relación de transición entre estados y un conjunto de estados finales, respectivamente.

Lógica Computacional, Fac. Ciencias, UNAM. Noé Hernández

Sea A=def{a,b,c}A \stackrel{\mathrm{def}}{=} \{a, b, c\}, iM=defai^{\mathcal{M}} \stackrel{\mathrm{def}}{=} a, FM=def{b,c}F^{\mathcal{M}} \stackrel{\mathrm{def}}{=} \{b,c\} y
RM=def{(a,a),(a,b),(a,c),(b,c),(c,c)}R^{\mathcal{M}} \stackrel{\mathrm{def}}{=} \{(a,a), (a,b), (a,c), (b,c), (c,c)\}

Lógica Computacional, Fac. Ciencias, UNAM. Noé Hernández

¿Es ∃y R(i,y)\exists y\, R(i, y) cierta?

  • ⇒ Sí

Lógica Computacional, Fac. Ciencias, UNAM. Noé Hernández

¿Es  ¬F(i)\ \neg F(i) cierta?

  • ⇒ Sí

Lógica Computacional, Fac. Ciencias, UNAM. Noé Hernández

¿Es
∀x∀y∀z(R(x,y)∧R(x,z)→y=z)\footnotesize\forall x \forall y \forall z (R(x,y)\!\land\! R(x,z)\!\to\!y=z)
cierta?

  • ⇒ No

  • ¿Qué pasa si hay un estado que no tiene transiciones que salgan de él?

  • Dicho estado satisface la fórmula

Lógica Computacional, Fac. Ciencias, UNAM. Noé Hernández

¿Es ∀x∃y R(x,y)\forall x \exists y\, R(x,y) cierta?

  • ⇒ Sí

Lógica Computacional, Fac. Ciencias, UNAM. Noé Hernández

Ejemplo 2

Sea F=def{e,⋅}\mathcal{F} \stackrel{\mathrm{def}}{=} \{e, \cdot\} y P=def{≤}\mathcal{P} \stackrel{\mathrm{def}}{=} \{\leq\}, donde ee 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

(t1⋅t2)≤(t⋅t).(t_1 \cdot t_2) \leq (t \cdot t).

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

Lógica Computacional, Fac. Ciencias, UNAM. Noé Hernández

¿Es ∀x((x≤x⋅ε)∧(x⋅ε≤x))\forall x \left( (x \leq x \cdot \varepsilon) \land (x \cdot \varepsilon \leq x) \right) cierta?

  • ⇒ Sí

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

  • ¿Es ∀x∃y (x≤y)\forall x \exists y\, (x\leq y) cierta?
  • ⇒ Sí
Lógica Computacional, Fac. Ciencias, UNAM. Noé Hernández

¿Es ∀x∀y∀z((x≤y)→(x⋅z≤y⋅z))\forall x \forall y \forall z \left( (x \leq y) \rightarrow (x \cdot z \leq y \cdot z) \right) cierta?

  • ⇒ No

  • ¿Es ¬∃x∀y((x≤y)→(y≤x))\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
Lógica Computacional, Fac. Ciencias, UNAM. Noé Hernández

Ejemplo 3

Considere los enunciados:

φ1=def∀x P(x,x)φ2=def∀x ∀y (P(x,y)→P(y,x))φ3=def∀x ∀y ∀z ((P(x,y)∧P(y,z))→P(x,z))\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 PP, cada una satisfaciendo solo dos de estas propiedades.

Lógica Computacional, Fac. Ciencias, UNAM. Noé Hernández

Considere los enunciados:

φ1=def∀x P(x,x)φ2=def∀x ∀y (P(x,y)→P(y,x))φ3=def∀x ∀y ∀z ((P(x,y)∧P(y,z))→P(x,z))\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 AA como los números enteros, y

P={(n,m) ∣  ∣n−m∣≤1}P=\{(n,m)\,|\,\ |n-m|\leq 1\}

  • Se satisfacen φ1\varphi_1 y φ2\varphi_2, pero no φ3\varphi_3.
Lógica Computacional, Fac. Ciencias, UNAM. Noé Hernández

Considere los enunciados:

φ1=def∀x P(x,x)φ2=def∀x ∀y (P(x,y)→P(y,x))φ3=def∀x ∀y ∀z ((P(x,y)∧P(y,z))→P(x,z))\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 AA como Bart, Lisa y Maggie Simpson, y

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

  • Se satisfacen φ2\varphi_2 y φ3\varphi_3, pero no φ1\varphi_1.
Lógica Computacional, Fac. Ciencias, UNAM. Noé Hernández

Considere los enunciados:

φ1=def∀x P(x,x)φ2=def∀x ∀y (P(x,y)→P(y,x))φ3=def∀x ∀y ∀z ((P(x,y)∧P(y,z))→P(x,z))\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 AA como los enteros, y

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

  • Se satisfacen φ1\varphi_1 y φ3\varphi_3, pero no φ2\varphi_2.
Lógica Computacional, Fac. Ciencias, UNAM. Noé Hernández

Ejemplo 4

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

∀x∀yQ(g(x,y),g(y,y),z)\forall x \forall y Q(g(x,y), g(y,y), z) depende del valor de zz. Elegimos AA como Z\mathbb{Z}, gM(n,m)=n−mg^{\mathcal{M}}(n, m)=n-m, y (p,q,r)∈QM(p,q,r)\in Q^{\mathcal{M}} si y solo si r=p⋅qr = p\cdot q.  gM(y,y)\, g^{\mathcal{M}}(y,y) se interpreta como 00 y QM(gM(x,y),gM(y,y),z)Q^{\mathcal{M}}(g^{\mathcal{M}}(x,y), g^{\mathcal{M}}(y,y), z) afirma que 00 es el valor de zz. M′\mathcal{M}' es idéntico a M\mathcal{M}, pero con l(z)=def0l(z) \stackrel{\mathrm{def}}{=} 0 la fórmula se cumple, mientras que con l′(z)=def1l'(z) \stackrel{\mathrm{def}}{=} 1 no.

Lógica Computacional, Fac. Ciencias, UNAM. Noé Hernández

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
Lógica Computacional, Fac. Ciencias, UNAM. Noé Hernández

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
Lógica Computacional, Fac. Ciencias, UNAM. Noé Hernández