| Revisión actual |
Tu texto |
| Línea 1: |
Línea 1: |
| {{Back|Lógica y Computabilidad}}
| |
|
| |
| [[Archivo:2014-10-21_18.27.04.jpg | 800px]] | | [[Archivo:2014-10-21_18.27.04.jpg | 800px]] |
|
| |
| =Ejercicio 1=
| |
|
| |
| Hay que probar la existencia y la unicidad de que existe una única valuación <math>v</math> que extiende a la función <math>f</math>.
| |
|
| |
|
| |
| *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 <math>comp(a) = 0</math>, entonces a es una variable proposicional. Entonces f(a) está definida. Por lo tanto <math>v(a) = f(a)</math>.
| |
|
| |
|
| |
| Paso Inductivo: supongamos válido hasta n, siendo n igual a la complejidad de a. Veamos si <math>comp(a) = n + 1</math>.
| |
|
| |
|
| |
| - Si <math>a = \neg b</math>, entonces <math>comp(b) = n</math>, por lo que por H.I. <math>v(b)</math> está definido. Queda que <math>v(a) = 1 - v(b)</math>.
| |
|
| |
|
| |
| - Si <math>a = b * c</math>, con <math>* \quad \in \{\wedge, \vee, \rightarrow \}</math>. 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:
| |
|
| |
|
| |
| <math>v(a) = min\{v(b),v(c)\}</math> si <math>a = b \quad \wedge \quad c</math>
| |
|
| |
|
| |
| <math>v(a) = max\{v(b),v(c)\}</math> si <math>a = b \quad \vee \quad c</math>
| |
|
| |
|
| |
| <math>v(a) = max\{1 - v(b),v(c)\}</math> si <math>a = b \quad \rightarrow \quad c</math>
| |
|
| |
|
| |
| La función <math>v</math> queda definido para toda fórmula de cualquier complejidad.
| |
|
| |
|
| |
| * La unicidad se prueba suponiendo que existiese otra función de valuación <math>w</math> que extiende a <math>f</math>
| |
|
| |
|
| |
| Consideremos el siguiente conjunto:
| |
|
| |
|
| |
| <math>I = \{ a \in Form \quad \mid \quad v(a) = w(a)\}</math>
| |
|
| |
|
| |
| Como <math>w</math> también extiende a <math>f</math>, <math>I</math> contiene a todas las variables proposicionales. Como <math>v</math> y <math>w</math> son ambas valuaciones, <math>I</math> es cerrado por los conectivos por lo que <math>Form \subseteq I</math>. Es decir, <math>v(P) = w(P</math>) para toda fórmula <math>P</math>.
| |
|
| |
|
| |
| Usa el teorema de que si un subconjunto S de <math>A*</math> es cerrado por los conectivos y 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 <math>L=<C,F,P></math>, para una interpretación se define:
| |
|
| |
|
| |
| - Un universo de interpretación, conjunto no nulo <math>U_I</math>. Ejemplo: Naturales.
| |
|
| |
| - Para cada símbolo de constante c <math>\in</math> C, mapea con un elemento <math>c_I \in U_I</math>. Ejemplo "cero" -> <math>c_i = 0</math>
| |
|
| |
| - Para cada símbolo de función k-aria <math>\in</math> F, mapea con una función <math>f_I</math> de k variables sobre el universo <math>U_I: f_I: U^{k}_{I} -> U_I</math>
| |
|
| |
| - Para cada símbolo de predicado k-ario <math>\in</math> P, mapea a una relación k-aria <math>P_I</math> sobre el universo <math>U_I</math>. Osea: <math>U^{k}_{I} = U_I x ... x U_I</math> k veces.
| |
|
| |
|
| |
| b)
| |
|
| |
| - Conmutativo:
| |
|
| |
| <math>a = \forall x \forall y (f^2(x,y) = f^2(y,x))</math>
| |
|
| |
|
| |
| - Asociativo:
| |
|
| |
| <math>b = \forall x \forall y \forall z (f^2(x,f^2(y,z)) = f^2(f^2(x,y),z))</math>
| |
|
| |
|
| |
| Solución: <math>a \wedge b</math>
| |
|
| |
|
| |
| =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 <math>f:\mathbb{N}^2 \to \mathbb{N}</math> tal que <math>f(a,b)</math> devuelve la cantidad de divisores positivos desde <math>0</math> hasta <math>b</math>. Con <math>a</math> y <math>b</math> naturales.
| |
|
| |
|
| |
| Queremos que <math>\tau(n) = f(n,n) \forall n \in \mathbb{N}</math> definiendo a <math>f</math> de la siguiente forma:
| |
|
| |
|
| |
| <math>f(n,0) = n(n)</math>
| |
|
| |
| <math>f(n,m+1) = g(n,m,f(n,m))</math>
| |
|
| |
|
| |
| Con <math>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}\right. </math>
| |
|
| |
|
| |
| donde <math>P = u^3_1(a,b,c) \quad \mid \quad suc(u^3_2(a,b,c))</math>
| |
|
| |
| Más sencillo:
| |
|
| |
| <math>f(n,0) = n(n)</math>
| |
|
| |
| <math>f(n,m+1) = P(n, m+1) + f(n,m) </math>
| |
|
| |
| donde <math>P(a,b) = a \mid b</math>
| |
|
| |
| La función "divide a" (<math>\mid</math>) es primitiva recursiva y booleana, por lo que devuelve 1 o 0.
| |
|
| |
| La suma también es primitiva recursiva.
| |
|
| |
|
| |
|
| |
| <math>f</math> cumple con el esquema de recursión primitivo.
| |
|
| |
| <math>n(n)</math> es la función inicial nula aplicada a <math>n</math>
| |
|
| |
| El predicado <math>P</math> usa la función proyección y la función "divide a" (<math>\mid</math>) que es primitiva recursiva.
| |
|
| |
| La función <math>g</math> es una división de casos disjuntos y usa las funciones iniciales de proyección y sucesor.
| |
|
| |
| Por todo lo anterior, la función <math>f(n,m)</math> es primitiva recursiva (con <math>n</math> y <math>m</math> naturales)
| |
|
| |
|
| |
| Falta ver que <math>\tau (n) = f(n,n)</math>. Probamos por inducción en el segundo parámetro.
| |
|
| |
| *Caso base:
| |
|
| |
| <math>\tau(0) = 0</math>
| |
|
| |
| <math>f(0,0) = n(0) = 0</math>
| |
|
| |
|
| |
| *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:
| |
|
| |
| <math>f(n,m+1) = g(n,m,f(n,m))</math>
| |
|
| |
| Dos casos:
| |
|
| |
| - <math>n \mid (m+1)</math>: <math>g(n,m,f(n,m)) = f(n,m) + 1</math>. 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 <math>f(n,m+1) = f(n,m) + 1</math>
| |
|
| |
|
| |
| - <math>\neg (n \mid (m+1))</math>: <math>g(n,m,f(n,m)) = f(n,m)</math>. 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 <math>f(n,m+1) = f(n,m)</math>
| |
|
| |
|
| |
| Por lo tanto, <math>\tau(n) = f(n,n) \forall n \in \mathbb{N}</math>
| |
|
| |
| =Ejercicio 4=
| |
|
| |
|
| |
| Sea:
| |
|
| |
|
| |
| <math>f(x) = \{\begin{matrix} Halt(x,x) \quad \quad x \neq 0 \\ 2 \quad \quad \quad x = 0\end{matrix}</math>
| |
|
| |
|
| |
| La <math>Img(f) = \{ 0,1,2 \}</math>. Tiene exactamente 3 elementos.
| |
|
| |
|
| |
| Supongamos que <math>f(x)</math> es computable, entonces <math>\exists P \quad </math> programa que computa <math>f(x)</math>.
| |
|
| |
|
| |
| Si <math>f(x) = 2</math>, entonces <math>x = 0</math>.
| |
|
| |
|
| |
| Si <math>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))</math>
| |
|
| |
|
| |
| Sea <math>e = \#P</math>, caso particular, <math>x=e</math>: <math>Halt(e,e)</math> determina si el programa <math>e</math> con entrada <math>e</math> termina o no.
| |
|
| |
|
| |
| Como vimos en las teóricas, estamos resolviendo el ''halting problem''.
| |
|
| |
| Absurdo! pues ''Halt'' no es computable. Vino de suponer que <math>f(x)</math> era computable.
| |
|
| |
| Entonces <math>f(x)</math> no computable.
| |
