Logica

L´ogica, Matem´atica, Deducci´on Autom´atica
Manuel Ojeda Aciego
Dept. Matem´atica Aplicada. Universidad de M´alaga
Email: aciego@ctima.uma.es

Resumen
Presentamos una breve perspectiva hist´orica del desarrollo en paralelo y, a veces, entrelazado, de la L´ogica y las Matem´aticas, con el
objetivo final de presentar la L´ogica Computacional y, en particular,
la Deducci´on Autom´
atica, como un´area de investigaci´on matem´atica
de extraordinario potencial pr´actico, no en balde distintos autores de
conocido prestigio afirman que la L´ogica es a la Computaci´on como el
C´
alculo Infinitesimal es a la F´ısica.

1.

Introducci´
on

La importancia de la L´ogica viene siendo reconocida desde la antig¨
uedad,
ya los griegos cl´asicos sab´ıan que el razonamiento es un proceso sujeto a ciertosesquemas y que, al menos parcialmente, est´a gobernado por leyes perfectamente formulables. Pero su importancia en la actualidad se debe, sin
duda, al destacado papel que ha tomado recientemente en los m´as diversos
campos de la Inform´atica (an´alisis, s´ıntesis y verificaci´on de programas, programaci´on l´ogica, inteligencia artificial, control de procesos, rob´otica, etc)
y todo ello no de formacompletamente accidental ya que, como veremos,
la L´ogica naci´o como un intento de mecanizar los procesos intelectivos del
razonamiento.
En el caso que nos ocupa se suele establecer, generalmente, que la L´ogica
moderna se desarroll´o a partir de la confluencia de Matem´aticas, Ingenier´ıa y
Ling¨
u´ıstica. Cuando se concretan referencias a la Ingenier´ıa y a la Ling¨
u´ıstica
se percibe unaroma con el que todo matem´atico aplicado se siente identificado. Comentaremos brevemente estas dos disciplinas para, en el resto de este
trabajo, centrarnos fundamentalmente en la aportaci´on de las Matem´aticas.

1

Podr´ıamos situar el comienzo de la aportaci´on de la Ingenier´ıa a la L´ogica en 1938, cuando Claude E. Shannon (m´as tarde famoso por su Teor´ıa
de la Informaci´on) observ´o que lasfunciones realizadas por circuitos combinatorios, inicialmente construidos con rel´es, se pod´ıan representar con la
notaci´on simb´olica del ´algebra de Boole [52]. A mediados de la d´ecada de
los 50, D.A. Huffman extendi´o este trabajo a los circuitos secuenciales, lo
cual dio origen al desarrollo de la teor´ıa de m´aquinas de estados finitos [32].
La contribuci´on de la Ling¨
u´ıstica llega afinales de los 50. Noam Chomsky,
con su teor´ıa de las gram´aticas formales, establece las bases de la ling¨
u´ıstica
matem´
atica e inicia el camino hacia la formalizaci´on en la descripci´on de
los lenguajes naturales [12]. Al mismo tiempo, se estaba trabajando en la
especificaci´on de la sintaxis de lenguajes de programaci´on de ordenadores:
Backus adapt´o algunos trabajos de E. Post [45] atales especificaciones en [3],
y obtuvo una notaci´on que era una variante de las gram´aticas libres de
contexto de Chomsky. Por otra parte, el estudio de las clases de lenguajes
generados por las gram´aticas formales y el estudio de las m´aquinas de estados
finitos llev´o al establecimiento de una relaci´on inmediata y sorprendente: los
mismos fen´omenos aparec´ıan de forma independiente en amboscampos, de
manera que se pod´ıan establecer isomorfismos entre ambos modelos.
La implicaci´on de la L´ogica Matem´atica en el nacimiento de la Inform´atica, y de la L´ogica Computacional en su desarrollo actual, hace que el estudio
de esta disciplina para un docente e investigador en Matem´atica Aplicada
sea doblemente atractivo: por una parte, es atrayente la juventud del campo
de estudio frenteotras ramas tradicionales de las Matem´aticas, por otra parte, sus or´ıgenes resultan especialmente interesantes desde el punto de vista
hist´orico.
En lo que sigue nos centraremos especialmente en las interrelaciones entre la historia de la L´ogica y la de las Matem´aticas y su confluencia en la
creaci´on de la L´ogica Matem´atica y en los fundamentos de la Inform´atica.
Para empezar, y de modo...