Árbol semántico
![]() | Este artículo o sección sobre semántica necesita ser wikificado, por favor, edítalo para que cumpla con las convenciones de estilo. Este aviso fue puesto el 21 de abril de 2013. |
El método de las tablas semánticas, presentado por E. Beth y popularizado como árboles semánticos por R. Smullyan, consiste básicamente en examinar, de manera sistemática, todas las posibilidades que podrían hacer falsa una proposición dada y buscar si una de estas posibilidades es lógicamente viable.
Un árbol semántico es una sucesión de sucesiones de fórmulas llamadas ramas, generadas a partir de un conjunto (no vacío) de fórmulas, por aplicación a éstas de las reglas (y a las fórmulas resultantes que sean complejas).
Conceptos previos
- Proposición: Llamaremos de esta forma a cualquier afirmación que sea verdadera o falsa, pero no ambas cosas a la vez.
- Conexión entre proposiciones: trabajaremos con estos tipos;
- Conjunción; dadas dos proposiciones cualesquiera p y q, llamaremos conjunción de ambas a la proposición compuesta “p y q” y la notaremos p ∧ q. Esta proposición será verdadera únicamente en el caso de que ambas proposiciones lo sean.
- Disyunción; dadas dos proposiciones cualesquiera p y q, llamaremos disyunción de ambas a la proposición compuesta “p o q” y la notaremos p ∨ q. Esta proposición será verdadera si al menos una de las dos p ó q lo es.
- Negación; dada una proposición cualquiera, p, llamaremos “negación de p” a la proposición “no p” y la notaremos ¬p. Será verdadera cuando p sea falsa y falsa cuando p sea verdadera.
- Proposición condicional; Dadas dos proposiciones p y q, a la proposición compuesta “si p, entonces q” se le llama “proposición condicional” y se nota por p → q. A la proposición “p” se le llama hipótesis, antecedente, premisa o condición suficiente y a la “q” tesis, consecuente, conclusión o condición necesaria del condicional. Una proposición condicional es falsa únicamente cuando siendo verdad la hipótesis, la conclusión es falsa (no se debe deducir una conclusión falsa de una hipótesis verdadera).
- Proposición bicondicional; Dadas dos proposiciones p y q, a la proposición compuesta “p si y sólo si q” se le llama “proposición bicondicional” y se nota por p ↔ q
- Método de demostración por contradicción: La demostración de un teorema diremos que es por contradicción cuando suponiendo que la conclusión, Q, es falsa y utilizando la hipótesis P, y otros teoremas y equivalencias lógicas establecidas previamente, se llega a una contradicción.
Tablas o árboles semánticos
El método de demostración por contradicción o reducción al absurdo (mencionado en el apartado anterior) nos permite utilizar las llamadas tablas semánticas para comprobar si un argumento es o no valido. El método (descubierto en los años cincuenta por Beth y Hintikka, independientemente uno del otro) permite saber si una proposición es una contradicción. Para ello, se construye un árbol donde los nodos (finitos) son las proposiciones, el conectivo ∧ se representa por una arista vertical;
y el conectivo V por un par de aristas en la forma;
El resto de los conectivos se traducen a esa forma. Así, el condicional p → q se representa como;
ya que p → q ↔ ¬p V q.
Por otro lado, como:
p ↔ q ↔ (¬p V q) ∧ (¬q V p)
p ↔ q ↔ (¬p ∧ ¬q) V (¬p ∧ p) V (q ∧ ¬q) V (q ∧ p)
p ↔ q ↔ (¬p ∧ ¬q) V (p ∧ q)
la bicondicional se representará;
En este método, se van descomponiendo, por turno, cada proposición compuesta, de acuerdo con las reglas anteriores, marcando dicha proposición como ya utilizada. Conviene descomponer primero los bicondicionales y sus negaciones antes que otras conectivas que creen ramas. Si en una sucesión de nodos del árbol (camino), aparece una proposición y su negación, se dice que es un camino cerrado y se marca con * el nodo final. Si al final del proceso todos los caminos se cierran, la proposición es una contradicción; en caso contrario, cada camino abierto es un modelo de la proposición inicial. Así pues, si queremos demostrar o refutar un argumento del tipo H → C calculamos la tabla semántica de H ∧ ¬ C. Si al finalizar todos los caminos se cierran, tenemos que H ∧ ¬C es una contradicción, es decir, el argumento H → C es válido. Por el contrario, la existencia de una rama abierta nos llevará a concluir que el argumento no es válido. Del mismo modo, si tenemos un sistema de proposiciones {p1, p2, . . . ,pn}, sabremos que es consistente, si al construir la tabla semántica de p1 ^ p2 ^ . . . . ^ pn, nos queda algún camino abierto que representara un modelo para dicho sistema.
Ejemplos del método
- 1) Demostrar el “modus tollens”: ((p → q) ∧ ¬q) → ¬p
Argumento válido
- 2) Demostrar o refutar {p V q} → p
Argumento inválido
- En este ejemplo vemos que {¬p, q} es un contraejemplo ya que si p es falsa y q verdadera, p V q es verdadera y (p V q) → p es falsa.
- En este ejemplo vemos que {¬p, q} es un contraejemplo ya que si p es falsa y q verdadera, p V q es verdadera y (p V q) → p es falsa.
- 3) Si hay probabilidad de lluvia o hace viento, Manuel no cortará el césped. Siempre que no hay nubes en el cielo, no hay probabilidad de que llueva. Hoy no hace viento y no hay nubes en cielo. Entonces, Manuel cortará el césped.
- Llamemos:
- p: “Hay probabilidad de lluvia”
- q: “Hace viento”
- n: “Hay nubes en el cielo”
- c: “Manuel cortará el césped”
- Llamemos:
- Se trata de ver si, de las hipótesis: {((p V q) → ¬c), ¬n → ¬p, ¬q, ¬n} se puede deducir c.
- Al desarrollar la tabla, se comprueba que {¬p, ¬q, ¬n, ¬c} es un contraejemplo, ya que aunque no llueva y no haga viento, nadie nos permite asegurar que Manuel vaya a cortar el césped.
- Se trata de ver si, de las hipótesis: {((p V q) → ¬c), ¬n → ¬p, ¬q, ¬n} se puede deducir c.
Principales ventajas de las tablas semánticas respecto a las tablas de verdad
- Es menos costoso de aplicar.
- Es una buena base para programar demostradores automáticos.
- Puede extenderse a otras lógicas más potentes que la lógica de proposiciones, para las cuales el método de las tablas de verdad deja de tener sentido.
- En el caso de que el argumento no sea válido las tablas semánticas nos muestran explícitamente un contraejemplo.
Véase también
Modus tollendo tollens
Bibliografía
- Cardona, Sergio; Torres, Augusto. Lógica Matemática Para Ingeniería de Sistemas Y Computación.
- Salguero, Francisco. Árboles semánticos para lógicas modales mixtas.
- González, Francisco; Gutiérrez, José. Apuntes de Lógica Matemática.
- Camacho, Luis. Lógica Simbólica Básica.
- Universidad da Coruña. Matemáticas discretas.
- http://www.cs.us.es/~acordon/sll/sesiones3.htm
Datos: Q811591