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 |
||
| (No se muestran 2 ediciones intermedias de otro usuario) | |||
| Línea 1: | Línea 1: | ||
{{Back|Lógica y Computabilidad}} | |||
=Ejercicio 1= | =Ejercicio 1= | ||
| Línea 6: | Línea 8: | ||
=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 <math><</math>. | ||
Probar que 0, 1 y 2 son distinguibles. | Probar que 0, 1 y 2 son distinguibles. | ||
=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 actual - 17:03 7 abr 2015
Ejercicio 1[editar]
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[editar]
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[editar]
es un conjunto de naturales. Demostrar que es recursivo si y sólo si y son recursivamente enumerables.
Ejercicio 4[editar]
Demostrar que no es computable.
