Edición de «Final del 21/10/14 (Lógica y Computabilidad)»
De Cuba-Wiki
Puedes deshacer la edición. Antes de deshacer la edición, comprueba la siguiente comparación para verificar que realmente es lo que quieres hacer, y entonces publica los cambios para así efectuar la reversión.
Revisión actual | Tu texto | ||
Línea 1: | Línea 1: | ||
[[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 | 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. | *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 | 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 | - 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: | Consideremos el siguiente conjunto: | ||
I = {a fórmula | 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. | |||
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= | =Ejercicio 2= | ||
Línea 58: | Línea 38: | ||
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. | 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: | |||
Sea | |||
- Un universo de interpretación, conjunto no nulo <math>U_I</math>. Ejemplo: Naturales. | - 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 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 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. | - 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) | b) | ||
Línea 81: | Línea 55: | ||
<math>b = \forall x \forall y \forall z (f^2(x,f^2(y,z)) = f^2(f^2(x,y),z))</math> | <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> | Solución: <math>a \wedge b</math> | ||
Línea 87: | Línea 60: | ||
=Ejercicio 3= | =Ejercicio 3= | ||
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. | 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: | 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,0) = n(n)</math> | ||
Línea 101: | Línea 70: | ||
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 | 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 \neg P \end{matrix}</math> | ||
donde <math>P = u^3_1(a,b,c) \mid u^3_2(a,b,c)</math> | |||
<math>f</math> cumple con el esquema de recursión primitivo. | <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> | <math>n(n)</math> es la función inicial nula aplicada a <math>n</math> | ||