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

De Cuba-Wiki
(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,…»)
 
 
Línea 19: Línea 19:
Pruebe que si g es computable, entonces h es computable.
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).
Solución:
 
      <nowiki>Y <- k
  [A] Id X=0 GOTO E
      Y <- g(Z,Y)
      Z <- Z + 1
      X <- X - 1
      GOTO A</nowiki>

Revisión actual - 23:19 10 nov 2019

Ejercicio 1[editar]

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[editar]

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[editar]

Sea TOT := {}. Pruebe que TOT no es recursivamente enumerable.

Ejercicio 4[editar]

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.

Solución:

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