TEMA TABLEAUX (Tableros semánticos).
TABLEROS SEMÁNTICOS
Las tablas o árboles semánticos son un mecanismo de decisión para sentencias de un lenguaje formal. Aunque se puede decir que los procedimientos tabulares comienzan con Gentzen (en 1935). Se considera a Beth el creador del procedimiento de árboles semánticos, destacando su “Semantic entailment and formal derivability”.Beth la define como un intento de búsqueda sistemática de contra ejemplos para determinar si una fórmula es consecuencia lógica de otras.
Este método se utiliza para verificar la satisfacibilidad de una fórmula proposicional.
Para implementar este metodo o algoritmos es necesario tener en cuenta los siguientes y muy importantes fundamentos:
Literales y formulas complementarias.
Un literal es una variable proposicional o la negación de una variable proposicional, por ejemplo p, ¬q, s, ¬t son literales. Un conjunto de literales es satisfacible si y sólo si no contiene un par complementario de literales.
1- Si p es un átomo,{p, ¬p} son una pareja complementaria de literales.
Si se asigna v(p) = V entonces v(¬p) = F, si se asigna v(p) = F entonces v(¬p) = V.
2- Si A es una fórmula, {A,¬A} es un par complementario de fórmulas A es el complemento de ¬A y viceversa.
Para el caso de las fórmulas por ejemplo si se tiene: v(p → q) = V, entonces su complemento es: v(¬(p → q)) = F.
Método de los Tableros semánticos
Este método realiza una búsqueda sistemática de modelos, disminuyendo la satisfacibilidad de toda fórmula a la de algunos literales de la misma.
Considere la fórmula A: (p v ¬q). El conjunto de literales es: {p, ¬q} se tiene que no es un par complementario de literales, por lo tanto se puede establecer un modelo para la fórmula A: v(p) = V, v(q)= F. La fórmula (p v ¬q) es satisfacible.
Si se tiene la fórmula A: (p & q) → ¬r. el conjunto de literales es: {p, q, ¬r} se tiene que no es un par complementario de literales, por lo tanto se puede establecer un modelo para la fórmula A: v(p) = V, v(q)= F v(¬r) = V. La fórmula (p & q) → ¬r es satisfacible.
Dada la fórmula A: (p & ¬p) .entonces v(A) = V si y solo si v(p) = V y v(¬p) = V para este caso se tiene el conjunto de literales es : {p, ¬p} este conjunto tiene un par complementario de literales, y podemos afirmar que no se puede encontrar un modelo para la fórmula A, es decir que A es insatisfacible.
De lo anterior se puede afirmar que un conjunto de literales es satisfacible si y solo si no contiene un par complementario de literales.
Considere la fórmula A: p & (p v ¬p) , A es verdadera si v(q) = V y v(p v ¬q) = V. Entonces v(A) = V, si:
1. v(q) = V y v(p) = V o
2. v(q) = V y v(¬q) = V
La satisfacibilidad para una fórmula A queda asociada a la satisfacibilidad de un conjunto de literales.
En el anterior ejemplo tenemos el primer conjunto de literales {q, p} y se observa que no es un par complementario lo que nos permite afirmar que el conjunto es satisfacible y se puede establecer un modelo para la fórmula A, el cual es: v(q) =V y v(p) = V, por lo tanto la fórmula es satisfacible. El segundo conjunto de literales {q, ¬q} es un par complementario, este conjunto no es satisfacible y no se puede encontrar un modelo
Fórmulas alfa (α) y beta (β).
Hay dos tipos de reglas:
1-Las α que son conjuntivas y estas satisfacen si y sólo si ambas fórmulas α₁ y α₂ son satisfacibles.
2-Las β que son disyuntivas y estas satisfacen si al menos una de las fórmulas β₁ y β₂ son satisfacibles.
Las fórmulas alfa, junto con sus componentes son:
-Si F es alfa con componentes F₁ y F₂ entonces F ≡ F₁ ᴧ F₂.
Las fórmulas beta, junto con sus componentes son:
-Si F es alfa con componentes F₁ y F₂ entonces F ≡ F₁ v F₂.
Definiciones:
1- Una rama de un árbol de verdad es cerrada si y sólo si contiene una formula y su negación.
2- Una rama de un árbol de verdad es abierta si y sólo si contiene fórmulas descompuestas atómicas y sus negaciones.
3- Un árbol de verdad es abierto si y sólo si contiene al menos una rama completa abierta.
4- Un árbol de verdad es cerrado si y sólo si todas sus ramas son cerradas.
5- Una fórmula es satisfacible si y sólo si tiene un árbol de verdad abierto.
Ejemplo tablero semántico.
Búsqueda exitosa de modelos de modelos por tableros semánticos.
Búsqueda fallida de modelos por tableros semánticos.
DIAGRAMA DE CLASES
DIAGRAMA DE FLUJO
BIBLIOGRÁFICA
Blog base y muy completo para saber sobre este tema:
http://logicaftablerossemanticos.blogspot.com.co/2014/10/tableros-semanticos-las-tablas-o.html
