Autor Tema: Lógica Proposicional: Subconjunto independiente de un conjunto de formulas.

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

14 Abril, 2018, 11:21 pm
Leído 3650 veces

Nico1

  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 105
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
Hola amigos, quisiera ayuda con este ejercicio de lógica proposicional. He estado tratando de hacerlo pero me cuesta mucho escribirlo con formalidad.

\( \Gamma \subseteq{FORM} \)
Probar que para todo conjunto \( \Gamma \) finito, existe un subconjunto \( \Sigma \) independiente tal que \( \forall{\alpha}\in{\Gamma}\textrm{, }\alpha\in{C(\Sigma)} \)


Donde:
\( C(\Sigma) \): Consecuencias de \( \Sigma \)
\( \Sigma \) es independiente si: \( \forall{\alpha}\in{\Sigma}\space\textrm{. }\alpha \not\in{C(\Sigma-\alpha)} \)

Saludos!

14 Abril, 2018, 11:42 pm
Respuesta #1

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Hola amigos, quisiera ayuda con este ejercicio de lógica proposicional. He estado tratando de hacerlo pero me cuesta mucho escribirlo con formalidad.

\( \Gamma \subseteq{FORM} \)
Probar que para todo conjunto \( \Gamma \) finito, existe un subconjunto \( \Sigma \) independiente tal que \( \forall{\alpha}\in{\Gamma}\textrm{, }\alpha\in{C(\Sigma)} \)


Donde:
\( C(\Sigma) \): Consecuencias de \( \Sigma \)
\( \Sigma \) es independiente si: \( \forall{\alpha}\in{\Sigma}\space\textrm{. }\alpha \not\in{C(\Sigma-\alpha)} \)

Considera todos los subconjuntos \( \Sigma\subset \Gamma \) con la propiedad de que \( \forall{\alpha}\in{\Gamma}\textrm{, }\alpha\in{C(\Sigma)} \). No es vacío, pues \( \Gamma \) es uno de ellos. Toma uno que tenga el menor número de elementos posible y prueba que es independiente.

20 Junio, 2018, 04:31 am
Respuesta #2

Nico1

  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 105
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
Perdón la tardanza, siguiendo lo que me comentabas intenté resolverlo de la siguiente manera:

Como \( \Gamma \) es finito \( \Gamma = \{\alpha_1 , \alpha_2 , ... , \alpha_k\} \)

La idea es construir inductivamente el subconjunto \( \Sigma \) que quiero, "quitando" las formulas que rompen con la independencia.

Entonces, llamo

\( \Gamma_0 = \Gamma \)

\( \Gamma_{n+1} = \begin{cases} \Gamma_n & \text{si}& \alpha_{n+1} \not\in{C(\Gamma_n - \{\alpha_{n+1}\})}\\\Gamma_n - \{\alpha_{n+1}\} & \text{sino}\end{cases} \)

Así mi conjunto buscado sería: \( \Sigma = \Gamma_k \). Veamos que es Independiente:

Supongo \( \Sigma \) dependiente, entonces \( \exists{ \alpha_i} \in{C(\Sigma - \{\alpha_i\})} \)

Notemos que toda valuación \( v(\Sigma - \{\alpha_i\}) = 1 \) también \( v(\Gamma_{i-1} - \{\alpha_i\})=1 \) pues \( \Gamma_{i-1} \subseteq{\Sigma} \) y entonces,  \( \alpha_i \in{C(\Gamma_{i-1} - \{\alpha_i\})} \) lo que es un Absurdo por como definimos \( \Sigma \)

Por lo tanto, \( \Sigma \) es independiente.

Ahora hay que ver que se cumple que \( \forall{\alpha} \in{\Gamma}, \alpha \in{C(\Sigma)} \)

Sea \( \alpha_j \in{\Gamma} \) tengo dos opciones:

1. \( \alpha_j \in{\Sigma} \) es decir que al momento de definir \( \Gamma_j \) "no lo saque". Entonces, \( \alpha_j \in{C(\Sigma)} \)

2. \( \alpha_j \not\in{\Sigma} \) es decir que al momento de definir \( \Gamma_j \) "lo saque" y entonces \( \Gamma_j = \Gamma_{j-1} - \{\alpha_j\} \Rightarrow \alpha_j \in{C(\Gamma_{j-1} - \{\alpha_j\})} \) y como \( \Gamma_j \subseteq{\Sigma} \Rightarrow C(\Gamma_j) \subseteq C(\Sigma) \Rightarrow \alpha_j \in C(\Sigma) \)

Por lo tanto, \( \forall{\alpha} \in \Gamma , \alpha \in C(\Sigma) \)

20 Junio, 2018, 09:47 am
Respuesta #3

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
¿Y no es más sencillo que tomes directamente un \( \Sigma\subset \Gamma \) con la propiedad de que \( \forall \alpha\in \Gamma, \alpha\in C(\Sigma) \) con el menor número de elementos posible? Ese \( \Sigma \) cumple lo que quieres y te ahorras toda la construcción inductiva. Sólo tienes que probar que es independiente.

24 Junio, 2018, 06:44 pm
Respuesta #4

Nico1

  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 105
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
¿Y no es más sencillo que tomes directamente un \( \Sigma\subset \Gamma \) con la propiedad de que \( \forall \alpha\in \Gamma, \alpha\in C(\Sigma) \) con el menor número de elementos posible? Ese \( \Sigma \) cumple lo que quieres y te ahorras toda la construcción inductiva. Sólo tienes que probar que es independiente.

Hola Carlos, en verdad no me doy cuenta así de antemano cual sería el \( \Sigma \) con el menor número de elementos posibles.

24 Junio, 2018, 07:05 pm
Respuesta #5

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Hola Carlos, en verdad no me doy cuenta así de antemano cual sería el \( \Sigma \) con el menor número de elementos posibles.

Pero si no hay nada de lo que te tengas que dar cuenta. Lo que te digo es: tienes un conjunto finito \( \Gamma \) de fórmulas. Existe un subconjunto \( \Sigma_0\subset \Gamma \) (basta tomar \( \Sigma_0=\Gamma \)) tal que todas las fórmulas de \( \Gamma \) son consecuencia de las fórmulas de \( \Sigma_0 \). Puede que  \( \Sigma_0=\Gamma \) sea el único posible o que haya otros con la mirma propiedad, y sólo tienes que llamar \( \Sigma \) a un subconjunto con esa propiedad que tenga el mínimo número de elementos posibles. Ya está. No tienes que darte cuenta de nada. Defines \( \Sigma \)  como un subconjunto de \( \Gamma \) con el mínimo número de elementos posible de entre todos los subconjuntos con la propiedad de que todas las fórmulas de \( \Gamma \) son consecuencias de las fórmulas de \( \Sigma \).

Y, definiendo así \( \Sigma \), es fácil probar que ese \( \Sigma \) que acabamos de definir, ya está, tiene además la propiedad de que es independiente.

24 Junio, 2018, 08:02 pm
Respuesta #6

Nico1

  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 105
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
Pero si no hay nada de lo que te tengas que dar cuenta. Lo que te digo es: tienes un conjunto finito \( \Gamma \) de fórmulas. Existe un subconjunto \( \Sigma_0\subset \Gamma \) (basta tomar \( \Sigma_0=\Gamma \)) tal que todas las fórmulas de \( \Gamma \) son consecuencia de las fórmulas de \( \Sigma_0 \). Puede que  \( \Sigma_0=\Gamma \) sea el único posible o que haya otros con la mirma propiedad, y sólo tienes que llamar \( \Sigma \) a un subconjunto con esa propiedad que tenga el mínimo número de elementos posibles. Ya está. No tienes que darte cuenta de nada. Defines \( \Sigma \)  como un subconjunto de \( \Gamma \) con el mínimo número de elementos posible de entre todos los subconjuntos con la propiedad de que todas las fórmulas de \( \Gamma \) son consecuencias de las fórmulas de \( \Sigma \).

Y, definiendo así \( \Sigma \), es fácil probar que ese \( \Sigma \) que acabamos de definir, ya está, tiene además la propiedad de que es independiente.

Ahora sí entendí. Gracias por la paciencia y la explicación!