Apuntes Tema 7 Sistemas formales Recordamos la idea general de sistema formal que aprendimos en el tema 3: Un sistema lógico es un conjunto de esquemas de argumento válido, organizados en esquemas básicos y esquemas derivados. Un sistema lógico-formal es un sistema lógico que usa un lenguaje formal para representar las formas de argumento válido y que puede definirse de forma puramente sintáctica, sin hacer referencia a ningún contenido semántico. Para definir un sistema formal hay que especificar: • su lenguaje, que a su vez queda definido especificando: • su vocabulario primitivo • sus reglas de formación • su mecanismo deductivo, que queda definido al especificar: • sus axiomas • sus reglas de transformación o de deducción Ahora que sabemos qué es la relación de consecuencia, podemos ver los sistemas formales como unos mecanismos generadores de consecuencias. (Al dar una semántica a LP, hemos formulado una definición que nos dice en qué consiste la relación de consecuencia, y tenemos unos métodos de decisión que nos permiten contestar sí o no a preguntas concretas sobre la existencia de una relación de consecuencia entre un conjunto y una fórmula dados. Ahora aprenderemos un sistema formal que nos permitirá extraer consecuencias a partir de un conjunto dado de premisas.)

7.1. Dos tipos de sistemas formales: leyes y reglas Un sistema formal se define mediante un conjunto de axiomas y un conjunto de reglas de transformación, pero es posible que el conjunto de axiomas sea vacío. Esta posibilidad hace que habitualmente se distingan dos tipos de sistemas formales: aquellos cuyo conjunto de axiomas es vacío y aquellos cuyo conjunto de axiomas es no vacío. Los sistemas formales cuyo conjunto de axiomas es vacío quedarán definidos solamente mediante un conjunto de reglas de transformación. Se suelen llamar cálculos de deducción natural. Los sistemas formales con un conjunto de axiomas no vacío quedan definidos cuando se especifican tanto sus axiomas como sus reglas de transformación. Estos sistemas se suelen llamar cálculos axiomáticos. Los sistemas formales axiomáticos fueron los que primero aparecieron en la historia de la lógica: la Conceptografía de Frege es el primer sistema axiomático de lógica formal. Lo que le interesa a Frege es formular de manera rigurosa los fundamentos de la aritmética. Para eso, necesita reducir los conceptos y leyes de la aritmética a conceptos y leyes lógicas. Como quiere garantizar que lo que pone en juego es la "pura lógica", busca unas leyes lógicas básicas (que le parecen verdades lógicas evidentes: son los axiomas de su sistema) y muestra cómo las demás verdades lógicas se derivan de las básicas mediante reglas lógicas (las reglas de deducción de su sistema). Lo que interesa en un sistema formal axiomático es el conjunto

resultante de verdades lógicas (unas básicas y otras derivadas mediante reglas), a las que llamaremos leyes lógicas. Por eso a los sistemas axiomáticos se les llama "sistemas de leyes". Los sistemas formales de tipo axiomático tuvieron mucho éxito a principios del siglo XX (aparte de Frege, otros dos lógicos-matemáticos que hicieron importantes contribuciones a la lógica fueron el británico B. Russell y el alemán D. Hilbert). Pero en los años treinta del siglo XX los lógicos empiezan a interesarse menos por la fundamentación de las verdades matemáticas y más por el razonamiento matemático mismo. En 1934 el lógico y matemático alemán Gerhard Gentzen publica un cálculo que él llama de "deducción natural", que será el origen de la otra manera de entender los sistemas formales, centrada no en las leyes lógicas, sino en las reglas de deducción (por eso se llaman "sistemas de reglas"). En los mismos años, los lógicos polacos estaban también trabajando con sistemas de reglas (por ejemplo, Stanislaw Jaśkowski parece que había inventado uno, aunque no lo publicó, hacia 1926). En los sistemas de deducción natural las reglas de deducción son las que reflejan las leyes de la argumentación. En un sistema de deducción natural hay muchas reglas de deducción, y son ellas las que están organizadas en básicas y derivadas. Lo que interesa no es demostrar leyes lógicas, sino usar las reglas de deducción para extraer consecuencias de premisas, construyendo así deducciones. La invención de sistemas de este tipo favoreció la evolución de la lógica desde su aplicación a la fundamentación de la matemática hacia el estudio de la argumentación en general (porque, en principio, las deducciones lógicas reflejan mejor que las demostraciones axiomáticas los procesos "naturales" de razonamiento).

7.2. Deducción natural: el sistema DNP Vamos a aprender un sistema formal "de reglas" para la lógica proposicional, al que llamaremos DNP (deducción natural proposicional). Su lenguaje es LP, ya definido, y su mecanismo deductivo no tiene axiomas, sino solamente reglas de deducción. El mecanismo deductivo de DNP nos permitirá construir el conjunto de todas las deducciones posibles entre fórmulas de LP. Una deducción en DNP de la fórmula A a partir del conjunto de premisas Γ (Γ A) es una secuencia finita de fórmulas de LP cuya última fórmula es A, y en la que cada una de las fórmulas presentes está justificada por ser: o bien una premisa del conjunto Γ, o bien un supuesto cancelado (más adelante sabremos qué es esto), o bien una fórmula que se deriva de fórmulas anteriores mediante aplicación de una regla de deducción de DNP. ejemplo: sabiendo que el modus ponens (A→B), A B es una de las reglas de deducción de DNP, construir una deducción de la fórmula q a partir del conjunto {p, (p→q)} 1. p

justificación: es una premisa

2. (p→q) 3. q

justificación: es una premisa

justificación: se sigue de 1 y 2 mediante el modus ponens

Puesto que hemos encontrado la deducción, podemos decir que la fórmula q se deduce (en DNP) del conjunto {p, (p→q)}, o que la fórmula q es consecuencia sintáctica (en DNP) del conjunto {p, (p→q)}. Abreviadamente, escribiremos p, (p→q) q. Recordemos que un sistema formal es, en principio, una estructura vacía de contenido. Las deducciones en DNP son construcciones puramente sintácticas. Después, se puede dar un contenido al sistema (nosotros ya lo hemos hecho: tenemos ya una semántica para LP) y

poner en relación las nociones sintácticas con las semánticas. Por ejemplo, la noción sintáctica de deducción se relacionará con la noción semántica de consecuencia. Pero, en principio, el sistema se define sin ninguna alusión a nociones semánticas.

Definición del sistema DNP:

Lenguaje para DNP (el lenguaje LP): • vocabulario primitivo: • variables proposicionales: p, q, r, s… • conectivas: ¬, ∧, ∨, →, ↔ • (paréntesis izquierdo y derecho como símbolos auxiliares) • reglas de formación: • si A es una variable proposicional, entonces A es una fbf de LP • si A es una fbf de LP, entonces ¬A es una fbf de LP • si A y B son fbfs de LP y δ es una conectiva diádica, entonces (AδB) es una fbf de LP • ninguna otra secuencia de símbolos es fbf de LP Mecanismo deductivo para DNP: • reglas básicas de deducción (no hay axiomas) Las reglas de deducción nos indican cuándo una fórmula se deduce de otras. Nos dicen qué fórmulas podemos añadir a una deducción, a partir de las fórmulas que ya tengamos escritas en ella. Vamos a distinguir dos tipos de reglas: unas que nos dicen qué se deduce de una determinada fórmula ya presente en nuestra deducción (reglas de eliminación) y otras que nos dicen de qué se deduce una determinada fórmula que queremos añadir a la deducción (reglas de introducción). Las clasificamos teniendo en cuenta la estructura de las fórmulas: en concreto, su conectiva principal. Para cada conectiva definiremos un par de reglas básicas: una de introducción, que indicará cómo obtener una fórmula cuyo signo lógico principal sea esa conectiva (a partir de fórmulas existentes en la deducción), y otra de eliminación, que indicará qué fórmulas se pueden obtener a partir de una fórmula (existente en la deducción) cuyo signo lógico principal sea esa conectiva. Reglas básicas de INTRODUCCION Introducción de Conjunción (IC)

A B (A ∧ B)

B A (A ∧ B)

Introducción de Disyunción (ID)

A (A ∨ B)

B (A ∨ B)

Reglas básicas de ELIMINACION Eliminación de Conjunción (EC)

(A ∧ B) A

(A ∧ B) B

Eliminación de Disyunción (ED)

(A ∨ B) A  B  C  C C

Teorema de Deducción (TD)

Modus Ponens (MP)

A  B (A → B) Reducción al Absurdo (RA)

A (B ∧ ¬B)

¬A Introducción de Bicondicional (IB)

(A→B) (B→A) (A↔B)

(B→A) (A→B) (A↔B)

(A→B) A

A (A→B)

B

B

Doble Negación (DN)

¬¬A A Eliminación de Bicondicional (EB)

(A↔B) (A→B)

(A↔B) (B→A)

Representamos las reglas disponiendo las fórmulas en vertical, usando una raya horizontal en lugar del signo "" para indicar qué se deduce de qué. Lo que aparece encima de la raya horizontal es lo que la regla dice que debemos tener en la deducción para poder aplicar la regla, y lo que aparece debajo de la raya horizontal es lo que podemos añadir en virtud de la regla. Las reglas ED, TD y RA son especiales: esas rayitas a la izquierda de las fórmulas indican que se ha trabajado con supuestos auxiliares: los supuestos (marcados con ) son fórmulas que no estaban en nuestra deducción pero que añadimos cuando queremos (nos los "inventamos"), y que nos ayudan provisionalmente a aplicar otras reglas de deducción (la parte de la deducción que depende de un supuesto queda marcada prolongando la barra vertical que sale del supuesto), pero que no deben estar en nuestra deducción definitiva: por eso deben "cancelarse" (se indica "cerrando" la barra vertical hacia la última fórmula que hemos obtenido en esta deducción dependiente del supuesto: ). Cancelar un supuesto siempre nos lleva a añadir a la deducción la fórmula que nos indica la regla correspondiente (la que aparece debajo de la raya horizontal en la formulación de la regla: esa es la fórmula que se deduce de las otras, mientras que el supuesto y toda la deducción dependiente de él en realidad no forman parte de la deducción: una vez cancelado el supuesto, es como si desaparecieran). Estas reglas nos dicen cómo, partiendo de unas premisas, podemos ir añadiendo fórmulas a una lista hasta conseguir que esa lista de fórmulas sea una deducción de una determinada fórmula a partir de esas premisas. El mecanismo deductivo de DNP define el conjunto de todas las deducciones que se pueden obtener entre fórmulas de LP (de manera análoga a como las reglas de formación de LP nos permiten generar todas las fbfs de LP, las reglas de deducción de DNP nos permiten generar todas las deducciones posibles en DNP).

Construcción de una deducción de la fórmula A partir del conjunto de premisas Γ:

1º. Se escriben una debajo de otra las fórmulas del conjunto de premisas Γ. 2º. Se aplican reglas de deducción a las fórmulas que nos interesen (ver sección "Estrategias"), con lo que se van añadiendo fórmulas hasta obtener la fórmula A como última fórmula de la secuencia.

Cada vez que se añade una fórmula, se numera y se añade a la derecha su justificación (qué regla hemos aplicado y a qué fórmulas). Y, una vez que forma parte de la deducción, es una fórmula más a la que se pueden aplicar reglas de deducción. ejemplo: deducción (p∧q) p: 1. (p∧q) 2. p

(premisa) (EC 1)

Esta secuencia de fórmulas es la deducción que buscábamos: su última fórmula es p, y cada fórmula está justificada por ser: o premisa (1) o seguirse de fórmulas anteriores (2). 3º. En algunos casos se introducen fórmulas que no son premisas ni se deducen de fórmulas anteriores en virtud de ninguna regla, sino que son supuestos ("premisas" provisionales) que deben ser cancelados. Los supuestos se representan así: B, y dan lugar a deducciones subsidiarias (que se indican prolongando la línea vertical del supuesto) hasta que se obtiene una fórmula que permite cerrar el supuesto. Hay tres reglas que nos dicen cómo cerrar supuestos (TD, ED y RA: ver sección "Estrategias"): una vez cerrado, se añade a la deducción la fórmula que nos indica la regla correspondiente y se escribe a la derecha de esa fórmula su justificación. Entonces la deducción subsidiaria queda eliminada de la deducción (no se pueden aplicar reglas de deducción a las fórmulas que quedan encerradas dentro de la línea vertical que se abre con el supuesto y se cierra con la fórmula que nos ha permitido cerrarlo: es como si no existieran en la deducción). Una vez cerrado el supuesto, lo que la deducción subsidiara desaparecida deja en nuestra deducción es la fórmula que añadimos en virtud de la regla correspondiente. ejemplo: 1. (p∧q) (no es premisa ni se sigue de nada, es un supuesto provisional)  2. q (deducción dependiente del supuesto, por EC 1) 3. (r∨q) (sigue la deducción subsidiaria, por ID 2: es la fórmula que permite cerrar) 4. ((p∧q)→(r∨q)) (el supuesto se ha cancelado y queda esta fórmula por TD 1-3)

Estrategias

a) Dos tipos de deducción (directa o indirecta): A veces es posible avanzar directamente desde las premisas (a las que seguramente se aplicarán reglas de eliminación) hacia la construcción de la conclusión (que puede ser un "trozo" obtenido de descomponer las premisas, o puede que haya que construirla aplicando reglas de introducción). ejemplos: deducción ¬¬p p 1. ¬¬p 2. p

(premisa) (DN 1: era un trozo de la premisa)

deducción p, q ((p∧q)∨r)

1. p

(premisa)

2. q

(premisa)

3. (p∧q)

(IC 1, 2)

4. ((p∧q)∨r)

(ID 3: hemos construido la conclusión usando reglas de introducción)

Cuando la deducción directa no es posible, hay que aplicar una deducción indirecta por reducción al absurdo (utilizando la regla de deducción que tiene este nombre). Se empieza suponiendo lo contrario de lo que se busca (si queremos obtener A, se introduce como supuesto auxiliar ¬A) y se aplican reglas de deducción hasta llegar a una contradicción, es decir, hasta añadir a nuestra deducción una conjunción de la forma (B∧¬B) (donde B puede ser cualquier fórmula). Una vez que esté en la deducción esa conjunción, podremos cerrar el supuesto mediante la regla RA y añadir a la deducción, de acuerdo con la regla RA, la negación del supuesto. ejemplo: deducción de p a partir del conjunto {q, ¬q} 1. q

(premisa)

2. ¬q

(premisa)

3. ¬p (supuesto provisional, para una reducción al absurdo)  4. (q∧¬q) (IC 1, 2) 5. ¬¬p 6. p

(RA 3-4) (DN 5)

En algunas deducciones hay que combinar las dos estrategias. Ejemplo: deducción de (p∧q) a partir de {q, ¬q} 1. q

(premisa)

2. ¬q

(premisa)

3. ¬p (supuesto provisional, para una reducción al absurdo)  4. (q∧¬q) (IC 1, 2) 5. ¬¬p 6. p

(RA 3-4) (DN 5)

7. (p∧q)

(IC 1, 6)

b) Dos tipos de reglas (de introducción y de eliminación): Como estrategia general para construir una deducción, una vez escritas en la deducción las premisas (y cada vez que añadamos nuevas fórmulas), hay que mirar qué tenemos (fórmulas ya presentes en la tabla) y qué buscamos (fórmulas cuya presencia nos interesa en la

deducción: quizá la conclusión, o quizá otra fórmula que nos permita construir la conclusión que buscamos). Las reglas de eliminación se aplican a las fórmulas ya presentes en la tabla para obtener nuevas fórmulas cuya presencia interese en la deducción. • si tenemos una conjunción, podemos añadir a la deducción cualquiera de sus partes (también las dos, si nos interesa) por EC; • si tenemos una disyunción, la regla ED nos dice cómo obtener una fórmula nueva introduciendo supuestos (cuidado: la regla ED no nos permite, en principio, obtener las partes de la disyunción, estas fórmulas se ponen como supuestos, pero después se cancelan y lo que se obtiene es una fórmula nueva, indicada con la metavariable C en la formulación de la regla); • si tenemos un condicional y su antecedente (las dos fórmulas, por separado, deben estar en nuestra deducción), podemos añadir el consecuente por MP; • si tenemos una doble negación, podemos añadir la fórmula sin negación por DN; • si tenemos un bicondicional, podemos añadir a la deducción cualquiera de los dos condicionales (A→B) o (B→A) (o los dos, si nos interesan) por EB. Las reglas de introducción se aplicarán en función de la conectiva principal de la fórmula que queramos obtener: • si buscamos una conjunción, tendremos que obtener sus dos partes por separado y aplicar la regla IC; • si buscamos una disyunción, bastará con obtener una de sus partes y aplicar la regla ID; • si buscamos un condicional, tendremos que suponer su antecedente y tratar de obtener su consecuente para aplicar después la regla TD; • si buscamos una negación, tendremos que suponer la fórmula sin el negador y tratar de obtener una contradicción para aplicar la regla RA (esta regla se aplica en la estrategia de demostración indirecta, cuando la directa no es posible, aunque lo que se busca no sea una negación: en ese caso se supondrá la fórmula negada y se obtendrá por RA la doble negación, que se elimina por DN); • si buscamos un bicondicional, el problema se reduce a la obtención de los dos condicionales correspondientes para aplicar después IB. En cuanto a la introducción y eliminación de supuestos, es importante introducir únicamente aquellos supuestos que sepamos cómo van a ser eliminados. Sólo hay tres reglas que nos permitan cancelar supuestos (ED, TD y RA) y cada una de ellas debe utilizarse en el momento adecuado: ED si hay una disyunción que queramos eliminar, TD si buscamos un condicional y RA cuando intentamos una reducción al absurdo. Se pueden introducir nuevos supuestos sin haber cancelado los anteriores, simplemente hay que tener cuidado al cerrarlos: se cancelan en orden inverso al de su introducción. Hay que acordarse de cerrar todos los supuestos abiertos, y tener en cuenta que, una vez cancelado un supuesto, la subdeducción correspondiente deja de formar parte de la deducción. Además, en una ED, cada una de las deducciones subsidiarias es independiente de la otra: no pueden aplicarse reglas de deducción a fórmulas dependientes de uno de los supuestos mientras se trabaja en la subdeducción dependiente del otro supuesto. ejemplo de deducción con supuestos:

deducción de (p→r) a partir de {(q∨q), (q→r)} Primero, escribimos las premisas 1. (q∨q) 2 (q→r) A continuación, pensamos qué tenemos: una disyunción, a la que podríamos aplicar ED, y un condicional, al que podríamos aplicar MP si tuviéramos su antecedente. Pensamos también qué buscamos: un condicional, que obtendríamos por TD. Decidimos entonces suponer el antecedente del condicional que queremos obtener, y tratar de deducir su consecuente para poder aplicar entonces TD. 3.  p

(supuesto: antecedente del condicional que buscamos)

Ahora buscamos el consecuente r, que podríamos obtener aplicando MP a 2: para esto necesitamos en la deducción su antecedente q, que no podemos obtener, pero que está en la disyunción 1. Probamos a aplicar ED, introduciendo supuestos que nos permitan seguir aplicando reglas: 4.

q

q

(son dos supuestos independientes, las dos partes de la disyunción 1)

Trabajamos con la primera subdeducción: 5.

r

(MP 2, 4)

Esta fórmula es justo la que nos interesaba: puede funcionar como la "C" de la regla ED. Pasamos entonces al otro supuesto de la disyunción, y tratamos de conseguir la misma fórmula. (Aquí es fácil, porque los dos supuestos son idénticos: repetimos lo que hemos hecho antes. Pero normalmente hay que trabajar independientemente con cada uno de los supuestos: incluso puede que las dos subdeducciones sean de distinta longitud, no importa.) r

(MP 2, 4)

Cuando tenemos las misma fórmula obtenida a partir de los dos supuestos de la disyunción, la regla ED nos permite cancelar los dos supuestos y añadir a nuestra deducción esa misma fórmula, ahora independiente de los supuestos y ya perfectamente justificada en la deducción. Quedaría así: 1. (q∨q) 2 (q→r) 3.  p 4.

q

q

5.

r (MP 2, 4)

r

6.

r

(MP 2, 4)

(ED 1, 4-5)

Todavía queda un supuesto sin cerrar (3), pero ya tenemos el consecuente que buscábamos: la regla TD nos permite cancelar el supuesto y añadir a la deducción el condicional que queríamos obtener. 1. (q∨q) 2 (q→r) 3.  p

4. 

q

q

5. 

r (MP 2, 4)

r

6. 

r

7. (p→r)

(MP 2, 4)

(ED 1, 4-5) (TD 3-6)

Una vez obtenida la conclusión (y cancelados todos los supuestos), la secuencia resultante es una deducción de (p→r) a partir del conjunto dado de premisas.

Nociones sintácticas fundamentales del sistema formal DNP:

La noción básica en DNP es la noción de deducción de una fórmula A a partir de un conjunto de premisas Γ. • Una deducción en DNP de la fórmula A a partir del conjunto de premisas Γ es una secuencia finita de fórmulas de LP cuya última fórmula es A, y en la que cada una de las fórmulas presentes está justificada por ser: o bien una premisa del conjunto Γ, o bien un supuesto cancelado, o bien una fórmula que se deriva de fórmulas anteriores mediante aplicación correcta de una regla de deducción de DNP. Pero la presencia en DNP de reglas que funcionan con supuestos provisionales permite construir deducciones sin premisas. Cuando el conjunto Γ es el conjunto vacío, la deducción se llama demostración. • Una demostración en DNP de la fórmula A es una secuencia finita de fórmulas de LP cuya última fórmula es A, y en la que cada una de las fórmulas presentes está justificada por ser: o bien un supuesto cancelado, o bien una fórmula que se deriva de fórmulas anteriores mediante aplicación correcta de una regla de deducción de DNP. La posibilidad de construir deducciones o demostraciones de fórmulas determina las siguientes propiedades sintácticas de fórmulas: • Una fórmula A es consecuencia sintáctica de un conjunto Γ en el sistema DNP sii es posible construir una deducción de A a partir de Γ en DNP (es decir, sii la fórmula es deducible de Γ en DNP). • Una fórmula A es una ley lógica del sistema DNP sii es posible construir una demostración de ella en DNP (es decir, sii la fórmula es demostrable en DNP). El sistema DNP tiene una propiedad metalógica interesante, que se llama teorema de deducción: si Γ, A B entonces Γ (A→B). Como caso particular tenemos: si A B entonces  (A→B), es decir, si una fórmula B es consecuencia sintáctica de otra A, el condicional que tiene a A como antecedente y a B como consecuente es una ley lógica. El teorema de deducción permite relacionar así las nociones de deducción (noción básica de los sistemas de deducción natural) y de ley lógica (noción básica de los sistemas axiomáticos).

Aplicación del sistema DNP a la demostración de propiedades semánticas de fórmulas:

Aunque un sistema formal se define independientemente de cualquier contenido semántico, si se quiere que sirva para algo se construye con vistas a una "interpretación

pretendida". Por ejemplo, los símbolos primitivos de LP quieren representar nexos y enunciados, las reglas de formación de LP quieren reflejar las estructuras del lenguaje natural en las que se combinan enunciados simples para dar lugar a enunciados compuestos, y las reglas de deducción de DNP quieren reflejar esquemas de argumentación correcta del lenguaje natural. (Por ejemplo, hemos elegido MP como regla básica de deducción de DNP porque, si "→" expresa una condición suficiente, el esquema (A→B), A B se corresponde con un esquema correcto de argumentación, el modus ponens.) El que hayamos construido DNP con vistas a una semántica concreta hace que haya una relación entre las nociones sintácticas que acabamos de definir y las nociones semánticas del tema 6. Por eso DNP puede usarse para demostrar propiedades y relaciones semánticas (y, por tanto, validez de argumentos). Para demostrar que una fórmula A es una tautología habrá que construir una demostración de A en DNP (sin premisas):  A. Para demostrar que una fórmula A es consecuencia (semántica) de un conjunto de premisas Γ habrá que construir una deducción de A a partir de Γ: Γ A. Para demostrar que A y B son equivalentes, habrá que construir dos deducciones: A B y B A. Para demostrar que el argumento A, B, C ∴ D es válido, habrá que construir una deducción de D a partir del conjunto {A, B, C}: A, B, C D.

Muy importante: el hecho de que no sepamos construir la deducción no quiere decir que hayamos demostrado que la fórmula no es tautología o que el argumento no es válido, etc. Puede que sea posible construir la deducción, pero no hayamos dado con ella. La deducción natural sólo nos da respuestas afirmativas (sí es válido, sí implica, sí es tautología… cuando tenemos la deducción correcta), pero no negativas (si no tenemos la deducción, no sabemos si es válido o no, si implica o no, etc.). Para garantizar la respuesta negativa (no es válido, no es tautología, no implica, etc.) habría que aplicar un método de los que dan una respuesta "sí o no" (tablas de verdad, tablas analíticas…).

Consejos prácticos para hacer deducciones:

El único truco para aprender a hacer deducciones es hacer muchas. Algunas cosas con las que hay que tener cuidado: • Al trabajar con supuestos: • No es una buena estrategia suponer "a lo loco" (por ejemplo, no es una buena estrategia: "necesito p, voy a suponer p"). Al introducir un supuesto, hay que pensar más en el resultado final (lo que está debajo de la raya horizontal en la formulación de la regla) que en el supuesto mismo. Porque el supuesto debe cancelarse, y esto significa que: • siempre que se introduzca un supuesto hay que saber cómo se va a cancelar (con ED, con TD o con RA): suponemos las partes de una disyunción para aplicar ED, suponemos el antecedente cuando buscamos un condicional y pensamos aplicar TD, o suponemos la negación de lo que buscamos para aplicar RA. Si no tenemos una de estas tres cosas en perspectiva, es mejor no introducir el supuesto.

• una vez cancelado el supuesto, la subdeducción y el supuesto mismo desaparecen, y lo que queda en la deducción es lo que la regla nos dice que añadamos: esto es lo que hay que tener en la cabeza al introducir el supuesto, hacia dónde nos llevará (es decir, sí es una buena estrategia: "necesito p, voy a suponer algo que me lleve a p"). • Hay que recordar que, una vez cerrado el supuesto, no se pueden usar fórmulas dependientes de él (es decir, no se les pueden aplicar reglas a las fórmulas que quedan dentro de la raya de un supuesto cerrado). • Del mismo modo, hay que acordarse de que las subdeducciones de una ED son independientes: cuando se trabaja con uno de los supuestos no se pueden usar fórmulas dependientes del otro. Y, una vez cerrados, desaparecen las dos subdeducciones, como ocurre con cualquier supuesto cerrado. • No se pueden cerrar supuestos en desorden, ni dejar supuestos sin cerrar. Es importante recordar esto, porque a veces obtenemos la fórmula que buscábamos, pero nos queda un supuesto abierto: todavía no está terminada la deducción, hay que cerrarlo. O a veces obtenemos una fórmula que queríamos para cerrar un supuesto, pero queda otro supuesto abierto por debajo: no se puede cerrar el de arriba hasta que no se cierre el de abajo. Tampoco se puede cerrar sólo uno de los supuestos de una eliminación de disyunción dejando abierto el otro: se deben cerrar los dos a la vez. • Tampoco se pueden "cerrar" supuestos inventándose una regla inexistente. Sólo cierran supuestos las reglas ED, TD y RA: debajo del cierre del supuesto tiene que aparecer la fórmula que estas reglas nos dicen que añadamos, y a su derecha deberá estar la justificación (por ejemplo, ED 3, 4-8, o TD 2-6, o RA 3-4). • Al trabajar con disyunciones: • No confundir EC con ED: la eliminación de disyunción no nos permite deducir ninguna de las partes de la disyunción, sino que nos obliga a introducir supuestos, deducir otra cosa, y obtener al final esa otra cosa como deducida de la disyunción. • No es una buena estrategia introducir una disyunción a menos que sea la disyunción que buscamos. A veces es tentador introducir una disyunción con la ilusión de luego eliminarla: no debe hacerse esto, aunque parezca tan fácil (porque la regla ID nos permite "inventar" una parte teniendo la otra), porque lo que no es fácil es eliminarla luego (hay que suponer las dos partes y tratar de llegar a la misma conclusión "C": si nos hemos "inventado" una parte, es difícil que lo consigamos). • En general, cuidado con qué fórmulas se pueden usar en la deducción: • No se pueden aplicar reglas a trozos de fórmulas, siempre se aplican las reglas a la conectiva principal. En concreto, ninguna regla nos sirve para eliminar ¬(α∧β), ¬(α∨β), ¬(α→β) o ¬(α↔β). Si aparecen fórmulas con esta estructura en nuestra deducción, es probable que nos sirvan para hacer la función de "¬B" en una reducción al absurdo: por ejemplo, si tenemos ¬(α→β), por algún lado aparecerá (α→β), y construiremos ((α→β)∧¬(α→β)), que será el (B∧¬B) que nos permitirá cerrar el supuesto de la RA.

• No se pueden usar fórmulas que no pertenezcan a la deducción (aunque parezca un consejo tonto, cuidado con confundir con nuestra deducción el enunciado del problema que queremos resolver: la deducción empieza con la primera línea numerada, el enunciado A, B  C no pertenece a la deducción). • No se pueden usar fórmulas de supuestos cerrados o del "otro" supuesto en una ED. • Sí se pueden usar fórmulas de supuestos abiertos, incluso el supuesto mismo. • Sí se pueden usar varias veces las mismas fórmulas, y aplicarles las mimas o distintas reglas, tantas veces como sea necesario. Algunas estrategias generales, por "tipos" de ejercicios: • Cuando buscamos un condicional: habrá que suponer el antecedente y buscar el consecuente, para aplicar después TD. Si el consecuente es otro condicional, se vuelve a suponer (debajo del primer supuesto) su antecedente y se busca su consecuente. Si el consecuente es otro condicional, etc. Al final se cierra toda la cadena de supuestos por sucesivas aplicaciones de TD. • Cuando tenemos un condicional pero no podemos aplicar MP porque no tenemos su antecedente: hay que construir ese antecedente (como si fuera un problema pequeñito dentro del otro) y, cuando se consigue añadir a la deducción, se aplica MP normalmente. • Cuando buscamos una disyunción el problema se reduce a encontrar una de sus partes (no hacen falta las dos para aplicar ID), aunque a veces es más fácil probar indirectamente, suponiendo la negación de la disyunción y buscando una contradicción. • Cuando tenemos una disyunción, hay que suponer las dos partes por separado, y buscar una fórmula C que podamos deducir independientemente a partir de cada una, para después cancelar los dos supuestos y añadir otra vez C ya sin depender de ningún supuesto. El problema con ED es que nadie nos dice qué fórmula es C: suele ser bueno probar si C puede ser la conclusión que buscamos al final. • Cuando no hay manera de encontrar lo que buscamos, podemos probar por reducción al absurdo: suponemos su negación y buscamos una contradicción. A veces tenemos ya en nuestra deducción una fórmula (B: una cualquiera) y su negación (¬B). Esto es bueno, porque nos permite deducir lo que queramos: suponemos su negación, introducimos la conjunción (B∧¬B) y con ella cerramos el supuesto y obtenemos al final la fórmula que buscábamos. • Normalmente habrá que combinar varias de estas estrategias: por ejemplo, suponer el antecedente de un condicional que buscamos, a continuación suponer la negación de su consecuente para obtenerlo por RA, eliminar una disyunción para sacar una fórmula que es el antecedente de un condicional que ya tenemos y al que queremos aplicar MP, etc.

Reglas básicas y reglas derivadas

Hemos hablado antes de las propiedades sintácticas de las fórmulas, y hemos definido la noción de consecuencia sintáctica. (Una fórmula es consecuencia de un conjunto Γ en el sistema DNP sii es posible construir una deducción de A a partir de Γ en DNP.) Ahora, podemos distinguir dos tipos de consecuencias sintácticas: mediatas e inmediatas.

Una fórmula es consecuencia sintáctica inmediata de un conjunto de fórmulas Γ cuando es el resultado de la aplicación de una única regla básica a las fórmulas de ese conjunto. Por ejemplo, q es consecuencia inmediata de {(p→q), p}, porque es el resultado de aplicar la regla MP a esas dos fórmulas. Una fórmula es consecuencia sintáctica mediata de un conjunto de fórmulas Γ cuando es el resultado de la aplicación de varias reglas básicas. Por ejemplo, la fórmula (q∨r) es consecuencia mediata de {(p→q), p}, porque es el resultado de aplicar dos reglas de deducción: primero MP para obtener q (como paso intermedio), y luego ID para obtener (q∨r). Ahora podemos observar que hay una correspondencia entre cada relación de consecuencia inmediata y una regla básica: (p→q), p  q se corresponde con el modus ponens p, q,  (p∧q) se corresponde con la introducción de conjunción, etc. Análogamente, podríamos convertir en reglas de deducción cualquiera de las deducciones más largas que podemos construir en DNP. Por ejemplo: 1. (p→q) 2. ¬q

(premisa) (premisa)

3.



4. 5.

q (MP 1, 3) (q∧¬q) (IC 4, 2)

6.

¬p

p

(supuesto provisional, para una reducción al absurdo)

(RA 3-5)

Esta deducción nos dice que ¬p es consecuencia mediata de {(p→q), ¬q}, es decir: (p→q), ¬q  ¬p Podríamos usar esta relación de consecuencia sintáctica mediata para fundar una nueva regla de deducción (a la que llamaremos Modus Tollens): (p→q) ¬q ¬p Decimos que esta es una regla de deducción derivada, porque no está basada inmediatamente en el significado de los nexos, sino que se justifica mediante una deducción previamente construida utilizando reglas básicas. Las reglas derivadas, si se usan en una deducción, permiten simplificarla, porque se hace en un solo paso lo que, por ejemplo, requeriría cuatro (en el caso del modus tollens). Podríamos añadir al sistema DNP todas las reglas derivadas que quisiéramos (siempre que estuvieran justificadas por la correspondiente deducción), pero esto no cambiaría en nada la capacidad deductiva de DNP: lo que se puede deducir de manera simplificada usando las reglas derivadas, se puede deducir también sin ellas, añadiendo los pasos correspondientes a la deducción. Una vez que tenemos una correspondencia entre deducciones y reglas de deducción, podemos decir que en un sistema de deducción natural, lo que hace el papel de esquemas de

argumento válido son las reglas de deducción mismas: por eso se les llama "sistemas de reglas". (En un sistema axiomático, los esquemas de argumento válido son las leyes lógicas: por eso se les llama "sistemas de leyes".) Y la distinción típica de los sistemas formales entre "esquemas básicos" y "esquemas derivados" se convierte, en los sistemas de deducción natural, en la distinción entre reglas básicas y derivadas. (Es como si las reglas básicas fueran los axiomas, y las derivadas los teoremas.) Nosotros no vamos a usar reglas derivadas en nuestras deducciones, pero sí es interesante conocer algunas de ellas (además, puede servir como ejercicio el hacer la deducción que justifica a cada una de ellas).

Algunas reglas derivadas: modus tollens

contraposición

transitividad del condicional (A→B) (B→C) (A→C)

(A→B) ¬B ¬A

(A→B) (¬B→¬A)

silogismo disyuntivo (A∨B) ¬A B

dilema (A∨B) (A→C) (B→C) C

doble negación A ¬¬A

definición de → en ∧ ¬(A∧¬B) (A→B)

de Morgan (∧/∨) ¬(A∧B) (¬A∨¬B)

definición de ∧ en ∨ ¬(¬A∨¬B) (A∧B)

definición de ∧ en → ¬(A→¬B) (A∧B)

de Morgan (∨/∧) ¬(A∨B) (¬A∧¬B)

definición de ∨ en ∧ ¬(¬A∧¬B) (A∨B)

7.3. Sistemas axiomáticos: el sistema PM Del conjunto total de las leyes lógicas, los distintos sistemas formales eligen cuáles colocan como leyes básicas (son los axiomas) y formulan unas reglas de deducción que les permitan extraer como leyes derivadas el resto de las leyes del sistema. El que vamos a poner como ejemplo es el sistema de Whitehead y Russell en Principia Mathematica (1910-1913).

Lenguaje LPM (para lógica proposicional): • símbolos primitivos: • variables proposicionales: p, q, r, s… • conectivas: ∼, ∨, ⋅, ⊃, ≡ • (usaremos nuestros paréntesis como símbolos auxiliares) • reglas de formación (análogas a las de LP: queda como ejercicio formularlas)

Combinando los símbolos primitivos de manera adecuada, siguiendo las reglas de formación, se puede construir el conjunto de las fórmulas bien formadas de LPM. Por ejemplo, ((p∨q)⊃r) es una fbf de LPM.

Mecanismo deductivo del sistema PM (para lógica proposicional): • axiomas:

A1: ((p∨p)⊃p) A2: (q⊃(p∨q)) A3: ((p∨q)⊃(q∨p)) A4: (((p∨(q∨r))⊃(q∨(p∨r))) A5: ((q⊃r)⊃((p∨q)⊃(p∨r))) • reglas de deducción (nos dicen qué fórmula se deriva de otras):

R1 (regla de sustitución): Si A y B son fbfs de PM, el resultado de sustituir en A todas las apariciones de una misma variable proposicional por la fórmula B es una fbf de PM que se deriva de A. ejemplo:

(q⊃(p∨q)) ((q⊃r)⊃(p∨(q⊃r)))

sust q/(q⊃r)

R2 (regla de separación): (A⊃B), A B R3 (reglas de definición de conectivas): Si A es una fbf de PM en la que aparece una conectiva diádica δ, la fórmula equivalente a A que resulta de aplicar las siguientes definiciones para cada δ es una fórmula que se deriva de A. (A⋅B)=df∼(∼A∨∼B) (A⊃B)=df(∼A∨B) (A≡B)=df∼(∼(∼A∨B)∨∼(∼B∨A)) ejemplo:

((p∨p)⊃p) (∼(p∨p)∨p)

def ⊃

Con el mecanismo deductivo de PM podemos construir demostraciones de leyes lógicas. Son leyes lógicas de PM los cinco axiomas indicados antes, más todas las fórmulas que se deriven de una ley lógica previamente establecida, de acuerdo con las reglas de deducción de PM. Una demostración de la ley lógica A en el sistema PM será una sucesión ordenada de fórmulas de LPM cuya última fórmula sea A, y en la que todas las fórmulas de la lista estén justificadas por ser: o bien un axioma de PM, o bien una ley lógica previamente demostrada, o bien una fórmula que se derive de alguna(s) fórmula(s) anterior(es) mediante aplicación de una regla de deducción de PM. Ejemplos: Demostración de la ley lógica (p⊃(p∨p): 1. (q⊃(p∨q)) 2. (p⊃(p∨p)

justificación: es el axioma 2 justificación: se deriva de 1 por la regla de sustitución (sust q/p)

Demostración de la ley lógica ((p⊃(q⊃r))⊃(q⊃(p⊃r))):

1. ((p∨(q∨r))⊃(q∨(p∨r)))

justificación: es el axioma 4

2. ((∼p∨(q∨r))⊃(q∨(∼p∨r)))

justificación: se deriva de 1 por sust p/∼p

3. ((∼p∨(∼q∨r))⊃(∼q∨(∼p∨r))) 4. ((∼p∨(q⊃r))⊃(∼q∨(q⊃r)))

justificación: se deriva de 2 por sust q/∼q justificación: se deriva de 3 por def ⊃

5. ((p⊃(q⊃r))⊃(q⊃(p⊃r))) justificación: se deriva de 4 por def ⊃