Final del 23/10/18 (Lógica y Computabilidad)

Ejercicio 1

Dadas $\alpha$ y $\beta$ fórmulas proposicionales que no comparten variables, demostrar que si $\alpha \vee \beta$ es una tautología, $\alpha$ es una tautología o $\beta$ es una tautología.

Ejercicio 2

Dado un lenguaje $L$ con igualdad, y un símbolo de función $f^{2}$ binaria. Dadas dos interpretaciones $I_{1}$ e $I_{2}$, ambas con universo en el intervalo real abierto $(0,1)$. En $I_{1}$, $f^{2}$ es interpretada como el producto. En $I_{2}$, $f^{2}$ es interpretada como la distancia ($f^{2}(x,y)=|x-y|$). 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 $P$

b) Demostrar que las funciones primitivas recursivas son computables.

Ejercicio 4

Demostrar que $f(x)=HALT(0,x)$ no es computable.