Diferencia entre revisiones de «Final del 22/10/18 (Lógica y Computabilidad)»

De Cuba-Wiki
Saltar a: navegación, buscar
(Página creada con «=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,…»)
(Sin diferencias)

Revisión del 19:11 10 nov 2019

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 , 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 := {}. Pruebe que TOT no es recursivamente enumerable.

Ejercicio 4

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