Diferencia entre revisiones de «Final del 13/11/18 (Lógica y Computabilidad)»
Línea 28: | Línea 28: | ||
Es fácil de demostrar escribiendo un programa que compute f, como por ejemplo el siguiente programa Q: | Es fácil de demostrar escribiendo un programa que compute f, como por ejemplo el siguiente programa Q: | ||
[A] IF P | [A] IF P(X<sub>1</sub>, ..., X<sub>n-1</sub>, Z) = 1 goto [B] | ||
<math> Z\leftarrow Z + 1</math> | <math> Z\leftarrow Z + 1</math> | ||
goto [A] | goto [A] |
Revisión actual - 17:47 14 nov 2018
Ejercicio 1[editar]
Sean α y β fórmulas de la lógica proposicional. Determinar la validez del siguiente enunciado:
es contingencia es Tautologia y es contingencia.
Solución:
Es falso, la vuelta no vale si , y es contingencia. Luego se cumple el antecedente pero
Ejercicio 2[editar]
Sea L un lenguaje de logica de primer orden. Sean α y β fórmulas de la lógica de primer orden con solo una variable x libre.
Probar si el siguiente enunciado es universalmente válido:
Solución: Se resuelve usando árbol de refutación.
Ejercicio 3[editar]
Sea P = P(X1, ..., Xn) un predicado computable. Demostrar que es parcial computable.
Solución:
Es fácil de demostrar escribiendo un programa que compute f, como por ejemplo el siguiente programa Q:
[A] IF P(X1, ..., Xn-1, Z) = 1 goto [B] goto [A] [B]
Luego es parcial computable ya que P es computable y Q computa f.
Ejercicio 4[editar]
Demostrar que a cada número natural n le corresponde la codificación de una única instrucción en el lenguaje S.