Edición de «Final del 17/03/07 (Lógica y Computabilidad)»

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

== Ejercicio 3 (2 p.) ==
Sea <math>\Gamma</math> un conjunto de fórmulas de la lógica proposicional. Demostrar que si <math>\Gamma</math> es consistente entonces es satisfacible. (Aclaración: no hace falta demostrar el lema de Lindenbaum.)

== Ejercicio 4 ==
Sea <math>L</math> = {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 <math>\varphi, \psi \in Form(L)</math> tal que
* <math>\varphi</math> sea verdadera sii c no pertenece al rango de f
* <math>\psi</math> sea verdadera sii f es inyectiva

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

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

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