Diferencia entre revisiones de «Final del 17/03/07 (Lógica y Computabilidad)»

De Cuba-Wiki
(Sin diferencias)

Revisión del 17:47 24 feb 2015

Plantilla:Back

Ejercicio 1 (2,5 p.)

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

Ejercicio 2 (2,5 p.)

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

Ejercicio 3 (2 p.)

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

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.