Diferencia entre revisiones de «Final del 21/10/14 (Lógica y Computabilidad)»

De Cuba-Wiki
Sin resumen de edición
Sin resumen de edición
Línea 61: Línea 61:
=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 0 hasta b. Con a y b 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,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 \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>n(n)</math> es la función inicial nula aplicada a <math>n</math>

Revisión del 15:35 22 oct 2014

2014-10-21 18.27.04.jpg

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 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.

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 . Ejemplo: Naturales. - Para cada símbolo de constante c C, mapea con un elemento . Ejemplo "cero" -> - Para cada símbolo de función k-aria F, mapea con una función de k variables sobre el universo - Para cada símbolo de predicado k-ario P, mapea a una relación k-aria sobre el universo . Osea: k veces.

b)

- Conmutativo:


- Asociativo:

Solución:


Ejercicio 3

Sea tal que devuelve la cantidad de divisores positivos desde hasta . Con y naturales.

Queremos que definiendo a de la siguiente forma:


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 \neg P \end{matrix}}


donde


cumple con el esquema de recursión primitivo. es la función inicial nula aplicada a