Lógica - FCE

LOGICA DE ENUNCIADOS

1. El lenguaje de enunciados Si se restringe el lenguaje de primer orden (o lenguaje de predicados) eliminando los cuantificadores y se toma como ultima unidad de análisis enunciados (fórmulas cerradas) atómicos, se obtiene el lenguaje de enunciados (abreviado LE). En el lenguaje de enunciados los únicos símbolos lógicos son las conectivas. La lógica que descansa exclusivamente en las conectivas recibe el nombre de Lógica de enunciados. Así, pueden distinguirse en LE las siguientes categorías de símbolos 1.1 Símbolos descriptivos: Serán los símbolos para enunciados: p, q, r, s, t (o con subíndices p1, p2, p3, etc., de modo de tener una cantidad potencialmente ilimitada de3 símbolos). Estos símbolos son llamados letras esquemáticas o a veces variables de enunciados. 1.2. Símbolos lógicos. Serán las conectivas: conjunción, & ("y"), disyunción, ∨ ("o"), condicional, → ("si ... entonces"), negación, ¬ ("no"). Estos símbolos vinculan enunciados, o, más en general, sirven para obtener nuevos enunciados, más complejos, a partir de otros dados. 1.3 Observaciones. (a) Los símbolos de enunciados p, q, r, etc. se usan para referirse a enunciados que no contienen conectivas (enunciados atómicos como se los llamará). (b) La negación se aplica a una sola fórmula, de ahí que se la llame una conectiva unaria, o de aridad 1. Las demás conectivas son binarias, o de aridad 2. 1.4. Símbolos auxiliares. Para construir expresiones se emplearán además, una serie de símbolos que no tienen significado especificado, sino que son sólo auxiliares: paréntesis, corchetes, puntos y comas. Los paréntesis “(“ y “)” son, en rigor, también símbolos del LE. 15. Variables metalingüísticas. Las letras A, B, C, D y E se emplearan como variables metalingüísticas de fórmulas (eventualmente con subíndices). 1.6. Fórmulas de LE. (a) los símbolos para enunciados: p, q, r, s, t (o con subíndices p1, p2, p3, etc.) son

fórmulas de LE (b) Si A y B son fórmulas de LE, entonces (A&B), (A∨B), (A → B) y (¬A) son fórmulas de LE. (c) Sólo son fórmulas de LPO las construidas según las cláusulas (a) y (b).

1.6.1. Ejemplos de fórmulas de LE. Los siguientes son casos de fórmulas de LE: (¬(p) & q), (((p&q) ∨ q) → s), ¬(¬(q → (s&r))).

1.7. Símbolos definidos de LE. Existen otros símbolos lógicos, que pueden definirse mediante los dados. Uno de ellos es el bicondicional: (D↔) (A ↔ B) =df ((A → B) & (B → A)), que se lee como “si y sólo si”. (El símbolo “=df” es una manera de abreviar la expresión metalingüística “es igual por definición”.) También se puede definir otro símbolo, w, que representa la disyunción exclusiva, generalmente expresada como “o bien, ..., o bien” y que se define como (Dw) (A w B) =df ((A&¬B) ∨ (¬A&B)). 1.8. Más observaciones. 1.8.1. Convención acerca del uso de paréntesis. A los efectos prácticos de simplificar la simbolización en LPO, se aceptará la convención siguiente. Los símbolos ¬, &, ∨, →, ↔ para las conectivas vinculan fórmulas de manera más fuerte en ese orden, de modo que pueden ahorrarse aplicaciones de paréntesis. Asimismo, pueden omitirse los paréntesis externos. Por ejemplo, en vez de escribir ((¬(A)&B) → C), se escribirá ¬A&B → C; en vez de (A ∨ (B & ¬(C))) se escribirá A ∨ B&¬C, pero en ((A → B) & ¬(B ∨ C)) únicamente se pueden eliminar los paréntesis exteriores, obteniéndose la fórmula (A → B) & ¬(B ∨ C) . En lo que sigue se hará uso de esta convención, de modo de facilitar la escritura. 1.8.2. Concepto de subfórmula. Si ¬A, A&B, A∨ B, A→B y A↔B son fórmulas de LPO, entonces A y B son subfórmulas de esas fórmulas. 1.8.3. Fórmulas atómicas y moleculares. (a) Aquellas fórmulas que no contienen apariciones conectivas se llaman fórmulas atómicas. (b) Se llama símbolo principal de una fórmula de LE a la conectiva que vincula sus subfórmulas inmediatas. (c) Una fórmula es llamada molecular, si tiene al menos una conectiva. 1.8.4. El condicional. En el caso del condicional (a diferencia de las demás conectivas vistas) importa si una fórmula está a la derecha o a la izquierda del símbolo →, lo cual está en conexión con el significado que tiene esta conectiva. Así, en un condicional A → B, diremos que A es el antecedente y B el consecuente del condicional. 1.8.5. Lema de formación única. Toda fórmula de LE puede ser formada o construida de una única manera (de acuerdo con la definición de fórmula). Esto lleva a la siguiente afirmación: LFU: Si una formula cualquiera A no es atómica, entonces existe un único símbolo lógico * tal que A es *Bi (i = 1 o 2).

Este es el lema de formación única. De manera correspondiente, hay una único modo de descomponer una formula en sus componentes atómicos. 1.8.6. Arboles de generación para fórmulas de LE El lema de formación única se comprueba al descomponer una fórmula. Ello puede representarse gráficamente mediante árboles que indiquen la composición, y a su vez determinen si una expresión es fórmula o no. Los árboles que se tratarán de ahora en adelante son un tipo particular de grafos: grafos conectados sin ciclos. Serán además árboles binarios, es decir, que sus bifurcaciones generan a lo sumo dos ramas. En el caso de estos árboles de generación, se supone que los nodos, es decir, los puntos conectados del árbol son fórmulas del LE. Los siguientes son ejemplos de estructuras que adoptarán los árboles de generación (los astericos indican los lugares a ser ocupados por fórmulas del LE): (a) * │ * / \ * * │ /\ * ** (b) * │ * (c) * / \ * * /\ ** │ * Por ejemplo, a la expresión (p → (q & r)) le corresponde el siguiente árbol (no se hace uso de la convención respecto de paréntesis): (p → (q & r)) / \ p (q & r) /\ q r Puesto que p, q y r son fórmulas del LE, lo que se obtiene en cada uno de los pasos de descomposición, hasta el último, es una fórmula (ya que sigue la definición recursiva dada). Por el contrario, tómese la siguiente expresión: ((s & (t & r))→ (p∨)), cuyo árbol de generación es:

((s & (t & r)) → (p ∨ )) / \ (s & (t & r)) (p ∨ ) / \ │ s (t & r) ? / \ t r Esta expresión no es fórmula de LE puesto que (p ∨) no lo es, aunque s, t y r sí sean fórmulas. Los árboles de generación muestran la manera en que una fórmula está construida de acuerdo con las cláusulas de la definición de fórmula. Por ejemplo, las fórmulas ((p&q) → r) y (p & (q → r)) son fórmulas distintas pese a tener las mismas fórmulas atómicas y las mismas conectivas (y en igual cantidad). La diferencia (evidenciada ya por medio de los paréntesis) está en la composición de cada una: su estructura es diferente, y esa diferencia en la composición es lo que indican los árboles. 2. Semántica para LE 2.1. Condiciones de verdad para las conectivas El significado de las conectivas puede darse mediante la indicación de las condiciones de verdad para los enunciados que las contengan como símbolo principal. (&) Un enunciado de la forma A&B es verdadero si y sólo si tanto A como B son verdaderos. (∨) Un enunciado de la forma A ∨ B es verdadero si y sólo si A es verdadero o B es verdadero. (→) Un enunciado de la forma A→B es verdadero si y sólo si A es falso o B es verdadero. (¬) Un enunciado de la forma ¬A es verdadero si y sólo si A es falso. (↔) Un enunciado de la forma A↔B es verdadero si y sólo si A y B son verdaderos o A y B son falsos. El concepto de verdad había servido para dar una primera caracterización de la validez de una forma de razonamiento: Una forma de razonamiento es válida si todo caso concreto, todo ejemplo de la misma con premisas verdaderas tiene conclusión verdadera, o, de manera equivalente, si no existe un caso concreto, un ejemplo, con premisas verdaderas y conclusión falsa. Otro tanto ocurría con las leyes lógicas y la consistencia de conjuntos de enunciados. Si además se toma en cuenta que, en definitiva, la validez de un razonamiento depende de los símbolos lógicos que aparecen en él (lo que se evidencia en su estructura o forma), será importante caracterizar las conectivas en términos de condiciones de verdad.

2.2. Valuaciones booleanas Tanto la verdad como la falsedad de enunciados pueden considerarse como el valor que tiene una función aplicada a enunciados de LE. Esta función la llamaremos valuación. Esta función de valuación, a la que representaremos con V, asignará un único valor de verdad, verdadero o falso (representados como v y f respectivamente) a todo enunciado de LE. En esto se sigue el principio de bivalencia que se enunció anteriormente. En la lógica de enunciados el concepto de valuación se restringe a enunciados atómicos y moleculares. Las valuaciones así restringidas reciben el nombre de valuaciones booleanas, por el lógico y matemático inglés George Boole (1815-1864) quien desarrolló la estructura algebraica subyacente a la lógica de enunciados (llamada justamente álgebra booleana). Las valuaciones booleanas dan a todo enunciado uno de los dos valores v o f, interpretables como verdad y falsedad, pero también se pueden interpretar abstractamente como objetos cualesquiera. El conjunto {v, f} determina un álgebra booleana. Es común emplear 0 y 1 en lugar de v y f para indicar este carácter abstracto. Así las valuaciones booleanas para LE se definen como sigue: 1. V(A) ∈ {v,f}, para todo enunciado A de LE, 2. V(A&B) = v sii V(A) = V(B) = v; 3. V(AvB) = v sii V(A) = v o V(B) = v; 4. V(A→B) = v sii V(A) = f o V(B) = v; 5. V(A↔B) = v sii V(A) = V(B); 6. V(¬A) = v sii V(A) = f. 2.2.1 Valuaciones booleanas y tablas de verdad Estas valuaciones booleanas se presentan como matrices conocidas como “tablas de verdad” que tienen la siguiente forma: asignando valores de verdad a los enunciados componentes resultan determibados valores, v o f, para cada conectiva.. A v f v f

B v v f f

¬A f v f v

A&B v f f f

A∨B v v v f

A→B v v f v

A↔B v f f v

2.2.2 Consecuencia lógica en LE:. Un enunciado C de LE es consecuencia lógica de enunciados A1, ..., An, de LE si y sólo si no hay ninguna valuación booleana V tal que V(A1) = v, ..., V(An) = v, y V(C) = f.

2.2.3. Razonamientos válidos y valuaciones Este concepto semántico de consecuencia lógica es una reformulación precisa, sobre la base del concepto de valuación booleana y relativa al lenguaje de enunciados,

del concepto intuitivo de validez para razonamientos basado en el concepto de verdad. Se obtiene así un método de las valuaciones para determinar la validez de razonamientos de la lógica de predicados de primer orden: Un razonamiento es válido, si y sólo si, la conclusión es consecuencia lógica (en el sentido que se acaba de definir) de las premisas. Así puede establecerse la validez de razonamientos. Tómese el ejemplo del siguiente razonamiento: p ∨ q → r, ¬ r / ¬ p Supóngase una valuación booleana V tal que V(p ∨ q → r) = v, V(¬r) = v y V(¬p) = f, es decir V constituye un contraejemplo. Ahora bien, por la definición de valuación booleana V(p) = v y V(r) = f. Además de la valuación para la primera premisa se sigue que V(p ∨ q) = f o V(r) = v. En el primer caso, se da que V(p) = V(q) = f, de modo que se contradice el principio de que a cada enunciado le corresponde un único valor de verdad. En el segundo caso, ocurre lo mismo. Así no puede darse una valuación booleana que funcione como un contraejemplo del razonamiento. Este procedimiento puede llevarse aun método mecánico mediante el empleo de las tablas de verdad u otros métodos (como el de los árboles analíticos). 3. tautologías 3.1. Las tautologías son las verdades lógicas del lenguaje de enunciados, es decir, un enunciado A del lenguaje de enunciados es una tautología si y sólo si para toda valuación booleana V, V(A) = v. 3.2. Las contradicciones son las falsedades lógicas, es decir, A es una contradicción (de la lógica de enunciados) si y sólo si para toda valuación booleana V, V(A) = f. 3.3. Enunciados contingentes son aquellos que no son ni tautologías ni contradicciones. 3.4 .Un conjunto de enunciados del lenguaje de enunciados es inconsistente si y sólo no existe una valuación booleana V tal que V(A) = v para todo enunciado A de ese conjunto. De otro modo, es consistente. 4. Arboles lógicos para la lógica de enunciados 4.1 El sistema de árboles lógicos T* tiene reglas únicamente para las conectivas, de modo que es un sistema de deducción para la lógica de enunciados, siendo sus reglas las siguientes. (&1)

A&B │ A B

(&2)

¬(A&B) ┌──┴──┐ ¬A ¬B

(v1)

A∨B ┌──┴──┐ A B

(v2)

¬(A∨B) │ ¬A

¬B (→1)

A→B ┌──┴──┐ ¬A B

(→ 2)

(↔1)

A↔B ┌──┴──┐ A ¬A B ¬B

(¬1)

A : ¬A x

(↔2)

(A es un enunciado atómico)

(¬2)

¬(A→B) │ A ¬B ¬(A↔B) ┌──┴──┐ A ¬A ¬B B ¬¬A | A

Puede verse claramente que el sistema T* es una restricción del sistema TN al caso de LE. De manera análoga a como ocurría con el sistema TN, un razonamiento de la lógica de enunciados es válido si y sólo si el árbol formado a partir de sus premisas y la negación de la conclusión es cerrado. Los conceptos de derivación y teorema en T* se formula de la misma manera que para T.2 (4.1.1) Un enunciado C de LE es derivable en T* a partir de enunciados A1, ..., An del LE, si el árbol formado a partir de A1, ..., An y ¬C es un árbol cerrado. (4.1.2) Un enunciado C de LE es teorema en T*, si el árbol formado a partir de ¬C es un árbol cerrado. 4.2. Debido a que el sistema es adecuado respecto de las valuaciones booleanas, puede observarse que (i) un enunciado del lenguaje de enunciados es una tautología, si el árbol formado a partir de su negación es cerrado; (ii) un enunciado es una contradicción si el árbol formado a partir de él es cerrado; (iii) un enunciado es una contigencia si tanto árbol formado a partir de él como el árbol formado a partir de su negación tienen ambos al menos una rama abierta. Así, los conceptos de teorema en T* y tautología son equivalentes. 4.3. Además, de lo anterior se sigue que (i) si un enunciado A de LE es tautología, entonces ¬A es una contradicción y (ii) si A es una contradicción, entonces ¬A es una tautología. 4.4. Ejemplos. (a) El enunciado (A→B) ∨ (B→A) es una tautología, lo que se demuestra en T* mediante la siguiente derivación. √¬(A→B) ∨ (B→A)

√¬(A→B) √¬((B→A) A ¬B B ¬A x (b) El enunciado A∨¬A → B&¬B es una contradicción, lo que se demuestra en T* mediante el siguiente árbol. √ A∨¬A → B&¬B / \ √¬( A∨¬A) √B&¬B ¬A B √¬¬A ¬B A x x (c) El enunciado A∨B → B es una contingencia, lo que se demuestra del siguiente modo mediante árboles en T*. √¬(A∨B → B) √A∨B ¬B / \ A B x √A∨B → B / \ √¬(A∨B) B ¬A ¬B 5. Decidibilidad de la lógica de enunciados La lógica de enunciados es decidible. Esto quiere decir: existe un método mecánico o algoritmo para decidir si un enunciado es tautología o no, o si un razonamiento de enunciados es valido o no. El método de los arboles -restringido a la lógica de enunciados- es un ejemplo de un algoritmo semejante. Esto es así porque tanto los enunciados como los razonamientos de la lógica de enunciados dan lugar siempre a árboles finitos, es decir, con ramas que tienen un número finito de nodos, de modo que siempre podrá afirmarse, para toda rama, si es abierta o cerrada, y, por lo tanto, para todo árbol, si es abierto o cerrado. Asimismo, puede verse claramente por qué los árboles son, respecto de la lógica de enunciados, siempre finitos: Cada enunciado del lenguaje de enunciados contiene un número finito de conectivas y toda regla de árboles para las conectivas da

lugar a un número finito de ramas, cada una de ellas con un número finito de enunciados, y, finalmente, el conjunto de enunciados que es necesario examinar en la lógica de enunciados es siempre finito. 6. una notación uniforme Los enunciados del lenguaje de enunciados de la forma A*B y ¬(A*B), donde * es una conectiva diadica cualquiera, pueden agruparse en dos categorías, aquellas que se comportan de manera conjuntiva y aquellas que lo hacen de manera disyuntiva. Las primeras se llamaran fórmulas α y a las segundas fórmulas β. Para cada formula α se definen dos componentes α1 y α2, y lo mismo para las fórmulas β, obteniéndose la siguiente tabla: enunciados conjuntivos α2 α α1  A&B A B ¬(A∨ B) ¬A ¬B ¬(A → B) A ¬B

enunciados disyuntivos β β1 β2  ¬(A&B) ¬A ¬B A∨B A B A → B ¬A B

De acuerdo con esta tabla, las reglas del sistema de arboles pueden dividirse en reglas α y reglas β (es decir, reglas conjuntivas y disyuntivas): reglas α: (&1), ( ∨2), (→ 2) reglas β: (&2), (∨1), (→ 1) forma: α | α1 α2

forma: β / \ β1 β2

7. Dualidad 7.1 Sean * y + dos conectivas binarias. Entonces, se dirá que * es el dual de + si ¬(A+B) es equivalente con ¬A*¬B. 7.2 Si A una formula del lenguaje de enunciados, entonces AD es el resultado de reemplazar las apariciones de toda conectiva binaria por su dual y diremos que AD es el dual de A. Proposición: el dual de una tautología es una contradicción (y conversamente). Proposición: Si un enunciado de LE es una tautología, entonces la negación de su dual es también una tautología. 8. Formas normales 8.1 Si p es un enunciado atómico de LE, entonces tanto p como ¬ p serán llamados literales.

8.2 Forma normal disyuntiva: Un enunciado del LE está en forma normal disyuntiva (FND), si es una serie de disyunciones, cada miembro de la cual es un literal o una conjunción de literales. Esto puede representarse simbólicamente del siguiente modo: C1 ∨ .... ∨ Cn, con Ci = l1 & ... & lm, donde l1, ..., lm son literales. 8.3 Forma normal conjuntiva: Un enunciado del lenguaje de enunciados está en forma normal conjuntiva (FNC), si es una serie de conjunciones, cada miembro de la cual es un literal o una disyunción de literales. En símbolos: D1 & ... & Dn, con Di = l1 ∨ ... ∨ lm, donde l1, ..., lm son literales. 8.4 Teorema de la forma normal: Para todo enunciado del lenguaje de enunciados existe una FND y una FNC equivalentes. 8.5 Obtención de la FND: Dado un enunciado, constrúyase el árbol correspondiente, aplicando exhaustivamente las reglas. Entonces, para cada rama abierta del árbol, póngase en conjunción a los literales que contenga. Las ramas cerradas no cuentan. Finalmente, póngase en disyunción a todas estas conjunciones. El siguiente es un ejemplo de árbol de un enunciado y la FND que resulta de él: √p&r → ¬(q∨p → r∨p) / \ √¬(p&r) √ ¬(q∨p → r∨p) / \  ¬p ¬q √ q∨ p √¬(r∨p) ¬r ¬p / \ q p x FND: ¬p ∨ ¬q ∨ (¬r & ¬p) Arboles de este tipo serán aquí denominados “árboles rectos” en oposición a los árboles que se expondrán a continuación. 8.6 Obtención de la FNC: árboles duales A cada regla, ya sea del tipo α o β, le corresponde una regla dual, según la siguiente estructura: α / \ α1 α2

β | β1 β2

Así, cada enunciado tiene su "árbol dual". Para obtener la FNC de un enunciado, constrúyase su árbol dual correspondiente. A continuación, para cada rama del árbol así obtenido, ponga en disyunción a los literales que contiene, eliminando los que se repitan. Finalmente, ponga en conjunción todas las disyunciones obtenidas. Ejemplo de árbol dual y la FNC obtenida de él: √p&r → ¬(q&p → r∨p) √¬(p&r) √¬(q&p → r∨p) ¬p ¬r / \ √q&p √¬(r∨p) / \ / \ q p ¬r ¬p x FNC: (q ∨ ¬r ∨ ¬p) & (¬r ∨ ¬p) & (¬p ∨ ¬r)

8.7 Formas normales como método de decisión 8.7.1 Dada una FND, si en cada miembro (conjunción) de la misma aparece un enunciado atómico y su negación, entonces el enunciadooriginario es una contradicción. En este caso, cada miembro es eliminado y se obtiene entonces la FND vacía, que por convención se escribe como: p & ¬p. 8.7.2 Dada una FNC, si en cada miembro (disyunción) de la misma aparece un enunciado atómico y su negación, entonces el enunciado originario es una tautología. En este caso, cada miembro es eliminado y se obtiene, entonces, la FNC vacía, que, por convención, se escribe como: p ∨ ¬p. 8.7.3 De aquí, resulta que la construcción de la FND es útil para determinar si el enunciado es contradicción o no: Si el la FND del enunciado no es vacía, entonces no es una contradicción. Igualmente, la obtención de la FNC es útil para determinar si el enunciado en cuestión es una tautología o no: Si la FNC del enunciado no es vacía, entonces no es una tautología. 8.7.4 Ejemplos: (a) la FND de p∨q → (¬q → p) es ¬p&¬q ∨ q ∨ p. Así, no es vacía, y por lo tanto no es una contradicción, pero su FNC es vacía, de modo que es una tautología. (b) la FNC de ¬((p → q) → q) & p es (q ∨ ¬p) & q & p. Así, no es vacía y por lo tanto no es una tautología, pero su FND es vacía, de modo que es una contradicción. (c) la FND de (p → r) → p&r es p&¬r ∨ p&r, de modo que no es una contradicción. Su FNC es p & (¬r∨p) & (p∨r), de modo que no es una tautología. Luego, es una contingencia.

9. Reducción de conectivas En relación con las formas normales normales, puede verse que todo enunciado A de LE puede reducirse a otro enunciado A´ que contenga exclusivamente las conectivas ¬ y ∨, o a otro enunciado A´´ que contenga exclusivamente las conectivas ¬ y &. 10. Cláusulas 10.1 Como se ha mencionado antes, se llama literal a una fórmula atómica del LPO o su negación. Por ejemplo, p, ¬p, q, ¬q, Pa, ¬Rxa, ¬Qcd, Saxbc, etc. son literales. Sean l1, ..., ln literales, entonces se dice que l1 ∨ ... ∨ ln es una cláusula. Es decir, una cláusula es una disyunción de literales. Las formas normales conjuntivas son también llamadas formas clausuladas. 10.2 Las cláusulas que tienen la forma ¬p1 ∨ ... ∨ ¬pn ∨ q son llamadas cláusulas de Horn (por el lógico Alfred Horn, quien se ocupó de ellas). Es decir, una cláusula de Horn tiene a lo sumo una fórmula atómica sin negación, que es llamada la cabeza de la cláusula. Nótese que q tambien es una cláusula de Horn, pero que carece de fórmulas atómicas negadas. Nótese también que la forma de las cláusulas de Horn es equivalente, en lógica clásica, con la siguiente forma p1 & ... & pn → q, lo cual puede demostrarse mediante cualquiera de los sistemas vistos anteriormente. Es decir, las cláusulas de Horn expresan fórmulas condicionales. Las cláusulas de Horn que contienen una única fórmula atómica afirmada son llamadas átomos. Esta terminología (cláusulas, cláusulas de Horn, átomos, etc.) se emplea particularmente en la interpretación de la programación lógica (programación basada en lógica; el lenguaje Prolog es un ejemplo de programación lógica). 11. Resolución Uno de los caminos en la búsqueda de métodos automáticos de demostración condujo, a fines de la década de 1950, a trabajar exclusivamente con cláusulas. Es sabido que, en lógica clásica, cualquier fórmula del lenguaje de enunciados puede expresarse mediante formas clausuladas, en las cuales cada conyunto puede ser considerado una cláusula independiente, de modo que no se pierde capacidad expresiva. Sobre la base de cláusulas se desarrolló el método de resolución (debido a John Alan Robinson en 1965), que es un método de refutación y emplea una única regla de inferencia.

11.1 Regla de resolución. Sean A1, ..., Am, B1, ..., Bn, literales y p una fórmula atómica. Entonces, se tiene la siguiente regla: p ∨ A1 ∨ ... ∨ Am ¬p ∨ B1 ∨ ... ∨ Bn ────────────────────── A1 ∨ ... ∨ Am ∨ B1 ∨ ... ∨ Bn que puede verse como una forma generalizada de la regla del silogismo disyuntivo y es, por lo tanto, una forma válida de razonamiento. La conclusión recibe el nombre de resolvente y las premisas son las cláusulas progenitoras. 11.2 El Método de resolución. Se trata de un método de refutación (como también lo era el de árboles), pero que tiene como única regla la de resolución. Dado un razonamiento en lógica de enunciados, el método consiste en: 1) representar las premisas y la negación de la conclusión como cláusulas, 2) aplicar la regla de resolución al conjunto de cláusulas obtenido (dispuesto en una columna), analizando en cada oportunidad de arriba hacia abajo (aunque esto no es esencial) y marcando las cláusulas que se van empleando (es decir, cada cláusula puede emplearse una única vez). 3) como resultado de este procedimiento pueden ocurrir dos cosas: o bien quedan cláusulas a las que no se les puede aplicar la regla, o bien se obtiene la cláusula vacía, a la que podemos simbolizar, retomando una vieja idea, como ┴. Obviamente, la clásula vacía representa una contradicción (o inconsistencia, desde el punto de vista semático), con lo cual el razonamiento originario será válido. De otro modo es inválido. 11.2.1 Ejemplos. Tómese el siguiente razonamiento: p&q → r, ¬(r&¬s), ¬¬q ├ p → s . Entonces, √1) ¬p ∨ ¬q ∨ r √2) ¬r ∨ s 3) q 4) p 5) ¬s √6) ¬p ∨ ¬q ∨ s √7) ¬p ∨ s 8) s 9) ┴

de la primera premisa de la segunda premisa de la tercera premisa de la negación de la conclusión de la negación de la conclusión de 1) y 2) de 6) y 3) de 7) y 4) de 8) y 5)

El razonamiento es válido, pues se obtuvo la cláusula vacía. Ahora bien, si se desea determinar si de p&q → r se sigue p → r, se tiene √1) ¬p ∨ ¬q ∨ r 2) p 3) ¬r

de la primera premisa de la negación de la conclusión de lo negación de la conclusión

√4) ¬q ∨ r 5) ¬r

de 1) y 2) de 3) y 4)

El razonamiento no es válido, pues no puede llegarse a la cláusula vacía. 11.2.2 Observaciones. (a) El orden en que se tome las cláusulas es irrelevante. (b) La resolución es claramente un método de decisión. 11.3 Arboles y resolución. El método de resolución está fuertemente vinculado con el de los árboles. Por de pronto, ambos métodos son formalizaciones de la estrategia de la refutación, pero además, el método de resolución se obtiene al simplificar los árboles. Tómese el siguiente caso. Se quiere determinar si r se sigue de p → q y q → r. El árbol sería como sigue: √p → q √q → r ¬r / \ ¬q r / \ x ¬p q x El árbol muestra que la inferencia es inválida. Si se aplica el método de resolución al mismo caso, se tiene √1) ¬p ∨ q √2) ¬q ∨ r 3) ¬r 4) ¬q 5) ¬p (que también muestra que la inferencia es inválida). Si se compara la derivación obtenida al aplicar la regla de resolución con el árbol, se advierte que la derivación coincide, en sus elementos, con la rama abierta. Piénsese en la distinción entre reglas α y β respecto de los árboles para la lógica de enunciados. En realidad, los árboles trabajan implícitamente con formas normales. Y el método de resolución es una simplificación de los árboles. La resolución va, por así decirlo, generando la rama que va quedando abierta hasta que finalmente se cierre o quede definitivamente abierta. Otra manera de presentar graficamente el proceso de resolución en este ejemplo sería la siguiente: ¬r ¬q ∨ r >>

¬q ¬p ∨ q >>

¬p

y que es aplicable a los casos precedentes (la doble flecha >> representa la aplicación de la regla de resolución).

Históricamente, el concepto de cláusula y el método de resolución han sido ideas básicas para desarrollar el lenguaje de programación Prolog (aunque, de hecho, la regla de resolución no sea la única manera de interpretar el mecanismo computacional de Prolog).