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

=Ejercicio 1=
Sea A = {p, |, ¬, ʌ, v, →, (, )} y sea S un sub-conjunto de A* cerrado por los conectivos. Probar que si S contiene a todas las variables proposicionales, entonces S contiene a todas las fórmulas.

''hint'': sale de la demostración de conjuntos cerrados por los conectivos en los apuntes de la materia.

=Ejercicio 2=
Sea ẟ una fórmula de un lenguaje L de primer orden con una única variable libre ''x'', y sea H un conjunto satisfacible de enunciados de L. Pruebe que si <math>\exists x \delta \isin H</math>, entonces el conjunto que se obtiene agregando a H un enunciado de la forma ẟ(x/c), donde c es un simbolo de constante del vocabulario de L que no figura en ninguno de los enunciados de H, sigue siendo satisfacible.

=Ejercicio 3=
Sea TOT := {<math>n \isin \mathbb{N}_0 : \forall x  \phi (x, n) \darr</math>}. Pruebe que TOT no es recursivamente enumerable.

=Ejercicio 4=
Sean <math>k \isin \mathbb{N}_0</math> y g(x, y) una función total de dos variables. Sea h la función total de una variable definida por

h(0) = k

h(t + 1) = g(t, h(t))

Pruebe que si g es computable, entonces h es computable.

''hint'': sale de armar un programa que calcule h usando g (dado que es computable).
@@ Línea 19: / Línea 19: @@
 Pruebe que si g es computable, entonces h es computable.
-Solución:
+''hint'': sale de armar un programa que calcule h usando g (dado que es computable).
-       <nowiki>Y <- k
-   [A] Id X=0 GOTO E
-       Y <- g(Z,Y)
-       Z <- Z + 1
-       X <- X - 1
-       GOTO A</nowiki>