Árbol semántico

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;

Conectivo ∧

y el conectivo V por un par de aristas en la forma;

Conectivo V

El resto de los conectivos se traducen a esa forma. Así, el condicional p → q se representa como;

Condicional

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á;

Bicondicional

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.

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”

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.

Principales ventajas de las tablas semánticas respecto a las tablas de verdad

1. Es menos costoso de aplicar.
2. Es una buena base para programar demostradores automáticos.
3. 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.
4. 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

1. Cardona, Sergio; Torres, Augusto. Lógica Matemática Para Ingeniería de Sistemas Y Computación. 
2. Salguero, Francisco. Árboles semánticos para lógicas modales mixtas. 
3. González, Francisco; Gutiérrez, José. Apuntes de Lógica Matemática. 
4. Camacho, Luis. Lógica Simbólica Básica. 
5. Universidad da Coruña. Matemáticas discretas. 
6. http://www.cs.us.es/~acordon/sll/sesiones3.htm

• Datos: Q811591