Final del 13/11/18 (Lógica y Computabilidad)

De Cuba-Wiki

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.