Diferencia entre revisiones de «Final del 10/09/14 (Lógica y Computabilidad)»

De Cuba-Wiki
(Página creada con «=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...»)
 
Sin resumen de edición
Línea 6: Línea 6:
=Ejercicio 2=
=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 <.  
<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.
Probar que 0, 1 y 2 son distinguibles.
    
    
Línea 12: Línea 12:
=Ejercicio 3=
=Ejercicio 3=


B 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.
<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=
=Ejercicio 4=


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

Revisión del 00:40 13 sep 2014

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

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


Ejercicio 3

es un conjunto de naturales. Demostrar que es recursivo si y sólo si y son recursivamente enumerables.


Ejercicio 4

Demostrar que no es computable.