Ver el código de «Final del 23/10/18 (Lógica y Computabilidad)»

=Ejercicio 1=
Dadas <math>\alpha</math> y <math>\beta</math> fórmulas proposicionales que no comparten variables, demostrar que si <math>\alpha \wedge \beta</math> es una tautología, <math>\alpha</math> es una tautología o <math>\beta</math> es una tautología.

=Ejercicio 2=
Dado un lenguaje <math>L</math> con igualdad, y un símbolo de función <math>f^2</math> binaria. Dadas dos interpretaciones <math>I_1</math> e <math>I_2</math>, ambas con universo en el intervalo real abierto <math>(0,1)</math>. En <math>I_1</math>, <math>f^2</math> es interpretada como el producto. En <math>I_2</math>, <math>f^2</math> es interpretada como la distancia (<math>f^2(x,y) = |x-y|</math>). Encontrar un enunciado que sea válido en una interpretación y no en la otra.

=Ejercicio 3=
a) Dar una noción de función parcial computable desde un programa <math>P</math>

b) Demostrar que las funciones primitivas recursivas son computables.

=Ejercicio 4=
Demostrar que <math>f(x) = HALT(0,x)</math> no es computable.