Brevísima historia de la Lógica
Traducción libre de"A Brief history of Logic" de Moshe Y. Vardi (2003)
Trivia
La palabra trivia tiene una interesante etimología. Se compone de "tri" (que significa "3") y "via" (que significa "caminos"). Originalmente se refería al trivium, los tres currículos fundamentales que debía seguir cualquier estudiante: gramática, retórica y lógica. El dominio de estas materias se consideraba esencial antes de que el estudio pudiera continuar con el quadrivium, que consistía en aritmética, geometría, música y astronomía.
¿Por qué se consideró que la lógica era fundamental para la propia educación? Para responder a esta pregunta, es necesario explicar a qué nos referimos con el término "lógica".
Algunas tareas que se relacionan habitualmente con la lógica son (aunque algunos conceptos no los hayamos definido previamente):
- Capacidad de determinar las respuestas correctas a través de un proceso estandarizado.
- Estudio de la inferencia formal.
- Secuencia de afirmaciones verificadas.
- Razonamiento, en contraposición a intuición.
- Deducción de afirmaciones a partir de un conjunto de afirmaciones previas.
En un sentido laxo, todas estas definiciones son correctas, y algunas de ellas muy similares.
La lógica fue estudiada originalmente por los Sofistas, que fueron famosos por sus debates formales. Por ello, eventualmente, trataron de idear un sistema objetivo de reglas para determinar más allá de toda duda quién había ganado una discusión, y la lógica fue concebida originalmente para este propósito.
Como dijo Francis Bacon, en 1605,
"La lógica difiere de la retórica... en que la lógica maneja la razón exacta y la verdad, y la retórica la maneja tal como está plantada en las opiniones y maneras populares."
Así que la lógica trata de un conjunto de reglas para razonar y discutir. Se trata, pues, de un problema fundamental de la actividad intelectual: cómo distinguir lo que es verdadero de lo que es falso, lo que es correcto de lo que es incorrecto.
1ª era de la Lógica: Lógica Simbólica (500 a.C. - siglo XIX)
Originalmente, la lógica se ocupaba de los argumentos en los lenguajes naturales usados por los humanos. Por ejemplo, se usaría para demostrar la corrección de argumentos como el que sigue:
Todos los hombres son mortales.
Sócrates es un hombre.
Por tanto, Sócrates es mortal.
Si cambiamos "todos" por "algunos", el argumento no es válido. Pero, ¿cómo podríamos demostrarlo? Podríamos intentar definir palabras como "todos" y "algunos" en términos de las inferencias que podríamos sacar de ellas. Entonces, la demostración se obtendría a partir de estas definiciones. El problema es que el lenguaje natural resulta ser muy ambiguo. Por ejemplo, consideremos la interpretación de la palabra "una" en la siguiente afirmación:
"Eric no cree que Mary pueda pasar una prueba."
Aquí, "una" podría interpretarse como "ninguna" o "una en particular". Solo el contexto e información adicional pueden aclarar el uso exacto en esta frase.
Otro problema con el lenguaje natural es que conduce a muchas paradojas. La más famosa es "La paradoja del mentiroso":
Considera la afirmación "Esta frase es mentira". Si fuera cierta, entonces debe ser mentira, como dice, lo cual es un absurdo. Del mismo modo, si fuera mentira, entonces lo que dice es verdad, que también es otro absurdo... entonces, ¿es verdad o no?
Hay muchísimos ejemplos similares, por ejemplo, "La paradoja del examen sorpresa":
Un profesor de lógica anuncia a su clase que habrá un examen la semana que viene, pero no dirá qué día, sino que será una sorpresa. Los alumnos deducen que el examen no podrá ser el viernes: si se hiciera el viernes, esa misma mañana ya sabrían que se tiene que hacer ese día y, por lo tanto, no se sorprenderían. Pero como ahora saben que no puede ser el viernes, razonan que tampoco puede ser el jueves, ya que ya no se sorprenderían el jueves por la mañana. Del mismo modo, no se podía celebrar el miércoles, martes o lunes. Pero el martes, el profesor pone el examen, y los estudiantes quedan sorprendidos...
Paradojas como estas, junto con las ambigüedades del lenguaje natural, llevaron finalmente al esfuerzo de formular la lógica en un lenguaje simbólico que intentase evitar las ambigüedades propias de los lenguajes naturales.
2ª era de la Lógica: Lógica Algebraica (mediados y finales del siglo XIX)
En 1847, George Boole, en "The Mathematical Analysis of Logic" intentó formular la lógica en términos de un lenguaje matemático. Las reglas de inferencia fueron modeladas a partir de varias leyes para manipular expresiones algebraicas:
"El diseño del siguiente tratado es investigar las leyes fundamentales de las operaciones de la mente mediante las cuales se realiza el razonamiento; darles expresiones en el lenguaje simbólico de un cálculo, y sobre esta base establecer la ciencia de la lógica y construir sus métodos".
La base de su trabajo fue la similitud que se podía apreciar entre la unión e intersección de conjuntos y la suma y multiplicación numérica, por ejemplo:
$a(b + c) = (ab) + (ac)$ es similar a $x\cap (y \cup z) = (x \cap y) \cup (x \cap z)$.
Aunque este tipo de similitudes pueden, en efecto, mostrar propiedades interesantes y fructíferas, desafortunadamente Boole a veces llevaba la analogía demasiado lejos, y por ejemplo intentó hacer una operación de conjuntos análoga a la división, aunque no existe tal operación en la lógica.
Poco después, al trabajo de Boole le seguiría el de Charles Ludwig Dodgeson, conocido como Lewis Carroll, quien publicó varios textos sobre el tema, y desarrolló los Diagramas de Venn como un medio para razonar sobre los conjuntos, una práctica común hoy en día y que se ha convertido en la vía natural para introducirse en este tipo de teorías.
Fue también durante este período que Ernst Schröeder anticipó la importancia de desarrollar algoritmos rápidos para decidir varios problemas lógicos y matemáticos, adelantándose a lo que sería una de las líenas principales de trabajo hoy en día. En "The Algebra of Logic" escribe:
"Dominar las consecuencias de cualquier premisa, o al menos el método más rápido para obtener estas consecuencias, me parece uno de los más nobles, si no el objetivo final, de las matemáticas y la lógica."
Una vez que la lógica simbólica maduró, se volvió tremendamente útil para resolver muchos problemas serios que se desarrollaban en otras áreas de las Matemáticas.
3ª era de la Lógica: Lógica Matemática (finales del siglo XIX y mediados del siglo XX)
A medida que las pruebas matemáticas se volvieron más sofisticadas, también las paradojas comenzaron a aparecer en ellas, al igual que en el lenguaje natural.
Por ejemplo, en 1820: Cauchy "demostró" que para todas las secuencias infinitas
$$f_1(x),f_2(x),...$$
de funciones continuas, la suma
$$\sum_{i\geq 1} f_i(x)$$
también era una función continua. Pero en 1826 Abel encontró un contraejemplo, probando así que la "demostración" de Cauchy no podía ser correcta.
Para tratar temas como estos, en 1879 Frege propuso la lógica como lenguaje para las Matemáticas. Este desarrollo fue anticipado mucho tiempo antes por Leibnitz, pero no fue hasta finales del siglo XIX que existieron las herramientas lógicas que permitieron abordar el problema. Con ello, el rigor de las pruebas matemáticas aumentó dramáticamente, evitando problemas como el que había sufrido Cauchy (por ejemplo, en el campo del Análisis Matemático, la definición, ahora estándar, que hace uso de epsilon-delta para el límite resolvió el problema que había encontrado).
Con el rigor de esta nueva formalización, Cantor pudo analizar la noción de infinito de maneras que antes eran imposibles. Y concluyó, por ejemplo, que, en lugar de haber un solo infinito, había toda una jerarquía de ellos. Su argumento fue el siguiente:
Consideremos el conjunto $2^N$ de todos los subconjuntos de números naturales. Supongamos que, por el contrario, sólo hay un infinito. Entonces este conjunto, que es infinitamente grande, debe ser del mismo tamaño que los números naturales, que también es infinitamente grande. Por lo tanto, podríamos asignar a cada subconjunto de $N$ un $n\in N$ distinto, formando una secuencia infinita $A_0,A_1,A_2, ...$ de subconjuntos de $N$. Ahora consideremos el conjunto $B$ de los números naturales $n$ tales que $n\notin A_n$. Como $B\subseteq N$, se le debe haber asignado algún número $j\in N$. Pero entonces consideremos la cuestión de si $j \in B$ o no:
$$j\in B \iff j\in A_j\iff j\notin B$$
que es una contradicción. Por tanto, nuestra suposición original es incorrecta, y $2^N$ es estrictamente más grande que $N$. (Nótese que esto deja abierta la cuestión de la existencia de otros conjuntos con tamaños entre estos dos construidos.)
Podríamos seguir un argumento análogo y concluir que $2^{2^N}$ es estrictamente mayor que $2^N$, y así sucesivamente, formando una jerarquía infinita de infinitos cada vez más grandes.
Entonces, ¿cómo determinamos el tamaño de los conjuntos infinitos? Cantor definió el tamaño relativo de dos conjuntos como sigue:
$|A| < |B|$ si existe una función inyectiva de $A$ a $B$.
Esto lleva a un orden total entre todos los tamaños posibles, que desde entonces se conocerán con el nombre de números cardinales. Comienza con un tamaño para cada uno de los números naturales, y luego continúa con los tamaños de los conjuntos infinitos. Estos nuevos tamaños se indican con el símbolo $\aleph$ (leído como "aleph"). El primer tal tamaño ($\aleph_0$) es el tamaño de los números naturales.
$$0,1,2,...\aleph_0,\aleph_1,...$$
Luego, a principios del siglo XX, David Hilbert, el matemático más prominente de su tiempo y uno de los más grandes de la historia, propuso un gran programa para idear un procedimiento formal único del que derivar toda la verdad matemática:
"Una vez que se establece un formalismo lógico, se puede esperar que sea posible un tratamiento sistemático, por así decirlo, computacional, de las fórmulas lógicas, lo que correspondería en cierto modo a la teoría de las ecuaciones en Álgebra".
El primer gran obstáculo se produjo cuando Bertrand Russell descubrió que la Teoría de Conjuntos, tal y como estaba definida entonces, al igual que las lógicas del lenguaje natural, conducían a paradojas. En concreto, Russell se preguntó si la colección de todos los conjuntos era un conjunto o no (algo que nos puede parecer una tontería), y concluyó que con las definiciones de la época (que siguen siendo las mismas que intuitivamente tenemos hoy en día) esto conduce a la llamada "Paradoja de Russell". Para ver porqué es una paradoja, consideremos el conjunto siguiente:
$T = \{S\quad conjunto \quad | \quad S\notin S\}$
Es natural preguntarse si esta colección de conjuntos es en sí misma un conjunto o no, y si lo es, entonces solo tendrá dos opciones, o estar en $T$ o no. Pero: $T \in T \iff T \notin T$ (una contradicción). Esperamos que haya quedado patente el parecido entre esta paradoja y la del mentiroso vista anteriormente.
Russell trabajó alrededor de este problema reformulando las Matemáticas en términos de una jerarquía de conjuntos. Los conjuntos de una jerarquía determinada sólo pueden contener conjuntos de jerarquías inferiores. Su trabajo culminó en el "Principia Mathematica", un trabajo conjunto con Alfred North Whitehead, que demostró formalmente (es decir, con pura manipulación simbólica) la mayor parte del conocimiento matemático de su tiempo.
Además, los matemáticos pronto aprovecharon el hecho de que la Lógica Simbólica, al ser un sistema formal, podía ser objeto de investigación matemática. En la medida limitada en que la Lógica formó una base para las Matemáticas, los resultados de esta investigación arrojaron resultados sobre la naturaleza de las Matemáticas mismas.
Por ejemplo, una pregunta natural que surgió de la prueba de Cantor acerca de infinitos grandes fue: ¿cuál es la relación entre $2^{\aleph_0}$ y $\aleph_1$? Se conjeturó que $2^{\aleph_0}=\aleph_1$, que se conoció como la "Hipótesis del Continuo" (CH). A pesar de muchos intentos de probarlo y refutarlo, nadie tuvo éxito. Más tarde, en la década de 1930, Kurt Gödel demostró que, en el marco de la Lógica y la Teoría Formal de Conjuntos como fundamento de las Matemáticas, suponer que CH es verdadero nunca conducirá a una contradicción. Más tarde, ya en la década de 1960, Cohen demostró que suponer la negación de CH tampoco conduciría a una contradicción. Esto estableció la independencia de esta hipótesis de las matemáticas basadas en la Teoría de Conjuntos (es decir, la Matemática que se concluye de la Teoría de Conjuntos y que es base de la mayoría del resto de Matemáticas, no puede decir nada acerca de la verdad o falsedad de esta hipótesis, y se podría añadir, y de hecho se hace, ella o su negación, como axiomas adicionales para crear dos "mundos matemáticos" con distintas implicaciones).
Aunque el análisis de la Lógica como objeto matemático resultó ser una técnica muy poderosa, pronto dio dos resultados que fueron devastadores para el Programa de Hilbert:
- Primer Teorema de Incompletitud de Gödel. Kurt Gödel demostró que, en un sistema formal lo suficientemente potente como para formar afirmaciones sobre lo que el mismo sistema puede probar, siempre habrá afirmaciones verdaderas que el sistema puede expresar pero no puede probar. Estas afirmaciones podrían probarse con sistemas aún más potentes, pero estos nuevos sistemas podrían expresar nuevas afirmaciones que no podrían probar, y así sucesivamente.
- El Segundo Teorema de Incompletitud de Gödel. Kurt Gödel demostró que un sistema formal lo suficientemente potente como para formar afirmaciones sobre aritmética no puede probar su propia consistencia (es decir, probar que no es capaz de llegar a contradicciones internas).
Alonzo Church y Alan Turing mostraron que hay algunos problemas que ningún algoritmo podría resolver. Si tales problemas existen, entonces no podría haber esperanza de encontrar un solo algoritmo para producir (ni reconocer) toda la verdad matemática.
A pesar de estos resultados, y quizás motivada por ellos, la Lógica continuó floreciendo, no ya con la esperanza de ser la base última universalmente aceptada de todas las Matemáticas, pero sí como otra rama fundamental de la misma. Además, varios sistemas formales independientes podrían todavía servir como base para las ramas individuales de las Matemáticas.
4ª era de la Lógica: Lógica Computacional
La Lógica ha sido determinante para el desarrollo de la Computabilidad y la resolubilidad efectiva de problemas. Antes de 1920, toda computación debía ser hecha en papel y con máquinas muy primitivas para realizar operaciones muy básicas. Pero desde el advenimiento de la computadora electrónica, se ha encontrado un nuevo hogar para la Lógica: la Computación.
En Computación se diseñan y estudian sistemas mediante el uso de lenguajes formales que pueden ser interpretados por un sistema formal. Así que es muy natural que los lenguajes descriptivos formales de la Lógica moderna puedan servir como una herramienta de trabajo para la Computación.
Algunas de las aplicaciones más básicas de la Lógica a la Computación son:
Circuitos Booleanos: El diseño de hardware construido a partir de puertas que implementan primitivas de Lógica Booleana. Esto constituye la base del diseño digital moderno. Aunque se diseñaron máquinas para trabajar directamente con representaciones decimales (como ENIAC), se descubrió que trabajar en la Lógica Booleana era mucho más fácil. Miles de millones de dólares se gastan anualmente en esta industria. Boole pretendía descubrir las "leyes de la mente", pero su mayor impacto ha sido en la industria informática. En Ingeniería Eléctrica la Lógica Booleana es hardware formado a partir de puertas.- Algunos problemas parecen ser tan difíciles que los ordenadores no pueden resolverlos, por muy rápidos que sean. La razón de esta dificultad es una explosión combinatoria que parece ser inherente a este problema. La Lógica jugó un papel crucial en el desarrollo de la Teoría de NP-completitud, que formaliza y mide el concepto de explosión combinatoria.
A una computadora se le tiene que decir qué hacer de una manera muy precisa y formal. Una aplicación de esta descripción exacta es SQL (Standard Query Language): un lenguaje utilizado para la interfaz con las bases de datos. Aunque la sintaxis es diferente, es esencialmente equivalente a la Lógica estándar de Primer Orden. Pero no es el único representante de lenguaje de programación inspirado fuertemente por los fundamentos lógicos, otros lenguaje, como Prolog, se han convertido en piezas fundamentales del tablero de programación para muchos objetivos concretos.- Semántica Formal: Para asegurar que diferentes implementaciones de un lenguaje de programación produzcan los mismos resultados, los lenguajes de programación deben tener una semántica formal. La Lógica proporciona la herramienta para desarrollar esa semántica.
- Validación de Diseño y Verificación: para verificar la corrección de un diseño con una certeza superior a la de las pruebas convencionales se utiliza Lógica Temporal. El famoso bug de Intel de 1995, que implicaba divisiones de punto flotante defectuosas, costó 500 millones de dólares. Hoy en día, sistemas que se soportan claramente en la Lógica se encargan de verificar los diseños de los microprocesadores que se diseñan cada año.
Inteligencia Artificial: razonamiento automático y sistemas expertos. Hay muchos campos en los que la experiencia adquirida por los seres humanos a lo largo de décadas puede describirse con un sistema formal. El sistema resultante a menudo puede producir resultados comparables a los del experto humano, y a veces mejores. Trata de captar el "razonamiento de sentido común" de una manera formal.- Seguridad: Con el creciente uso de la red, la seguridad se ha convertido en un gran problema. De ahí el concepto de código con prueba incorporada. Sería muy interesante que un programa viniese con su propia prueba de seguridad y corrección.
A medida que nuestra comprensión de la Informática y de la Lógica mejora, se establecen conexiones cada vez más profundas. Como resultado, la Lógica se describe a veces como el "Cálculo de la Informática".