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 f(X<sub>1</sub>, ..., X<sub>n-1</sub>) = Min<sub>t</sub> P((X<sub>1</sub>, ..., X<sub>n-1</sub>, t) es parcial computable.

=Ejercicio 4= 
Demostrar que a cada número natural n le corresponde la codificación de una única instrucción en el lenguaje S.
@@ Línea 22: / Línea 22: @@
 =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.
+Demostrar que f(X<sub>1</sub>, ..., X<sub>n-1</sub>) = Min<sub>t</sub> P((X<sub>1</sub>, ..., X<sub>n-1</sub>, t) 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.