PDF de programación - Lógica, Matemática, Deducción Automática

Lógica, Matemática, Deducción Automática

Manuel Ojeda Aciego

Dept. Matemática Aplicada. Universidad de Málaga

Email: [email protected]

Resumen

Presentamos una breve perspectiva histórica del desarrollo en pa-
ralelo y, a veces, entrelazado, de la Lógica y las Matemáticas, con el
objetivo final de presentar la Lógica Computacional y, en particular,
la Deducción Automática, como un área de investigación matemática
de extraordinario potencial práctico, no en balde distintos autores de
conocido prestigio afirman que la Lógica es a la Computación como el
Cálculo Infinitesimal es a la Física.

1.

Introducción

La importancia de la Lógica viene siendo reconocida desde la antig¨uedad,
ya los griegos clásicos sabían que el razonamiento es un proceso sujeto a cier-
tos esquemas y que, al menos parcialmente, está gobernado por leyes per-
fectamente formulables. Pero su importancia en la actualidad se debe, sin
duda, al destacado papel que ha tomado recientemente en los más diversos
campos de la Informática (análisis, síntesis y verificación de programas, pro-
gramación lógica, inteligencia artificial, control de procesos, robótica, etc)
y todo ello no de forma completamente accidental ya que, como veremos,
la Lógica nació como un intento de mecanizar los procesos intelectivos del
razonamiento.

En el caso que nos ocupa se suele establecer, generalmente, que la Lógica
moderna se desarrolló a partir de la confluencia de Matemáticas, Ingeniería y
Ling¨uística. Cuando se concretan referencias a la Ingeniería y a la Ling¨uística
se percibe un aroma con el que todo matemático aplicado se siente identifica-
do. Comentaremos brevemente estas dos disciplinas para, en el resto de este
trabajo, centrarnos fundamentalmente en la aportación de las Matemáticas.

1

Podríamos situar el comienzo de la aportación de la Ingeniería a la Lógi-
ca en 1938, cuando Claude E. Shannon (más tarde famoso por su Teoría
de la Información) observó que las funciones realizadas por circuitos com-
binatorios, inicialmente construidos con relés, se podían representar con la
notación simbólica del álgebra de Boole [52]. A mediados de la década de
los 50, D.A. Huffman extendió este trabajo a los circuitos secuenciales, lo
cual dio origen al desarrollo de la teoría de máquinas de estados finitos [32].
La contribución de la Ling¨uística llega a finales de los 50. Noam Chomsky,
con su teoría de las gramáticas formales, establece las bases de la ling¨uística
matemática e inicia el camino hacia la formalización en la descripción de
los lenguajes naturales [12]. Al mismo tiempo, se estaba trabajando en la
especificación de la sintaxis de lenguajes de programación de ordenadores:
Backus adaptó algunos trabajos de E. Post [45] a tales especificaciones en [3],
y obtuvo una notación que era una variante de las gramáticas libres de
contexto de Chomsky. Por otra parte, el estudio de las clases de lenguajes
generados por las gramáticas formales y el estudio de las máquinas de estados
finitos llevó al establecimiento de una relación inmediata y sorprendente: los
mismos fenómenos aparecían de forma independiente en ambos campos, de
manera que se podían establecer isomorfismos entre ambos modelos.

La implicación de la Lógica Matemática en el nacimiento de la Informáti-
ca, y de la Lógica Computacional en su desarrollo actual, hace que el estudio
de esta disciplina para un docente e investigador en Matemática Aplicada
sea doblemente atractivo: por una parte, es atrayente la juventud del campo
de estudio frente otras ramas tradicionales de las Matemáticas, por otra par-
te, sus orígenes resultan especialmente interesantes desde el punto de vista
histórico.

En lo que sigue nos centraremos especialmente en las interrelaciones en-
tre la historia de la Lógica y la de las Matemáticas y su confluencia en la
creación de la Lógica Matemática y en los fundamentos de la Informática.
Para empezar, y de modo ciertamente informal, podemos decir que la Lógi-
ca Matemática no es en absoluto necesaria (en el sentido de ciencia) si se
pretenden mecanizar tareas tales como:

Cálculos basados en operaciones aritméticas (que un humano puede
memorizar y aplicar sin necesidad de razonar);
Búsqueda de datos (por simple comparación con un patrón dado);
Clasificación u ordenación de datos (siguiendo un criterio establecido);

2

pero, si lo que se pretende es mecanizar tareas en las que interviene destaca-
damente la capacidad deductiva, que podemos calificar como ((inteligentes)),
en las que se requiere:

Tener conocimiento sobre el dominio del discurso;
Razonar con tal conocimiento;
Conocer cómo dirigir o guiar tal razonamiento;

entonces es preciso definir con claridad y precisión, así como analizar desde
el punto de vista matemático, los procesos deductivos que el hombre ejercita
de modo natural. Tal es el objetivo de la Lógica.

La estructura de este trabajo es la siguiente: en la próxima sección se
describe un símil comúnmente usado entre las ventajas aportadas por la
introducción del Cálculo Infinitesimal desde el punto de vista de la me-
canización del estudio de fenómenos físicos y la introducción de la Lógica
Computacional desde el punto de vista de la mecanización del estudio de
gestión de la información; las secciones siguientes presentan distintas etapas
históricas en el desarrollo de la Lógica, comenzando por la silogística aris-
totélica, haciendo hincapié precisamente en los avances obtenidos gracias a
la interacción con las Matemáticas. Finalmente, se dedica una sección a pre-
sentar de modo informal el contenido matemático del área de investigación
de la Lógica Computacional conocida como Deducción Automática.

2. De Euclides y Arquímedes a Newton y Leibniz

Reafirmando lo indicado en el resumen, algunos autores han afirmado
que la Lógica es a la Computación como el Cálculo es a la Física. Por esta
razón presentamos una brevísima visión de la importancia del Cálculo como
herramienta para la mecanización del conocimiento de fenómenos físicos
para, en las secciones siguientes, esbozar la historia de la Lógica Matemática
y su aportación a la Informática actual.

En el desarrollo histórico de las ciencias matemáticas se pueden distinguir
varias etapas aunque, sin duda, no es hasta la civilización griega cuando
las Matemáticas aparecen como una disciplina ((formal)). En contraste con
sus antecesores, los griegos tuvieron la originalidad de hacer un esfuerzo
considerable para que sus demostraciones estuvieran fuera de toda duda
respecto a su verosimilitud. El origen de la lógica formal puede centrarse,
asimismo, en este periodo histórico.

3

Durante la época de esplendor de la Grecia Clásica, Platón (c. 428–348
a.C.) hizo de la Geometría un requisito imprescindible para entrar a su
Academia. Es bien conocido el lema de su Academia ((Nadie pase sin saber
Geometría)), pues de un experto en geometría se suponía, como el valor a un
soldado, la habilidad para razonar con corrección y exactitud.

No hay dudas de que Euclides de Alejandría (c.330–c.275 a.C.) fue el
impulsor definitivo del método axiomático en Geometría: en sus Elementos,
Euclides agrupó las derivaciones de la escuela Pitagórica y las de muchos
otros en un todo unificado. Los Elementos proporcionaron un modelo para
todos los subsiguientes trabajos matemáticos, y representan el principio de
la matemática moderna (forman el primer sistema formal de la matemática),
que ha estado en uso durante más de dos mil años.

Arquímedes (287–212 a.C.), entre otros, mostró cómo usar la geometría
sintética para calcular áreas y volúmenes de muchas figuras y sólidos sim-
ples. También resolvió geométricamente muchos problemas de mecánica, hi-
drostática y óptica. En sus trabajos se puede observar cómo surgen proble-
mas de índole matemática a partir de los esfuerzos científicos para extraer las
leyes de la naturaleza. Por su parte, parece ser que la motivación principal
de Euclides al desarrollar su geometría fue fundamentalmente artística, es
decir, el placer estético. Se intuye, pues, la existencia de dos enfoques de las
Matemáticas: uno encaminado a objetivos eminentemente prácticos (¿ma-
temática aplicada?) y otro cuya motivación es de carácter puramente formal
alejada de todo pragmatismo (¿matemática pura?). Veremos más adelante,
sin embargo, que precisamente el estudio formal del método axiomático, y
sus connotaciones respecto de los fundamentos de las Matemáticas, fue el
detonante del estudio de la computabilidad y, finalmente, del desarrollo de
la Informática.

En los veinte siglos que separan a Euclides y Arquímedes de Newton
(1640–1722) y Leibniz (1640–1710), se resolvieron problemas de dificultad
creciente en distintas disciplinas físicas, cada uno de los cuales necesitó de
métodos desarrollados ad hoc. Cada avance en Física o Matemáticas conse-
guido con el método geométrico requería el extraordinario talento matemáti-
co de, por ejemplo, una figura de la talla de Galileo (1564–1642).

Las cosas cambiaron completamente después de que Descartes (1596–
1650) descubriera que los problemas geométricos se podían traducir a pro-
blemas algebraicos. De este modo los métodos geométricos fueron reempla-
zados por cálculos algebraicos.

Ya había indicios de la aplicación de métodos proto-algebraicos de in-
tegración y diferenciación en los trabajos de Fermat (1601–1665), Barrow

4

(1630–1677), que fue profesor de Newton, y Cavalieri (1598–1647), que fue
predecesor de Leibniz. Los métodos simbólicos de diferenciación e integra-
ción descubiertos por Newton y Leibniz hicieron posible que las sucesivas
generaciones usaran cálculos ordinarios para desarrollar la ciencia y la inge-
niería sin necesidad de ideas (geométricas) felices. Estos métodos aún están
en la base de la comprensión, modelado, simulado, diseño y