Curso de lógica XXI: cálculo deductivo
Lamento comunicaros que los posts dedicados al curso de lógica finalizan hoy. Es una lástima, cierto, pero no iban a ser infinitos. En cualquier caso, hoy vamos a ver uno de los trucos más flamantes que podemos hacer utilizando la lógica formal. Se trata del cálculo deductivo, introducido en 1934 por Gerhard Gentzen, un lógico alemán. Gracias a este cálculo podemos demostrar con rigor formal que todo lo que dicen los demás son estupideces. No, es broma. En realidad no sirve para eso. Lo que el cálculo deductivo nos permite es extraer conclusiones a partir de un conjunto finito de premisas. Para hacer tal cosa, contamos con una serie de reglas de inferencia, las cuales nos permiten derivar enunciados a partir de otros enunciados.
Antes de meternos en faena, hay que decir que el cálculo de deductivo no es nuevo en este blog. En efecto, en el segundo artículo dedicado al significado de los nombres echamos mano de este cálculo para reducir al absurdo la tesis de que los nombres son etiquetas. Bien, dicho esto, vamos al lío, como dicen en mi pueblo.
Las reglas de inferencia
Lo primero que vamos a hacer es presentar las reglas de inferencia. Estas son las reglas que nos permitirán extraer enunciados a partir de otros enunciados. Lo que hacen las reglas, generalmente, es eliminar o introducir alguna conectiva. El cálculo deductivo se representa en tres columnas y un número finito de filas. En la columna de nuestra izquierda ha de aparecer el número de fila junto a nuestro conjunto de secuentes, esto es, las premisas con las que trabajamos; en la central la fórmula que ocupa esa fila, que puede ser una del conjunto de premisas inicial (la representamos así: PI) sobre el que se realiza el cálculo o una que hayamos derivado al aplicar las reglas de inferencia. Finalmente, a la derecha, especificamos si la fórmula central es una premisa inicial, una premisa auxiliar (PA) o una fórmula obtenida a partir de una regla (se pone el nombre de la regla y los números de las filas sobre las que esta se ha aplicado). Bien, vamos ya a por las reglas.
La primera regla se llama introducción a la conjunción (IConj.) esta nos permite introducir una conjunción a partir de otras dos premisas. Por ejemplo, si tenemos Pa en una línea y Pb en otra, podemos aplicar IConj. sobre ambas líneas y obtener Pa˄Pb. Funciona así:
1. {Pa,Pb} Pa PI
2. {Pa,Pb} Pb PI
3. {Pa,Pb} Pa˄Pb IConj. en 1 y 3
¿Fácil, no? Veamos la regla que nos permite eliminar una conjunción, (EConj., eliminación de la conjunción). Es inversa a la anterior. En efecto, si tenemos una conjunción, podemos extraer cualquiera de los enunciados de esta. Funciona de este modo:
1. {Pa˄Pb} Pa˄Pb PI
2. {Pa˄Pb} Pa EConj. en 1
Las dos siguientes reglas sirven para el condicional, →. La primera de ellas es la simple y sencilla eliminación del condicional, EC (también es conocida como Modus Ponens), la cual nos permite obtener el consecuente de un condicional si contamos con el antecedente. Así:
1. {Pa→Qa,Pa} Pa→Qa PI
2. {Pa→Qa,Pa} Pa PI
3. {Pa→Qa,Pa} Qa EC en 1 y 2
La regla de introducción del condicional (IC) es algo más complicada que las anteriores. Para obtener un condicional, tenemos que tener, por un lado, el antecedente. Después, por otro lado, hemos de demostrar el consecuente utilizando la el antecedente, que será una premisa o un supuesto o un paso al que hayamos llegado mediante la aplicación de una regla en líneas previas. Y una vez que tenemos el consecuente demostrado y el antecedente, usamos ambas líneas para introducir el condicional. Por ejemplo, queremos deducir Pa→(Qa˄Rab) a partir del siguiente conjunto de premisas: Pa, Pa→Qa, Pb˄Rab.
1. {Pa, Pa→Qa,Pb˄Rab} Pa PI
2. {Pa, Pa→Qa,Pb˄Rab} Pa→Qa PI
3. {Pa, Pa→Qa,Pb˄Rab} Pb˄Rab PI
4. {Pa, Pa→Qa,Pb˄Rab} Rab Econj. en 3
5. {Pa, Pa→Qa,Pb˄Rab} Qa EC en 1 y 2
6. {Pa, Pa→Qa,Pb˄Rab} Qa˄Rab IConj. en 4 y 5
7. {Pa, Pa→Qa,Pb˄Rab} Pa→(Qa˄Rab) IC en 1 y 6
Las dos reglas siguientes se aplican a la disyunción, ˅. La primera es la Introducción de la disyunción (ID). Esta regla es sumamente sencilla. Podemos extraer Pa˅Qa a partir de Pa.
1. {Pa} Pa PI
2. {Pa} Pa˅Qa ID en 1
Es sumamente fácil. Desgraciadamente, la regla de eliminación de la disyunción (ED) es un quebradero de cabeza. Esta nos permite deducir un enunciado, Qa pongamos por caso, a partir de una disyunción, Pa˅Qb. Para realizar tal proeza, hemos de deducir Qa tanto a partir de Pa como a partir de Qb. De este modo, supongamos que tenemos el siguiente conjunto de premisas: A = {Pa˅Qb, Qa→Qb, Pa→Qa}
1. {Pa˅Qb,Qa→Qb,Pa→Qa} Pa˅Qb PI
2. {Pa˅Qb,Qa→Qb,Pa→Qa} Qb→Qa PI
3. {Pa˅Qb,Qa→Qb,Pa→Qa} Pa→Qa PI
4. {Pa˅Qb,Qa→Qb,Pa→Qa,Pa} Pa PA
5. {Pa˅Qb,Qa→Qb,Pa→Qa,Pa} Qa EC en 2 y 4
6. {Pa˅Qb,Qa→Qb,Pa→Qa,Qb} Qb PA
7. {Pa˅Qb,Qa→Qb,Pa→Qa,Qb} Qa EC en 4 y 6
8. {Pa˅Qb,Qa→Qb,Pa→Qa} Qa EC en 1, 4 y 7
Para eliminar e introducir negaciones utilizamos una sola regla, la reducción al absurdo (Abs.) en este caso, para negar un enunciado (o eliminar la negación) hemos de derivar a partir de él una contradicción. Por ejemplo, si tenemos el siguiente conjunto de premisas, {Pa→Qb, ¬Qb}, podemos demostrar que ¬Pa mediante la reducción al absurdo.
1. {Pa→Qa,¬Qb} Pa→Qb PI
2. {Pa→Qa,¬Qb} ¬Qb PI
3. {Pa→Qa,¬Qb,Pa} Pa PA
4. {Pa→Qa,¬Qb,Pa} Qb EC en 1 y 3
5. {Pa→Qa,¬Qb,Pa} ¬Qb˄Qb IConj. en 2 y 4
6. {Pa→Qa,¬Qb} ¬Pa Abs. en 3 y 5
La regla de introducción del bicondicional (IB),↔, es otra de las complicadas. En este caso, para obtener un condicional hemos de derivar el antecedente a partir del consecuente. Después, hemos de derivar el consecuente a partir del antecedente. Una vez hecho esto, podemos introducir el bicondicional. Por ejemplo, si tenemos este conjunto de premisas A = {Pa→Qb,Qb→Pa} y queremos obtener Qb↔Pa, haremos esta derivación:
1. {Pa→Qb,Qb→Pa} Pa→Qb PI
2. {Pa→Qb,Qb→Pa} Qb→Pa PI
3. {Pa→Qb,Qb→Pa,Pa} Pa PA
4. {Pa→Qb,Qb→Pa,Pa} Qb EC en 1 y 3
5. {Pa→Qb,Qb→Pa,Qb} Qb PA
6. {Pa→Qb,Qb→Pa,Qb} Pa EC en 2 y 5
7. {Pa→Qb,Qb→Pa} Qb↔Pa IB en 4 y 6
Con la regla de eliminación del bicondicional (EB) podemos eliminar esta conectiva de manera muy parecida a como eliminamos un condicional. Por ejemplo, si queremos obtener Qb a partir de Qa↔Qb y Qa, entonces:
1. {Qa↔Qb,Qa} Qa↔Qb PI
2. {Qa↔Qb,Qa} Qa PI
3. {Qa↔Qb,Qa} Qb EB en 1 y 2
Además de estas conectivas, tenemos los cuantificadores. Para ellos también hay respectivas reglas de introducción y eliminación. Estas pueden resultar algo más complejas que las anteriores. En primer lugar, comenzaremos por la más sencilla, la eliminación del cuantificador universal (E∀). Esta me permite obtener un enunciado de la forma Pa a partir de enunciados cuantificados universalmente. Para ello, debo contar con un enunciado de la forma ∀xPx y, a partir de aquí, puedo aplicar E∀ para obtener Pa. Supongamos que tengo este conjunto de premisas: A = {∀xPx˄∀yQy}
1. {∀xPx˄∀yQy} ∀xPx˄∀yQy PI
2. {∀xPx˄∀yQy} ∀xPx EConj. en 1
3. {∀xPx˄∀yQy} Pc E∀ en 2
La regla de introducción del cuantificador universal (I∀) nos ayuda a demostrar que todo objeto tiene determinada propiedad, es decir, a partir de un enunciado de la forma Pa podemos obtener uno de la forma ∀xPx. Para ello lo que hacemos es demostrar que un objeto arbitrario cualquiera, a (esta constante es auxiliar y no debe aparecer en las premisas), tiene esa propiedad. Por ejemplo, vamos a demostrar ∀xPx a partir de A = {∀x(Qx˄Px)}
1. {∀x(Qx˄Px)} ∀x(Qx˄Px) PI
2. {∀x(Qx˄Px)} Qa˄Pa E∀ en 1
3. {∀x(Qx˄Px)} Pa EConj. en 2
4. {∀x(Qx˄Px)} ∀xPx I∀ en 3
Pasamos ya a las reglas del cuantificador existencial, ∃. La introducción del cuantificador existencial, I∃, es una regla sencilla. Si tenemos un enunciado de la forma Pa, entonces podemos introducir uno de la forma ∃xPx. Así, para un conjunto de premisas A = {∀xPx˄∀yPy} podemos deducir ∃xPx como sigue:
1. {∀xPx˄∀yPy} ∀xPx˄∀yPy PI
2. {∀xPx˄∀yPy} ∀xPx EConj. en 1
3. {∀xPx˄∀yPy} Pb E∀ en 2
4. {∀xPx˄∀yPy} ∃xPx I∃ en 3
La regla de eliminación el cuantificador existencial E∃ nos permite obtener una fórmula de la forma ∃xPx a partir de otra de la forma ∃xQx. Para hacer tal cosa, tenemos que introducir una nueva constante auxiliar, b pongamos por caso, que no esté en nuestro conjunto de premisas ni en la fórmula que queremos demostrar ni en aquella de la cual partimos. Por ejemplo, vamos a deducir ∃xPx a partir de A = {∃xQx˄∀xPx}
1. {∃xQx˄∀xPx} ∃xQx˄∀xPx PI
2. {∃xQx˄∀xPx} ∀xPx EConj. en 1
3. {∃xQx˄∀xPx} Pb E∀ en 2
4. {∃xQx˄∀xPx} ∃xPx I∃ en 3
5. {∃xQx˄∀xPx} ∃xPx E∃ en 1 y 4
Finalmente, nos quedan las dos reglas de la identidad, =. En este caso, tenemos, en primer lugar, la regla de reflexividad, R=. Esta nos permite derivar, de todo conjunto de premisas, una fórmula del tipo a = a. Podemos hacer esto aunque nuestro conjunto de premisas esté vacío. La otra regla de la identidad, la sustitución, S=, es bastante más compleja. Si tenemos que a = b, por un lado, y Pa, por otro, podemos deducir Pb mediante el uso de esta regla. Vamos a ver cómo se aplica con un ejemplo. Nuestro conjunto de premisas es A = {∀xPx→a=b,∀xPx→Pa,∀xPx}
1. {∀xPx→a=b,∀xPx→Pa,∀xPx} ∀xPx→a=b PI
2. {∀xPx→a=b,∀xPx→Pa,∀xPx} ∀xPx→Pa PI
3. {∀xPx→a=b,∀xPx→Pa,∀xPx} ∀xPx PI
4. {∀xPx→a=b,∀xPx→Pa,∀xPx} Pa EC en 3
5. {∀xPx→a=b,∀xPx→Pa,∀xPx} a=b EC en 1
6. {∀xPx→a=b,∀xPx→Pa,∀xPx} Pb S= en 4 y 5
