reading

Gutiérrez García, Ismael

Matemáticas para informática / Ismael Gutiérrez García. -- Barranquilla, Col. : Ediciones Uninorte, 2010.

x, 188 p. : il. ; 16 x 24 cm.

ISBN 978-958-741-075-4

ISBN 978-958-741-935-1 (epub)

1. Computadores Matemáticas. 2. Lógica simbólica y matemática. 3. Teoría de conjuntos. I. Tít.

(511.3 G984) (CO-BrUNB: 98667)

El presente libro tiene su origen en los cursos de Matemáticas Discretas y de Lógica Matemática ofrecidos por el autor durante los últimos años en los programas de Ingeniería de Sistemas y Matemáticas, respectivamente, en la Universidad del Norte.

En el contenido de la obra se destacan dos partes bien diferenciadas: la Lógica Matemática y la Teoría de Conjuntos. En la primera parte se presentan dos capítulos: El cálculo proposicional y Una introducción a la Lógica de primer orden. En el primer capítulo se presentan la sintaxis y la semántica para el cálculo proposicional, donde el principal resultado es el teorema de completitud, es decir, se demuestra la equivalencia entre fórmulas demostrables y tautologías. En el segundo capítulo se introducen los lenguajes de primer orden y se demuestra, solo en una dirección, el teorema de completitud de Gödel. La segunda parte del texto está dedicada a la presentación del sistema axiomático de Zermelo-Fränkel para la teoría de conjuntos. Al final del capítulo se presentan los números naturales y el principio de inducción.

Otro aspecto relevante de la presente publicación es la elaboración del software educativo MaXI, que anexamos como un producto visible del proyecto de investigación “Dos tópicos en matemáticas discretas", financiado por la Universidad del Norte en la convocatoria interna del período 2008 - 2009.

El objetivo de esta herramienta pedagógica es ayudar en el proceso de aprendizaje de los diferentes conceptos presentados en el aula de clases. Para la elabo-ración, diagramación y programación de los diferentes algoritmos involucrados en el software se vincularon al proyecto en calidad de jóvenes investigadores los ingenieros de sistemas Luis Carlos Lombana, Alonso García y el ingeniero electrónico Darwin Villar.

En este punto es preciso agradecer a la Dirección de Investigación y Proyectos de la Universidad del Norte por el apoyo durante la ejecución del proyecto de investigación, a Ediciones Uninorte, al Departamento de Matemáticas, a Luis Lombana por su dedicación, esfuerzo científico y excelente trabajo durante la coordinación del Grupo de Jóvenes Investigadores, a Darwin Villar por la lectura del manuscrito y sus valiosas sugerencias, a Alonso García por su apoyo constante.

En el primer capítulo abordamos el cálculo proposicional. Inicialmente presentamos algunos aspectos históricos de la misma y posteriormente nos concentramos en dos tópicos centrales, la sintaxis y la semántica, parte en donde se destacan la demostración del teorema de completitud para el cálculo proposicional y las formas normales de una fórmula proposicional.

Durante mucho tiempo se han distinguido tres grandes partes de la lógica: la lógica formal, la lógica simbólica y la lógica matemática. En la actualidad existen algunas subdivisiones adicionales, por ejemplo, la lógica paraconsistente, cuántica e intuicionista entre otras. La lógica formal fue iniciada por los griegos hace por lo menos veinticinco siglos. Aristóteles¹ estableció y desarrolló las bases de la lógica formal. Para él, la lógica era una introducción al saber general, por cuanto constituye una especie de instrumento para todas las ciencias.

Establecidos en lo que posteriormente se denominó el Organon, que significa instrumento, los tratados lógicos de Aristóteles contienen el primer tratamiento sistemático de las leyes del pensamiento en relación con la adquisición del conocimiento, que hacen especial énfasis en el estudio del silogismo. Este es un conjunto de tres enunciados o proposiciones que tienen entre sí la siguiente relación: el tercero se deduce de los dos primeros. A los dos primeros se les denominan premisas y al último se le llama conclusión. Aristóteles consideró cuatro tipos de premisas:

La característica más importante de la lógica aristotélica es que se fundamentó en los denominados lenguajes naturales y, por ende, se mantuvo al margen de las matemáticas.

Los mejores trabajos en lógica elaborados durante la Edad Media se deben a Ibn-Sina², conocido en Occidente como Avicenna. Estos fueron escritos en árabe y traducidos de manera incompleta al latín.

Durante los dos últimos años el prestigioso lógico Wilfrid Hodges, profesor de la Escuela de Ciencias Matemáticas Queen Mary, de la Universidad de Londres, ha traducido a partir de fuentes originales en árabe muchos de los trabajos de Avicenna entre los que se destacan: Ibn Sina on modes, Ibn Sina and conflict in logic, Ibn Sina on understood time and aspect, Ibn Sina on patterns of proofs y Abstract State Machines as a tool for history of logic. Estos trabajos han puesto en evidencia que la alta componente formal de algunas lógicas de Aviccena las hace muy cercanas a algunas de J. Lukasiewicz³. Todos estos documentos pueden obtenerse en la página web [10].

Los lógicos de Occidente contemporáneos con Avicenna no alcanzaron a establecer una teoría con un alto componente formal, en la medida en que su mayor esfuerzo se concentró en estudiar y formular leyes lógicas para el lenguaje natural del momento, el latín. Como su nombre lo indica, los lenguajes naturales tienen su origen y desarrollo de manera espontánea, esto es, su evolución no obedece a la implementación de una teoría previamente elaborada, sino que, por el contrario, esta se realiza con posterioridad a su misma consolidación.

En la era contemporánea los lógicos fundamentaron su éxito en la introducción y estudio de lenguajes formales o simbólicos que se desarrollaron a través del establecimiento de una teoría como fundamento de dicho lenguaje, cual es, por ejemplo, el lenguaje de la lógica matemática. El punto de partida de un lenguaje formal es el establecimiento de un alfabeto, o sea, un conjunto de símbolos con los que se pueden construir las palabras. En este aspecto no existe diferencia con los lenguajes naturales, es decir, la sola posesión de un alfabeto, probablemente distintos, es un punto en común.

Haciendo uso de la yuxtaposición de los símbolos del alfabeto y de la definición de unas reglas claras se construyen las fórmulas proposicionales, que se definen de manera recursiva y que van a representar las palabras del nuevo lenguaje. En los lenguajes naturales las oraciones pueden definirse como una sucesión finita de palabras. Sin embargo, la consistencia de cualquier combinación de palabras no está garantizada: esta depende de una sintaxis y una semántica que son fruto de la formalización del desarrollo espontáneo del lenguaje natural en consideración. Así se concluye que con los lenguajes naturales la situación es similar, pero a la inversa.

Una diferencia sustancial entre los lenguajes naturales y formales es que en los últimos el simbolismo inherente no permite preestablecer una interpretación de una fórmula proposicional considerada, mientas que en un lenguaje natural dado cada palabra en una oración tiene de antemano su significado. Así, los lenguajes formales en principio están al margen de cualquier componente semántico; desde el punto de vista de la informática esto es una fortaleza, ya que de entrada se eliminan las ambigüedades propias de la polisemántica típica de los lenguajes naturales.

Uno de los grandes pensadores de la época interesado en dar su aporte en ese sentido fue G. Leibniz.⁴ A la muy temprana edad de 19 años presentó la propuesta de una lingua philosophica o characteristica universalis, es decir, un lenguaje riguroso, exacto y universal en el que se reflejara la estructura del pensamiento y con el que, además, con este se pudiesen deducir todo lo relacionado con consistencia y consecuencia. Leibniz presentó en 1690 su propuesta en la obra Ars Combinatoria (Discurso sobre el arte combinatorio) con el objetivo de utilizar la simplicidad de la estructura matemática para reflejar la complejidad de los pensamientos. Como gran dificultad aparecía que un simple análisis del lenguaje no era suficiente para efectuar un análisis profundo de los contenidos de los pensamientos. No obstante, Leibniz aplicó con éxito métodos matemáticos a la interpretación de la silogística Aristotélica, y propuso un cálculo de la adición real mostrando que partes del álgebra están abiertas a interpretación no aritmética. Lamentablemente su obra no fue ampliamente conocida en su época.

A partir del siglo XVIII el término lógica fue utilizado por grandes filósofos, como E. Kant⁵ y F. Hegel⁶, en un sentido muy distante de la concepción clásica de su significado. En su obra Crítica de la razón pura Kant afirmó inicialmente que existen formas puras a priori del entendimiento y de la razón. La lógica la divide en analítica trascendental y dialéctica trascendental. Por su parte para Hegel la lógica no era simplemente un problema de las reglas del razonamiento verdadero, sino que la lógica es la ciencia del ser, cuyo objetivo es revelar su esencia. Por ello la lógica hegeliana es una ontología. Hegel desarrolló su estudio de la lógica haciendo uso de un esquema de tres categorías: las fundamentales del ser, las fundamentales de la esencia y, finalmente, las fundamentales del concepto.

En el siglo XIX se retomaron y ampliaron las ideas de Leibniz. Los trabajos de un gran número de matemáticos y filósofos procuraron expresar la forma de los argumentos válidos en el lenguaje simbólico. Entre estos podemos destacar inicialmente a W. Hamilton⁷ y A. De Morgan⁸. Años más tarde G. Boole⁹ aplicó una serie de símbolos a operaciones lógicas e hizo que estos símbolos y operaciones conservaran la misma estructura lógica que el álgebra abstracta. En 1854 publicó su obra An investigation of the Laws of thought on which are founded the mathematical theories of Logic and Probabilities, libro que trataba por completo de la lógica simbólica y su álgebra.

El desarrollo posterior de la lógica simbólica, segunda mitad del siglo XIX, se recogió en las investigaciones de grandes genios; sin embargo, ocupó un lugar especial G. Frege¹⁰, considerado el autor de la lógica contemporánea. En 1879 publicó la obra Begriffsschrift (Escritura conceptual), la primera del autor en el campo de la lógica; con ella introdujo una nueva sintaxis en la que destacó la inclusión de los llamados cuantificadores, y fue el primero en separar la caracterización formal de las leyes lógicas de su contenido semántico. Una vez fijados los principios axiomáticos de la lógica acometió la tarea de edificar la aritmética sobre la base de aquella; su obra Grundgesetze der Arithmetik (Fundamentos de la aritmética) apareció en 1884.

Después de Frege apareció la colosal obra Principia Mathematica de A. Whitehead¹¹ y B. Russell¹², cuyos tres volúmenes fueron publicados, respectivamente, en 1910, 1912 y 1913. Esta obra puede considerarse como la conclusión de algunas de la propuestas centrales de Frege en la medida en que introdujo en la lógica los métodos y notación del álgebra abstracta. La idea de Russell y Whitehead era evitar la paradoja presentada en el sistema lógico de Frege y demostrar la posibilidad de deducir toda la matemática de la lógica, esto es, resolver un problema de completitud.

Durante la segunda mitad del siglo XX se dieron los principales avances en lo que hoy se denomina lógica matemática; a diferencia de lo anterior, ahora se estudian los sistemas formales, lo que da origen a la usualmente denominada Metamatemática. Uno de los problemas a considerar es la axiomatización de las teorías matemáticas, es decir, preguntarse si existe para toda teoría un conjunto finito de axiomas a partir de los cuales se pudiese derivar formalmente todos los teoremas de la teoría considerada.

Uno de los principales exponentes de esta parte de la teoría fue D. Hilbert,¹³ quien durante el congreso internacional de 1900, presentó en París una lista de problemas, entre los que se destacó la importancia de dar formalidad a la noción de algoritmo. De un modo concreto Hilbert planteó el problema de la decisión del sistema axiomático (Entscheidungsproblem), el cual consistía en encontrar un algoritmo que decidiera en un número finito de pasos si un teorema era o no deducible formalmente a partir de un conjunto de axiomas.

Un papel central jugó K. Gödel¹⁴: a los 24 años de edad como estudiante de la Universidad de Viena presentó su tesis doctoral sobre un conjunto de axiomas de lógica elemental con los cuales se demostró que es posible derivar todas y solamente las verdades de la lógica. La demostración del teorema de completitud para el cálculo de predicados trajo la falsa esperanza a los matemáticos que trabajaban en esa área de que el programa de axiomatización de Hilbert sería viable. No obstante, un año después, en 1931, el mismo Gödel publicó en la revista alemana Monatshefte für Mathematik und Physik el extremadamente difícil y brillante artículo titulado Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme (Sobre proposiciones formalmente indecidibles de Principia Mathematica y sistemas afines) con el cual echó por tierra el sueño hilbertiano.

El trabajo de Gödel es sin duda uno de los más famosos de la historia de la matemática. Sin embargo, distaba del alcance de muchos miembros de la comunidad matemática de la época. En esta joya de la matemática moderna, el término proposiciones indecidibles indicaba la existencia de proposiciones que no pueden ser demostradas ni refutadas dentro de un sistema dado. Como notamos antes, la expresión Principia Mathematica se refería a la obra de Whitehead y Russell.

Una de las primeras consecuencias negativas del teorema de incompletitud era que resultaba imposible encontrar un sistema axiomatizado consistente con el cual puede deducirse toda la aritmética elemental de los números naturales. Por consiguiente, existirán verdades matemáticas no susceptibles de obtenerse como teoremas, es decir, no existe siempre una equivalencia entre los conceptos de verdad matemática y teorema. Otra consecuencia del teorema de incompletitud era la no existencia de un algoritmo de decisión, ya que toda teoría decidible es axiomatizable. Podemos decir, sin embargo, que con Hilbert se colocaron las bases para las relevantes aplicaciones de la lógica matemática en la informática.

Entre las múltiples aplicaciones podemos destacar el problema de la calculabilidad y los problemas de inteligencia artificial. Los personajes centrales en el desarrollo de la calculabilidad fueron E. L. Post¹⁵, A. Church¹⁶ y A. Turing¹⁷. Entre los aportes de Post se encuentran la elaboración de un sistema para controlar la validez de las fórmulas de la lógica sentencial mediante tablas de verdad. Este cofundador de la teoría moderna de la computación introdujo el concepto de grado de indecidibilidad y creó el sistema formal llamado máquina de Post, equivalente a la posteriormente denominada máquina de Turing. Por otra parte, en los trabajos de Church fue notable su concepto de calculabilidad y su demostración de la indecidibilidad de la lógica de primer orden. Desarrolló el cálculo de conversión lambda que permitió efectuar operaciones lógicas con variables generalizadas. Por otro lado, lo que hoy se conoce como máquina de Turing suministró una influencia enorme a la formalización de los conceptos de algoritmo y computación. Ésta no solo era un ejemplo de su teoría de computación sino también una prueba de que tal tipo de máquina computadora podía ser construida.

Aunque menos conocido por las circunstancias propias de la Segunda Guerra Mundial, K. Zuse¹⁸ podría considerarse como otro de los grandes en esta dirección. Zuse construyó las máquinas Z1, Z2 y la Z3. Esta última, denominada por él la primera computadora funcional del mundo, fue destruida durante los bombardeos a Berlín y reconstruida veinte años después para el Deutsches Museum (Museo Alemán) de Munich.

Finalmente, la lógica moderna presentó otras alternativas de estudio; por ejemplo, no es difícil observar situaciones en las que para su discusión fue necesario la introducción de un espectro más amplio a fin de medir la verdad o falsedad de éstas, esto es, se hizo necesario prescindir de la lógica bivalente clásica. Algunas de tales situaciones están asociadas a la percepción y comportamiento del ser humano, por ejemplo, la belleza y la riqueza.

A lo largo del siglo pasado se han propuesto varias lógicas multivaluadas: la lógica triádica de Ch. Peirce¹⁹; la lógica intuicionista, de L. Brouwer²⁰, cuyos fundamentos fueron desarrolladados por H. Weyl²¹ y A. Heyting²²; la lógica polivalente, introducida por la escuela polaca, que tuvo como principal representante a J. Lukasiewicz, y la lógica borrosa o difusa, de L. Zadeh,²³ que consistió en reemplazar para los valores de verdad el conjunto {0, 1} por el intervalo real [0, 1].

Otras lógicas a resaltar, aunque pudiesen considerarse antiguas, solo han sido formalizadas y complementadas durante las últimas décadas, entre otras se han destacado: la lógica modal, el cálculo de secuentes, la lógica categórica, la lógica cuántica, la lógica paraconsistente y la lógica lineal.

La lógica modal puede entenderse como un sistema lógico específico en el que se estudian las relaciones de inferencia entre proposiciones afectadas por operadores modales tales como la necesidad, la posibilidad, la contingencia y la imposibilidad. Según lo anteriormente citado ya en la lógica medieval de Avicenna se encuentran diferentes modos en que una proposición podía ser falsa o verdadera. Entre las principales figuras modernas de esta lógica se destacan C. I. Lewis²⁴ y S. Kripke²⁵. La etapa sintáctica de esta lógica abarca el período comprendido entre 1912 y 1959. Los trabajos de Lewis en lógica modal marcaron no solo el inicio de la etapa sintáctica, sino mucho de la historia de esta disciplina. Podría decirse que la etapa semántica de la lógica modal alcanza su mayor difusión con los trabajos de Kripke.

El cálculo de secuentes no es más que otra forma de resolver los problemas de satisfacibilidad, validez y consecuencia lógica para la lógica proposicional. En términos generales considera un objetivo inicial con base en un problema que se desea resolver y descomponerlo en objetivos más simples hasta llegar a situaciones cuya solución sea trivial. Esta teoría fue introducida por G. Gentzen²⁶ en 1934.

La lógica categórica se enmarca dentro de la teoría de categoría, muy cerca de la lógica matemática, pero más inclinada hacia las conexiones con la informática teórica. Puede decirse que la lógica categórica se originó en los trabajos de F. W. Lawvere²⁷ entre los que podríamos citar Functorial Semantics of Algebraic Theories (1963) y Elementary Theory of the Category of Sets (1964).

La lógica cuántica fue propuesta inicialmente por G. Birkhoff²⁸ y J. von Neumann²⁹. Se trataba de describir la estructura lógica que subyace en las teorías físicas como la mecánica cuántica, que no han cuadrado dentro de la lógica clásica. La lógica cuántica forma la base de las operaciones lógicas aplicables en un eventual ordenador cuántico.

La lógica paraconsistente apareció en la década de los sesenta, introducida por N. da Costa³⁰. Fue desarrollada teniendo como objetivo comprender mejor las contradicciones en vez de excluirlas del estudio. Es decir, en la lógica paraconsistente se admite que una conclusión pueda obtenerse a partir de premisas contradictorias.

Finalmente, la lógica lineal fue desarrollada en principio por J. Y. Girard³¹ (1987) y puede considerársele como un refinamiento de las lógicas clásicas e intuicionista. Desde el punto de vista de la informática, además de tener aplicaciones promisorias en paralelismo, la lógica lineal permite un mejor tratamiento de algunos procesos computacionales, por ejemplo, la localización de la memoria.

Iniciamos con el estudio de ciertos objetos formales denominados fórmulas proposicionales, que involucran variables proposicionales y dos tipos de conectivos lógicos, uno unario (la negación) y cuatro binarios (conjunción, disyunción, implicación y equivalencia).

el universal afirmativo	Todo A es B
el universal negativo	Ningún A es B
el particular afirmativo	Algún A es B
el particular negativo	Algún A no es B