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

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 $A$ y ${\overline {A}}$ son r.e.

Ejercicio 3 (2 p.)

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

Ejercicio 4 (3 p.)

Sea $L$ = {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 $\varphi ,\psi \in Form(L)$ tal que

• $\varphi$ sea verdadera sii c no pertenece al rango de f
• $\psi$ sea verdadera sii f es inyectiva

2. (1 p.) Para $\theta =(\varphi \wedge \psi )$, probar que si $A\vdash \theta$ entonces $A$ es infinito.

3. (0,5 p.) Definir $\theta '\in Form(L)$ tal que si $A$ es infinito entonces $A\vdash \theta '$.

4. (1 p.) ¿Existe $\theta ''\in Form(L)$ tal que $A$ es infinito sii $A\vdash \theta ''$? Justificar.