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

Ejercicio 1

Sean α y β fórmulas de la lógica proposicional. Determinar la validez del siguiente enunciado:

$(\alpha \rightarrow \beta )$ es contingencia $\leftrightarrow \exists \delta /(\alpha \rightarrow \delta )$ es Tautologia y $(\delta \rightarrow \beta )$ es contingencia.

Solución:

Es falso, la vuelta no vale si $\alpha =F$, $\beta =F$ y $\delta$ es contingencia. Luego se cumple el antecedente pero $(\alpha \rightarrow \beta )=F\rightarrow F=T$

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:

$((\exists x\alpha \wedge \exists x\beta )\rightarrow (\exists x(\alpha \wedge \exists x\beta )))$

Solución: Se resuelve usando árbol de refutación.

Ejercicio 3

Sea P = P(X₁, ..., X_n) un predicado computable. Demostrar que $f(X_{1},...,X_{n-1})=Min_{t}P(X_{1},...,X_{n-1},t)$ 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]
     $Z\leftarrow Z+1$
     goto [A]
 [B] $Y\leftarrow Z$

Luego $\Phi _{Q}(X_{1},...,X_{n-1})=f(X_{1},...,X_{n-1})=Min_{t}P(X_{1},...,X_{n-1},t)$ 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.