La versión para imprimir ya no se admite y puede contener errores de representación. Actualiza los marcadores del navegador y utiliza en su lugar la función de impresión predeterminada del navegador.
Ejercicio 1
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
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
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
Demostrar que a cada número natural n le corresponde la codificación de una única instrucción en el lenguaje S.