1

LOGICA II

EL METODO DE LOS ARBOLES ANALITICOS

0. Introducción: Deducción y búsqueda de contraejemplos

El sistema de reglas de árboles analíticos (también llamado “árboles lógicos”)que se expone a continuación ofrece un método de deducción para la lógica depredicados de primer orden. El sistema se basa en el método de refutación o de“búsqueda del contraejemplo”: una demostración formal en el sistema se interpretacomo la imposibilidad de construir un contraejemplo para el razonamiento o enunciadoen cuestión. Por esta razón es algo así como una formulación puramente sintáctica (entérminos de reglas formales) de métodos originalmente semánticos para determinar lavalidez de razonamientos deductivos. Estos métodos se basan en la caracterizaciónde las constantes lógicas por medio de la indicación de sus condiciones de verdad.

Recuérdese que, según una de las definiciones de validez, una forma derazonamiento es válida si carece de contraejemplo. Esto quiere decir que una formade razonamiento es válida si no existe una interpretación de sus símbolos no lógicos,es decir, un caso concreto de esa forma de razonamiento, que haga a sus premisasverdaderas y a su conclusión falsa. Esta era una definición de validez para formas derazonamiento. Por lo tanto, si se construye un contraejemplo (un “caso en contrario” dela forma), la forma de razonamiento es inválida. Por el contrario, si resulta imposibleconstruir tal contraejemplo, esta es válida. Cosa semejante ocurre con las leyeslógicas (que, recuérdese, se pueden entender como formas válidas de razonamientoque carecen de premisas). Este es el procedimiento que el método de árbolesreproduce formalmente.

Como se verá más adelante, el método funciona primariamente como un “testde consistencia” para un conjunto de enunciados. La validez de un razonamientosurgirá de manera secundaria o indirecta, al mostrar que es inconsistente suponer laverdad de las premisas y la falsedad de la conclusión.

El método se basa en un sistema de reglas que descomponen los enunciadosgenerales o moleculares hasta llegar a sus componentes atómicos, y por esto sepuede hablar de un análisis de enunciados. Este análisis se representa gráficamentemediante árboles, que tienen bifurcaciones o ramas. De allí el nombre del método. Elsistema de reglas, una vez formalizado, resultará muy conveniente para analizarpropiedades semánticas de la lógica de predicados de primer orden (tales comocorrección, completitud y otras). La presentación seguirá en líneas generales alsistema que Raymond Smullyan formuló en su libro First-Order Logic (Smullyan 1995),donde el sistema recibe el nombre de “tableaux analíticos”.

1. El concepto de verdad y los símbolos lógicos

Se supondrá para todo enunciado A lo siguiente: A es verdadero o A es falso.

Esto es lo que se denomina principio de bivalencia, es decir, el principio de que paratodo enunciado hay dos valores de verdad, verdadero y falso, y todo enunciado tieneexactamente uno de ellos.

2

Esta suposición tiene un alto grado de idealización, pues en diversassituaciones puede darse el caso de enunciados que carezcan de valor de verdad, perono se tomará en cuenta esa situación. El principio de bivalencia conduce así a unapartición del conjunto de enunciados en dos conjuntos: el de los enunciadosverdaderos y el de los enunciados falsos. Y esto es algo importante para lo que sigue.

1.1. Condiciones de verdad para los símbolos lógicos

Para las constantes lógicas, cuantificadores y conectivas, valen las siguientescondiciones de verdad:

( ∀) Un enunciado de la forma ∀xA[x] es verdadero si y sólo si A[u] es verdadero paratodo individuo u del dominio de cuantificación.

( ∃) Un enunciado de la forma ∃xA[x] es verdadero si y sólo si A[u] es verdadero paraalgún individuo u del dominio de cuantificación.

La variable x entre corchetes hace referencia a todas las apariciones de x que puedahaber en la fórmula representada esquemáticamente por A, La letra u es una variabledel metalenguaje para elementos del dominio.

(∧) Un enunciado de la forma A∧B es verdadero si y sólo si tanto A como B sonverdaderos.

(∨) Un enunciado de la forma A ∨ B es verdadero si y sólo si A es verdadero o B esverdadero.

(→) Un enunciado de la forma A→B es verdadero si y sólo si A es falso o B esverdadero.

(¬) Un enunciado de la forma ¬A es verdadero si y sólo si A es falso.

2. Reglas de verdad y falsedad

Sobre la base de las condiciones de verdad recién expuestas, son válidas lassiguientes reglas relativas a la verdad y falsedad de enunciados con símbolos lógicos:

( ∀i) Si un enunciado de la forma ∀xA[x] es verdadero, entonces puede inferirse queA[a] es verdadero, para toda constante de individuo a que designe a algún individuodel dominio.( ∀ii) Si un enunciado de la forma ∀xA[x] es falso, entonces puede inferirse que A[c] esfalso, donde c es una constante que se refiere de manera indeterminada a algúnindividuo del dominio.

( ∃i) Si un enunciado de la forma ∃xA[x] es verdadero, entonces puede inferirse queA[c] es verdadero, donde c es una constante que designa de manera indeterminada aalgún individuo del dominio.( ∃ii) Si un enunciado de la forma ∃xA[x] es falso, entonces puede inferirse que A[a] estambién falso, para toda constante de individuo a del LPO que designe a un individuodel dominio.

Nótese la función de la constante de individuo c en las reglas (∀ii) y (∃i), y como sediferencia de a en las reglas (∀i) y (∃ii). La constante c se usa para representar de

3

manera indeterminada a un individuo arbitrario del dominio de cuantificación, que nose sabe cuál elemento es. Por lo tanto, las constantes de individuo indicadas por c notienen una referencia fija, no designan un elemento concreto del dominio, sino que esalgo así como el “representante” del “algún” (o “algunos”) que no se sabe cuál es(cuáles son) y que hace (hacen) que A[c] sea respectivamente falso (en (∀ii)) yverdadero (en (∃i). Nótese que si fuera una constante cualquiera, estas reglas seríanclaramente incorrectas. En el caso de (∃1), a partir de que se afirme que existe unelemento que cumple con lo que dice A, no se sigue que de que sea el individuo quela constante b designa, por ejemplo, el individuo que cumple con lo que dice A.

(∧i) Si un enunciado de la forma A&B es verdadero, entonces puede inferirse quetanto A como B son verdaderos.(∧ii) Si un enunciado de la forma A&B es falso, entonces puede inferirse que A esfalso o B es falso.

(vi) Si un enunciado de la forma A∨B es verdadero, entonces puede inferirse que A esverdadero o B es verdadero.(vii) Si un enunciado de la forma A∨B es falso, entonces puede inferirse que tanto Acomo B son falsos.

(→i) Si un enunciado de la forma A→B es verdadero, entonces puede inferirse que Aes falso o B es verdadero.(→ii) Si un enunciado de la forma A→B es falso, entonces puede inferirse que A esverdadero y B es falso.

(↔i) Si un enunciado de la forma A↔B es verdadero, entonces puede inferirse que Ay B son verdaderos o A y B son falsos.(↔ii) Si un enunciado de la forma A↔B es falso, entonces puede inferirse que A esverdadero y B es falso o A es falso y B verdadero.

(¬i) Si un enunciado de la forma ¬A es verdadero, entonces puede inferirse que A esfalso.(¬ii) Si un enunciado de la forma ¬A es falso, entonces puede inferirse que A esverdadero.

2.1 Reglas de verdad y validez de razonamientos

A partir de estas reglas de verdad puede establecerse la validez derazonamientos deductivos y, también, desde luego, que ciertas formas de enunciadosson leyes lógicas (verdades lógicas). Tómese el siguiente ejemplo de razonamientopresentado en el simbolismo lógico

∀xQx _____________∀x (Px → Qx) .

Supóngase que el razonamiento es inválido, es decir, que es posible hacer que ∀xQxsea verdadero y ∀x (Px → Qx) sea falso. Entonces, sobre la base de esta suposición yrespecto de este segundo enunciado, para algún individuo (indeterminado) designadomediante la constante c, Pc→Qc es falso por la condición (∀ii). Esto quiere decir por(→ii) que Pc es verdadero y Qc es falso. Ahora bien, por (∀i) y la premisa, Qc debe serverdadero, cayendo en una inconsistencia, de modo que no es posible refutar la

4

validez del razonamiento. Queda así determinado, sobre la base de las reglas deverdad dadas, que el razonamiento es válido.

Considérese este ejemplo ulterior:

Pd → (Qd ∧ Sd))¬∃xSx_____________________¬Pd

Supóngase que el razonamiento es inválido, es decir, es posible considerar las dospremisas verdaderas y la conclusión falsa. De aquí, por las reglas precedentes, resultaque Pd es un enunciado verdadero, ∃xSx es falso. Además, Pd → (Qd ∧ Sd) será unenunciado verdadero. Dado este hecho, nos enfrentamos con una alternativa: Pd esfalso o Qd ∧ Sd es verdadero. En el primer caso, caemos en una inconsistencia: Pdresulta verdadero y falso. En el segundo caso, tendremos que Qd y Sd serán ambosverdaderos. Pero, resulta que como ∃xSx es falso, Sd debe ser falso, con lo quetambién caemos en una inconsistencia: Sd resulta verdadero y falso. Ante estaalternativa, ambas opciones nos llevan a una inconsistencia, de modo que no resultaposible que el razonamiento sea inválido.

3. El sistema de reglas para árboles analíticos

Las reglas para el método de los árboles analíticos se justifican, de maneraprefomal, en las reglas de verdad y falsedad recién expuestas. Ahora bien, las reglasformales del sistema de árboles tienen características peculiares, y no puedenconsiderarse reglas de inferencia en el sentido estricto considerado hasta ahora. Enefecto, estas reglas contienen la posibilidad de considerar conclusiones alternativas,que se expresarán como bifurcaciones a partir de un tronco común formado por lapremisa (justamente, las reglas hacen que el árbol se vaya generando). Las reglas sonlas que generan los árboles analíticos, de modo que siempre se aplican a enunciadosque están en un árbol.

3.1. Enunciados etiquetados

A fin de construir el sistema de reglas se introducirán dos símbolos más, que seentenderán como “etiquetas” para enunciados, y que al ser aplicados a las mismasdarán lugar a “enunciados etiquetados”. Estos son los símbolos V y F.

3.1.1. Definición. Una enunciado etiquetado será una expresión de las formas VA oFA, donde A es una enunciado.

Así, una enunciado estará etiquetado si es precedido por alguna de las etiquetas V oF. Por ejemplo V¬Sab, V∀x(Px ∨ Qx), F¬ ∃x ∀y Rxy, FQc&Pc → Sc, son enunciadosetiquetados. Queda claro que las etiquetas son símbolos auxiliares del sistema T y nonuevos símbolos lógicos. Tienen un carácter semejante a las líneas que se usaránpara indicar bifurcaciones (o a la x que se usará para cerrar una rama). En unainterpretación informal, las etiquetas V y F se interpretan respectivamente como “esverdadero” y “es falso”. En los árboles del sistema T sólo aparecerán enunciadosetiquetados.

5

3.2 La naturaleza de los árboles del sistema de reglas de árboles analíticos

Los árboles que se tratarán de ahora en adelante son un tipo particular deestructuras semióticas llamadas grafos: grafos conectados sin ciclos. Serán ademásárboles binarios, es decir, que sus bifurcaciones generan a lo sumo dos ramas. En elcaso de estos árboles analíticos, se da por sentado que los nodos, es decir, los puntosconectados del árbol son enunciados etiquetados. A continuación se ofrecen algunasdefiniciones acerca de árboles:

3.2.1: Un árbol es un conjunto de enunciados etiquetados ordenados por una relación(expresada gráficamente por la líneas que unen los enunciados) y en el cual existe unúnico subconjunto (no vacío) de enunciados etiquetados que constituyen el origen delos demás nodos del árbol (el tronco del árbol).

3.2.2: Una rama es una secuencia numerable de enunciados etiquetados quecomienza en el tronco y que o bien tiene un enunciado etiquetado final (rama finita) obien no lo tiene (rama infinita).

3.2.3: Dada una enunciado cualquiera A, si en una misma rama aparecen VA y FA,entonces se dirá que la rama es una rama cerrada, lo que se indicará marcando con xal extremo de la rama.

3.2.4: Una rama abierta es una rama finita que no es cerrada.

3.2.5: Un árbol cerrado es un árbol que tiene todas sus ramas cerradas.

3.2.6: Un árbol abierto es un árbol que tiene al menos una rama abierta.

3.2.7: Un árbol terminado es un árbol en el que a todo enunciado que contenga unsímbolo lógico se le ha aplicado la regla correspondiente (es decir, no quedanenunciados sin analizar).

Los siguientes son ejemplos de estructuras que adoptarán los árboles analíticos (losasteriscos indican el lugar que deben ocupar enunciados):

(a)*│*

/ \* *│ / \* * *

(b)*│*

6

(c)*

/ \* * / \ * *│*

3.3. Las reglas del método de los árboles analíticos

Las reglas, que se aplican a enunciados etiquetados, son las que se ofrecen acontinuación.

( ∀V) V∀xA[x] (∀F) F∀xA[x] │ │ VA[ai] FA[c]

( ∃V) V ∃xA[x] (∃F) F∃xA[x] │ │ VA[c] FA[ai]

Restricciones a las reglas de cuantificadores: (∀F) y (∃V) c debe ser una constante deindividuo nueva en la rama. Por el contrario en (∀V) y (∃F) ai es cualquiera de lasconstantes de individuo a1, ..., an ,que aparezcan en enunciados anteriores de la ramaen la que está el enunciado al cual se le aplica la regla o, en el caso de que ningúnenunciado de la rama contenga constantes, una nueva constante de individuo.

(∧V) VA∧B (∧F) F(A ∧B) │ ┌──┴──┐ VA FA FB VB

(∨V) VA∨B (∨F) F(A∨B) ┌──┴──┐ │ VA VB FA FB

(→V) VA→B (→ F) F(A→B) ┌──┴──┐ │ FA VB VA FB

(↔V) VA↔B (↔F) F(A↔B) ┌──┴──┐ ┌──┴──┐ VA FA VA FA VB FB FB VB

(¬V) V¬A (¬F) F¬A | |

7

FA VA

Nota: El resultado de aplicar una regla a una enunciado etiquetado debe escribirse entodas las ramas abiertas que aparezcan debajo de esta.

3.3.1. Regla de cierre de ramas.

Recuérdese que si en una misma rama aparecen VA y FA, entonces se diráque la rama está cerrada, lo que se indica marcando con una x al extremo de la rama.Esquemáticamente

:VA:

FAx

donde los dos puntos indican un número finito de nodos. En un sentido informal, elcierre de una rama significa que se ha hallado una inconsistencia (aceptando elsupuesto de que un enunciado no puede ser verdadero y falso).

El enunciado A debe ser atómico, ya que el método exige que se apliquentodas las reglas correspondientes a los símbolos lógicos que aparecen en enunciados.Es decir, tiene sentido aplicar la regla de cierre de rama únicamente en el caso en quelos enunciados sea atómicos. Por lo demás, imagínese un caso de razonamientocomo, por ejemplo

∀x∀y(Rxy&Syx → ∃zQxyz)_________________________∀x∀y(Rxy&Syx → ∃zQxyz)

que es trivialmente válido. No diríamos que con sólo etiquetarlos y cerrar la ramahemos aplicado el método (obre todo visto como un método mecánico o automático dededucción).

3.4. Observaciones.

Como puede verse, para cada símbolo lógico hay reglas de dos tipos: “reglasde verdad” (las de la izquierda) y “reglas de falsedad” (las de la derecha). La relacióncon las “reglas de verdad” (o condiciones de verdad para las constantes lógicas) delparágrafo 2 salta a la vista. Las reglas siempre descomponen o “analizan” lasenunciados en subenunciados (se puede decir que “eliminan” el símbolo lógico al quese aplican). Es por ello que a los árboles construidos de acuerdo con estas reglas selos llama “analíticos”.

Estas reglas sirven tanto para determinar la validez (o, en determinados casos,la invalidez) de un razonamiento formulado en el lenguaje lógico como para determinarsi un enunciado formulado en el lenguaje lógico es una ley lógica (o, en determinadoscasos, si no lo es), y finalmente para determinar también si un conjunto de enunciadoses o no consistente..

Así como las reglas se basan directamente en las condiciones de verdad paralos símbolos lógicos, el método se basa también en la definición de razonamientoválido basada en el concepto de verdad: un razonamiento es válido si su formacorrespondiente carece de contraejemplo, es decir, un ejemplo con premisas

8

verdaderas y conclusión falsa. Más precisamente, se basará en ver si, en el caso deun razonamiento, el conjunto de enunciados formado por las premisas junto con lanegación de la conclusión, o, en el caso de un único enunciado, el conjunto unitarioformado por la negación del enunciado, es consistente. Si no lo es, esto significa quela conclusión es se infiere deductivamente de las premisas, o que el enunciado seinfiere deductivamente del conjunto vacío de premisas. Por el hecho de partir de lascondiciones de verdad puede decirse que el sistema de árboles es una transposiciónde conceptos semánticos a un método de deducción.

Así, puede decirse también que el método procede por refutación o porbúsqueda de un contraejemplo y puede considerarse como una variante del métodopor el absurdo. Dicho de manera sucinta, dado un razonamiento, se supone junto laverdad de sus premisas y la falsedad de la conclusión. Luego se aplican las reglas atodo enunciado que contenga símbolos lógicos, obteniéndose un “árbol” de derivación.Si en toda rama construida aparece una enunciado atómica VA y FA, entonces elrazonamiento es válido. Análogamente se hará respecto de un único enunciado.

Una observación final: Obviamente las líneas que van indicando ramas ybifurcaciones no representan la inferencia lógica. Más bien, representa lo mínimo quese puede afirmar consistentemente a partir de los enunciados que están arriba de lalínea. Cuando aparece la x es que ya nada puede afirmarse con consistencia a partirde los enunciados enlazados en la rama.

Otra forma de interpretar las bifurcaciones indicadas por las líneas es como laconversa de la relación de inferencia lógica. Es decir, si la premisa es falsa, entoncesuna cualquiera de sus conclusiones es falsa. Dicho de otro modo, si cualquiera de lasconclusiones de una regla de árboles es verdadera, entonces la premisa seráverdadera. Esto está ligado al carácter refutatorio del método.

4. Arboles analíticos y validez

Un razonamiento formulado mediante enunciados del LPO será consideradoválido si, y sólo si, el árbol formado a partir de sus premisas etiquetadas con V y suconclusión etiquetada con F es un árbol cerrado. Asimismo, un enunciado A seráconsiderado un caso de ley lógica si, y sólo si, el árbol formado a partir del enunciadoetiquetado como FA es cerrado.

5. Ejemplos

E1. Tómese el razonamiento

∀xQx ______________∀x (Px → Qx)

visto en el parágrafo 2.1 y compárese el árbol resultante con la argumentaciónofrecida allí.

1. V∀xQx2. √F∀x (Px → Qx)

3. √F(Pc→Qc)4. VPc5. FQc6. VQc

x

9

El árbol obtenido puede verse como una proyección o representación de laargumentación presentada en el lenguaje cotidiano.

La única rama de este árbol está cerrada. El razonamiento es válido. En elárbol el enunciado 3. se obtiene de 2 (por la regla (∀F)), 4. y 5. se obtienen de 3 (por(→F)) y 6. se obtiene de 1 (por la regla (∀V)). La tilde √ indica que los enunciados asu derecha han sido objeto de la aplicación de una regla, de modo que no puedenvolver a ser utilizados. (Nótese que eso no sucede con el primer enunciado, que esuna cuantificación universal etiquetada con V.) Aquí se advierte claramente por quéestos árboles son llamados “analíticos”: las reglas llevan a descomponer losenunciados en subenunciados de menor complejidad a lo largo de la construcción delárbol, de modo que “analizan” el enunciado hasta llegar a sus componentes básicos eirreductibles.

E2. Véase ahora el segundo de los ejemplos dados en 2.1

Pd → (Qd ∧ Sd)¬∃xSx_____________________¬Pd

El árbol correspondiente es el siguiente:

√VPd → (Qd ∧ Sd)√V¬∃xSx

√F¬PdV Pd

F∃xSx/ \

FPd √VQd ∧ Sdx VQd VSd FSd

x

Aquí se obtienen dos ramas (lo que le da un aspecto realmente “arbóreo”) al gráficoconstruido mediante las reglas. Ambas ramas quedan cerradas, de modo que elrazonamiento se considera válido. (Nótese que el quinto enunciado, una cuantificaciónexistencial etiquetada con F, no se tilda).

E3. Determínese la validez del siguiente razonamiento:

∀x(Px → Qx)Pa ∧ Pb _____________Qa∧Qb

10

V ∀x(Px → Qx)√V Pa ∧ Pb√F Qa ∧ Qb

VPaVPb

√VPa → Qa√VPb → Qb

/ \FQa FQb/ \ / \

FPa VQa FPa VQax x x / \

FPb VQb x x

El razonamiento es válido.

E4. Determinese que la siguiente forma de enunciado es una ley lógica:

(A → ∃yB[y]) → ∃y(A → B[y])

√F((A → ∃yB[y]) → ∃y(A → B[y]))√ VA → ∃yB[y]F∃y(A → B[y])

/ \ FA √V∃yB[y]

√F(A → B[a]) √F(A → B[a])VA VA

FB[a] FB[a]x VB[b]

√ F(A → B[b]) VA FB[b]

x

La forma de enunciado es una ley lógica.

E5. Determínese si el siguiente razonamiento es válido o no:

∀x(Px ∨ Qx)______________∀x(Px → Qx)

V∀x(Px ∨ Qx)√F∀x(Px → Qx)

√F(Pa → Qa)VPaFQa

√ VPa ∨ Qa/ \

VPa VQa x

El razonamiento no es válido (hay una rama abierta).

11

6. La consistencia en los árboles analíticos

La idea de consistencia es esencial para los árboles lógicos, puesto que es untest de consistencia. En efecto, lo que el método muestra en el caso de unrazonamiento válido es que la negación de la conclusión es inconsistente con laspremisas, y esto se evidencia en que todas las ramas del árbol construido estáncerradas. Por lo tanto, si hay al menos una rama abierta el conjunto de partida paraconstruir el árbol es consistente (la negación de la conclusión es consistente con laspremisas, de modo que el razonamiento originario es inválido).

Este hecho sugiere la siguiente definición de consistencia mediante el métodode los árboles analíticos:

6.1. Un conjunto de enunciados es consistente si y sólo si el árbol construido a partirde sus miembros, etiquetados todos con V, mediante las reglas del sistema T tiene almenos una rama abierta.

De aquí se sigue directamente un método para determinar consistencia. Tómese elejemplo del conjunto formado por los enunciados Qa ∧ Sa, Pa→(Qa∧Sa) y ¬∀x¬Px.Este es el árbol resultante.

√V Qa ∧ Sa√V Pa → (Qa∧Sa)

√V¬∀x¬PxVQaVsa

√F∀x¬Px√V¬¬Pb√F¬Pb

VPb/ \

FPa √VQa & Sa VQa

VSa ,

el cual, al tener al menos una rama abierta (de hecho ambas ramas quedan abiertas),muestra que el conjunto es consistente.

7. Estrategias para la aplicación de las reglas

El sistema de árboles está concebido, en principio, como un sistema mecánicode deducción. Esto significa que si el razonamiento es válido (o el enunciado es leylógica), entonces el árbol quedará cerrado, sin importar el orden en que se apliquenlas reglas, siempre que estas estén correctamente aplicadas (a lo sumo puede variarla longitud de las ramas).

En los ejemplos dados se han seguido ciertas estrategias generales quepermiten abreviar los árboles. Así, en el caso de reglas para conectivas siempre seemplean las reglas que no bifurcan primero (de modo de ahorrar en la complejidad delas ramas). Véase el ejemplo 6.2 y comiéncese aplicando reglas al tercer enunciado(negación de la conclusión). En el caso de las reglas de cuantificadores, las reglas(∀F) y (∃V) también se aplican antes que las otras dos (de modo de asegurar que laconstante sea nueva y evitar la introducción de constantes superfluas). Así sucede enlos ejemplos E2, E3 y E4 La tilde √ indica que se ha aplicado una regla a la enunciadoque está a su derecha y por ello no puede volver a ser usada. Las aplicaciones de las

12

reglas (∀V) y (∃F) nunca son tildadas, pues las enunciados respectivas pueden volvera ser usadas cuantas veces sea necesario (esto se ve claro en el tercer ejemplo), y engeneral deben volver a ser usadas siempre que aparezcan nuevas constantes deindividuo (es decir, es obligatorio hacerlo). En los tres primeros ejemplos el árbolqueda cerrado. En el último el árbol queda abierto, de modo que el razonamiento noes válido. Esto significa que el método de los árboles también sirve para determinarrazonamientos inválidos (más adelante se verá que esto no vale para todos los casos).

En síntesis, debe tenerse en cuenta las siguientes reglas prácticas para laaplicación de las reglas de árboles. RP1. Aplíquese primero, siempre que sea posible, las reglas de cuantificación a losenunciados con significado existencial (los que comienzan con un cuantificadorexistencial o un universal negado).

RP2. Aplíquese en primer lugar, si ello es posible, la regla (¬F).

RP3. En el caso en que se aplique reglas de cuantificación a enunciados consignificado universal (los que comienzan con un cuantificador universal o un existencialnegado), debe aplicarse la regla respecto de todas las constantes de individuo queaparecen en la rama donde está el enunciado.

RP4. En el caso de las reglas de conectivas, aplíquese las reglas que no introducenbifurcaciones antes que las reglas que sí lo hacen, siempre que ello sea posible.

8. Arboles infinitos

Supóngase que se quiere determinar si el enunciado ∃x∀yRxy se sigue o no apartir de Raa mediante las reglas del método de árboles analíticos. El árbolcorrespondiente tendría el siguiente aspecto

VRaaF∃x ∀y Rxy√ F∀y Ray

F Rab√ F∀y Rby

F Rbc√ F∀y Rcy

F Rcd√ F∀y Rdy

FRde:

Claramente, el procedimiento continúa indefinidamente, pues siempre que hay unanueva constante se le debe aplicar las reglas (∀V) y (∃F) a enunciados universalesetiquetados con V o a cuantificaciones existenciales etiquetados con F. El árbol esentonces infinito.

Este caso muest8ra que el método de los árboles analíticos no da unarespuesta a si ∃x ∀y Rxy se deduce de Raa o no y, por consiguientemente, no puededeterminar si el razonamiento Raa / ∃x ∀y Rxy es válido o no. Por esta razón, losárboles lógicos no constituyen un método de decisión para la lógica de cuantificadoresy conectivas. Un método de decisión es un método que permita decidir (determinar,establecer) en un número finito de pasos si un enunciado se deduce o no en T a partirde otros, si un enunciado es un caso de ley lógica o no, o si un conjunto deenunciados es consistente o no.

13

Aquí aparecen ciertas limitaciones de los árboles analíticos; no permite, porejemplo, hacer una clara bipartición entre casos de leyes lógicas y aquellos queenunciados refutables (es decir, aquellos cuyo árbol es cerrado). Pues aparecen casosen los que no se puede dar una respuesta: el método nos lleva a seguirindefinidamente la construcción del árbol. Estos enunciados reciben el nombre deindecidibles.

9. Descripción del procedimiento de construcción de los árboles

Los procedimientos mediante se construyen árboles en este método puedenespecificarse en su totalidad. Los procedimientos (básicamente recursivos) puedendescribirse mediante las siguientes fases en la construcción de árboles.

(1) Escríbase en columna las premisas etiquetados con V y la conclusión etiquetadocon F (se obtiene así el tronco del árbol). Los enunciados candidatos a leyes lógicas overdades lógicas se toman como un caso especial (se los etiqueta con F y constituyenel único elemento del tronco).

(2) Aplíquese, si ello es posible, las reglas de árboles a los enunciados etiquetados deltronco del árbol tomando en cuenta las restricciones que tienen las reglas del métodoy siguiendo las reglas prácticas dadas anteriormente.

(3) Cierre todas las ramas que contenga un mismo enunciado A etiquetado con V y F,es decir VA y FA, de acuerdo con la caracterización de rama cerrada. Si quedan todaslas ramas cerradas, entonces la conclusión se deduce a partir de las premisas. Casocontrario, si queda al menos una rama abierta, pásese al paso (4).

(4) Si queda alguna enunciado no atómica sin marcar en alguna rama abierta,entonces pueden darse los siguientes casos: (a) Si es un enunciado molecular o consignificado existencial (comienza con un cuantificador existencial o la negación de ununiversal), entonces aplíquese la regla correspondiente volviendo al paso (2). (b) Si esun enunciado universal (que comienza con un cuantificador universal o con lanegación de un existencial), entonces obsérvese si hay en la rama alguna constantede individuo respecto de la cual pueda aplicarse la regla respectiva. En caso afirmativovuelva al paso (2). En caso contrario (es decir, los únicas enunciados sin marcar sonenunciados universales y no quedan constantes de individuo respecto de los cualespuedan aplicarse las reglas), la conclusión no se deduce de las premisas.

Nótese que en algunos casos el procedimiento puede continuarindefinidamente (árboles infinitos). Desde el punto de vista computacional, esto es loque se denomina problema de la parada: en tanto procedimiento mecánico, losenunciados indecidibles hacen que el procedimiento nunca se detenga.

10. Arboles analíticos con enunciados sin etiquetar. El sistema TN

A partir de las condiciones de verdad para la negación dadas en la sección 1. ylas reglas respectivas para la negación de la sección 2. se sigue que la negaciónpuede servir directamente para expresar la falsedad: afirmar ¬A es lo mismo queafirmar la falsedad de A. Este hecho conduce a la idea de presentar un sistema deárboles analíticos que no necesite enunciados etiquetados con V y F, sinosimplemente las enunciados de LPO: escribir una enunciado será afirmarla comoverdadera y escribir su negación será afirmarla como falsa. Ahora los nodos de losárboles estarán formados únicamente por enunciados de LPO y una rama cerrada

14

será aquella que contenga un enunciado A y su negación ¬A. Así, puede concebirseel sistema TN, cuyas reglas, formuladas en este caso para enunciados del LPO, sonlas que se ofrecen a continuación (un sistema análogo aparece el libro de RichardJeffrey Lógica formal. Su alcance y sus límites).

( 1) ∀xA[x] (2) ¬∀xA[x] │ │ A[ai] ¬ A[c]

( 1) ∃xA[x] (2) ¬∃xA[x] │ │ A[c] ¬A[ai]

(&1) A&B (&2) ¬(A&B) │ ┌──┴──┐ A ¬A ¬B B

(v1) A∨B (v2) ¬(A∨B) ┌──┴──┐ │ A B ¬A ¬B

(→1) A→B (→ 2) ¬(A→B) ┌──┴──┐ │ ¬A B A ¬B

(↔1) A↔B (↔2) ¬(A↔B) ┌──┴──┐ ┌──┴──┐ A ¬A A ¬A B ¬B ¬B B

(¬1) A (A es un (¬2) ¬¬A : enunciado |8 ¬A atómico) A x

Restricción: De manera análoga a lo que ocurre con el sistema T, en (∀2) y (∃1) cdebe ser una constante de individuo nueva en el árbol. Por el contrario en (∀1) y ( ∃2)ai es cualquiera de las constantes de individuo a1, ..., an , que aparezcan enenunciados anteriores de la rama en la que está el enunciado al cual se le aplica laregla o, en el caso de que ningún enunciado de la rama contenga constantes, unanueva constante de individuo.

Nota: El resultado de aplicar una regla a un enunciado debe escribirse en todas lasramas abiertas que aparezcan debajo del enunciado.

11.1 Observaciones.

Como puede verse, para cada símbolo lógico hay reglas de dos tipos: “reglasde afirmación” (las de la izquierda) y “reglas de negación” (las de la derecha). La

15

relación con las “reglas de verdad” (o condiciones de verdad para las constanteslógicas) del parágrafo 2 salta a la vista, teniendo en cuenta que, a partir de las reglasde verdad para la negación, afirmar un enunciado es afirmar su verdad, y afirmar lanegación de un enunciado es afirmar su falsedad. De este modo, la conectivanegación sirve, gracias a las reglas de verdad, para expresar la falsedad. Nótese loscambios en las reglas de negación: la primera, (¬1), expresa la situación en que sepuede cerrar un árbol, la segunda es una forma de la regla de doble negación.

Resulta obvio que estas reglas sirven tanto para determinar la validez (o, endeterminados casos, la invalidez) de un razonamiento formulado en el lenguaje LPOcomo para determinar si un enunciado de LPO es una ley lógica (o, en determinadoscasos, si no lo es).

En general, un gran número de características del sistema T se conservan enTN. Sin embargo, existe una diferencia importante. En el caso de T, la determinaciónde validez o invalidez o consistencia e inconsistencia, etc. (según cada caso),dependerá exclusivamente de aplicar las reglas para los símbolos lógicos queaparezcan en los enunciados en cuestión. Por el contrario, en el caso de TN siempredeberán aparecer las reglas para negación. Por ejemplo, para determinar en elsistema TN la validez de un razonamiento que contenga únicamente el condicional →como símbolo lógico, no bastarán las reglas relativas al condicional, sino que deberánusarse las reglas para la negación. Con ello las reglas dejan de ser separables oindependientes, una propiedad que por razones de teoría lógica se quiere tener ensistemas lógicos de este tipo. Cuando las reglas del sistema para cada símbolo lógicoson separables, es posible modificarlas localmente, sin alterar el resto, a fin de obtenerotras lógicas en las que no valen algunos principios clásicos (como por ejemplo, lalógica intuicionista).

Tómese como ejemplo el primero de los razonamientos analizados

∀xQx _____________∀x (Px → Qx)

cuyo árbol, según TN, sería el siguiente1. ∀xQx

2. √¬∀x (Px → Qx)3. √¬(Pc→Qc)

4. Pc5. ¬Qc6. Qc

x

Pese a no contener negación alguna, la determinación de la validez de esterazonamiento requiere la primera regla de la negación.

Los problemas de usar enunciados sin etiquetar van más allá de este hecho.Como ya se ha mencionado, hace más difícil la formulación de la reglas para otraslógicas (tema que, por lo demás, va más allá de esta presentación).

11.2. Equivalencia entre T y TN

No cabe duda que, estableciendo la correspondencia entre VA y A y entre FA y ¬A,para cualquier enunciado cerrada A del LPO, en las reglas de T y TN respectivamente,todo árbol T que represente una deducción puede convertirse en otro en TNcorrespondiente, que representa una deducción, y viceversa, de modo que ambossistemas resultan equivalentes y representan, en suma, un mismo método.