Final del 17/03/07 (Lógica y Computabilidad)

De Cuba-Wiki
Saltar a: navegación, buscar
Back.png Volver a la página de la materia

Ejercicio 1 (2,5 p.)[editar]

Enunciar y demostrar el teorema de Rice. (Aclaración: no hace falta demostrar el teorema de la Recursión.)

Ejercicio 2 (2,5 p.)[editar]

Demostrar que A es computable sii y son r.e.

Ejercicio 3 (2 p.)[editar]

Sea un conjunto de fórmulas de la lógica proposicional. Demostrar que si es consistente entonces es satisfacible. (Aclaración: no hace falta demostrar el lema de Lindenbaum.)

Ejercicio 4 (3 p.)[editar]

Sea = {c, f} un lenguaje de primer orden con igualdad donde c es un símbolo de constante y f un símbolo de función unaria.

1. (0,5 p.) Definir tal que

  • sea verdadera sii c no pertenece al rango de f
  • sea verdadera sii f es inyectiva

2. (1 p.) Para , probar que si entonces es infinito.

3. (0,5 p.) Definir tal que si es infinito entonces .

4. (1 p.) ¿Existe tal que es infinito sii ? Justificar.