Autor Tema: Problema de Lógica con Teorema de Compacidad

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

02 Diciembre, 2015, 05:28 pm
Leído 4198 veces

rboyart

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 20
  • Karma: +0/-0
  • Sexo: Masculino
Sea Γ un conjunto de sentencias tal que toda interpretación hace verdadera al menos una sentencia de Γ. Demuestre que hay un conjunto finito de sentencias de Γ tal que la disyunción de sus elementos es una formula válida.

Sugerencia: construya a partir de Γ un conjunto insatisfacible y aplique compacidad.

Me pueden guiar para resolverlo?

Gracias

02 Diciembre, 2015, 07:40 pm
Respuesta #1

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Sea Γ un conjunto de sentencias tal que toda interpretación hace verdadera al menos una sentencia de Γ. Demuestre que hay un conjunto finito de sentencias de Γ tal que la disyunción de sus elementos es una formula válida.

Sugerencia: construya a partir de Γ un conjunto insatisfacible y aplique compacidad.

El conjunto de las negaciones de las sentencias del conjunto dado es insatisfacible. Aplícale el teorema de compacidad.

03 Diciembre, 2015, 04:30 pm
Respuesta #2

rboyart

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 20
  • Karma: +0/-0
  • Sexo: Masculino
Hola,

(He pensado esto:)

Sea Δ un conjunto de negaciones de sentencias de Γ.

Supongo que todo subconjunto finito de Δ es satisfacible (consistente).
Entonces por Compacidad hay un modelo de Δ, es decir, una interpretación M en el que todas las sentencias de Δ son verdaderas.
—> Por lo tanto, todas las sentencias de Γ son falsas en una interpretación M.
Esto contradice la premisa del ejercicio, dado que en cada interpretación, al menos, una de las sentencias de Γ es verdadera
—>  Así que algún subconjunto finito de Δ es insatisfacible (inconsistente)

Este subconjunto que consiste en sentencias ¬ϕ1 i (donde i = 1 hasta n).
Δ= {¬ ϕ1 , ¬ ϕ2 , ¬ ϕ3 ,…, ¬ ϕn }
Entonces la disyunción de  la fórmula ( ¬ ϕ1  v ¬ ϕ2  v  ¬ ϕ3  v… v ¬ ϕn ) es válida
—> Entonces, la disyunción Γ = ( ϕ1  v ϕ2  v  ϕ3  v… v ϕn ) es también válida.

Puede ser que vaya por aqui el ejercicio?
Qué te parece esto, serìa correcto y completa la respuesta ?
Gracias por tu ayuda.

03 Diciembre, 2015, 10:54 pm
Respuesta #3

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Sea Δ un conjunto de negaciones de sentencias de Γ.

Supongo que todo subconjunto finito de Δ es satisfacible (consistente).
Entonces por Compacidad hay un modelo de Δ, es decir, una interpretación M en el que todas las sentencias de Δ son verdaderas.
—> Por lo tanto, todas las sentencias de Γ son falsas en una interpretación M.
Esto contradice la premisa del ejercicio, dado que en cada interpretación, al menos, una de las sentencias de Γ es verdadera
—>  Así que algún subconjunto finito de Δ es insatisfacible (inconsistente)

Este subconjunto que consiste en sentencias ¬ϕ1 i (donde i = 1 hasta n).
Δ= {¬ ϕ1 , ¬ ϕ2 , ¬ ϕ3 ,…, ¬ ϕn }

Hasta ahí perfecto.

Entonces la disyunción de  la fórmula ( ¬ ϕ1  v ¬ ϕ2  v  ¬ ϕ3  v… v ¬ ϕn ) es válida

Esto ya no es cierto. Tienes que razonar con la conjunción de las n fórmulas que has obtenido. ¿Qué puedes decir de ella? ¿Y de su negación?

04 Diciembre, 2015, 08:15 pm
Respuesta #4

rboyart

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 20
  • Karma: +0/-0
  • Sexo: Masculino
Yo creía que como era insatisfacible, al menos una de la sentencia es modelo de la interpretación M, por lo tanto,
la disyunción de la fórmula o de su negación, son siempre válidas.

Qué estoy pensando mal?

05 Diciembre, 2015, 12:19 pm
Respuesta #5

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Has llegado a un conjunto finito inatisfacible de sentencias y afirmas que la disyunción de todas ellas es lógicamente válida. Eso no es cierto. Imagina un caso en concreto, por ejemplo, el conjunto formado por dos sentencias de la forma no A y no B (no uso el LaTeX porque está dando problemas últimamente), concretamente,

no A = no (todo x es igual a x)

no B = no (para todo xy (x = y implica y = x)

El conjunto formado por esas dos sentencias es insatisfacible, y la disyunción de ambas es también insatisfacible, y en particular no es cierto que la disyunción sea lógicamente válida, como pretendes.

05 Diciembre, 2015, 04:19 pm
Respuesta #6

rboyart

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 20
  • Karma: +0/-0
  • Sexo: Masculino
O sea, El conjunto Δ es insatisfacible, por lo tanto, no existe ninguna interpretación que sea modelo para todas las sentencias del conjunto, por la tanto la disyunción es falsa. Pero si las ¬ negaciones de la sentencias de  Δ / Γ ⊆ ¬Δ ( ya que Δ son las negaciones de Γ ), una interpretación hace verdadera al menos una sentencia de Γ.
puedo hacer este salto para hablar de Γ ?

05 Diciembre, 2015, 07:14 pm
Respuesta #7

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
O sea, El conjunto Δ es insatisfacible, por lo tanto, no existe ninguna interpretación que sea modelo para todas las sentencias del conjunto, por la tanto la disyunción es falsa.

No. Por lo tanto, la conjunción  es insatisfacible, luego la negación de la conjunción (que es la disyunción de las negaciones) es lógicamente válida.

09 Diciembre, 2015, 08:35 pm
Respuesta #8

rboyart

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 20
  • Karma: +0/-0
  • Sexo: Masculino
Esta sería mi respuesta final entonces :

Sea Δ un conjunto de negaciones de sentencias de Γ.

Supongo que todo subconjunto finito de Δ es satisfacible (consistente).
Entonces por compacidad hay un modelo de Δ, es decir, una interpretación M en el que todas las sentencias de Δ son verdaderas.
—> Por lo tanto, todas las sentencias de Γ son falsas en una interpretación M.
 Y eso contradice la premisa del ejercicio, dado que en cada interpretación, al menos, una de las sentencias de Γ es verdadera
—>  Entonces, algún subconjunto finito de Δ es insatisfacible (inconsistente)

Ese subconjunto insatisfacible consiste en sentencias ¬ϕi (donde i = 1 hasta n).
β = {¬ ϕ1 , ¬ ϕ2 , ¬ ϕ3 ,…, ¬ ϕn }
Por compacidad, el conjunto Δ es insatisfacible, o sea, por lo menos tiene un subconjunto insatisfacible, por la tanto la fórmula de conjunción de sentencias de β es insatisfacible, luego la negación de la conjunción (que es la disyunción de las negaciones) es lógicamente válida.

qué te parece?

Muchas gracias por todo ! :)

09 Diciembre, 2015, 11:46 pm
Respuesta #9

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Si acaso, yo destacaría que la negación de la conjución es una disyunción de sentencias del conjunto de partida, tal y como se requería.