Autor Tema: Lógica para la computación. Examen

0 Usuarios y 1 Visitante están viendo este tema.

09 Junio, 2011, 01:33 pm
Leído 1527 veces

loztrnger

  • Junior
  • Mensajes: 63
  • Karma: +0/-0
  • Sexo: Masculino
Buenas, espero alguien pueda dar solución a este problema:

Un conjunto \(  \Gamma \) es independiente si \( \forall{} A \in{\Gamma}, \Gamma - {A} \nvDash{A}  \)



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

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

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

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

POR INTERNET ENCONTRE: Considerar: \( \{A_1, A_1 \wedge A_2, A_1 \wedge A_2 \wedge A_3, ...\}  \)

Aclaraciones sobre notaciones:
fbf: fórmula bien formada.
fbfs: fórmulas bien formadas.
\( A \models B \): B se infiere de A.
A \( \nvDash \) B: B no se infiere de A.

15 Junio, 2011, 01:32 am
Respuesta #1

Óscar Matzerath

  • Lathi
  • Mensajes: 565
  • Karma: +0/-0
  • Sexo: Masculino
Hola,

El a) se sigue mediante una sencilla inducción en el número de axiomas (es decir el cardinal de \( \Gamma \)). 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 \( \Gamma \). Supongamos que de cualquier conjunto con n axiomas podemos extraer un subconjunto independiente de axiomas. Entonces dado \( \Gamma = \{ A_0,... A_{n+1} \} \) considera \( \Gamma' = \{ A_0,...,A_n \} \). Por hipótesis de inducción hay un subconjunto independiente \( \Delta' \). Ahora tenemos dos posibilidades, o bien \( \Delta' \models A_{n+1} \), en cuyo caso podemos tomar como conjunto de axiomas independientes para \( \Gamma \) el propio \( \Delta' \), o bien \( \Delta' \not\models A_{n+1} \), y entonces \( \Delta = \Delta' \cup \{A_{n+1} \} \) es un subconjunto independiente de axiomas para \( \Gamma \).

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

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

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

Saludos

Editado un detalle técnico del apartado a.

15 Junio, 2011, 05:05 pm
Respuesta #2

loztrnger

  • Junior
  • Mensajes: 63
  • Karma: +0/-0
  • Sexo: Masculino
Hola, Óscar Matzerath

Muchas gracias por tu ayuda.