Entrada de la toeria dada el dia 26/10/2010
Esta semana ha sido cargadita, al principio de la sesión hemos repasado los conceptos de tablas de verdad y contraejemplo mediante ejemplos y en la segunda parte de la sesión la profesora a puesto el turbo con más conceptos que intentaré explicar a continuación.
El siguiente punto pertenece todavia a “Fundamentos teóricos para validar semánticamente un razonamiento”
-
Fórmula y conjunto de fórmulas satisfacible e insatisfacible
-Una fórmula lógica es satisfacible (consistente) si existe alguna interpretación que la hace verdadera.
-Una fórmula lógica es insatisfacible si y sólo si es falsa para todas sus interpretaciones.
-Conjunto de fórmulas satisfacible: si existe una interpretación que es un modelo para todas las fórmlas del conjunto.
-Conjunto de fórmulas insatisfacible: si no existe ninguna interpretación que sea modelo (que haga verdadero el conjunto) para todas las fórmulas del conjunto .
Pasamos a ver ahora otro punto del tema:
-
Estudio de la validez de un razonamiento a partir del conjunto de fórmulas que lo conforman
Para demostrar la validez de un razonamiento nos basaremos en el siguiente resultado:
– Teorema
Veremos cómo aplicamos los conocimientos aprendidos para ver si un conjunto de fórmulas es correcto o no según si es satisfacible o no.
Un razonamiento R: P1, P2, …Pn = Q es correcto si y sólo si, el conjunto de fórmulas C={P1, P2, …Pn, ¬Q} es insatisfacible
Todas las fórmulas juntas no pueden ser V al mismo tiempo si son premisas V y “Q” F, entonces decimos que es insatisfacible o una falacia.
Demostración:
Dem: P1, P2,… Pn ⇒ Q es correcto
⇒ Q es consecuencia lógica de P1, P2,… Pn
⇒ La fbf: P1 ∧ P2 ∧… ∧ Pn → Q es tautología
⇒ ¬ (P1 ∧ P2 ∧ Pn ∧ ¬Q) es tautología (por equivalencias)
⇒ (P1 ∧ P2 ∧ Pn ∧ ¬Q) es insatisfacible ⇔ C = {P1, P2… Pn, ¬Q } es insatisfacible.
– Estudio del conjunto de fórmulas aplicando la regla de resolución
Tenemos que demostrar que C={P1, P2, …Pn, ¬Q} es insatisfacible. Para ello hacemos:
·Aplicamos la regla de resolución sobre “C” hasta obtener dos fórmulas contradictorias, esto significará que “C” es insatisfacible.
·La regla de resolución se aplica sólo a fórmulas escritas en forma clausal. Luego antes de su aplicación debemos obtener la forma clausal de las premisas y de la negación de la conclusión.
– Forma clausal de una fórmula
Consiste en transformar fórmulas en otras fórmulas más simples de evaluar. Dichas fórmulas se caracterizan por la inexistencia del implicador. Una fórmula está escrita en forma clausal si dicha fórmula está representada por su conjunto de cláusulas.
-Cláusula: disyunción de literales.
-Literales: fórmula atómica afirmada o negada.
-Cláusula vacía: cláusula sin literales. Se representa por [] y su valor es siempre contradicción.
– Proceso para obtener la forma clausal de una fórmula
Aplicar, si es el caso, cada uno de los siguientes pasos a una fórmula dada:
Paso 1– Eliminar implicadores y coimplicadores mediante la aplicación de la regla:
A → B = ¬A ∨ B
Paso 2– Normalizar negadores mediante la aplicación de reglas:
·Leyes de Morgan: ¬(A ∨ B) = ¬A ∧ ¬B; ¬(A ∧ B) = ¬A ∨ ¬B
·Ley del doble negador: ¬¬A = A
Paso 3- En fórmulas cuantificadas, renombrar variables, si es necesario, para que dos cuantificadores no coincidan en el nombre de variable que cuantifican.
Paso 4- Eliminar cuantificadores existenciales aplicando el criterio de Skolem.
Paso 5- Poner los cuantificadores universales a la cabeza de la fórmula y no volver a escribirlos en los pasos sucesivos, ya que llegados a este punto todas las variables de la fórmula están cuantificadas universalmente, por lo que no es necesario especificarlo.
Paso 6- Aplicar, si es necesario, la regla distributiva: A ∨ (B ∧ C) = (A ∨ B) ∧ (A ∨ C) para obtener una fórmula cuya conectiva principal sea la conjunción. Reducir y simplificar la fórmula aplicando reglas de equivalencia.
Paso 7- Extraer las cláusulas de la fórmula que serán cada una de las disyunciones de la fórmula obtenida en el paso anterior.
Paso 8- Las cláusulas no pueden coincidir en los nombres de argumentos variables, luego cambiar, si es necesario, los nombres de los argumentos variables coincidentes. Las constantes pueden coincidir.
-
Método de Resolución de Robinson
Con este método se comprueba si un conjunto de cláusulas es insatisfacible. Esta prueba es fundamental en los sistemas deductivos automáticos, como el sistema Prolog.
–Regla de Resolución Proposicional
La regla de resolución para una fórmula proposicional obtiene para dos cláusulas C1 y C2, una nueva cláusula C3 llamada resolvente de C1 y C2 que resulta ser una consecuencia lógica de ellas. Para ello, debe suceder lo siguiente: C1 debe contener, al menos, un literal L y C2, al menos, un literal ¬L. La cláusula C3 será la disyunción de todos los literales de C1 y de C2 menos los literales L y ¬L.
El resolvente de dos cláusulas es una cláusula que es consecuencia lógica de ellas.
Ejemplos:
P y ¬P v Q C3=Q
P v Q y ¬P v Q C3=Q
P v Q y ¬P v ¬Q C3=Q v ¬Q ; P v ¬P (dos posibilidades)
¬P y P C3=nada
P v Q y ¬P v R C3=Q v R
Con todo esto, a partir de un conjunto de cláusulas C, si la cláusula resolvente es la cláusula vacía, C es insatisfacible, por tanto el razonamiento es correcto. Si no se encuentran cláusulas resolventes, C no es insatisfacible.
Y si no me falla la memoria ya he terminado con la teoria de hoy que como vereis no es poca, ahora solo falta ponerla en práctica y ver las dudas que salen
Un beso corazones!!!!