Final del 10/09/14 (Lógica y Computabilidad)
De Cuba-Wiki
Ejercicio 1
a) Dar el concepto de consecuencia para lógica proposicional b) Demostrar que es consecuencia lógica de si y sólo si { U ¬} es insatisfacible
Ejercicio 2
L es un lenguaje con igualdad y un predicado binario P. Dada una interpretación con universo en los Naturales y con el predicado <. Probar que 0, 1 y 2 son distinguibles.
Ejercicio 3
B es un conjunto de naturales. Demostrar que es recursivo si y sólo si y son recursivamente enumerables.
Ejercicio 4
Demostrar que halt(0,y) no es computable.