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