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 4 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.
 
=Ejercicio 4=
 
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.
 
2. Existe un conjunto <math>\Gamma</math> tal que <math>\Gamma \models A</math> sii A tiene universo finito.


Usando el '''Teorema de Correctitud''' de la lógica proposicional probar que si
3. El conjunto <math>\Gamma</math> del ítem 1 necesariamente es infinito.

Revisión actual - 17:03 7 abr 2015

Plantilla:Back

Ejercicio 1

Probar que la clase de funciones computables es una clase PRC

Ejercicio 2

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 es satisfactible entonces es consistente.

Ejercicio 4

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.