Edición de «Final del 13/11/18 (Lógica y Computabilidad)»


=Ejercicio 1=
Sean α y β fórmulas de la lógica proposicional. Determinar la validez del siguiente enunciado:

<math>(\alpha \rightarrow \beta)</math> es contingencia <math>\leftrightarrow \exists \delta / (\alpha \rightarrow \delta)</math> es Tautologia y <math>(\delta \rightarrow \beta)</math> es contingencia.


Solución:

Es falso, la vuelta no vale si <math>\alpha = F<\math>, <math>\beta = F<\math> y <math>\delta<\math> es contingencia. Luego se cumple el antecedente pero <math>(\alpha \rightarrow \beta) = F \rightarrow F = T</math>

=Ejercicio 2=
Sea L un lenguaje de logica de primer orden. Sean α y β fórmulas de la lógica de primer orden con solo una variable x libre.

Probar si el siguiente enunciado es universalmente válido:

<math>((\exists x \alpha \wedge \exists x \beta) \rightarrow (\exists x(\alpha \wedge \exists x \beta)))</math>

Solución:
Se resuelve usando árbol de refutación.

=Ejercicio 3=
Sea P = P(X<sub>1</sub>, ..., X<sub>n</sub>) un predicado computable.
Demostrar que <math>f(X_1, ..., X_{n-1}) = Min_t P(X_1, ..., X_{n-1}, t)</math> es parcial computable.

Solución:

Es fácil de demostrar escribiendo un programa que compute f, como por ejemplo el siguiente programa Q:

  [A] IF P(X<sub>1</sub>, ..., X<sub>n-1</sub>, Z) = 1 goto [B]
      <math> Z\leftarrow Z + 1</math>
      goto [A]
  [B] <math> Y \leftarrow Z</math>

Luego <math>\Phi_Q(X_1, ..., X_{n-1})=f(X_1, ..., X_{n-1}) = Min_t P(X_1, ..., X_{n-1}, t)</math> es parcial computable ya que P es computable y Q computa f.

=Ejercicio 4= 
Demostrar que a cada número natural n le corresponde la codificación de una única instrucción en el lenguaje S.