Edición de «Final del 05/08/13 (Lógica y Computabilidad)»
De Cuba-Wiki
Puedes deshacer la edición. Antes de deshacer la edición, comprueba la siguiente comparación para verificar que realmente es lo que quieres hacer, y entonces publica los cambios para así efectuar la reversión.
Revisión actual | Tu texto | ||
Línea 1: | Línea 1: | ||
Ejercicio 1 | |||
Probar que la clase de funciones computables es una clase '''PRC''' | Probar que la clase de funciones computables es una clase '''PRC''' | ||
Ejercicio 2 | |||
Definir '''conjunto de índices'''. Enunciar y demostrar el '''Teorema de Rice''' | Definir '''conjunto de índices'''. Enunciar y demostrar el '''Teorema de Rice''' | ||
Ejercicio 3 | |||
Usando el '''Teorema de Correctitud''' de la lógica proposicional probar que si <math>\Gamma</math> es satisfactible entonces <math>\Gamma</math> es consistente. | Usando el '''Teorema de Correctitud''' de la lógica proposicional probar que si <math>\Gamma</math> es satisfactible entonces <math>\Gamma</math> es consistente. | ||
Ejercicio 4 | |||
Dado ''L'' un lenguaje de primer orden con igualdad. Decidir si las siguientes afirmaciones son verdaderas o falsas. | Dado ''L'' un lenguaje de primer orden con igualdad. Decidir si las siguientes afirmaciones son verdaderas o falsas. | ||
Línea 21: | Línea 19: | ||
2. Existe un conjunto <math>\Gamma</math> tal que <math>\Gamma \models A</math> sii A tiene universo finito. | 2. Existe un conjunto <math>\Gamma</math> tal que <math>\Gamma \models A</math> sii A tiene universo finito. | ||
3. El | 3. El conjutno <math>\Gamma</math> del ítem 1 necesariamente es infinito. |