Diferencia entre revisiones de «Final del 11/12/14 (Lógica y Computabilidad)»
De Cuba-Wiki
(Página creada con «=Ejercicio 1= Enunciar el halting problem y demostrar que HALT no es computable =Ejercicio 2= Enunciar y demostrar el teorema de Rice =Ejercicio 3= Definir consistente...») |
Sin resumen de edición |
||
| Línea 14: | Línea 14: | ||
Dar un conjunto de formulas <math>\Gamma</math> tal que <math>\Gamma</math> es valida sii el modelo que la satisface es infinito. | Dar un conjunto de formulas <math>\Gamma</math> tal que <math>\Gamma</math> es valida sii el modelo que la satisface es infinito. | ||
¿Existe una formula <math>\varphi</math> tal que <math>\varphi</math> es valida sii el modelo que la satisface es finito? | ¿Existe una formula <math>\varphi</math> tal que <math>\varphi</math> es valida sii el modelo que la satisface es finito? ¿Por que ? | ||
Revisión del 03:56 12 dic 2014
Ejercicio 1
Enunciar el halting problem y demostrar que HALT no es computable
Ejercicio 2
Enunciar y demostrar el teorema de Rice
Ejercicio 3
Definir consistente, maximal consistente y demostrar el Lema de Lindenbaum
Ejercicio 4
Dar un conjunto de formulas tal que es valida sii el modelo que la satisface es infinito. ¿Existe una formula tal que es valida sii el modelo que la satisface es finito? ¿Por que ?
