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).