Final del 28/12/10 (Lógica y Computabilidad)

De Cuba-Wiki
Saltar a: navegación, buscar
Back.png Volver a la página de la materia

Ejercicio 1[editar]

Probar que si A y B son c.e., entonces también son c.e. los conjuntos A ∪ B y A ∩ B

Ejercicio 2[editar]

Enunciar y demostrar el Teorema de Rice.

Ejercicio 3[editar]

Enunciar y demostrar el Lema de Lindenbaum para la lógica proposicional.

Ejercicio 4[editar]

Sea 𝓛 = { 0, S, <, +, · } con igualdad y sea 𝓝 = ⟨ ; 0, S, <, +, · ⟩ una 𝓛-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 en donde existe un elemento inalcanzable (desde el 0, usando la función sucesor S).