Revisión actual - 17:03 7 abr 2015

Ejercicio 1[editar]

Probar que la clase de funciones computables es una clase PRC

Definir conjunto de índices. Enunciar y demostrar el Teorema de Rice

Usando el Teorema de Correctitud de la lógica proposicional probar que si $\Gamma$ es satisfactible entonces $\Gamma$ es consistente.

Dado L un lenguaje de primer orden con igualdad. Decidir si las siguientes afirmaciones son verdaderas o falsas.

1. Existe un conjunto $\Gamma$ tal que $\Gamma \models A$ sii A tiene universo infinito.

2. Existe un conjunto $\Gamma$ tal que $\Gamma \models A$ sii A tiene universo finito.

3. El conjunto $\Gamma$ del ítem 1 necesariamente es infinito.

@@ Línea 1: / Línea 1: @@
-Ej 1
+{{Back|Lógica y Computabilidad}}
+=Ejercicio 1=
 Probar que la clase de funciones computables es una clase '''PRC'''
+=Ejercicio 2=
+Definir '''conjunto de índices'''. Enunciar y demostrar el '''Teorema de Rice'''
+=Ejercicio 3=
+Usando el '''Teorema de Correctitud''' de la lógica proposicional probar que si <math>\Gamma</math> es satisfactible entonces <math>\Gamma</math> es consistente.
+=Ejercicio 4=
+Dado ''L'' un lenguaje de primer orden con igualdad. Decidir si las siguientes afirmaciones son verdaderas o falsas.
+. Existe un conjunto <math>\Gamma</math> tal que <math>\Gamma \models A</math> sii A tiene universo infinito.
+. Existe un conjunto <math>\Gamma</math> tal que <math>\Gamma \models A</math> sii A tiene universo finito.
+. El conjunto <math>\Gamma</math> del ítem 1 necesariamente es infinito.