Autor Tema: Lógica Proposicional. Conjuntos de Fórmulas Satisfactibles

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

26 Noviembre, 2014, 02:27 am
Leído 2213 veces

Nico1

  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 105
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
Hola a todos, les pido si pueden darme una mano con este ejercicio de Lógica proposicional. Gracias a todo de antemano!

V o F. Justificar.

\(
\Sigma\subset{Form} \textsf{ cumple que }\Gamma\subset{\Sigma} \textsf{ y } \#\Gamma\leq{2} \Longrightarrow{\Gamma}\textsf{ es satisfactible. Entonces, }\Sigma\textsf{ es satisfactible. } \)

\(
\textsf{Donde: } \)

\(
\textsf{Form es el conjunto de todas las fórmulas de la lógica proposicional. } \)
\(
\textsf{Un conjunto de fórmulas se denomina Satisfactible si existe una v valuación que hace verdadera a cualquiera de sus fórmulas. } \)

\(
\textsf{Notación: } \)

\(
\Delta\subset{Form}\textsf{ es satisfactible si }\exists{v}\textsf{ valuación, tal que }v(\alpha)=1 \forall{\alpha}\in{\Delta}  \)

26 Noviembre, 2014, 10:31 am
Respuesta #1

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Prueba con \( \Sigma=\{p\land \lnot(p\land q\land r), q\land \lnot(p\land q\land r),r\land \lnot(p\land q\land r)\} \).

26 Noviembre, 2014, 11:46 am
Respuesta #2

Nico1

  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 105
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
Prueba con \( \Sigma=\{p\land \lnot(p\land q\land r), q\land \lnot(p\land q\land r),r\land \lnot(p\land q\land r)\} \).

Muchas Gracias Carlos por tu contra-ejemplo!

Muy bien, entonces la idea aquí fue construir un conjunto \( \Sigma \) que cumple la propiedad y que termine siendo Insatisfactible.
Así, suponemos nuestro \( \Sigma=\{p\land \lnot(p\land q\land r), q\land \lnot(p\land q\land r),r\land \lnot(p\land q\land r)\} \) satisfactible y entonces, sea \( v \) la valuación que los satisface. \( v(\Sigma)=1 \) y miramos fórmula por fórmula:

\( v(p\land \lnot(p\land q\land r)) = min\{ v(p), 1 - min \{min \{v(p), v(q)\}, v(r)\}\} = 1 \)
Entonces, tenemos que deben ser: \( v(p) = 1, v(q) = 0 \) y \( v(r) = 1 \textsf{ o } v(r) = 0 \)

\( v(q\land \lnot(p\land q\land r)) = min\{v(q), 1 - min\{min\{v(p), v(q)\}, v(r)\}\} = 1 \)
Entonces, tenemos que deben ser: \( v(p) = 1, v(q) = 1, v(r) = 0 \) obligadamente por construcción.

\( v(r\land \lnot(p\land q\land r)) = min\{v(r), 1 - min\{min\{v(p), v(q)\}, v(r)\}\} = 1 \)
Donde, por lo anterior, \( v(p) = 1, v(q) = 1 \) y debe ser \( v(r) = 1 \) lo que nos da como resultado que el \( min\{1, 0\} = 1 \) Absurdo! que vino de suponer que \( \Sigma \) es satisfactible.

Notemos que, si tomamos cualquier \( \Gamma\subset{\Sigma}, \#\Gamma\leq{2} \) es satisfactible y entonces \( \Sigma \) cumple la propiedad propuesta y es insatisfactible. Lo que nos lleva a la conclusión que la afirmación es Falsa.



26 Noviembre, 2014, 02:04 pm
Respuesta #3

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
No estaría de más que comprobaras que las fórmulas son satisfacibles dos a dos.

26 Noviembre, 2014, 02:50 pm
Respuesta #4

Nico1

  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 105
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
Es cierto Carlos, que la última observación:


Notemos que, si tomamos cualquier \( \Gamma\subset{\Sigma}, \#\Gamma\leq{2} \) es satisfactible(...)

No es trivial y debe ser comprobada. No obstante creo que para los fines de éste hilo, ha sido todo aclarado. Me ayudaste mucho Gracias por tus rápidas respuestas.  ;D