Ver el código de «Final del 10/09/14 (Lógica y Computabilidad)»

=Ejercicio 1=

 a) Dar el concepto de consecuencia para lógica proposicional
 b) Demostrar que <math>\beta</math> es consecuencia lógica de <math>\Gamma</math> si y sólo si {<math>\Gamma</math> U ¬<math>\beta</math>} es insatisfacible

=Ejercicio 2=

<math>L</math> es un lenguaje con igualdad y un predicado binario <math>P</math>. Dada una interpretación con universo en los Naturales y con el predicado <. 
Probar que 0, 1 y 2 son distinguibles.
  

=Ejercicio 3=

<math>B</math> es un conjunto de naturales. Demostrar que <math>B</math> es recursivo si y sólo si <math>B</math> y <math>\overline{B}</math> son recursivamente enumerables.
 

=Ejercicio 4=

Demostrar que <math>halt(0,y)</math> no es computable.