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

De Cuba-Wiki

Plantilla:Back

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 .


  • 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 , entonces a es una variable proposicional. Entonces f(a) está definida. Por lo tanto .


Paso Inductivo: supongamos válido hasta n, siendo n igual a la complejidad de a. Veamos si .


- Si , entonces , por lo que por H.I. está definido. Queda que .


- Si , con . 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:


si


si


si


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


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


Consideremos el siguiente conjunto:



Como también extiende a , contiene a todas las variables proposicionales. Como y son ambas valuaciones, es cerrado por los conectivos por lo que . Es decir, ) para toda fórmula .


Usa el teorema de que si un subconjunto S de 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 , 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

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 tal que devuelve la cantidad de divisores positivos desde hasta . 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.