Diferencia entre revisiones de «Final del 13/11/18 (Lógica y Computabilidad)»
(No se muestran 2 ediciones intermedias del mismo usuario) | |||
Línea 17: | Línea 17: | ||
<math>((\exists x \alpha \wedge \exists x \beta) \rightarrow (\exists x(\alpha \wedge \exists x \beta)))</math> | <math>((\exists x \alpha \wedge \exists x \beta) \rightarrow (\exists x(\alpha \wedge \exists x \beta)))</math> | ||
Solución: | |||
Se resuelve usando árbol de refutación. | Se resuelve usando árbol de refutación. | ||
=Ejercicio 3= | =Ejercicio 3= | ||
Sea P = P(X<sub>1</sub>, ..., X<sub>n</sub>) un predicado computable. | Sea P = P(X<sub>1</sub>, ..., X<sub>n</sub>) un predicado computable. | ||
Demostrar que f(X<sub>1</sub>, ..., X<sub>n-1</sub>) = | Demostrar que <math>f(X_1, ..., X_{n-1}) = Min_t P(X_1, ..., X_{n-1}, t)</math> 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(X<sub>1</sub>, ..., X<sub>n-1</sub>, Z) = 1 goto [B] | |||
<math> Z\leftarrow Z + 1</math> | |||
goto [A] | |||
[B] <math> Y \leftarrow Z</math> | |||
Luego <math>\Phi_Q(X_1, ..., X_{n-1})=f(X_1, ..., X_{n-1}) = Min_t P(X_1, ..., X_{n-1}, t)</math> es parcial computable ya que P es computable y Q computa f. | |||
=Ejercicio 4= | =Ejercicio 4= | ||
Demostrar que a cada número natural n le corresponde la codificación de una única instrucción en el lenguaje S. | Demostrar que a cada número natural n le corresponde la codificación de una única instrucción en el lenguaje S. |
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.