Final del 10/09/14 (Lógica y Computabilidad)

Ejercicio 1

a) Dar el concepto de consecuencia para lógica proposicional
b) Demostrar que $\beta$ es consecuencia lógica de $\Gamma$ si y sólo si {$\Gamma$ U ¬$\beta$} 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 $B$ es recursivo si y sólo si $B$ y ${\overline {B}}$ son recursivamente enumerables.

Ejercicio 4

Demostrar que $halt(0,y)$ no es computable.