Diferencia entre revisiones de «Final del 05/08/13 (Lógica y Computabilidad)»
De Cuba-Wiki
Sin resumen de edición |
Sin resumen de edición |
||
| (No se muestran 2 ediciones intermedias de 2 usuarios) | |||
| Línea 1: | Línea 1: | ||
Ejercicio 1 | {{Back|Lógica y Computabilidad}} | ||
=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 | =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 | =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 | =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. | ||
1. Existe un conjunto <math>\Gamma</math> tal que <math>\Gamma \models A</math> sii A tiene universo infinito. | 1. Existe un conjunto <math>\Gamma</math> tal que <math>\Gamma \models A</math> sii A tiene universo infinito. | ||
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 conjunto <math>\Gamma</math> del ítem 1 necesariamente es infinito. | |||
Revisión actual - 17:03 7 abr 2015
Ejercicio 1[editar]
Probar que la clase de funciones computables es una clase PRC
Ejercicio 2[editar]
Definir conjunto de índices. Enunciar y demostrar el Teorema de Rice
Ejercicio 3[editar]
Usando el Teorema de Correctitud de la lógica proposicional probar que si es satisfactible entonces es consistente.
Ejercicio 4[editar]
Dado L un lenguaje de primer orden con igualdad. Decidir si las siguientes afirmaciones son verdaderas o falsas.
1. Existe un conjunto tal que sii A tiene universo infinito.
2. Existe un conjunto tal que sii A tiene universo finito.
3. El conjunto del ítem 1 necesariamente es infinito.
