19/02/2020, 13:15:31 *
Bienvenido(a), Visitante. Por favor, ingresa o regístrate.
¿Perdiste tu email de activación?

Ingresar con nombre de usuario, contraseña y duración de la sesión
Noticias: Homenaje a NUMERARIUS
 
 
Páginas: [1]   Ir Abajo
  Imprimir  
Autor Tema: Lógica para la computación. Examen  (Leído 1466 veces)
0 Usuarios y 1 Visitante están viendo este tema.
loztrnger
Semi pleno
***

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Perú Perú

Mensajes: 63


Ver Perfil
« : 09/06/2011, 08:33:12 »

Buenas, espero alguien pueda dar solución a este problema:

Un conjunto [texx] \Gamma[/texx] es independiente si [texx]\forall{} A \in{\Gamma}, \Gamma - {A} \nvDash{A} [/texx]



(a) pruebe que para todo conjunto finito [texx] \Gamma[/texx] existe un subconjunto [texx]\bigtriangleup [/texx] independiente talque [texx]\forall{}[/texx] fbf A [texx]\in{} \Gamma , \bigtriangleup  \models A[/texx].

(b) Sea una enumeración de[texx] \Gamma =\{A_1,A_2, .... \}[/texx]. Encontrar una sucesión de fbfs [texx]\Gamma_2 =\{ B_1,B_2, ... \}[/texx] equivalente a [texx]\Gamma [/texx] tal que:[texx] \models B_{i+1} \rightarrow{} B_i [/texx] y [texx]\nvDash B_i \rightarrow{} B_{i+1} \forall{ i}[/texx]

(c) Considerando [texx] \Gamma_2[/texx] del ítem (b). Defina [texx]C_1 = B_1[/texx], y , [texx]C_{n+1} = B_n \rightarrow{} B_{n+1}[/texx]. Probar que  [texx]\Gamma_3 = \{ C1, C2, ... \}[/texx] es independiente y equivalente a [texx]\Gamma_2[/texx].

(d) Pruebe que todo conjunto infinito numerable de fbfs [texx]\Gamma [/texx], es equivalente a un conjunto independiente.

POR INTERNET ENCONTRE: Considerar: [texx]\{A_1, A_1 \wedge A_2, A_1 \wedge A_2 \wedge A_3, ...\} [/texx]

Aclaraciones sobre notaciones:
fbf: fórmula bien formada.
fbfs: fórmulas bien formadas.
[texx]A \models B[/texx]: B se infiere de A.
A [texx]\nvDash[/texx] B: B no se infiere de A.
En línea
Óscar Matzerath
Moderador Global
Pleno*
*

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 565


Ver Perfil
« Respuesta #1 : 14/06/2011, 20:32:26 »

Hola,

El a) se sigue mediante una sencilla inducción en el número de axiomas (es decir el cardinal de [texx]\Gamma[/texx]). Si sólo hay un axioma, es independiente por definición. Si sólo hay un axioma y este axioma no es una tautología entonces es independiente. Si es una tautología, el conjunto vacío es un subconjunto independiente de [texx]\Gamma[/texx]. Supongamos que de cualquier conjunto con n axiomas podemos extraer un subconjunto independiente de axiomas. Entonces dado [texx]\Gamma = \{ A_0,... A_{n+1} \}[/texx] considera [texx]\Gamma' = \{ A_0,...,A_n \}[/texx]. Por hipótesis de inducción hay un subconjunto independiente [texx]\Delta'[/texx]. Ahora tenemos dos posibilidades, o bien [texx]\Delta' \models A_{n+1}[/texx], en cuyo caso podemos tomar como conjunto de axiomas independientes para [texx]\Gamma[/texx] el propio [texx]\Delta'[/texx], o bien [texx]\Delta' \not\models A_{n+1}[/texx], y entonces [texx]\Delta = \Delta' \cup \{A_{n+1} \}[/texx] es un subconjunto independiente de axiomas para [texx]\Gamma[/texx].

Para el b), define los [texx]B_i[/texx] por recursión: [texx]B_1=A_1[/texx] y  [texx]B_{n+1} = B_n\wedge A_k[/texx] donde [texx]A_k[/texx] es el primer axioma aún no usado en [texx]B_n[/texx] y tal que [texx]\not\models B_n \longrightarrow A_k[/texx]. Comprueba que esto cumple lo que te piden.

Para el c), simplemente comprueba que todo funciona. Para ver que [texx]\Gamma_3[/texx] y [texx]\Gamma_2[/texx] son equivalentes: en un sentido es solamente aplicar modus ponens, y en el otro darse cuenta que [texx]B_{i+1} \models B_i \longrightarrow B_{i+1} [/texx]. Falta ver que [texx]\Gamma_3[/texx] es independiente. Para ello basta con dar, para cada n, un modelo (una valuación [texx]v_n[/texx]) en el que [texx]v_n(C_i)=1[/texx] para todo [texx]i \neq n[/texx] y [texx]v_n(C_n)=0[/texx]. Como tenemos [texx]\not\models B_i \longrightarrow B_{i+1}[/texx] existe una valuación [texx]v_n[/texx] tal que [texx]v_n(B_n \longrightarrow B_{n+1})=0[/texx], esto es, [texx]v_n(B_n)=1[/texx] y [texx]v_n(B_{n+1})=0[/texx]. Nota que como para todo i [texx]\models B_{i+1} \longrightarrow B_i[/texx], esto implica [texx]v_n(B_i)=0[/texx] para todo [texx]i > n[/texx] y [texx]v_n(B_i)=1[/texx] para todo [texx]i \leq n[/texx]. Es fácil ver que esta valuación hace verdaderas todas las fórmulas de [texx]\Gamma_3 - \{C_n \}[/texx] pero hace falsa a [texx]C_n[/texx]. Esto prueba que [texx]\Gamma_3 - \{C_n \} \not\models C_n[/texx], es decir, [texx]\Gamma_3[/texx] es independiente.

El d) es simplemente juntar los resultados de b) y c).

Saludos

Editado un detalle técnico del apartado a.
En línea
loztrnger
Semi pleno
***

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Perú Perú

Mensajes: 63


Ver Perfil
« Respuesta #2 : 15/06/2011, 12:05:02 »

Hola, Óscar Matzerath

Muchas gracias por tu ayuda.
En línea
Páginas: [1]   Ir Arriba
  Imprimir  
 
Ir a:  

Impulsado por MySQL Impulsado por PHP Powered by SMF 1.1.4 | SMF © 2006, Simple Machines LLC XHTML 1.0 válido! CSS válido!