logica

L´gica, Matem´tica, Deducci´n Autom´tica
o
a
o
a
Manuel Ojeda Aciego
Dept. Matem´tica Aplicada. Universidad de M´laga
a
a
Email: aciego@ctima.uma.es

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

1.

Introducci´n
o

La importancia de la L´gica viene siendo reconocida desde la antig¨edad,
o
u
ya los griegos cl´sicos sab´que el razonamiento es un proceso sujeto a ciera
ıan
tos esquemas y que, al menos parcialmente, est´ gobernado por leyes pera
fectamente formulables. Pero su importancia en la actualidad se debe, sin
duda, al destacado papel que ha tomado recientemente en los m´s diversos
a
campos de la Inform´tica (an´lisis, s´
a
a
ıntesis y verificaci´n de programas, proo
gramaci´n l´gica, inteligenciaartificial, control de procesos, rob´tica, etc)
o o
o
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
o
o
razonamiento.
En el caso que nos ocupa se suele establecer, generalmente, que la L´gica
o
moderna se desarroll´ a partir de la confluencia de Matem´ticas, Ingenier´ y
o
a
ıa
Ling¨´uıstica. Cuando se concretan referencias a la Ingenier´ y a la Ling¨´
ıa
uıstica
se percibe un aroma con el que todo matem´tico aplicado se siente identificaa
do. Comentaremos brevemente estas dos disciplinas para, en el resto de este
trabajo, centrarnos fundamentalmente en la aportaci´n de las Matem´ticas.
o
a

1

Podr´
ıamos situar el comienzo de la aportaci´n de la Ingenier´ a la L´gioıa
o
ca en 1938, cuando Claude E. Shannon (m´s tarde famoso por su Teor´
a
ıa
de la Informaci´n) observ´ que las funciones realizadas por circuitos como
o
binatorios, inicialmente construidos con rel´s, se pod´ representar con la
e
ıan
notaci´n simb´lica del ´lgebra de Boole [52]. A mediados de la d´cada de
o
o
a
e
los 50, D.A. Huffman extendi´ este trabajo a los circuitossecuenciales, lo
o
cual dio origen al desarrollo de la teor´ de m´quinas de estados finitos [32].
ıa
a
La contribuci´n de la Ling¨´
o
uıstica llega a finales de los 50. Noam Chomsky,
con su teor´ de las gram´ticas formales, establece las bases de la ling¨´
ıa
a
uıstica
matem´tica e inicia el camino hacia la formalizaci´n en la descripci´n de
a
o
o
los lenguajes naturales [12]. Al mismotiempo, se estaba trabajando en la
especificaci´n de la sintaxis de lenguajes de programaci´n de ordenadores:
o
o
Backus adapt´ algunos trabajos de E. Post [45] a tales especificaciones en [3],
o
y obtuvo una notaci´n que era una variante de las gram´ticas libres de
o
a
contexto de Chomsky. Por otra parte, el estudio de las clases de lenguajes
generados por las gram´ticas formales y el estudiode las m´quinas de estados
a
a
finitos llev´ al establecimiento de una relaci´n inmediata y sorprendente: los
o
o
mismos fen´menos aparec´ de forma independiente en ambos campos, de
o
ıan
manera que se pod´ establecer isomorfismos entre ambos modelos.
ıan
La implicaci´n de la L´gica Matem´tica en el nacimiento de la Inform´tio
o
a
a
ca, y de la L´gica Computacional en su desarrolloactual, hace que el estudio
o
de esta disciplina para un docente e investigador en Matem´tica Aplicada
a
sea doblemente atractivo: por una parte, es atrayente la juventud del campo
de estudio frente otras ramas tradicionales de las Matem´ticas, por otra para
te, sus or´
ıgenes resultan especialmente interesantes desde el punto de vista
hist´rico.
o
En lo que sigue nos centraremos...