Final del 22/02/18 (Lógica y Computabilidad)

De Cuba-Wiki
Saltar a: navegación, buscar

Ejercicio 1[editar]

Demostrar que una función es primitiva recursiva sii pertenece a toda clase PRC.

Ejercicio 2[editar]

Definir conjunto de índices. Dar un ejemplo de un conjunto que sea de índices y uno que no lo sea. Enunciar y demostrar el Teorema de Rice.

Ejercicio 3[editar]

Usando el teorema de correctitud de la lógica proposicional, probar que si es un conjunto de fórmulas satisfacible, entonces es consistente.

Ejercicio 4[editar]

Sea = {0, S, <, +, ·} con igualdad y sea = {; 0, S, <, +, ·} la -estructura de primer orden con la interpretación usual. Mostrar que existe un modelo de los Naturales en donde valen todas las verdades de , pero donde existe un elemento inalcanzable (desde el 0, usando la función sucesor S).