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 $\exists x\delta \in H$, 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 := {$n\in \mathbb {N} _{0}:\forall x\phi (x,n)\downarrow$}. Pruebe que TOT no es recursivamente enumerable.

Ejercicio 4

Sean $k\in \mathbb {N} _{0}$ 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.

Solución:

      Y <- k
   [A] Id X=0 GOTO E
       Y <- g(Z,Y)
       Z <- Z + 1
       X <- X - 1
       GOTO A