El cálculo de proposiciones y de predicados

Tema 6: El cálculo de proposiciones y de predicados Introducción 1. El cálculo como parte de un sistema lógico 1.1. Qué son los sistemas lógicos 1.2. Consecuencia y derivabilidad 1.3. Los cálculos de deducción natural 2. Cálculo de proposiciones 2.1. Sintaxis y semántica 2.2. Traducibilidad 2.3. Un cálculo de deducción natural 3. Cálculo de predicados 3.1. Sintaxis y semántica 3.2. Traducibilidad 3.3. Un cálculo de deducción natural Conclusión Bibliografía y webgrafía Guión-resumen Cuestionario Introducción ¿Qué es la lógica y por qué nos puede interesar en filosofía? Desde un punto de vista muy abstracto, se dice que la lógica es la ciencia matemática que estudia relaciones de inferencia, de modo que sirve para determinar cuándo una pieza de información (la conclusión) se sigue de un cuerpo inicial de piezas de información (las premisas). Desde un punto de vista menos abstracto y más cercano a nuestras prácticas cotidianas, se dice también que la lógica es la ciencia que estudia los argumentos válidos, aquéllos donde la conclusión se sigue de las premisas. Bajo este punto de vista, nos interesa la lógica porque nos interesa, en filosofía y en la vida cotidiana, tanto producir como reconocer argumentos válidos. Vamos a exponer la lógica de proposiciones y la de predicados, subdisciplinas más elementales de esta ciencia, con especial mención a sus respectivos cálculos de deducción natural. El apartado 1 introduce el concepto de sistema lógico, en relación al cual se comprende mejor el concepto de cálculo. El apartado 2 es una exposición de la lógica de proposiciones. Y el 3 una exposición de la lógica de predicados. En ambos casos abordaremos (por este orden) la sintaxis, la semántica, la traducibilidad hacia y desde el español, así como un cálculo de deducción natural. Una forma rápida de abordar el tema sería estudiando sólo los apartados 1.1, 1.3, 2.3, 3.3. Escribimos “sii” para “si y solamente si”. Al decir “completud” nos referimos siempre a la completud de algún cálculo, mientras que en el tema 7 hablaremos unas veces de la completud de cálculos y otras veces de la completud de teorías. ENLACE: Este tema puede ser estudiado de forma independiente. Conviene, por otro lado, dominar este tema antes de abordar el 5 (historia de la lógica) y el 7 (sistemas formales).

1. El cálculo como parte de un sistema lógico 1.1. Qué son los sistemas lógicos La lógica, como se ha dicho, es una teoría matemática que estudia relaciones de inferencia. Interesa saber bajo qué circuntancias una pieza de información “se sigue” de otras. Cuándo podemos decir p.ej. que cierto conjunto de afirmaciones acerca de la reputación de una persona sustentan una nueva afirmación acerca de su comportamiento probable en el futuro. O cuándo podemos decir que ciertas afirmaciones sobre las propiedades de un metal implican una nueva afirmación relativa al modo en que ha interaccionado con un campo magnético. Lo que interesa a la lógica, por supuesto, no son ni los hábitos de conducta ni la composición de los metales, sino el modo en que ciertas afirmaciones se siguen de otras en virtud de su estructura abstracta, esto es, con independencia de cuál sea el tema sobre el que se está hablando. Discutir la verdad de los diferentes cuerpos de afirmaciones es tarea de sus respectivas ciencias, cada una de ellas ocupada con un campo de estudio. Ahora bien, estudiar las relaciones de inferencia entre afirmaciones cualesquiera es tarea de la lógica, que en este sentido preciso es una ciencia instrumental para todas las demás ciencias. ¿Cómo se ocupa la lógica de las relaciones de inferencia? Lo que observamos es que en lógica se construyen, manejan y analizan diferentes sistemas lógicos. Un sistema lógico es una construcción matemática que consta de tres elementos: un lenguaje artificial o conjunto de cadenas de símbolos, una semántica que atribuye significado al lenguaje en la medida en que lo relaciona con estructuras matemáticas, y un cálculo que sirve para pasar de unas expresiones del lenguaje a otras. (Los sistemas formales del tema 7 son construcciones que constan solamente de lenguaje y cálculo.) A veces se utilizan los sistemas lógicos como herramientas: con ellos se puede representar un argumento en un lenguaje artificial y comprobar allí si el argumento es válido. Otras veces se toman los sistemas lógicos como objeto de estudio. En cualquier caso, siempre están presentes cuando se está haciendo lógica. Mediante un sistema lógico se pretende codificar un determinado concepto de inferencia, luego diferentes sistemas lógicos codifican diferentes relaciones de inferencia. ¿Qué es entonces una inferencia? Toda inferencia puede verse en términos dinámicos (inferencia como proceso) o estáticos (inferencia como resultado de un proceso). Dinámicamente, una inferencia es un proceso por el cual se parte de unas premisas y se llega a una conclusión; inferre en latín significa precisamente “llevar hacia”. Tanto la naturaleza de premisas y conclusiones como la naturaleza del proceso mismo pueden ser muy diversos. En psicología, premisas y conclusiones pueden ser creencias, y el proceso que conduce de unas a otras puede ser un proceso mental superior. En informática, sin embargo, se entenderá que el proceso de inferencia es un cómputo (secuencia finita de transformaciones de cadenas de símbolos) que parte de las premisas como inputs y llega a la conclusión como output. Este sentido dinámico de inferencia es el más primitivo, aunque también el más difícil de estudiar. El enfoque estático entiende cualquier inferencia como resultado de un proceso. Es el enfoque adoptado por Aristóteles y por la mayoría de los lógicos del siglo XX. Es también el enfoque adoptado por la lógica simbólica, y por tanto el enfoque seguido en este tema. Lo que se toma esta vez como objeto de estudio suelen ser ciertos fragmentos lingüísticos, llamados “argumentos”, en los cuales hay una afirmación (generalmente aparece al final) que parece estar justificada de algún modo por todo aquello que aparece en el resto del fragmento. Se trata de la “conclusión”. Si el argumento está bien

estructurado, pueden distinguirse también algunas afirmaciones cuya presencia garantiza la conclusión. Se trata de las “premisas”. PREGUNTA-CLAVE: Objeto de la lógica. Qué es un sistema lógico. ¿Por qué decimos que la inferencia admite un enfoque estático y uno dinámico?

1.2. Consecuencia y derivabilidad Dado cualquier sistema lógico, podemos definir desde su semántica (sin tener en cuenta el cálculo) una relación de consecuencia; también podemos definir desde su cálculo (sin tener en cuenta la semántica) una relación de derivabilidad. Estas dos relaciones se definen sobre el lenguaje del sistema, determinando cada una a su modo cuándo una fórmula del lenguaje (la conclusión) “se sigue” de un conjunto de fórmulas (las premisas). Consecuencia y derivabilidad son, pues, dos intentos complementarios de atrapar matemáticamente el concepto estático de inferencia. Consecuencia. Para definir semánticamente la relación de consecuencia, se delimita cierta clase de estructuras matemáticas externas a L y se establece alguna manera en que las fórmulas de L pueden “ser verdaderas” respecto de tales estructuras. Una vez hecho esto, la semántica nos proporciona ya un concepto de inferencia. Definición: Decimos (en relación al lenguaje y a la semántica de un sistema lógico) que C es consecuencia de {A1, ..., An} sii para toda estructura, si todas las fórmulas de {A1, ..., An} son verdaderas con respecto a ella, también lo es C. Escribimos entonces {A1, ..., An}╞ C. Así pues, una fórmula es consecuencia de un conjunto de fórmulas sii la verdad de éstas entraña la verdad de aquélla. O también, es incompatible la verdad de éstas con la falsedad de aquélla. Ejemplo: “hay en Huelva un rinoceronte albino”╞ “hay en Huelva un animal albino de más de 50 kg”. No hace falta ir a Huelva para saber que la conclusión se sigue de la premisa, lo que refuerza la idea de que en lógica interesa solamente la relación entre fórmulas en virtud de su estructura formal, con independencia de aquello sobre lo cual están hablando. En general, si quisiéramos probar que C es consecuencia de {A1, ..., An} a partir de lo que indica expresamente la definición, deberíamos examinar una a una las infinitas estructuras posibles para constatar que siempre que una estructura hace verdaderas a las premisas hace verdadera también a la conclusión. Más fácil es probar que C no es consecuencia de {A1, ..., An}, pues en este caso basta exhibir una estructura que hace verdaderas a las premisas y falsa a la conclusión. Esa estructura es un “contraejemplo”. Derivabilidad. Un cálculo lógico es un conjunto de reglas con las cuales podemos construir derivaciones. Dado un conjunto inicial {A1, ..., An} de fórmulas que entendemos como premisas, una derivación es una secuencia finita de fórmulas donde cada elemento o bien es una premisa (las premisas suelen colocarse al comienzo de la secuencia) o bien se ha obtenido mediante aplicación rigurosa de alguna de las reglas del cálculo sobre fórmulas previas. Definición: Decimos (en relación al lenguaje y al cálculo de un sistema lógico) que C es derivable a partir de {A1, ..., An} sii existe una derivación de C a partir de {A1, ..., An}. Escribimos entonces {A1, ..., An}├ C.

Intuitivamente, una derivación de C a partir de {A1, ..., An} es una secuencia de fórmulas que empieza con {A1, ..., An}, acaba con C y contiene entre aquéllas y ésta una serie de fórmulas que podemos ver como pasos intermedios que han servido para llegar hasta C a partir de {A1, ..., An}. No tiene por qué ser fácil producir una derivación. Sin embargo, es una tarea rutinaria determinar si una secuencia de fórmulas es o no es una derivación. Para verlo mejor pensemos en el ajedrez. Los movimientos de una persona jugando al ajedrez serían los pasos de una derivación. Las piezas de ajedrez serían las fórmulas del lenguaje; las reglas del ajedrez serían las reglas del cálculo. No es fácil jugar bien, como no es fácil llevar a cabo una derivación, pero cualquiera puede comprobar si un jugador está siguiendo las reglas del juego. Por último, aunque probar que C es derivable a partir de {A1, ..., An} sólo exige mostrar una derivación, probar que C no es derivable a partir de {A1, ..., An} exigiría examinar una a una las infinitas derivaciones posibles con objeto de constatar que ninguna de ellas parte de {A1, ..., An} y acaba en C. Consecuencia y derivabilidad. Consecuencia se define en términos semánticos mediante la noción de interpretación; derivabilidad en términos sintácticos mediante la noción de derivación. Esto es lo que podemos decir sobre ellas por separado. ¿Pero cómo se relacionan entre sí? La respuesta más inmediata pasa por investigar si en un sistema lógico determinado se cumplen estos dos teoremas. Teorema de Corrección: Si {A1, ..., An}├ C, entonces {A1, ..., An}╞ C Teorema de Completud: Si {A1, ..., An}╞ C, entonces {A1, ..., An}├ C Dado un sistema lógico, su cálculo es “correcto” sii se cumple el teorema de corrección; es “completo” sii se cumple el teorema de completud. Es un hecho bien conocido que existen cálculos correctos y completos tanto para la lógica de proposiciones como para la lógica de predicados; naturalmente, los cálculos de los apartados 2.3 y 3.3 son correctos y completos. A pesar de la simetría entre corrección y completud, esta última es mucho más interesante –y más difícil de establecer– que la corrección. Pensemos que la correción de un cálculo solamente nos dice de él que está “libre de errores” en el sentido de que con él nunca probaremos que una fórmula es derivable de un conjunto de premisas a menos que sea consecuencia de las mismas. Esto, evidentemente, es lo mínimo que se le puede pedir a un cálculo. El siguiente paso es exigirle que siempre que una fórmula sea consecuencia de unas premisas sea posible derivar esa fórmula a partir de esas premisas. Esto es más interesante: nos dice que para demostrar la validez de un argumento todo lo que nos hace falta es una aplicación inteligente de las reglas del cálculo. ¿Pero por qué molestarse en definir y estudiar dos nociones tan diferentes como son consecuencia y derivabilidad? La lógica es el estudio de la inferencia, por lo que cualquiera de estas dos nociones debería, en principio, satisfacernos. Nos ahorraría el trabajo de tener que pensar en la otra; más aún, nos ahorraría el trabajo de tener que demostrar los teoremas de corrección y completud. Pues bien, la respuesta a esta última pregunta se desprende de las observaciones que ya hemos hecho a las nociones de consecuencia, no-consecuencia. derivabilidad, no

derivabilidad. Las dos afirmaciones que siguen son meros corolarios de las definiciones vistas más arriba, pero tienen la enorme importancia de decirnos qué tipo de demostración debemos buscar en función de lo que tratemos de conseguir. 1. Para demostrar que C se sigue de {A1, ..., An} conviene usar la noción de derivabilidad, pues en ella se menciona la existencia de una sola derivación, mientras que en la noción de consecuencia se menciona la existencia de infinitas estructuras. 2. Para demostrar que C no se sigue de {A1, ..., An} conviene usar la noción de no-consecuencia, pues en ella se menciona la existencia de una sola estructura, mientras que en la noción de no-derivabilidad se menciona la existencia de infinitas derivaciones. PREGUNTA-CLAVE: Define consecuencia y derivabilidad. ¿Por qué la primera noción es semántica y la segunda sintáctica? Formula y comenta los teoremas de corrección y de completud. Explica por qué la definición de consecuencia es más útil para demostraciones de invalidez de argumentos que de validez de los mismos, mientras que con la definición de derivabilidad ocurre justo lo contrario.

1.3. Los cálculos de deducción natural Los cálculos de deducción natural, que son un tipo particular de cálculo, fueron propuestos por el lógico polaco Jan Łukasiewicz (1878-1956) en un seminario de la Universidad de Varsovia en 1926, de donde surgieron algunos artículos firmados por Stanisław Jaśkowski (1906-1965). Pero fue el matemático alemán Gerhard Gentzen (1909-1945) quien desarrolló suficientemente este tipo de cálculos. Lo hizo en su tesis doctoral Untersuchungen über das logische Schliessen, “Investigaciones sobre la inferencia lógica”, defendida en 1933 en la Universidad de Gotinga y publicada (en dos partes) en la revista Mathematische Zeitschrift en 1934 y 1935. Uno de los propósitos del autor era construir un cálculo lógico inspirado en el tipo de razonamiento que los matemáticos llevan a cabo en sus prácticas cotidianas. Se trataba de reaccionar ante el método axiomático de los tratados de lógica matemática de finales del XIX y comienzos del XX, en los cuales se utilizan unos cálculos que se alejan mucho de la manera natural de razonar, por lo cual resultan difíciles de utilizar. Más adelante, la monografía Natural Deduction (1965) del lógico sueco Dag Prawitz (1936-) mejoró y popularizó los cálculos de deducción natural de Gentzen. Un cálculo de deducción natural no contiene axiomas (afirmaciones que puedan tomarse como premisas en cualquier momento de cualquier derivación). El motivo es que en las demostraciones matemáticas no se usan axiomas, sino que se parte de un conjunto inicial de premisas que parecen relevantes, se parte asimismo de la conclusión a la que se quiere llegar, se deducen de premisas y conclusión tantas afirmaciones como es posible, y finalmente se combinan esas afirmaciones hasta construir los pasos intermedios de la demostración. Así es que Gentzen, en consonancia con esto, diseña un tipo de cálculo donde cada derivación parte de premisas particulares y avanza hasta la conclusión mediante la aplicación de reglas de eliminación e introducción de conectivas lógicas. Estas últimas son partículas que no significan nada si aparecen aisladas pero que sirven para construir afirmaciones complejas a partir de afirmaciones más simples (ejemplos: no, y, o, implica, si y sólo si, todo, alguno). Cada paso de la derivación, siguiendo a Gamut (1991: 128), puede ser visto como una respuesta a una pregunta. 1. ¿Qué fórmula podemos obtener aquí a partir de una fórmula previa cuya

conectiva principal es k? Con la regla Ek respondemos a esta pregunta. 2. ¿Qué fórmula cuya conectiva principal sea k podemos obtener aquí a partir de fórmulas previas? Con la regla Ik respondemos a esta pregunta. Además de en las premisas iniciales, una derivación en un cálculo de deducción natural puede apoyarse en fórmulas que adoptamos como premisas de manera temporal. Se trata de los supuestos. En cualquier momento de la derivación podemos asumir un supuesto y sacar de allí alguna conclusión, pero inmediatamente después debemos desechar (no volver a utilizar en la derivación) tanto el supuesto como todas las fórmulas que dependían de él. Si queremos construir una derivación de C a partir de {A1, A2}, en el caso más simple tendría este aspecto. 1. 2. 3. 4. 5. 6. 7. 8.

A1 A2 B1 B2 B3 B4 B5 C

Premisa Premisa Regla U en 2 Regla V en 3 Regla W en 1, 4 Regla X en 5 Regla Y en 6 Regla Z en 3, 7

En la columna del centro aparecen las fórmulas de la derivación. A la izquierda se numeran esas fórmulas. A la derecha hay indicaciones: se explica si la fórmula es una premisa o es resultado de aplicar alguna regla del cálculo a fórmulas anteriores, en cuyo caso se explicitan tales fórmulas. También pueden darse subderivaciones a partir de supuestos. Tendríamos entonces dos restricciones: (i) toda subderivación debe cerrarse, (ii) ninguna regla puede utilizar fórmulas de las subderivaciones que se hayan cerrado, excepto para obtener la fórmula que precisamente cierra la subderivación. 1. 2. 3. 4. 5. 6. 7. 8.

A1 A2 B1 B2 B3 B4 B5 C

Premisa Premisa Regla U en 2 Supuesto Regla V en 3, 4 Regla W 1, 5 Regla X en 4–6 Regla Y en 2, 7

Pueden incluso darse subderivaciones dentro de subderivaciones. 1. 2. 3. 4. 5. 6. 7. 8.

A1 A2 B1 B2 B3 B4 B5 C

Premisa Premisa Supuesto Supuesto Regla U en 2, 3 Regla V en 4–5 Regla W en 3, 6 Regla X en 3–7

Lo que no puede ocurrir es que se cierre una subderivación antes de que se hayan cerrado los supuestos abiertos que caen dentro de ella. El esquema de derivación siguiente sería inadmisible. 1. 2. 3. 4. 5. 6. 7. 8.

A1 A2 B1 B2 B3 B4 B5 C

Premisa Premisa Supuesto Supuesto Regla U en 2 Regla V en 3–5 Regla W en 4–6 Regla X en 7

Se ha cerrado la subderivación 3–5 dejando abierta la suposición del paso 4. Esto es inadmisible, pues permite en 6 dar por sentado algo que se apoya en una suposición hipotética formulada en 4. PREGUNTA-CLAVE: Relaciona los conceptos de argumento válido y derivación. Describe cómo son las reglas en un cálculo de deducción natural. Describe cómo es una derivación en un cálculo de deducción natural. ¿Qué diferencia hay entre premisas y supuestos?

2. Cálculo de proposiciones Un cálculo de proposiciones es un cálculo lógico que opera con fórmulas del lenguaje proposicional. Este lenguaje considera las afirmaciones declarativas simples, del tipo “es de día”, “hay nubes”, “se ve el sol”, unidades básicas de significado. Las formaliza mediante símbolos como p, q, r. También construye (con tales símbolos y otros nuevos) expresiones como (p∧¬q)→r, que formalizan afirmaciones declarativas complejas, en este caso “si es de día y no hay nubes entonces se ve el sol”. Pero lo que realmente nos interesa son los argumentos. Ejemplo: “Si vinieses a cenar y fueras educado, traerías vino; pero no traes vino; luego no vienes a cenar o eres poco educado.” Lo que buscamos en lógica proposicional son dos cosas: cómo formalizar ese tipo de argumentos, cuyos elementos son afirmaciones declarativas simples, y cómo demostrar matemáticamente si son válidos o no. 2.1. Sintaxis y semántica Construimos lenguajes formales (o artificiales) porque los naturales, como el español o el alemán, están llenos de imperfecciones desde el punto de vista de su capacidad para transmitir información de manera unívoca. Se prefiere, en lógica simbólica, estudiar el fenómeno de la inferencia en lenguajes formales, donde la información se codifica lingüísticamente de la manera más precisa y unívoca posible. En particular, el lenguaje de la lógica proposicional debe su nombre a que parte de las proposiciones como elementos más simples. Una proposición es lo expresado por una oración declarativa, que informa de que tales o cuales cosas son de esta o de aquella manera. También se dice a veces, aunque resulta más problemático, que una oración es lo expresado por una creencia. Por tanto, una proposición es un objeto abstracto susceptible de ser verdadero o falso con respecto de alguna interpretación.

Por abuso del lenguaje, a veces llamamos “proposiciones” a las expresiones lingüísticas que expresan proposiciones. Ejemplos de tales expresiones: (i) (ii) (iii) (iv) (v)

Está nevando a pesar de que estamos en mayo. La Rusia de Putin es un estado democrático. En la universidad hay profesores y becarios que hablan inglés. La oración (iv) es falsa. Todos los números primos mayores que 2 son impares.

Muchas veces, como en (i), no es posible establecer la verdad de una expresión mientras ignoremos el contexto en que ha sido proferida o escrita. También es frecuente la ambigüedad. En (ii) se aprecia ambigüedad semántica con el término “democrático”, mientras que en (iii) hay ambigüedad sintáctica con el alcance del sintagma “que hablan inglés”. El problema en (iv) es que la expresión, a pesar de ser significativa, no puede ser verdadera ni falsa debido al fenómeno de la autorreferencia. Sólo a partir de expresiones como (v) podemos determinar la verdad de la proposición sin preocuparnos por el contexto, la ambigüedad o los problemas de autorreferencia. Sintaxis. Llamamos L0 al lenguaje de la lógica proposicional. Por ser un lenguaje formal, desatendemos en un primer momento su capacidad portar significados y nos centramos en la mera descripción de L0 como conjunto de cadenas de símbolos. Necesitamos para su descripción tanto un alfabeto como una gramática. Aquél es un conjunto de símbolos que se pueden combinar para formar las expresiones del lenguaje; ésta es un conjunto de reglas que sirven para generar las fórmulas de L0. El alfabeto de L0 está compuesto por un conjunto infinito enumerable de variables proposicionales (p1, p2, p3 ...), un conjunto de conectivas con las que enlazar expresiones (¬, ∧, ∨, →, ↔), el paréntesis izquierdo y el paréntesis derecho. Si en una determinada aplicación hay pocas variables, escribimos p, q, r... en vez de p1, p2, p3 ... Las conectivas se llaman negación (¬), conjunción (∧), disyunción (∨), condicional o implicación (→), bicondicional o coimplicación (↔). En cuanto a la gramática, las cadenas de símbolos de L0 que son fórmulas son aquellas y sólo aquellas generadas por las siguentes reglas: 1. Las variables p1, p2, p3 ... son fórmulas (llamadas “átomos”) 2. Si A es una fórmula, también lo es ¬A. 3. Si A y B son fórmulas, también lo son (A∧B), (A∨B), (A→B), (A↔B). Usamos A, B, C ... como variables metalingüísticas: en su lugar pueden ponerse fórmulas cualesquiera. Las generadas por 1 son “atómicas”, el resto son “complejas”. La conectiva principal de una fórmula es la última que se usó en su construcción gramatical. Dicha conectiva da nombre a la fórmula: una fórmula de la forma ¬A es una negación, otra de la forma (A∧B) una conjunción, etc. Expresión formal

Lectura intuitiva

Forma lógica

¬A

no es cierto que A

Negación

(A∧B)

AyB

Conjunción

(A∨B)

AóB

Disyunción

(A→B)

si A, entonces B

Condicional

Expresión formal (A↔B)

Lectura intuitiva

Forma lógica

A si y solamente si B Bicondicional

Las subfórmulas de una fórmula son todas las subcadenas de símbolos que asimismo son fórmulas. Ejemplo: las subfórmulas de ((p∨q)→(¬p→q)) serían ((p∨q)→ (¬p→q)), (p∨q), (¬p→q), p, q, ¬p. En las fórmulas complejas podemos economizar paréntesis. Se eliminan los paréntesis externos, conque escribimos ¬p→q en vez de (¬p→q). Disyunciones y conjunciones reiteradas solamente necesitan paréntesis externos, de modo que ((p∨q)∨ ¬q)→¬p es lo mismo que (p∨q∨¬q)→¬p. Conjunción y disyunción ligan más fuerte que implicación y coimplicación, luego p∨q→p es lo mismo que (p∨q)→p. Semántica. La semántica de la lógica proposicional viene regida por dos principios. Bivalencia: los átomos pueden recibir uno, y sólo uno, de entre dos valores semánticos, lo verdadero (1) y lo falso (0). Composicionalidad: si en una fórmula compleja A se conocen los valores de verdad de todos sus átomos, entonces puede calcularse mecánicamente el valor de verdad de A. El principio de bivalencia se plasma cada vez que definimos una función v, llamada “modelo” o “interpretación”, que asigna valores de verdad (1 ó 0) a un conjunto P de átomos. Por ejemplo, si P = {p, q}, hay cuatro interpretaciones posibles, es decir, cuatro maneras de distribuir valores de verdad a los elementos de P. En general, para n atómos hay 2n interpretaciones distintas.

interpretación p q v1

1 1

v2

1 0

v3

0 1

v4

0 0

La tercera fila se leería diciendo que v3 hace falsa a p y verdadera a q. La columna bajo q se leería diciendo que q es verdadera sólo bajo v1 y v3. Podríamos también escribir v1(p)=1, v1(q)=1, v2(p)=1, v2(q)=0, etc. El principio de composicionalidad requiere un mecanismo tal que, dados un conjunto de átomos P y una interpretación v sobre P, sea posible extender v para interpretar cualquier fórmula compleja cuyos átomos estén tomados de P. Supongamos de nuevo P = {p, q}. Y supongamos que queremos extender la interpretación v3 a las fórmulas complejas ¬p y ¬q. Como queremos que la negación de una verdad sea una falsedad, y que la negación de una falsedad sea una verdad, queremos llegar a v3(¬p)=1 y v3(¬q)=0. Para ello basta aplicar la regla:

A ¬A 1

0

0

1

Análogamente, para el resto de conectivas tenemos que:

A B A∧B

A∨B

A→B

A↔B

1 1

1

1

1

1

1 0

0

1

0

0

0 1

0

1

1

0

0 0

0

0

1

1

Mediante tablas podemos calcular paso a paso cómo los valores de verdad de los átomos de una fórmula A determinan el valor de verdad de A. Basta escribir bajo las columnas de la izquierda todas las interpretaciones posibles de los átomos de A, escribir sucesivamente todas las subfórmulas que componen A, calculando en las columnas todas las combinaciones de valores de verdad, y llegar finalmente hasta A. Veamos cómo se construye la tabla de verdad de ¬(p∧q)→¬q. p q p∧q ¬(p∧q) ¬q (p∧q)→¬q 1 1

1

0

0

1

1 0

0

1

1

1

0 1

0

1

0

0

0 0

0

1

1

1

Dividimos las fórmulas de la lógica proposicional en tres grupos: 1. Tautologías. Fórmulas “siempre verdaderas”, es decir, verdaderas bajo toda interpretación posible. Ejemplo: p∨¬p. Sólo hay 1s debajo de ellas en su tabla de verdad. 2. Contradicciones. Fórmulas “siempre falsas”, es decir, falsas bajo toda interpretación posible. Ejemplo: p∧¬p. Sólo hay 0s debajo de ellas en su tabla de verdad. 3. Contingencias. Fórmulas “a veces verdaderas y a veces falsas”, es decir, verdaderas bajo alguna interpretación y falsas bajo alguna otra. Ejemplo: p∧p. Hay al menos un 1 y al menos un 0 debajo de ellas en su tabla de verdad. Existen infinitas tautologías, que además pueden clasificarse de muy distintas maneras. Veamos algunas tautologías que contienen una sola conectiva, el condicional. T1. T2. T3. T4.

A→A A→(B→A) [(A→B)→C]→(B→C) (A→B)→[(C→A)→(C→B)]

T5. T6. T7. T8. T9. T10. T11. T12. T13. T14.

(A→B)→[(B→C)→(A→C)] (A→B)→[(A→(B→C))→(A→C)] [(A→B)→(A→C)]→(B→(A→C)) [(A→B)→(A→C)]→(A→(B→C)) (A→(B→C))→(B→(A→C)) (A→(B→C))→((A→B)→(A→C)) (A→(A→B))→(A→B) A→((A→B)→B) ((A→A)→B)→B ((A→B)→A)→A

Añadamos ahora la negación. Obtenemos tautologías como estas: T15. Τ16. T17. T18. T19. Τ20.

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

Hay tautologías cuya conectiva principal es el bicondicional. Son importantes porque nos dicen que lo que hay a la izquierda del bicondicional es equivalente a lo que hay a su derecha. T21. T22. T23. T24. T25. T26. T27. T28. T29. T30. Τ31. Τ32. T33. T34.

A∨(B∨C)↔(A∨B)∨C A∧(B∧C)↔(A∧B)∧C A∨B↔B∨A A∧B↔B∧A A↔A∨A A↔A∧A A∨(A∧B)↔A A∧(A∨B)↔A A∨(B∧C)↔(A∨B)∧(A∨C) A∧(B∨C)↔(A∧B)∨(A∧C) ¬(A∨B)↔¬A∧¬B ¬(A∧B)↔¬A∨¬B A→B↔¬A∨B (A→B)↔A∧¬B

Consecuencia. La definición de consecuencia que ya vimos antes se puede hacer un poco más precisa como sigue, donde se dan por supuestos el lenguaje proposicional L0 y su semántica estándar. Definición: Decimos que C es consecuencia de {A1, ..., An} sii para toda interpretación v, si v(A1)=1, ... , v(An)=1, entonces v(C)=1. Escribimos en ese caso {A1, ..., An}╞ C. Otra manera de decirlo: C es consecuencia de {A1, ..., An} sii no existe ninguna v

tal que v(A1)=1, ... , v(An)=1, pero v(C)=0. Desde esta formulación es evidente que una fórmula es tautología sii es consecuencia del conjunto vacío de premisas. Mediante tablas de verdad podemos comprobar si C es consecuencia de A1, ..., An. ¿Cómo? Se construye la misma tabla de verdad para premisas y conclusión; en el caso y sólo en el caso de que no exista ninguna interpretación que haga verdaderas a todas las premisas y falsa a la conclusión tendremos que ésta es consecuencia de aquéllas. PREGUNTA-CLAVE: ¿Qué es una proposición? Explica la diferencia entre tautología, contradicción y contingencia. ¿Qué relación se da entre la noción de consecuencia y la de tautología?

2.2. Traducibilidad El principal motivo para llevar a cabo traducciones desde un lenguaje natural hasta uno artificial es que entendemos los lenguajes formales como modelos simplificados de fragmentos del lenguaje natural, de suerte que para estudiar un argumento primero se traduce desde el lenguaje natural en que está formulado hasta algún lenguaje formal, y se determina en este último si el argumento original era válido o inválido. También es común traducir fragmentos de un lenguaje natural a uno formal para comprender mejor la manera en que los lenguajes naturales codifican información. Al traducir una frase de un lenguaje natural a una fórmula de algún lenguaje artificial podemos, si no descubrir “el” significado de la frase original, sí al menos poner algo de orden entre los distintos significados a que puede dar lugar. Los distintos manuales ofrecen listas de traducciones tanto español-L0 como L0español, así como indicaciones más o menos generales sobre cómo llevar a cabo nuevas traducciones. Es una tarea para la cual existen muchas indicaciones pero muy pocas reglas seguras. Veamos algunos ejemplos de traducción inversa: 1. Para ¬A tenemos: no A, es falso que A, no es el caso que A, etc. 2. Para A∧B tenemos: A y B, A además de B, A aparte de B, A y sin embargo B, A pero B, A aunque B, A no obstante B, A a pesar de B, etc. 3. Para A∨B tenemos: A o B, o bien A o bien B, ya A ya B, ora A ora B, A a menos que B, A excepto si B, etc. 4. Para A→B tenemos: si A entonces B, A implica B, de A se sigue B, A entraña B, A sólo si B, basta A para B, A es condición suficiente de B, B es condición necesaria de A, hace falta B para A, B si A, etc. 5. Para A↔B tenemos: A si y solo si B, A siempre y cuando B, A es condición necesaria y suficiente para B, A equivale a B, A es lo mismo que B, etc. Los lenguajes de la lógica proposicional y de predicados no fueron diseñados para analizar cualquier tipo de discurso expresado lenguaje natural. En realidad, fueron inventados para analizar aquellos discursos de las lenguas naturales en los cuales se razona sobre objetos matemáticos, que son inmutables y susceptibles en principio de estar bien definidos. Dicho esto, podemos suponer que una extensión de los recursos expresivos de los lenguajes lógicos podría llegar a reflejar adecuadamente la estructura de las lenguas naturales. Desde esta suposición llevamos tan lejos como podemos los recursos expresivos del lenguaje lógico. Para comprobar si hemos traducido bien una oración del español a una fórmula proposicional A, lo que hacemos es comparar las condiciones de verdad de A con las diferentes maneras en que la oración en español se relaciona con distintas situaciones posibles que harían verdaderas o falsas las distintas partes de la oración. Esto implica,

por supuesto, un cierto nivel de dominio y reflexión sobre las peculiaridades del propio lenguaje natural. De este modo se pueden esclarecer p.ej. las traducciones inversas propuestas más arriba para “A a menos que B” y “A solamente si B”. Sin embargo, la traducción español-L0 es más un arte que una ciencia, por lo que debe ser aprendida mediante ejemplos. Los que siguen están inspirados en ejercicios de Manzano y Huertas (2006). Vocabulario: p significa que Paco es culpable, q que Quique es culpable, r que Ramón es culpable. 1. Paco es culpable y Ramón inocente. p∧¬r 2. Quique es inocente si no lo es Ramón. ¬¬r→¬q 3. Exactamente dos de los hermanos son culpables. [(p∧q)∨(p∧r)∨(q∧r)]∧¬(p∧q∧r) 4. Al menos dos de los hermanos son culpables. (p∧q)∨(p∧r)∨(q∧r) 5. Como mucho hay dos hermanos que sean culpables. ¬(p∧q∧r) 6. Alguno de los tres hermanos es culpable, pero no los tres a la vez. (p∨q∨r)∧¬(p∧q∧r) 7. Si Ramón fuera culpable, tendría exactamente un cómplice. r→(p∧¬q)∨(¬p∧q) 8. Quique y Ramón son ambos inocentes o ambos culpables. (¬q∧¬r)∨(q∧r) En cierto modo hemos tenido en cuenta el contexto. No podíamos haber formalizado muchos de los ejemplos si no hubiéramos sabido que eran tres los posibles candidatos a ser considerados culpables. Observamos también que la formalización de la oración 3 es la conjunción de las formalizaciones de 4 y de 5. PREGUNTA-CLAVE: Formaliza estas afirmaciones: “Nadie que no sea Ramón es inocente”, “Exactamente uno de los hermanos es culpable”, “Ramón es inocente sólo si Quique es culpable”.

2.3. Un cálculo de deducción natural Llamamos D0 al cálculo de deducción natural que presentamos para la lógica de proposiciones. La mayoría de manuales exponen este mismo cálculo o alguno muy similar. Sus reglas se dividen en dos grupos: cinco de eliminación y cinco de introducción. Para toda conectiva k ∈ {¬, ∧, ∨, →, ↔}, la regla Ek genera una fórmula nueva a partir de una fórmula cuya conectiva principal es k, mientras que Ik genera una fórmula cuya conectiva principal es k. Las reglas de eliminación son E¬, E∧, E∨, E→, E↔. Las reglas de introdución son I¬, I∧, I∨, I→, I↔. Cada regla viene formulada con un esquema que consta de dos partes. Lo que está

por encima de la raya horizontal es todo aquello que se requiere para la aplicación de la regla. La fórmula debajo de la raya es el resultado de aplicar la regla. Los puntos suspensivos indican que puede haber una o más fórmulas ocupando ese espacio. Los corchetes sirven para señalar subderivaciones dentro de la derivación principal, siendo la primera fórmula de cada subderivación un supuesto.

Eliminación Negación

Conjunción

[ ] A ⋮ B∧¬B ¬A

¬¬ A A

A∧B A

A∧B B

Disyunción

A∨B ⋮ A ⋮ C B ⋮ C C

Condicional

A ⋮ AB B

Bicondicional

[] []

A↔B AB

Introducción

A↔B B A

A ⋮ B A∧B

B ⋮ A B∧ A

A A∨B

A B∨ A

[]

A ⋮ B AB A B ⋮ B A A↔B

B A ⋮ B A B↔A

Repetimos (adaptándola al caso de D0) la definición de derivabilidad que ya teníamos. Se dan por supuestos el lenguaje L0 y las reglas de D0. Definición: Decimos que C es derivable a partir de {A1, ..., An} sii existe una derivación de C a partir de {A1, ..., An} conforme el cálculo D0. Escribimos entonces {A1, ..., An}├D0 C. Dicha derivación es cualquier secuencia de fórmulas acabada en C que podamos construir a partir tanto de las premisas A1, ..., An como de una aplicación correcta de las reglas del cálculo. Si uno prefiere no admitir la noción de “construir” por no ser lo bastante rigurosa, puede definir la derivación de C a partir de {A1, ..., An} conforme al

cálculo D0 como una secuencia de fórmulas tal que C es la última, A1, ..., An son todas las que pueden aparecer como premisas, cada fórmula se obtiene mediante aplicación de las reglas de D0 sobre fórmulas previas, y todos los supuestos están cancelados. Demostrar una fórmula a partir del conjunto vacío de premisas es posible porque varias reglas nos permiten introducir supuestos adicionales. Cuando demostramos una fórmula sin servirnos de premisas decimos que es un “teorema” del cálculo. Por corrección y completud de D0 toda tautología es teorema, y viceversa. Ofrecemos algunos ejemplos de demostración en D0. A partir del segundo ejemplo se utilizan supuestos, que han de ser cancelados antes de obtener la conclusión. Cuando la regla no necesita cancelar supuestos, escribimos los pasos previos a los que se aplica dicha regla separados por coma. Cuando la regla sí que cancela supuestos previos, escribimos los pasos cancelados separados por un guión. Ejemplo: Demostrar A∧B ├D0 A∨B 1. 2. 3.

A∧B A A∨B

Premisa E∧ en 1 I∨ en 2

Ejemplo: Demostrar ¬A∧B, ¬B ├D0 C 1. 2. 3. 4. 5. 6.

¬A∧B ¬B B ¬C B∧¬B C

Premisa Premisa E∧ en 1 Supuesto I∧ en 2, 3 I¬ en 4–5

En el paso 4 hemos introducido un supuesto. Podemos introducir tantos como queramos con tal de que sean cancelados antes de llegar a la conclusión. Ejemplo: Demostrar A→B, ¬A→¬B ├D0 A↔B 1. 2. 3. 4. 5. 6. 7. 8. 9. 10.

A→B ¬A→¬B B ¬A ¬B B∧¬B ¬¬A A B→A A↔B

Premisa Premisa Supuesto Supuesto E→ en 2, 4 I∧ en 3, 5 I¬ en 4–6 E¬ en 7 I→ en 3–8 I↔ en 1, 9

Por último, consideramos derivaciones donde no tenemos ninguna premisa inicial.

Cualquier fórmula que necesitemos ha de ser introducida como supuesto. Y la consecuencia de la derivación es un teorema del cálculo. Ejemplo: Demostrar ├D0 A→(B→A) 1. 2. 3. 4. 5. 6. 7. 8.

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

Supuesto Supuesto Supuesto I∧ en 1, 3 I¬ en 3–4 E¬ en 5 I→ en 2-6 I→ en 1–7

Ejemplo: Demostrar ├D0 A∨¬A 1. 2. 3. 4. 5. 6. 7. 8. 9.

¬(A∨¬A) A A∨¬A (A∨¬A)∧¬(A∨¬A) ¬A A∨¬A (A∨¬A)∧¬(A∨¬A) ¬¬(A∨¬A) A∨¬A

Supuesto Supuesto I∨ en 2 I∧ en 1, 3 I¬ en 2–4 I∨ en 5 I∧ en 1, 6 I¬ en 1–7 E¬ en 8

PREGUNTA-CLAVE: Comenta una a una todas las reglas del cálculo de deducción natural D0, poniendo ejemplos inspirados en razonamientos de la vida cotidiana. Trata después de demostrar que son teoremas algunas de las verdades lógicas que aparecen en el apartado 2.1.

3. Cálculo de predicados Hay argumentos válidos para cuyo análisis no es posible emplear la lógica de proposiciones. Ejemplo: “No existen bancos budistas, pero sí que hay algunas fundaciones budistas, de modo que alguna fundación no es un banco.” Tenemos tres afirmaciones distintas que no se dejan descomponer en otras más sencillas: no existen bancos budistas (p), hay algunas fundaciones budistas (q), alguna fundación no es un banco (r). Es evidente que no podemos demostrar que r sea consecuencia de {p, q}. Podría objetarse que la primera y quizás la tercera proposición anteriores pueden interpretarse como negaciones, pero incluso en ese caso comprobamos que un argumento construido a partir de afirmaciones y/o negaciones de p, q, r, donde una se sigue de las demás, sigue siendo indemostrable en lógica proposicional. La principal limitación de L0 es su incapacidad para penetrar en la estructura interna de las proposiciones. No es satisfactorio formalizar “Alguna fundación no es un banco” y “Lo que está prohibido a las fundaciones está permitido a los bancos” mediante dos letras proposicionales distintas, pues dejamos fuera aquello compartido

por esas dos proposiciones (el concepto de fundación y el concepto de banco), así como elementos lógicos que antes no tuvimos en cuenta. 3.1. Sintaxis y semántica Vamos a construir un lenguaje artificial que nos permita hablar sobre los individuos de un determinado universo de discurso. Y hablar sobre ellos supone ser capaces de atribuirles propiedades y establecer qué relaciones guardan unos con otros. En otras palabras, queremos ser capaces de hacer dos cosas: (i) identificar objetos, (ii) caracterizar esos mismos objetos mediante propiedades y relaciones. A nivel lingüístico, esto significa que en lógica de predicados distinguiremos entre términos y fórmulas. Los términos, que no existían en lógica proposicional, sirven para denotar individuos concretos dentro de un universo de dicurso. Las fórmulas, que sí estaban presentes en lógica proposicional, sirven para hacer afirmaciones, aunque esta vez las afirmaciones lo serán con respecto a un universo de discurso que se hace explícito. Un término denota (o no) a un individuo del universo, mientras que una fórmula es verdadera (o falsa) con respecto a ese mismo universo. Sintaxis. Como sucedía L0, también L1 es un lenguaje formal para cuya descripción se necesitan un alfabeto y una gramática. El alfabeto está compuesto por: 1. 2. 3. 4. 5. 6. 7.

Un conjunto infinito enumerable de variables: x1, x2, x3 ... El conjunto de conectivas de la lógica proposicional: ¬, ∧, ∨, →, ↔ Los cuantificadores: ∀, ∃ El símbolo de igualdad: = Paréntesis izquierdo y paréntesis derecho. Un conjunto infinito enumerable de constantes: a1, a2, a3 ... Un conjunto infinito enumerable de predicados: P1, Q2, R3 ...

Si hay pocas variables, escribimos x, y, z ... en lugar de x1, x2, x3 ... Los nombres de los cuantificadores son universal (∀) y existencial (∃). Si hay pocas constantes escribimos a, b, c ... Si hay pocos predicados escribimos P, Q, R ... Si queremos expresar que el individuo a cumple la propiedad P, escribimos Pa. Si queremos expresar que a guarda con b la relación Q, escribimos Qab. Tomando a como nombre de Antonio, b como nombre de Beatriz, P como la propiedad de ser perezoso y Q como la relación de querer, tenemos que Pa ∧ Qab representa “Antonio es un perezoso y Antonio quiere a Beatriz”, es decir, “Antonio es un perezoso y quiere a Beatriz”. Las variables son nombres propios indeterminados. Para determinar su alcance anteponemos los cuantificadores ∀x (para todo x) y ∃x (para algún x) ante la fórmula en que aparece esa x. Por ejemplo, ∃xPx expresa que hay algún perezoso, ∀xQxb que todo el mundo quiere a Beatriz, ∀xQbx que Beatriz quiere a todo el mundo, ∀x(Qbx→¬Px) que aquellos a quienes quiere Beatriz no son perezosos, etc. Las cadenas de símbolos de L1 que son términos son aquellas y sólo aquellas combinaciones de símbolos del afabeto que cumplen estas reglas: 1. Las variables x1, x2, x3 ... son términos. 2. Las constantes a1, a2, a3 ... son términos. Que un predicado sea n-ario significa que pueden escribirse detrás de él exactamente n términos. Las cadenas de símbolos de L1 que son fórmulas son aquellas

y sólo aquellas combinaciones de símbolos del afabeto que cumplen estas reglas: 1. 2. 3. 4.

Si t1, ..., tn son términos y P es un relator n-ario, Pt1, ..., tn es fórmula. Si t1, t2 son términos, t1=t2 es fórmula. Si A y B son fórmulas, también ¬A, (A∧B), (A∨B), (A→B), (A↔B). Si A es una fórmula, también ∀xA, ∃xA.

Escribimos t1≠t2 en lugar de ¬t1=t2. Cuando en algún lugar de una fórmula hay varios cuantificadores universales seguidos (ejemplo: ∀x∀y∀z), podemos escribir solamente el primero, seguido de tantas variables como había antes (ejemplo: ∀xyz). Lo mismo vale para los cuantificadores existenciales. Las convenciones sobre subfórmulas y sobre economía de paréntesis son las mismas que en lógica proposicional. En cuanto a la forma lógica, tenemos dos novedades: Expresión formal

Lectura intuitiva

Forma lógica

∀xA

para todo x se cumple A

Universal

∃xA

para algún x se cumple A

Existencial

El alcance de ∀x ó ∃x en una fórmula A es la subfórmula de A a la cual se aplicó el cuantificador en la construcción de A. Por ejemplo, el alcance de ∀x en ∀xPx∧Qx es Px, pero el alcance de ∀x en ∀x(Px∧Qx) es Px∧Qx. En el primer caso diríamos que la primera ocurrencia de x está cuantificada o ligada, y que la segunda ocurrencia de x está libre; en el segundo caso diríamos que las dos ocurrencias de x están ligadas. Una fórmula A es una sentencia sii no tiene variables libres. Las sentencias, como veremos, son aquellas fórmulas susceptibles de ser verdaderas o falsas con respecto de un dominio. Las fórmulas que no son sentencias se llaman fórmulas abiertas. Si escribimos A(x1, ..., xn) indicamos que {x1, ..., xn} es el conjunto de variables libres en A; si escrimos ∀x1 ... xn A(x1, ..., xn), ∃x1 ... xn A(x1, ..., xn) indicamos que hay ocurrencias de cada una de las variables x1, ..., xn en A, ocurrencias que por supuesto están ligadas; si escribimos A(c1, ..., cn) indicamos que {c1, ..., cn} es el conjunto de constantes en A. Semántica. Describir en detalle la semántica de L1 cae fuera de los límites de este tema, tanto por la extensión como por el aparato formal que ello requiere. Pero pueden mostrarse sus líneas maestras. Para ello debemos tener muy claro que cada vez que usamos L1 estamos hablando sobre los individuos de un universo, y esto implica o bien decir que cierto individuo cumple cierta propiedad o bien que entre ciertos individuos se establece cierta relación. Supongamos que queremos utilizar L1 para hablar acerca de los individuos que están dentro de un universo no vacío de discurso. Ese universo puede ser el de los números naturales, el de las cajas de ahorro en España, el de las personas cuyo nombre el lector recuerda o el de los átomos del universo. Llamaremos U a ese universo. A continuación, seleccionamos de la sintaxis de L1 las constantes y predicados que nos vayan a ser de utilidad para hablar sobre los individuos de U. ¿Cómo interpretar esas constantes y esos predicados sobre el universo? Mediante una interpretación I, que no es otra cosa que una función que asigna individuos de U a las constantes, conjuntos de individuos a los relatores monarios, conjuntos de pares de individuos a los relatores binarios, conjuntos de tríadas de individuos a los relatores binarios, etc. Una vez

tenemos el universo y la interpretación, escribimos m = (U, I), donde m es el modelo sobre el cual vamos a interpretar todas las expresiones de L1 que, de contener constantes o predicados, son los interpretados por I en U. Fijado un modelo m, las siguientes equivalencias nos dicen cuándo una sentencia es verdadera con respecto del modelo. m(Pt1, ..., tn) = 1

sii

(I(t1), ..., I(tn)) ∈ I(P)

m(t1=t2) = 1

sii

I(t1) = I(tn)

m(¬A) = 1

sii

m(A) = 0

m(A∧B) = 1

sii

m(A) = 1 y m(B) = 1

m(A∨B) = 1

sii

m(A) = 1 ó m(B) = 1

m(A→B) = 1

sii

m(A) = 0 ó m(B) = 1

m(A↔B) = 1

sii

m(A) = m(B)

m(∀xA) = 1

sii

m(A) = 1 para todo a ∈ U que sea interpretado como referente de x en A

m(∃xA) = 1

sii

m(A) = 1 para algún a ∈ U que sea interpretado como referente de x en A

Lo que en lógica proposicional eran tautologías, contradicciones y contingencias son aquí, respectivamente, fórmulas válidas, contradicciones y contingencias. A veces en lógica de predicados se llaman tautologías a las fórmulas válidas cuya estructura es isomorfa a la estructura de alguna tautología de la lógica de predicados. Tendríamos que Pa∨¬Pa es una fórmula válida que además es tautología, mientras que ∀x(x=x) es una fórmula válida que no es tautología. Veamos algunas fórmulas válidas. Tenemos, en primer lugar, las leyes de interdefinición de cuantificadores, que muestran el modo en que la negación nos permite definir el existencial a partir del universal, y viceversa. T35. T36. T37. T38.

∀xA(x) ↔ ¬∃x¬A(x) ¬∀xA(x) ↔ ∃x¬A(x) ∀x¬A(x) ↔ ¬∃xA(x) ¬∀x¬A(x) ↔ ∃xA(x)

Las siguientes leyes informan sobre cómo interactúan los cuantificadores si están pegados unos a otros. Por T39 y T40, cuantificadores idénticos pueden variar su orden de aparición. Por T41, del existencial-universal se sigue el universal-existencial. T39. T40. T41.

∀x ∀y A(x, y) ↔ ∀y ∀x Α(x, y) ∃x ∃y A(x, y) ↔ ∃y ∃x Α(x, y) ∃x ∀y A(x, y) → ∀y ∃x A(x, y)

En cuanto a las variables ligadas por los cuantificadores, las siguientes leyes nos dicen que carece de importancia el nombre exacto de tales variables. T42.

∀x A(x) ↔ ∀y A(y)

T43.

∃x A(x) ↔ ∃y A(y)

Las siguientes son las leyes de descenso cuantificacional. Formalizan la intuición de que el universal es más fuerte que la predicación de alguna propiedad acerca de un individuo concreto, lo cual a su vez es más fuerte que el existencial. T44. T45. T46.

∀x A(x) → A(c) A(c) → ∃x A(x) ∀x A(x) → ∃x A(x)

Las leyes que siguen reflejan el modo en que los cuantificadores interactúan con la conjunción, la disyunción, el condicional y el bicondicional. Las leyes 47, 50 y 53 son las más representativas. T47. T48. T49. T50. T51. T52. T53. T54. T55. T56. T57. T58.

∀x ( A(x) ∧ B(x) ) ↔ ∀x A(x) ∧ ∀x B(x) ∀x A(x) ∨ ∀x B(x) → ∀x ( A(x) ∨ B(x) ) ∀x ( A(x) ∨ B(x) ) → ∃x A(x) ∨ ∃x B(x) ∃x ( A(x) ∨ B(x) ) ↔ ∃x A(x) ∨ ∃x B(x) ∃x ( A(x) ∧ B(x) ) → ∃x A(x) ∧ ∃x B(x) ∃x A(x) ∧ ∀x B(x) → ∃x ( A(x) ∧ B(x) ) ∀x ( A(x) → B(x) ) → ( ∀x A(x) → ∀x B(x) ) ∀x ( A(x) → B(x) ) → ( ∃x A(x) → ∃x B(x) ) ∀x ( A(x) ↔ B(x) ) → ( ∀x A(x) ↔ ∀x B(x) ) ∀x ( A(x) ↔ B(x) ) → ( ∃x A(x) ↔ ∃x B(x) ) ( ∃x A(x) → ∃x B(x) ) → ∃x ( A(x) → B(x) ) ∃x ( A(x) → B(x) ) → ( ∀x A(x) → ∃x B(x) )

En último lugar, repasamos algunas leyes acerca de la identidad. T59, T60 y T61 dicen, respectivamente, que la identidad es una relación reflexiva, simétrica y transitiva. T62 dice que, dada una propiedad expresable mediante A, si dos cosas son idénticas entonces o bien ambas cumplen A o bien ninguna de ellas cumple A. Τ59. T60. T61. T62.

∀x ( x = x ) ∀xy ( x = y → y = x ) ∀xyz ( x = y ∧ y = z → x = z ) ∀xy ( x = y → (A(x) ↔ A(y)) )

Consecuencia. La definición de consecuencia en lógica de predicados es análoga a la que vimos en lógica proposicional. Pero hay que advertir dos cosas: (i) nos ceñimos a las sentencias, dejando fuera de la definición las fórmulas con variables libres, (ii) los modelos que se mencionan en la definición son esta vez estructuras que consisten en un universo y una interpretación. Definición: Decimos que C es consecuencia semántica de {A1, ..., An} sii para todo modelo m, si m(A1)=1, ... , m(An)=1, entonces m(C)=1. Escribimos en ese caso {A1, ..., An}╞ C. Otra manera de decirlo: C es consecuencia de {A1, ..., An} sii no existe ningún m tal que m(A1)=1, ... , m(An)=1, pero m(C)=0. Desde esta formulación es evidente que una

fórmula es válida sii es consecuencia del conjunto vacío de premisas. Como en lógica proposicional, esta definición de consecuencia no dice cómo demostrar que una fórmula es consecuencia de un conjunto de fórmulas. Sin embargo, y al igual que sucedía en lógica proposicional, esta definición de consecuencia sí que sugiere una manera de demostrar que una fórmula no es consecuencia de un conjunto de fórmulas. Basta encontrar un contraejemplo, es decir, un modelo que haga verdaderas a las premisas y falsa a la conclusión. (Si se trata de demostrar que una fórmula no es válida, lo que hacemos es buscar un modelo que la haga falsa.) Un ejemplo. Por T41 sabemos que ∃x∀yPxy→∀y∃xPxy es una fórmula válida. Lo que no sabemos todavía es si su inversa, ∀y∃xPxy→∃x∀yPxy, también lo es. A continuación demostraremos que no. Lo haremos exhibiendo un modelo que hace verdadero al antecedente ∀y∃xPxy pero falso al consecuente ∃x∀yPxy. Sea el modelo m = (U, I) con universo U = {3, 4, 5} e interpretación I(P) = {(3,3), (3,4), (4,5)}. Claramente, m hace verdadero al antecedente, pues para todo elemento y de U es cierto que hay un x con (x, y) ∈ I(P); tomando y = 3 tendríamos x = 3, tomando y = 4 tendríamos x = 3, tomando y = 5, tendríamos x = 4. Por otro lado, m hace falso al consecuente, pues no hay un x en U tal que (x, y) ∈ I(P) para todo y de U. La búsqueda de contraejemplos, como se acaba de ver, requiere algo de ingenio. También en lógica proposicional podía ser complicado dar con un contraejemplo, sólo que entonces podíamos optar por el método de las tablas de verdad; un método que no existe en lógica de predicados. PREGUNTA-CLAVE: ¿Para qué sirven los términos y para qué sirven las fórmulas? Explica por qué una fórmula que no es sentencia no puede ser verdadera ni falsa con respecto de ningún modelo.

3.2. Traducibilidad Las consideraciones sobre traducibilidad hechas en 2.2 siguen siendo pertinentes, aunque debemos tener en cuenta que L1 es un lenguaje mucho más expresivo que L0, lo que aumenta el número de dificultades y traducciones dudosas. No sólo hay que tener en cuenta las condiciones de verdad de las fórmulas, sino también su estructura interna. En particular, hay que tener cuidado con el orden y el alcance de los cuantificadores. Veamos cómo se formalizan los juicios categóricos de Aristóteles: Universal afirmativo: Universal negativo: Particular afirmatico: Particular negativo:

Todo S es P Ningún S es P Algún S es P Algún S no es P

∀x (Sx→Px) ∀x (Sx→¬Px) ∃x (Sx∧Px) ∃x (Sx∧¬Px)

Tomemos ahora un fragmento de L1 donde V, M son predicados monarios; P, H, A predicados binarios; c, d, e constantes individuales. El universo está formado por todos los seres humanos que han existido hasta ahora. Vocabulario: c es Carlos, d es Dora, e es Ester, Vx significa que x es varón, Mx significa que x es mujer, Pxy significa que x es progenitor (padre o madre) de y, Hxy significa que x es hermano o hermana de y, Axy significa que x es un antepasado de y.

1.

Nadie es progenitor de sí mismo. ¬∃xPxx

2.

Carlos tiene una tía, que no es Ester. ∃x ( Pxc ∧ ∃y (My ∧ Ηyx ∧ y≠e) )

3.

Un progenitor de un antepasado es también un antepasado. ∀x∀y∀z ( Pxy ∧ Ayz → Axz )

4.

Dos personas son hermanas si y sólo si tienen los mismos progenitores. ∀x∀y ( Hxy ↔ ∀z (Pzx↔Pzy) )

5.

Todo el mundo tiene algún bisabuelo varón. ∀x ∃u∃v∃w ( Vw ∧ Pwv ∧ Pvu ∧ Pux )

6.

Todo el mundo tiene a lo sumo dos progenitores. ∀x∀u∀v∀w ( Pux ∧ Pvx ∧ Pwx → u=v ∨ v=w ∨ u=w )

7.

Madre sólo hay una. ∀x ∃y ( My ∧ Pyx ∧ ∀z (Mz ∧ Pzx → z=y) )

8.

Dora es varón sólo si resulta ser hijo único. Vd → ∃x ( Pxd ∧ ∀y (Pxy → y=d) )

9.

Si Ester y Carlos son primos, Dora es madre de uno de los dos. ∃x∃y ( x≠y ∧ Pxe ∧ Pyc ∧ Hxy → Md ∧ (Pde ∨ Pdc) )

10. Dora tiene exactamente dos hermanos ninguno de los cuales es Carlos. ∃x∃y ( x≠y ∧ x≠c ∧ y≠c ∧ Hxd ∧ Hyd ∧ ∀z (Hzd → z=x ∨ z=y) ) Una dificultad típica es confundir lo que uno sabe acerca del universo con lo que la interpretación hace explícito. Por ejemplo, si queremos expresar que Dora es madre de Ester, no basta con escribir Pde, sino que hay que escribir Md ∧ Pde, ya que en la primera expresión hemos sobreentendido que Dora es mujer tan sólo porque su nombre en español suele ser nombre de mujer. Este problema aparece ya en las traducciones a nivel proposicional, pero aquí es especialmente peligroso. PREGUNTA-CLAVE: Formaliza estas afirmaciones: “Carlos es padre de alguien a menos que Dora sea Ester ”, “Quienes tengan primos son primos de Carlos”, “Ester no tiene antepasados sin antepasados”.

3.3. Un cálculo de deducción natural Las reglas del cálculo D1 son las diez de D0 más seis reglas nuevas. A cada cuantificador le corresponde una de eliminación y otra de introducción. Lo mismo sucede con la identidad. Las reglas de eliminación son E∀, E∃, E=, las de introducción son I∀, I∃, I=. Las convenciones relativas a puntos suspensivos y corchetes son aquí las mismas que en D0. La principal novedad estriba en que algunas reglas de D1 solamente pueden aplicarse bajo ciertas restricciones. Las expresiones A(x), A(c) y B en las nuevas reglas son esquemas de fórmulas. La variable x en A(x) indica que dentro de la fórmula esquematizada por A hay al menos una ocurrencia libre de x,. La constante c en A(c) indica que dentro de la fórmula esquematizada por A hay al menos una ocurrencia de c. La fórmula ∀yPxy↔Qy podría ser un caso particular tanto de A(x) como de A(y), la fórmula ∀xPxy↔Qy solamente

podría ser un caso particular de A(y), la fórmula ∀yPxy↔Qc podría ser un caso particular tanto de A(x) como de A(c).

Eliminación

Introducción

Restricciones

Universal

∀ x A x  Ac 

Ac  ∀ x A x 

En I∀, c no aparece en ningún supuesto previo no cancelado, ni en las premisas, ni en ∀xA(x).

Existencial

∃ A x  ⋮ Ac ⋮ B B

Ac ∃ x A x

∀ x  x=c  A x A c

A c ∀ x  x=c  A x

Identidad

[ ]

En E∃, c no aparece en ningún supuesto previo no cancelado, ni en las premisas, ni en ∃xA(x), ni en B. No hay restricciones.

Haremos dos observaciones que, si bien se siguen de todo cuanto llevamos dicho, pueden presentar alguna dificultad. 1. Las reglas de introducción podrán anteponer a la fórmula resultante una variable que ya esté cuantificada en la fórmula original. Mediante I∃, por ejemplo, podremos pasar desde Pa→∀xPx hasta ∀x(Px→∀xPx). 2. En todas las reglas excepto en I∃ la sustitución de variables por constantes o de constantes por variables se hace de forma uniforme. Esto quiere decir que todas las ocurrencias de x y de c que aparecen en A deben ser sustituidas, respectivamente y de acuerdo a la regla que se aplique, por c y por x. La excepción de I∃ se justifica por el hecho de que han de ser posibles argumentos como el que concluye ∃x∃yPxy a partir de Paa. Las reglas E∀, I∃, E=, I= son bastante intuitivas. La primera dice que si todos los individuos tienen cierta propiedad, entonces un individuo cualquiera c también la tiene. La segunda dice que si un individuo cualquiera c tiene una propiedad, entonces hay alguno que tiene esa propiedad. Las dos últimas, tomadas conjuntamente, dicen que el hecho de que un individuo c tenga una propiedad se puede parafrasear diciendo que cualquier individuo que sea c tiene esa misma propiedad. La regla I∀ tiene algo más de dificultad. A fin de cuentas, ¿cuándo podemos concluir que todo individuo cumple cierta propiedad a partir de la afirmación por la cual el individuo particular c la cumple? Respuesta: cuando c sea el nombre de un individuo “arbitrario”, es decir, un individuo acerca del cual no hemos hecho previamente ninguna suposición. Y esta es la idea que está detrás de la restricción formal. En E∃ partimos de que algo cumple cierta propiedad. Entonces, mediante A(c), damos nombre de forma temporal a un individuo que la cumple, deducimos de ahí alguna consecuencia en la que haya desaparecido el nombre de ese individuo, cerramos la subderivación y nos quedamos con la conclusión. Imaginemos que estoy hablando

con alguien acerca de la última fiesta de Nochevieja. Se menciona lo que hicieron Juan y Pedro. Cuando mi interlocutor dice que alguien dejó el congelador abierto, respondo: no sé quién lo hizo, pero llamémosle “Patoso”; entonces, si Patoso dejó el congelador abierto, se tuvo que derretir el hielo, luego nadie pudo comer tarta helada a las dos de la mañana. He deducido información sobre una tarta a partir de información sobre un congelador. Necesitaba un nombre en mitad del razonamiento, así es que propuse “Patoso”. Pero ese nombre tenía que desaparecer de la conclusión, pues no identifica a un individuo concreto; por otro lado, no podía utilizar un nombre que hubiera surgido en la conversación, como “Juan”, ya que hubiera atribuido las características de Juan a la persona que dejó el congelador abierto a pesar de que yo no sabía si era Juan o no. Si restringimos nuestra atención a las fórmulas de L1 sin variables libres (las sentencias), el concepto de derivabilidad en D1 es análogo al de D0. Definición: Decimos que C es derivable a partir de {A1, ..., An} sii existe una derivación de C a partir de {A1, ..., An} conforme el cálculo D1. Escribimos entonces {A1, ..., An}├D1 B. Veamos algún ejemplo. Primero demostraremos que, respecto a un dominio, si o bien todo elemento cumple P o bien todo elemento cumple Q, hay algún elemento que cumple o bien P o bien Q. La demostración contiene aplicaciones de las reglas E∀, I∃, las más sencillas de las seis que acabamos de introducir. Ejemplo: Demostrar ∀xPx ∨ ∀xQx ├D1 ∃x (Px ∨ Qx) 1. 2. 3. 4. 5. 6. 7. 8. 9. 10.

∀xPx ∨ ∀xQx ∀xPx Pa Pa ∨ Qa ∃x (Px ∨ Qx) ∀xQx Qa Pa ∨ Qa ∃x (Px ∨ Qx) ∃x (Px ∨ Qx)

Premisa Supuesto E∀ en 2 I∨ en 3 I∃ en 4 Supuesto E∀ en 6 I∨ en 7 I∃ en 8 E∨ en 1 por 2–5, 6–9

Demostramos ahora que T41 es un teorema de D1, lo que implica (por el teorema de corrección) que T41 es efectivamente una fórmula válida. Es una demostración interesante porque intervienen cuatro reglas nuevas: E∀, I∀, E∃, I∃. Ejemplo: Demostrar ├D1 ∃x ∀y Pxy → ∀y ∃x Pxy 1. 2. 3. 4. 5. 6.

∃x ∀y Pxy ∀y Pay Pab ∃x Pxb ∃x Pxb ∀y ∃x Pxy

Supuesto Supuesto E∀ en 2 I∃ en 3 E∃ de 1 en 2–4 I∀ en 5

7.

∃x ∀y Pxy → ∀y ∃x Pxy

I→ en 1–6

El siguiente ejemplo es de Marraud y Navarro (1988: 30). Se trata de formalizar un argumento y demostrar su validez: “Si existen los fantasmas, los materialistas están equivocados. Por consiguiente, si hay fantasmas materialistas, hay fantasmas equivocados.” Ser fantasma, ser materialista y estar equivocado son las tres propiedades relevantes, que representamos mediante Fx, Mx, Ex. Tomamos el marcador lingüístico “Por consiguiente” como elemento que separa las premisas de la conclusión. Ejemplo: Demostrar ∃xFx → ∀x (Mx → Ex) ├D1 ∃x (Fx ∧ Mx) → ∃x (Fx ∧ Ex) 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13.

∃xFx → ∀x (Mx → Ex) ∃x (Fx ∧ Mx) Fa ∧ Ma Fa ∃xFx ∀x (Mx → Ex) Ma → Ea Ma Ea Fa ∧ Ea ∃x (Fx ∧ Ex) ∃x (Fx ∧ Ex) ∃x (Fx ∧ Mx) → ∃x (Fx ∧ Ex)

Premisa Supuesto Supuesto E∧ en 3 I∃ en 4 E→ en 1, 5 E∀ en 6 E∧ en 3 E→ en 7, 8 I∧ en 4, 9 I∃ en 10 E∃ de 2 en 3–11 I→ en 2–12

La aplicación de E∃ en el paso 12 es correcta, pues se apoya en una subderivación cuyo supuesto (paso 2) contiene una constante que no está presente ni en la fórmula a eliminar, que es ∃x (Fx ∧ Mx), ni en ninguna premisa, ni en ningún supuesto previo no caneclado, ni tampoco en la conclusión obtenida: ∃x (Fx ∧ Ex). Por último, demostraremos que T60 es un teorema de D1, lo que implica (por el teorema de corrección) que T60 es efectivamente una fórmula válida. Con este último ejemplo ponemos en práctica una de las reglas de la igualdad. Ejemplo: Demostrar ├D1 ∀x ∀y ( x = y → y = x ) 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11.

a=b ∀x ( x = b → a = x ) a=b→a=a a=a ¬(b = a) ∀x ( x = b → ¬(x = a) ) a = b → ¬(a = a) ¬(a = a) (a = a) ∧ ¬(a = a) ¬¬(b = a) b=a

Supuesto I= en 1 E∀ en 2 E→ en 1, 3 Supuesto I= en 5 E∀ en 6 E→ en 1, 7 I∧ en 4, 8 I¬ en 5–9 E¬ en 10

12. 13. 14.

a=b→b=a ∀y ( a = y → y = a ) ∀x ∀y ( x = y → y = x )

I→ en 1–11 I∀ en 12 I∀ en 13

Al aplicar la regla I=, tanto a a = b en el paso 1 como a ¬(b = a) en el paso 5, hemos tenido que elegir cuál de las dos constantes iba a ser interpretada como la c que aparece en la formulación de la regla. En los dos casos hemos interpretado que la b que aparecía en la fórmula era la c de la regla. Tomando p.ej. la fórmula del paso 1, lo que hemos hecho ha sido interpetar la igualdad a = b como una afirmación donde se decía que b tenía la propiedad de ser idéntica al elemento a, de modo que en el paso 2 lo que se dice es que cualquier cosa idéntica a b tiene la propiedad de ser idéntica a ese elemento a. PREGUNTA-CLAVE: Comenta una a una todas las reglas del cálculo de deducción natural D1, poniendo ejemplos inspirados en razonamientos de la vida cotidiana. Trata después de demostrar que son teoremas algunas de las verdades lógicas que aparecen en el apartado 3.1.

Conclusión Se han expuesto en este tema tanto la lógica proposicional como la lógica de predicados, con especial énfasis en la definición y justificación de sendos cálculos de deducción natural. De estos últimos cabe destacar que sirven para construir derivaciones donde la conclusión se hace depender, no de axiomas, sino de premisas y supuestos. Las premisas son afirmaciones que pueden utilizarse en cualquier momento de la derivación y no tienen necesidad de ser canceladas; los supuestos, en cambio, se introducen a modo de premisas temporales, deben ser cancelados en algún momento y no pueden ser utilizados en la derivación tras haber sido cancelados. De premisas, supuestos y otras fórmulas que hayan sido derivadas y no estén canceladas se sirven las reglas del cálculo tanto para extraer fórmulas a partir de otras más complejas (eliminación) como para construir fórmulas a partir de otras más simples (introducción).

Bibliogafía y webgrafía Manuales de lógica simbólica para filósofos Badesa, C. et al. (2007). Elementos de lógica formal. 2ª ed. Barcelona: Ariel. 11998. [Tras una primera parte sobre teoría de conjuntos, este manual expone de manera accesible pero rigurosa la lógica proposicional y la de predicados. Hay abundantes ejercicios propuestos.] Barwise, J., Etchemendy, J. (2002). Language, Proof and Logic. Stanford: CSLI. 11999. [Una de las mejores introducciones al lenguaje de predicados, que puede aprenderse de forma muy intuitiva con el programa “Tarski’s World” que acompaña al libro. Se incluyen otros dos programas: “Boole” para el manejo de tablas de verdad, y “Fitch” para construir y verificar demostraciones en un cálculo de deducción natural.] Deaño, A. (2007). Introducción a la lógica formal. Madrid: Alianza. 11974. [Como el de Garrido, un manual clásico en español. Muy desfasado como libro de texto. Pero

todavía es de ayuda al docente por su selección de ejercicios resueltos, tanto de formalización como de derivación en deducción natural.] Falguera, J.L., Martínez, C. (1999). Lógica clásica de primer orden. Madrid: Trotta. [Muy útil por su exposición pormenorizada del cálculo de deducción natural. Va acompañado de un cuaderno de ejercicios.] Gamut, L.T.F. (1991). Logic, Language and Meaning. Volume 1: Introduction to Logic. Chicago / London: The University of Chicago Press. 11982. [Excelente introducción a la lógica para filósofos y lingüistas, con el acento puesto en la capacidad expresiva del lenguaje de predicados. El segundo volumen contiene material avanzado sobre lógica modal, teoría de tipos y gramática de Montague.] Garrido, M. (2001). Lógica simbólica. 4ª ed. Madrid: Tecnos. 11974. [Como el de Deaño, un manual clásico en español. Pocos ejercicios propuestos. Incluye un apéndice sobre historia de la lógica.] Manzano, M., Huertas, A. (2006). Lógica para principiantes. Madrid: Alianza. 12004. [Se presenta la lógica como herramienta para modelar información. Pensado para estudiantes de filosofía y de informática. Se exponen cuatro cálculos: tablas semánticas, diagramas de Venn (para lógica de predicados monarios), deducción natural y resolución, aunque se apuesta decididamente por el primero de ellos. Incluye CD con apéndices técnicos y cientos de ejercicios.] Tugendhat, E., Wolf, U. (1997). Propedéutica lógico-semántica. Barcelona: Anthropos. Original: Logisch-semantische Propädeutik, 1989. [De orientación filosófica, muy influido por Strawson. Se utiliza la lógica para analizar enunciados de existencia, negación, contradicción, posibilidad, obligación, analiticidad, verdad, etc.] Valdés, L.M. (1989). “Lógica elemental”. In M. Garrido [ed.], Lógica y lenguaje. Madrid: Tecnos, pp. 11-115. [Exposición condensada pero suficiente de la lógica de proposiciones y de predicados.] Libros de ejercicios Antón, A., Casañ, P. (2007a). Lógica Matemática I. Teoría y práctica. Lógica de enunciados. 3ª ed. Valencia: Nau Llibres. 11982. Antón, A., Casañ, P. (2007b). Lógica Matemática II. Teoría y práctica. Lógica de predicados. Valencia: Nau Llibres. 11998. Castrillo, P. (1997). Ejercicios de lógica. Madrid: UNED. 11991. García Trevijano, C. (2008). El arte de la lógica. 4ª ed. Madrid: Tecnos. 11993. Marraud, H., Navarro, P. (1988). Sistemas deductivos tipo Gentzen. Problemas de lógica de primer orden. Madrid: Universidad Autónoma de Madrid. Pérez Sedeño, E. (2007). Ejercicios de lógica. Madrid: Siglo XXI. 11991. Software para la enseñanza de la lógica Summa Logicae (M. Manzano) http://logicae.usal.es Aprende Lógica (F.J. Calzado) http://w3.cnice.mec.es/eos/MaterialesEducativos/mem2003/logica Logic software and logic education (H. van Dirtmasch) http://www.cs.otago.ac.nz/staffpriv/hans/logiccourseware.html

Guión-resumen 1. El cálculo como parte de un sistema lógico 1.1. Qué son los sistemas lógicos  La lógica estudia relaciones de inferencia. Se interesa por la validez de los argumentos con independencia de aquello sobre lo cual hablan.  Para ello construye, utiliza y estudia sistemas lógicos. Un sistema lógico es una construcción matemática que consta de lenguaje, semántica y cálculo. Cada sistema lógico se utiliza para codificar un determinado concepto de inferencia.  La inferencia se toma como algo estático: no es el proceso que lleva de premisas a conclusiones, sino el resultado de dicho proceso sobre el papel. Tal resultado suele tomar la forma de argumento.  Un argumento es un fragmento lingüístico donde una frase (la conclusión) se sigue de otras frases (las premisas). 1.2 Consecuencia y derivabilidad  Una fórmula C es consecuencia de un conjunto de fórmulas {A1, ..., An} sii para cualquier estructura sobre la cual pueden interpretarse las formulas del lenguaje, si todas las fórmulas de {A1, ..., An} son verdaderas con respecto a esa estructura, entonces también lo es C.  Una fórmula C es derivable a partir de un conjunto de fórmulas {A1, ..., An} sii existe una derivación de C a partir de {A1, ..., An}, es decir, una secuencia finita de fórmulas tal que C es la última, las fórmulas de {A1, ..., An} son las únicas que pueden aparecer como premisas, y cada fórmula se ha obtenido a partir de fórmulas anteriores de acuerdo a las reglas de un cálculo.  Teorema de corrección: si C se deriva de {A1, ..., An}, entonces C es consecuencia de {A1, ..., An}.  Teorema de completud: si C es consecuencia de {A1, ..., An}, entonces C se deriva de {A1, ..., An}.  Un cálculo es correcto (resp. completo) con respecto a un lenguaje y una semántica sii se cumple el teorema de corrección (resp. completud). Tanto la lógica de proposiciones como la de predicados admiten cálculos correctos y completos; entre ellos, los cálculos de deducción natural que vamosa ver.  Para demostrar que C se sigue de {A1, ..., An} conviene usar la noción de derivabilidad, pues en ella se menciona la existencia de una sola derivación, mientras que en la noción de consecuencia se menciona la existencia de infinitas estructuras.  Para demostrar que C no se sigue de {A1, ..., An} conviene usar la noción de noconsecuencia, pues en ella se menciona la existencia de una sola estructura, mientras que en la noción de no-derivabilidad se menciona la existencia de infinitas derivaciones. 1.3. Los cálculos de deducción natural  Los cálculos de deducción natural fueron propuestos por Łukasiewicz, desarrollados por Gentzen y popularizados por Prawitz.  Tratan de emular el modo en que razonan los matemáticos: se parte de premisas y conclusiones, se extraen afirmaciones y se combinan estas últimas para construir los pasos intermedios que van de las premisas a la conclusión.  Cada derivacón tiene sus propias premisas, algunas de las cuales (los supuestos) se asumen de manera temporal para llegar a determinadas conclusiones, tras lo cual son desechadas.  Hay dos reglas por conectiva: una de introducción y otra de eliminación.

2. Cálculo de proposiciones 2.1. Sintaxis y semántica  Construimos lenguajes formales para estudiar en ellos la relación de inferencia.  Los lenguajes naturales (español, alemán...) son ambiguos, dependientes del contexto, autorreferentes y sirven para demasiadas cosas distintas. Los lenguajes formales, en cambio, son independientes del contexto y codifican la información de manera precisa y unívoca.  El lenguaje de la lógica proposicional está compuesto por fórmulas, generadas a partir de variables proposicionales, conectivas y paréntesis. Las variables proposicionales son fórmulas atómicas que representan enunciados simples.  Toda fórmula atómica es verdadera o falsa en virtud de alguna interpretación. Y el valor de verdad de las fórmulas complejas está en función del valor de verdad de las fórmulas simples que la componen.  Tres tipos de fórmulas: tautologías (siempre verdaderas), contradicciones (siempre falsas), contingencias (a veces verdaderas y a veces falsas).  Una fórmula es consecuencia de un conjunto de fórmulas sii toda interpretación que hace verdaderas a las premisas hace verdadera a la conclusión. Una tautología es consecuencia del conjunto vacío de premisas. 2.2. Traducibilidad  Traducimos argumentos desde un lenguaje natural hasta uno artificial para comprobar e este último si el argumento era váliso o inválido.  Para la traducción español-L0 han de determinarse enunciados declarativos simples; se formalizan mediante fórmulas atómicas que después se combinan entre sí por medio de conectivas.  La traducción español-L0 se verifica al comparar las condiciones de verdad de la fórmula con las diferentes maneras en que el enunciado inicial en español se relacionaría con diferentes situaciones posibles. 2.3. Un cálculo de deducción natural  El cálculo de deducción natural para la lógica proposicional cuenta con diez reglas; a cada una de las cinco conectivas le corresponde una regla de eliminación y otra de introducción.  Cada regla corresponde a cómo introducimos o eliminamos conectivas en el razonamiento ordinario. 3. Cálculo de predicados 3.1. Sintaxis y semántica  En el lenguaje de predicados utilizamos términos para denotar individuos y fórmulas para hacer afirmaciones. Las fórmulas que vayan a usarse para hacer afirmaciones deben ser sentencias, es decir, fórmulas sin variables libres.  Los términos y las fórmulas reciben significadocuando se compara con un universo, que es un conjunto de individuos.  Entre el lenguaje y el universo definimos una interpretación que a cada constante del lenguaje le hace corresponder un individuo del universo y a cada predicado n-ario del lenguaje le hace corresponder un conjunto de secuencias de individuos (cada una de n miembros).  Un universo más una interpretación conforman un modelo.  Tres tipos de fórmulas: fórmulas válidas (siempre verdaderas), contradicciones (siempre falsas), contingencias (a veces verdaderas y a veces falsas).  Una fórmula es consecuencia de un conjunto de fórmulas sii todo modelo que

hace verdaderas a las premisas hace verdadera a la conclusión. Una fórmula válida es consecuencia del conjunto vacío de premisas. 3.2. Traducibilidad  Para la traducción español-L1 han de determinarse los individuos, las propiedades y las relaciones que aparecen en el discurso.  Las consideraciones generales sobre traducibilidad hechas en 2.2 siguen siendo válidas. A ellas se añaden dos tipos de dificultad típicas en lógica de predicados.  Una dificultad es elegir bien el orden y alcance de los cuantificadores.  Otra dificultad es confundir lo que sabemos sobre un predicado o un individuo con lo que explícitamente se dice en las fórmulas. 3.2. Un cálculo de deducción natural  El cálculo de deducción natural para lógica de predicados contiene las diez reglas del cálculo proposicional más otras seis reglas, dos para el existencial, dos para el universal y dos para la igualdad.  A diferencia del cálculo anterior, algunas reglas de este cálculo sólo pueden ser aplicadas bajo ciertas restricciones.

Cuestionario 1. Desde un punto de vista estático una inferencia es: a) Un fragmento de texto escrito. b) Un proceso mental. c) El recuerdo de un proceso mental. d) Un fragmento de una conversación. 2. En un cálculo de deducción natural: a) Existen axiomas y reglas. b) Se descomponen las fórmulas en subfórmulas. c) Hay reglas para introducir conectivas y reglas para eliminarlas. d) Se da siempre la completud con respecto de la semántica. 3. ¿Cuál de las siguientes expresiones es una fórmula de L0? a) A→(p∧¬q) b) A→(B∧¬A) c) q→(p∧¬q) d) De q→(p∧¬q) se sigue q→¬q 4. ¿Cuál de las siguientes afirmaciones es falsa? a) Una fórmula contingente no es ni tautología ni contradicción. b) Si A es una tautología, entonces ¬A es una fórmula contingente. c) Puede haber argumentos válidos con premisas falsas. d) Puede haber argumentos inválidos con consecuencia verdadera. 5. ¿Cómo traducirías a L0 la expresión “hay dolor de muelas e infección solamente si hay caries”, tomando m (hay dolor de muelas), i (hay infección), c (hay caries)? a) c → m ∨ i b) c → m ∧ i c) m ∨ i → c

d) m ∧ i → c 6. Para aplicar la regla de eliminación de la disyunción: a) Han de proponerse dos supuestos necesariamente distintos. b) Han de proponerse dos supuestos que no tienen por qué ser distintos. c) Basta con proponer un supuesto. d) Ninguna de las anteriores. 7. ¿Cuál de las siguientes expresiones es una sentencia de L1? a) ∀x ∧ ∃y Dxy b) ∀x ∃y Dxy ∧ Exy c) ∀x ∃y ( Dxy = Exy ) d) ∀x ∃y ( Dxy ∧ Exy ) 8. ¿Cuál de las siguientes afirmaciones es falsa? a) El lenguaje L1 sirve para hablar acerca de los individuos de un universo, indicando qué propiedades tienen y qué relaciones guardan unos con otros. b) El lenguaje L1 puede cuantificar sobre letras de predicado. c) Todas las fórmulas en L1 cuya forma sea la de una tautología de lógica proposicional son verdades lógicas. d) Una sentencia puede contener variables, pero han de estar cuantificadas. 9. ¿Cómo traducirías a L1 la expresión “Todo el mundo tiene al menos un admirador”, tomando Dxy como predicado para indicar que x admira a y? a) ∀x∃y Dyx b) ∃x∀y Dyx c) ∃x∃y Dxy d) ∀x∀y Dxy 10. Al aplicar la regla E∃ a una expresión ∃xA(x), debemos introducir en primer lugar: a) No hace falta introducir nada. b) Una premisa auxiliar A(c) cualquiera. c) Una premisa auxiliar A(x) donde x no aparezca en ningún supuesto previo no cancelado. d) Una premisa auxiliar A(c) donde c no aparezca en ningún supuesto previo no cancelado ni tampoco en ∃xA(x). Respuestas: 1.a, 2.c, 3.c, 4.b, 5.d, 6.b, 7.d, 8.b, 9.a, 10.d