Final del 21/10/14 (Lógica y Computabilidad)

Ejercicio 1

Hay que probar la existencia y la unicidad de que existe una única valuación que extiende a la función f.

• La existencia se prueba por inducción en la complejidad de la fórmula definiendo en cada caso cómo se evalúa.

Caso Base: sea a tal que comp(a) = 0, entonces a es una variable proposicional. Entonces f(a) está definida. Por lo tanto v(a) = f(a).

Paso Inductivo: supongamos válido hasta n, siendo n igual a la complejidad de a. Veamos si comp(a) = n + 1.

- Si a = ¬b, entonces comp(b) = n, por lo que por H.I. v(b) está definido. Queda que v(a) = 1 - v(b)

- Si a = b * c, con * siendo conector AND, OR o ->. Entonces comp(b) y comp(c) son menores a n+1. Por H.I. v(b) y v(c) están definidos. Por lo tanto:

v(a) = mín(v(b),v(c)) si a = b AND c

v(a) = máx(v(b),v(c)) si a = b OR c

v(a) = máx(1 - v(b),v(c)) si a = b -> c

La función v queda definido para toda fórmula de cualquier complejidad.

• La unicidad se prueba suponiendo que existiese otra función de valuación w que extiende a f

Consideremos el siguiente conjunto:

$I=\{a\in Form\quad \mid \quad v(a)=w(a)\}$

Como w también extiende a f, I contiene a todas las variables proposicionales. Y como v y w son ambas valuaciones, I es cerrado por los conectivos por lo que Form está incluido en I. Es decir, v(P) = w(P) para toda fórmula P.

Usa el teorema de que si subconjunto S de A* es cerrado por los conectivos u S contiene a todas las variables proposicionales entonces S contiene a todas las fórmulas.

Unicidad basado en el apunte de lógica de Roberto Cignoli y Guillermo Martínez. Según Alejandro Petrovich también salía por inducción en la complejidad de la fórmula.

Ejercicio 2

a) La interpretación de un lenguaje de primer orden es una extensión del lenguaje que mapea cada símbolo constante, función k-aria y predicado k-ario a algún elemento del universo de interpretación.

Sea L=<C,F,P>, para una interpretación se define:

- Un universo de interpretación, conjunto no nulo $U_{I}$. Ejemplo: Naturales.

- Para cada símbolo de constante c $\in$ C, mapea con un elemento $c_{I}\in U_{I}$. Ejemplo "cero" -> $c_{i}=0$

- Para cada símbolo de función k-aria $\in$ F, mapea con una función $f_{I}$ de k variables sobre el universo $U_{I}:f_{I}:U_{I}^{k}->U_{I}$

- Para cada símbolo de predicado k-ario $\in$ P, mapea a una relación k-aria $P_{I}$ sobre el universo $U_{I}$. Osea: $U_{I}^{k}=U_{I}x...xU_{I}$ k veces.

b)

- Conmutativo:

$a=\forall x\forall y(f^{2}(x,y)=f^{2}(y,x))$

- Asociativo:

$b=\forall x\forall y\forall z(f^{2}(x,f^{2}(y,z))=f^{2}(f^{2}(x,y),z))$

Solución: $a\wedge b$

Ejercicio 3

Una función es primitiva recursiva si se obtiene a través de las funciones iniciales por composición y/o recursión en finitos pasos.

Sea $f:\mathbb {N} ^{2}\to \mathbb {N}$ tal que $f(a,b)$ devuelve la cantidad de divisores positivos desde $0$ hasta $b$. Con $a$ y $b$ naturales.

Queremos que $\tau (n)=f(n,n)\forall n\in \mathbb {N}$ definiendo a $f$ de la siguiente forma:

$f(n,0)=n(n)$

$f(n,m+1)=g(n,m,f(n,m))$

Con Error al representar (error de sintaxis): {\displaystyle g(a,b,c) = \left\{ \begin{matrix} suc(u^3_3(a,b,c)) \quad si \quad P \\ u^3_3(a,b,c) \quad si \quad \quad \neg P \end{matrix}}

donde $P=u_{1}^{3}(a,b,c)\quad \mid \quad suc(u_{2}^{3}(a,b,c))$

$f$ cumple con el esquema de recursión primitivo.

$n(n)$ es la función inicial nula aplicada a $n$

El predicado $P$ usa la función proyección y la función "divide a" ($\mid$) que es primitiva recursiva.

La función $g$ es una división de casos disjuntos y usa las funciones iniciales de proyección y sucesor.

Por todo lo anterior, la función $f(n,m)$ es primitiva recursiva (con $n$ y $m$ naturales)

Falta ver que $\tau (n)=f(n,n)$. Probamos por inducción en el segundo parámetro.

• Caso base:

$\tau (0)=0$

$f(0,0)=n(0)=0$

• Paso inductivo. Se cumple la hipótesis inductiva f(n,m) devuelve los divisiores de n desde 0 hasta m. Ahora queremos ver para m+1:

Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle f(n,m+1) = g(n,m,f(n,m))}

Dos casos:

- Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle n \mid (m+1)} : Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle g(n,m,f(n,m)) = f(n,m) + 1} . Entonces por H.I. al dividir m+1 incremento en 1 a lo ya calculado en el paso recursivo anterior y éste calculo correctamente hasta m. Queda Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle f(n,m+1) = f(n,m) + 1}

- $\neg (n\mid (m+1))$: Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle g(n,m,f(n,m)) = f(n,m)} . Entonces por H.I. al no dividir m+1 no sumo nada a lo ya calculado en el paso recursivo anterior y éste calcula correctamente hasta m. Queda Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle f(n,m+1) = f(n,m)}

Por lo tanto, Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \tau(n) = f(n,n) \forall n \in \mathbb{N}}

Ejercicio 4

Sea:

Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle f(x) = \{\begin{matrix} Halt(x,x) \quad \quad x \neq 0 \\ 2 \quad \quad \quad x = 0\end{matrix}}

La Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle Img(f) = \{ 0,1,2 \}} . Tiene exactamente 3 elementos.

Supongamos que Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle f(x)} es computable, entonces $\exists P\quad$ programa que computa $f(x)$.

Si $f(x)=2$, entonces $x=0$.

Si $f(x)=0\quad o\quad f(x)=1\quad \longleftrightarrow \quad \psi _{p}(x)\downarrow \quad \rightarrow \quad Halt(x,x)\quad \vee \quad \neg Halt(x,x)$

Sea Error al representar (error de sintaxis): {\displaystyle e=#P} , caso particular, $x=e$: $Halt(e,e)$ determina si el programa $e$ con entrada $e$ termina o no.

Como vimos en las teóricas, estamos resolviendo el halting problem.

Absurdo! pues Halt no es computable. Vino de suponer que $f(x)$ era computable.

Entonces $f(x)$ no computable.