Bas 10210

NOfTAS

NOTAS SOBRE LA MECANIZACIN DE LAS

DEDUCCIONES LGICAS JOS ANTONIO LPEZ BRUGOS

Oviedo

esde Aristteles hasta los intentos re-cientes de prueba, automtica de teore-mas la historia de la lgica ha recorrido un camino en el que la construccin de diagramas y mquinas lgicas ha tenido papel, como ilustra, por ejemplo el libro de M. Gardner, Mquinas lgicas y dia-

gramas (ed. Grijalbo, Mxico, 1973). Un hito en esta historia es la mquina de Jevons (1869) para probar teoremas de lgebra de Boole.

Recientemente, desde mediados de los aos 50, los lgicos estaban empeados en construir programas para la prueba de teoremas lgicos con coiputadoras en dos direcciones: una, de inters para psiclogos y pedago-gos, bsicamente a partir de mtodos llamados heursti-cos (inteligencia artificial), y otra con el inters ms pu-ramente lgico de investigar en la teora de la deduc-cin, utilizando mtodos fundamentalmente algortmicos (complementados firecuentemente con recursos heursti-cos). La deduccin formal automtica se divide en dos familias de mtodos: la deduccin natural (tablas) y los procedimientos de Herbrand (resolucin).

En esta nota me centrar en la historia de esas dos familias de mtodos, sin tratar de describirlos tcnica-mente, y dejando para otra ocasin los programas.

Durante muchos siglos los lgicos han pensado que el nico medio de prueba era el silogismo, siguiendo la tradicin aristotlica. En los Analticos Posteriores, Arist-teles describe las caractersticas de una ciencia demos-trativa (apodeiktik episthme) de modo que supone ciertos axiomas (APst. A 3, 72bl8-22), pero el medio de prueba es el silogismo (APst. A 2, 71bl7 sq), como demuestra G. Patzig en Aristotle's theory of the syllogism (Dordrecht, 1968, pg. 132). En la Etica a Nicmaco (Z

3, 1139b26-31) distingue entre didaskalia di'epagogs y didaskalia sullogismo, base de la distincin histrica entre ciencias deductivas y ciencias inductivas. An en el siglo XIX se sigue planteando esta cuestin como un tpico lgico. Puede verse en Boole {An Investiga-tin of the Laws ofThought, pgs. 238-240), que con el nimo de encontrar la solucin definitiva se pregunta si el silogismo se considera el tipo fundamental de razonamiento, si el estudio de sus leyes es co-extensivo con el estudio de la lgica deductiva.

Su respuesta es que no se puede concebir que el silogismo sea el nico proceso esencial de razonamien-to, que hay que investigar las relaciones que sostienen las verdades de la lgica con otras verdades de la cien-cia y con los mtodos del arte de razonar.

La prctica misma de Aristteles contradice su opinin de que los silogismos se prueban desde silogis-mos y por medio de silogismos. Por medio de un silo-gismo parece que slo se puede probar la proposicin de su conclusin; para probar el silogismo entero sera preciso construir una implicacin entre las proposicio-nes que lo componen, es decir, se necesitara la lgica de enunciados en opinin de Patzig (desarrollada posteriormente por los megrico-esticos).

Pero algunas opiniones de Patzig, Bochenski, etc., sobre la silogstica aristotlica-iniciadas por Lukasie-wicz no son sostenidas actualmente por importantes investigadores, en especial la opinin de que el silogis-mo aristotlico es una tesis lgica y no una inferencia. Desde el punto de vista lgico la cuestin no tiene mayor importancia, puesto que se puede pasar de una a Otra, y, viceversa, por el teorema de deduccin y el de completud. La posicin de Lukasiewicz (y la de Bochenski, Patzig, etc.) contradeca la tradicin, que

EL BASILISCO 83

EL BASILISCO, nmero 2, mayo-junio 1978, www.fgbueno.es

consideraba el silogismo aristotlico como una inferencia. No obstante, a partir de 1970, dos artculos de G.G. Granger N. Oeffenberger respectivamente, pu-blicados en la revista L'age de la science, vol. III, n 4 (Le syllogisme catgorique d'Aristote, pgs. 281-310; Pour une fondation plurivalente de la thorie aristotlicienne du syllogisme, pgs. 311-322), han vuelto a reforzar los ar-gumentos que apoyan la idea tradicional. Sobre esta cuestin public J. Sanmartn un artculo en la revista Teorema (vol. III, nms. 2-3, 1973). Posteriormente J. Corcoran realiz varias investigaciones que refuerzan esta misma posicin, de las que concluye: el sistema deductivo desarrollado por Aristteles en su lgica se-gunda es un sistema de deduccin natural y no un sistema axiomtico, como se haba pensado anterior-mente (Lukasiewicz). La lgica de Aristteles es autosu-ficiente en dos sentido: a) que no supone otros concep-tos lgicos, ni incluso los de la lgica proposicional, b) que es fuertemente completa en el sentido de que cada argumento vlido formulable en el lenguaje del sistema es demostrable dentro del sistema por medio de una deduccin formal (Journal of Symbolic Logic, vol. 37, n 4, Dic. 1972, pgs. 696-702; Aristotle's natural deduction System, ibid. pgs. 437; A mathematical model of Aristo-tle's syllogistic, Archiv fr Geschichte der Philosophie).

Como es sabido, en el S. XIX se reconstruyen ios dos ncleos de las lgicas clsicas, aristotlica y megri-co-estica: desde contextos y objetivos diferentes entre s, Boole desarrolla la lgica de enunciados y Frege la de predicados cuantiflcada.

De cara al objetivo de la presente nota voy a re-montarme a Frege. Se suele admitir normalmente, que instaura con su teora de la cuantificacin una nueva etapa para la lgica. Aparte de mltiples correcciones de lnea y otros hallazgos originales (contra la opinin de Ventura Rey y Prosper, Teorema VIII, pg. 334), lo fundamental de Frege es su uso de la nocin de sistema formal.

De Frege a Russel prima el inters por deducir las matemticas de axiomas lgicos por medio de reglas formales (logicismo). Por otro lado, se fue consiguiendo reducir al mnimo el nmero de axiomas lgicos: Russell, Sheffer, Lukasiewicz, Bernays, Wadjsber, etc.

Pero Lwenheim (Uber Moglichkeiien im Relativkal-kl, Math Ann. 76, 1915, pgs. 447-470) toma otro camino, que se retrotrae a Schrder: fundamenta la l-gica de predicados sobre la teora de conjuntos, abriendo as el campo de la teora de modelos. Deja a un lado axio-mas, reglas de inferencia y la nocin de demostrabili-dad. Establece el siguiente teorema: si una frmula de la teora de la cuantificacin es satisfacible, lo es en un dominio denumerable, es decir, si una lgica L es con-sistente es un modelo sobre enteros positivos. De gran importancia histrica, este teorema fue perfeccionado dentro de los teoremas de completud por Skolem, Gdel, Tarski y Malcev, y usado significativamente por otros (Henkin, Vaught, Hanf, Beth, etc.). Se han sim-plificado su demostracin: Henkin (1949), Hasenjaeger (1953), Novak (1950), Rasiowa-Sikorski (1950), Beth (1951-3). (Ver, por ejemplo, J.B. Rosser, Deux esquisses de Logique, Pars, 1955, pgs. 39-43; Beth, L'existence en mathmatique, Pars, 1956, pgs. 11-34; Some Consequen-

ces of the theorem of L6u>enheim-Skolem-Godel-M.alcev, Ams-terdam Proceedings, vol. 56, 1953; una resea histrica breve en Bell y Slovasoa, Models and Ultraproducts, pg. 86).

Skolem en Uber die mathematische Logik (Norsk ma-tematisk tidsskrift 10, 1928, pgs. 125-142) utiliza un mtodo, sugerido por la demostracin de Lwenheim de su teorema de 1915 (pgs. 450-6), que llega a ser la base de la teora de Herbrand, como este mismo reco-noce: se trata de engendrar de un modo ordenado cier-tas constantes con las que obtener casos particulares de una frmula dada de la teora de la cuantificacin, y sa-car, a partir de ah, conclusiones acerca de dicha frmu-la. Herbrand parte de una frmula cuantificacional en forma prenex de Slokem, tratndola de satisfacer con'.una serie de constantes individuales no primitivas hasta construir una conjuncin o disyuncin de Her-brand para dicha frmula. As, por ejemplo, para la dis-yuncin podemos concluir: existe un nmero r, tal que la r-sima disyuncin de Herbrand de, digamos G, tiene, por las leyes de la lgica proposicional, el valor de verdad V. para toda eleccin de funciones lgicas de-finidas sobre S (la serie de constantes individuales), entonces la frmula G es vlida.

Para pasar de una frmula prenex a una frmula cuantificacional cualquiera es preciso definir de un modo ms general la conjuncin y disyuncin de Her-brand, dintinguiendo entre variables generales y restrin-gidas. Pero, por el mtodo de Herbrand, es una ope-racin mecnica verificar si la r-sima disyuncin de Herbrand de una frmula, digamos G, es vlida.

El teorema fundamental de Herbrand demuestra que el mtodo axiomtico y el de Herbrand se implican recprocamente (J. Herbrand, Ecrits Lgiques, Pars, 1968, pgs. 138-142). Gdel demostr, a su vez, que el mtodo axiomtico y el conjuntista ison equivalentes (teorema de completud, 1930). As los tres mtodos son equivalentes, pero, como Herbrand adoptaba el punto de vista finitista, no poda admitir las nociones conjuntistas. En consecuencia, Herbrand (con la escuela hilbertiana) slo considera problema vlido el de las relaciones entre su mtodo y el axiomtico, y a resol-verlo dirige su famoso teorema fundamental. En una nota de 1931, Herbrand expone sus ideas sobre Hilbert y Brouwer-formalismo e intuicionismo {Note nos signe sur Herbrand 1930, Annales de l'Universit de Pars, 6, 1931 a, Ecrits Lgiques, pgs. 186-9).

Gdel, y ulteriormente Dreben, Andrews, Aande-raa. Dentn y Scalon, corrigieron algunos errores de Herbrand, siendo uno de los ms importantes por sus consecuencias el de que no creyera que al realizar cier-tas aplicaciones de una regla de transformacin aumen-tara el orden de una frmula (ver el prefacio de van Heijenoort a los Ecrits Lgiques de Herbrand). Luego veremos cmo una interpretacin excesivamente restric-tiva del teorema de Herbrand (restingindoio a frmu-las prenex) por parte de importantes autores (Gentzen, Hilbert-Bernays, Church, Bernays) ha limitado por al-gn tiempo su influencia.

Aunque el problema de la decisin es una de las cuestiones fundamentales de la lgica de los aos 20 y

84 EL BASILISCO


30 llegando a importantes resultados, que van de Sko-lem y Behmann a Church, pasando por Gdel y otros , me referir a l ulteriormente, al tratar el cie-rre de las tablas semnticas y de ciertas propiedades de subclases de frmulas de cara a su calculabilidad efecti-va (ver, por ejemplo, Bernays y Schonfnkel, Zum ents-cheidungsproblem der mathematischen Logik, Math. Ann., Vol. 99, 1928, pgs. 342-372, que adems subraya la importancia de las dualidades en Lgica).

Dado el -carcter de la presente nota, voy a cen-trarme ahora en algunas consideraciones sobre la DE-DUCCIN NATURAL, que entre otras cosas inicia la deduccin por rboles, frente a la deduccin lineal tpica de la axiomtica.

G. Gentzen public sus clculos de Deduccin Na-tural en 1934 {Mathematische Zeitschrift, t. 39, pgs. 176-210 y 405-431; en 1955 R. Feys y J. Ladrire pu-blicaron una traduccin francesa con prefacio del prime-ro y notas muy amplias e ilustrativas de ambos, de la cual Cuadernos Teorema anuncia 'una versin castellana).

La exposicin ms completa y actual de la Deduc-cin Natural es la de D. Prawitz, Stockolm Studies in Phi-losophy 3, 1965 (reseada por R. Thomason en el Jour-nal of Symbolic Logic, 32, 1967, pgs. 255-6), incluyendo incluso su aplicacin a la lgica modal.

R. Feys escribi un artculo en 1946 (Les m'ethodes recentes de dduction naturelle, Revue Philosophique de Lou-vain, t. 44, pgs. 370-400), donde proporciona informa-cin histrica acerca de dichos clculos (que incorpora literalmente, como nota A, a su traduccin de los dos artculos de Gentzen citados) y algunas observaciones a modo de conclusin. Al ao siguiente Feys vuelve a publicar otro artculo, complementario del anterior, sobre los mtodos de deduccin natural (Note compl'e-mentaire sur les mthodes de dduction naturelle, Revue Phi-los. de Louvain, 45, 1947, pgs. 60-72), pero esta vez en las versiones de Jaskowski (On the rules of suppositions in formal logic, Studia Lgica, n. 1, Varsovie, 1934, 32 pgs.), que le proporcion Perelman (dedicado a la lgi-ca de la argumentacin retrica), y Ketonen (Untersu-chungen zum Prddikatenkalkl, Annales Academiae Scien-tiariim Fennicae, series A, 1. Mathematica-physica 23, Helsinki, 1944, 71 pgs.), concluyendo tambin con ciertas observaciones sobre las posibilidades de expre-sin que ofrecen los mtodos de deduccin natural. Jaskowski construy un mtodo idntico al primero de Gentzen (clculo N), independiente de ste, poniendo en prctica una sugerencia de Eukasiewicz haba hecho en 1926. En este ltimo trabajo Feys expone adems una simplificacin del segundo mtodo de Gentzen (clculo L) y utiliza dos variates de Kentonen

Feys expone los clculos de deduccin natural en su Logistik I (1944, \ \ 9 , 10, 16 pgs. 230-253 y 283-291). Johanssen los adapta a su clculo mnimo en 1936. Hay tambin diversos trabajos de Popper y otros que siguen mtodos anlogos a los del clculo N.

H.B. Curry ha hecho una importante reduccin (A theory of formal Deducibility, Notre Dame mathematical kctures, aP 6, 126 pgs.; y A note on the reduction of

Gentzen's calculus LJ (segundo mtodo, clculo intuicio-nista), Bull. Americ. Soc, 1939, t. 4.5, pgs. 280-293). Esta reduccin tiene la ventaja de simplificar el clculo LHJ (nuevo mtodo, clculo inruicionista). Demuestra la equivalencia del clculo LJ y las lgicas intuicionistas. Interpreta los enunciados bajo supuestos como enuncia-dos epitericos y construye los sistemas L en varias etapas lgicas sin negacin ni cuatificacin, lgicas con cuantificaciones, lgicas con negacin intuicionista o cl-sica. Aplica L a la lgica modal (S4 de Lewis). Demuestra el teorema fundamental para cada una de las etapas, ali-gerando as la demostracin.

La introduccin de los clculos de deduccin natural en E.E. U.U. fue hecha por Bernays, que ense en Princeton el clculo NK en 1936.

Un sistema de deduccin natural anlogo al de Gentzen es el de L. Nolin (Sur un systme de dduction naturelle, Comptes rendues des sances de lAcadmie des Sciences, Pars, voL 246, 1958, pgs. 1128-1131). Pero la simplificacin ms, conocida es la de Quine (On natu-ral dduction, The Journal of Symbolic Logic, vol. 15, n 2, June, 1950, pgs. 93-102; recogido tambin en los Mtodos de la Lgica). El objetivo prioritario de su mto-do es establecer la implicacin y secundariamente la va-lidez general. Para marcar las frmulas usa columnas con asteriscos, las cuales recuerdan la notacin de Jaskowski (como Quine mismo indica); las reglas de generalizacin se simplifican marcando las variables en cuestin.

Una versin ms perfeccionada es la de R. Monta-gue y D. Kalish (Remarks on description and natural d-duction, Archiv fr Mathemasche Logik und Grundlagen-forschung, Band 3, 1957, pgs. 50-73), "que Garrido uti-liza en la exposicin de la Teora de la identidad y descripciones en su Lgica Simblica, pg. 222.

La informacin que ahora interesa sin entrar en la descripcin tcnica de los clculos es la que propor-ciona Feys en los trabajos anteriormente citados o la del mismo Gentzen en la introduccin a Investigaciones sobre la deduccin lgica.

El campo sobre el que Gentzen trabaj es el clculo funcional restringido (Hilbert) o lgica de predicados, tanto en la versin llamada clsica como en la intuicionista. Parte de la formalizacin del razona-miento lgico elaborada por Frege, Russell, Hilbert, pero desde otros supuestos.

Presenta dos grupos de clculos: 1) Los clculos N (clculos de deduccin natu-

ral) que usan aserciones con supuestos (anlogos a los ya citados de Jaskowski) y

2) Los clculos L, que usan aserciones de conse-cuencia, reflejando de Hertz la notacin de secuencias y reglas expresadas por los esquemas de Strukturfiguren (Hertz, IJber Axiomensysteme fr beliebige Satzsysteme, Math. Ann., t. 87, 1922, pgs. 246-269; y t. 89, 1923, pgs. 76-102; y con el mismo ttulo, Ann. Phil. und phil. Krit., t. 8, 1929, pgs. 17.8-204; y Math. Ann., t. 101, 1929, pgs. 457-514; jber Axiomensysteme von Satzsystemen, D.M.-t. 38, 1929, 2 Abt. pgs. 45-6). En un artculo publicado en Febrero de 1932 (Uber die

EL BASILISCO 85


Existenz unabhdngiger Axiomerisysteme zu unendlichen . Satzsytemen,.Mathematische Annalen, 107, pgs. 329-350) Gentzen recoge cierta metodologa de Hertz, e incluso cierta terminologa, que luego us en las Investigaciones, como, por ejemplo, la transformacin del silogismo en cut, el antecedente y consecuente de las se-cuencias, etc., y sobre todo la nocin de consecuencia lgica. (Sobre estas aportaciones y otras, ver la intro-duccin de M. E. Zsabo a la obra de Gentzen en The Collected Papers of G. Gentzen, North-HoUand, 1969).

Gentzen introduce el clculo NJ para la lgica de predicados intuicionistas y el NK para la lgica de pre-dicados clsica; el clculo LJ para la intuicionista y el LK para la clsica. Como es sabido, los intuicionistas

^rechazan el clsico principio del tertio excluso.

La principal razn de la creacin del nuevo clculo L est en las dificultades de prueba, en el clculo N, del Teorema Fundamental.

Este teorema dice que toda demostracin pura-mente lgica puede llevarse a una forma normal deter-minada, que no es unvoca, {Recherches, pg. 4). Gent-zen cree que parte de este teorema haba ya sido de-mostrada por Herbrand. Se lo suele llamar teorema de Herbrand-Gentzen. Respecto a esta cuestin van Heije-noort dice en su introduccin a la obra de Herbrand:

En sus escritos de 1934 Gentzen estableci un verschrfter Hauptsatz para un sistema LK y escribe (nota 6, pg. 409, o 1955 pg. 115) que el teorema fundamental de Herbrand es un caso particular de l (Spetialfall). Parece pensar, contrariamente al texto mismo de Herbrand, que su teorema no se aplica ms que a frmulas prenex (y lo mismo Hilbert-Bernays, Church, Bernays); por tanto, traducido al sistema LK, el

- * - ^ -

torema se aplicara, segn Gentzen, a una secuencia.cu-yo antecedente es vaco y el consecuente consiste en una frmula prenex, mientras que el verschrfter Hauptsatz se aplica a toda la secuencia cuyas dos frmulas son prenex. Es precisaniente ah donde Gentzen ve la ma-yor generalidad de su, resultado. Pero Herbrand no ha restringido nunca su teorema a frmulas prenex y, como el 'verschrfter Hauptsatz, una vez que se tradu-ce al sistema LK a una versin corriente de la teora de la cuantifcacin, slo se aplica a frmulas de una es-tructura particular, es de hecho el verschrfter Haup-tsatz el que es un caso particular del teorema funda-mental de Herbrand. La Mittelsequenz de Gentzen es, en el sistema LK, el anlogo de la disyuncin de Her-brand. El estudio de los campos permite a Herbrand dar ms informacin sobre la naturaleza y el papel de esta disyuncin que la que da Gentzen acerca de la Mittelsequenz. La existencia de demostraciones sin cotte (Hauptsatz de Gentzen, 1934, pg. 196, o 1955, pg. .49) es anloga, para el clculo LK, al resultado, establecido por Herbrand en 1929, segn el cual la re-gla de implicacin es una regla derivada, es decir, su-perflua, en el sistema adoptado por Herbrand para la teora de la cuantificacin (pgs. 143, 182, y la nota D., escrita por Dreben,.en van Heijenoort, 1967, pg. 571). Subrayemos finalmente sto: si para un cierto nmero r la r-sima disyuncin de Herbrand de una frmula F es vlida (en lgica de proposiciones), la frmula F tiene, en el sistema de Herbrand, una demostracin que evi-

dentemente goza de la propiedad llamada de subfrmu-las (Ecrits logiques, pgs. 10-1).

Gentzen adapt este segundo clculo (L) a los for-malismos de Russell, Hilbert y Heyting con el nombre de LHJ (para la lgica de predicados intuicionistas) y LHK (para la clsica). Tambin demostr la equivalencia entre los clculos N y los L, tanto en la versin intui-cionista como en la clsica.

Hay que aadir que Gentzen construy las pruebas de su Hauptsatz para los clculos NI y NK, pero no las aplic. Una prueba del Hauptsatz de Gentzen para NI y una variante ms fuerte para NK puede encontrarse en A.R. Raggio (Gentzen's a Hauptsatz for the systems NI and NK, Logique et Analyse, 1965, pgs. 91-100).

Feys explica el sentido de los clculos de Gentzen del siguiente modo:

Ha despertado el uso, frecuente y natural en ma-temticas, de los razonamientos a partir de un supuesto (estos razonamientos proceden, en suma, como las pruebas ex suppositione de los Antiguos). Para formali-zar estos razonamientos deber introducir la asercin 'esto es verdadero bajo todo supuesto' como elemento formalizado de sus sistemas. Lci hace bajo dos formas: implcitamente en sus sistemas N, explcitamente en sus sistemas L. Siendo B verdadero suponiendo U, se pue-de aceptar que U implica B. Esta regla no define la im-plicacin por un equivalente que le es sustituible; per-mite introducir la implicacin desde el momento que la deduccin es posible: La gran novedad de ios mtodos L es esta introduccin de la asercin bajo supuesto, a continuacin la enunciacin de las reglas de su manejo, que, en los sistemas, L, revestirn la forma explcita de 'figuras de estructura'. El mtodo L 'clsico' o mtodo LK introduce, por su parte, una cierta dualidad de la asercin bajo supuesto, la asercin de consecuencias alternativas ('de sto se saca tal consecuencia o tal otra') con figuras de estructura apropiadas. (Prefacio de Feys a Recherches sur la dduction logique, pgs. VII-VIII).

Estas figuras no recuerdan en general los esquemas de reduccin usados por Hilbert y su escuela.

Resultados:

1. La aplicacin de los esquemas 'naturales' N permite demostrar ios teoremas de la lgica intuicionis-ta y no los de la lgica clsica. Para demostrarlos debe introducirse el tertio excluso como axioma suplementa-rio; en efecto, es el nico postulado que no es un es-quema de deduccin. Los esquemas L conducirn tam-bin nicamente a los teoremas intuicionistas, si no se razona ms .que sobre 'aserciones bajo supuestos' y no sobre aserciones con consecuencias alternativas.

2. El del 'teorema principal': Si procedemos segn los esquemas de la lgica L, todas las tesis demostrables pueden ser demostradas sin recurrir a eliminaciones (...) En un razonamiento por supuestos es posible demostrar todos los teoremas de la lgica construyndolos por complicacin sucesiva de una tautologa inicial, sin eli-minar nunca un trmino medio por un silogismo, ade-ms sin deber usar el moduns ponens (ibid., pg. IX).

86 EL BASILISCO


En su artculo de 1946 Jreys compara los mtodos de Gentzen a los de valores de verdad, quince aos anteriores, considerando .qufe inciden mejor que otros en el aspecto deductivo: se hacen razonamientos lgicos con vistas a establecer proposiciones 'verdaderas' o 'vli-das'; se hacen razonamientos lgicos con vistas a sacar consecuencias. Los nuevos mtodos, y slo ellos, pro-porcionan un acceso fcil a las lgicas 'no-clsicas'. El mtodo de valores de verdad se traspasa sin dificultad de las lgicas polivalentes; los mtodos de Gentzen se adaptan fcilmente a la lgica de los intuicionistas y a la lgica 'mnima'; ponen estas lgicas 'al alcance de to-dos'. Sobre este punto, subraymoslo, los clculos de valores de verdad y los de Gentzen tienen cada uno su dominio'privilegiado': la lgica de los intuicionistas se ex-presa difcilmente en trminos de lgicas polivalentes (con la ayuda de ia matriz de Jaskowski); y, por el con-trario, no se ve cmo adaptar los mtodos de Gentzen a las lgicas polivalentes (por el hecho de que los 'teo-remas de deduccin' no parecen demostrables en ellos). Donde los mtodos nuevos se vuelven indispensables, es en el terreno de los problemas metalgicos (proble-ma de decisin, problemas de no-contradiccin, y otros anlogos (pgs. 399-400).

Siguiendo a Feys en su Note Complmentaire apunta-remos algo sobre los mtodos de Jaskowski. La lgica que se deduce de las cuatro reglas de Jaskowski es la lgica bivalente formulada en trminos de implicacin y negacin (la del sistema axiomtico de Eukasiewicz). Jaskowski ha visto el partida que se puede sacar de su mtodo para el estudio de los sistemas incompletos, donde ciertos axiomas son omitidos o reemplazados por

otros ms dbiles. Muestra adems la equivalencia del sistema fundado sobre sus tres primeras reglas con una lgica positiva sin negacin y que se deduce de dos axiomas de Lukasiewicz: ::pF(qFp) y ::(pF(qFr) )F( (pFq) F (pFr) ).

Como esta lgica no menciona ms que implicacio-nes, las proposiciones vlidas en ella son las positiv identische Implikationsformeln de Hilbert-Bernays.

No menciona la posibilidad de deducir la lgica intuicionista desde la deduccin natural, cosa que vio clara Gentzen en su primer mtodo. Lo que s indica es cmo obtener las proposiciones vlidas en el clculo de Kolmogoroff (O principe tertium non datur, Matema'tt-cheskij Sobornik, t. 32, 1924-5, pgs. 646-667).

Jaskowski muestra tambin que el ex falso sequi-tur quodlibet no se puede deducir en la lgica de Kol-mogoroff, ni en la lgica formulada en 1936 por Johan-sson.

Sus esquemas para la deduccin de proposiciones generales no permiten deducir una lgica intuicionista de proposiciones generales.

El segundo mtodo de Gentzen puede tener dos variantes para las que Ketonen tiene inters. Los esque-mas de Ketonen son reversibles: se puede deducir la ex-presin de encima de la lnea tomando como premisa la de abajo. La aplicacin repetida de esquemas reversibles permite la descomposicin: un enunciado del clculo de proposiciones puede descomponerse en una serie de enunciados compuestos slo de proposiciones simples equivalentes a la primera (gracias a la reversibilidad de los esquemas). Pero el mtodo de descomposicin se limita a la lgica clsica de proposiciones.

Estas dos variantes han sido incorporadas a los cl-culos corrientes de deduccin natural (ver, por ejemplo, Kleene , Introd a la metamatem., cap. XV).

Lo que los lgicos han subrayado frecuentemente es, como dice Feys, que los mtodos naturales de deduccin son tambin mtodos naturales de expre-sin, que traducen ciertos encadenamientos de ideas de forma ms obvia que la lgica formalizada ordinaria.

En el campo de la metamatemtica se han sacado tambin consecuencias tiles del teorema de Herbrand-Gentzen, que suele formularse: si ADA' es un teorema de clculo de-predicados de primer orden y si A es una conjuncin, y A' una disyuncin de formas normales prenex, entonces hay una H-dediccin de ADA':

Una tarea de la metamatemtica, dice Craig, es re-lacionar conceptos sugestivos pero no elementales, de la teora de modelos con conceptos de la teora -^t^ la prueba ms elementales que los anteriores. Beth mos-tr, usando una versin modificada del teorema de H-G que una cierta nocin de definibilidad, de la teora de modelos para todos los sistemas de primer orden coin-cide con una cierta nocin de teora de la prueba {On Padoa's method in the theory of definitions, Indagationes mathematicae, vol. 15, 1953, pgs. 330-9). Posteriormen-te Craig (Three uses of the H-G theorem in relating model

EL BASILISCO 87


theory and proof theory, Journal of Symbolic Logic, vol. 22, n. 3, 1957, pgs. 269-285) generaliza los resultados de Beth de smbolos primitivos de predicados a frmulas y trminos arbitrarios: cualquier relacin funcional obteni-da entre conceptos que sean expresables en el sistema es ella misma expresable y probable en el sistema. Hace tambin una aplicacin a la jerarqua de frmulas de segundo orden. Y una tercera sobre un problema de axiomatizabilidad: para un sistema de primer orden exis-te un sistema axiomtico del tipo deseado si y slo si se satisface una cierta condicin de la teora de modelos.

En el mismo nmero de la revista indicada Craig publica, en las pgs. 250-268, otro artculo [Linear rea-soning. A new form of the H-G theorem), donde expone cmo se puede pasar del nivel libre de cuantifcadores al nivel cuantificacional. En el teorema de Herbrand o en . el Hauptsatz de Gentzen extendido se afirma que vale una cierta relacin entre las estructuras de A y A', si A implica a A' (i.e., A3A' es vlida) y adems A es una conjucin y A' una disyuncin de frmulas de pri-mer orden en forma normal prenex, pero desgraciada-mente la relacin est descrita de vina forma indirecta, relacionando A y^A' con una tautologa libre de cuanti-fcadores. Y sto es precisamente lo que resuelve Craig en este artculo. (Para estas cuestiones ver Mostoinski, Thirty 'years of foundational studies, Oxford, 1966, pgs. 43-50).

La lnea del teorema de H-G es una base funda-mental para la construccin de programas para la prue-ba de teoremas con ordenadores, la otra lnea es la de las tablas semnticas de Beth. La obra de este autor tiene especial inters en el perodo preparatorio de al-gunos de los primeros programas.

Si queremos que una teora deductiva sea lo ms simple posible, es preciso tener un mtodo que nos permita garantizar la independencia de los trminos pri-mitivos, como se hizo anteriormente con los axiomas. Para conseguir sto, Beth parti del mtodo de las defi-niciones de Padoa (1901), que consiste en la construc-cin de un modelo apropiado (artculo de 1953, citado antes). Estaba preocupado por aplicar los resultados del anlisis de la teora de modelos a la teora de la prueba, por aplicar la semntica al anlisis de las teoras deducti-yas; en concreto, como se ver en un artculo que co-mentar despus (On remarks...), estaba preocupado por encontrar un procedimiento de decisin para la validez intuicionista de las frmulas clsicas vlidas (Kleene le demostr luego que no exista tal procedimiento).

Comenzar por algunas observaciones sobre el pro-blema de la decisin. El problema se puede reducir a dos casos fundamentales: Hay un mtodo general que nos permita decidir- si una expresin dada U es una tesis o no.'' Hay un mtodo general que permita deci-dir, para- cualquier conjunto D de expresiones, si una expresin U dada est contenida en K(D) o no?.

El teorema de Church (A note on the entscbeidungs-prqblem, Journal of Symbolic Logic, vol. 1, 1936, pgs. 40-1 y 101-2) obliga a excluir la posibilidad de una so-lucin general para ambos casos. De ah que la investi-gacin haya ido en direcciones particulares. Beth apunta tres (Les Fondements logiques des mathmatiques, Pars, 1955, pgs. 52-3, 41):

1) La investigcjh de una solucin para clases es-peciales de expresiones (los primeros resultados fueron los de Skolem, 1919, y los de Behmann, 1922).

ter 2) La investigacin de casos particulares cuyo carc-

insoluble es demostrable.

3) La reduccin del problema de la decisin para ciertas clases de expresiones al mismo problema para otras ciases (el primer resultado fue el de Lwenheim, 1915).

Ms recientemente J. Friedman (A computer program for a solvable case of the decisin problem, Journal of the ACM, 1963, pg. 348 vol. 10) apunta tres direcciones para mitigar los efectos del teorema de Church:

1) Restriccin de la clase de expresiones que ha de ser considerada de modo que se abtengan casos solu-bles;

2) Construccin de procedimientos de prueba que reconozcan eventuaknente cualquier teorema, pero que pueden proceder indefinidamente para un no-teorema;

3) Construccin de procedirnientos de semi-deci-siti, que incluyan procedimientos de decisin para sub-clases que se sabe que son solubles y que, confrontadas con expresiones fuera de esos casos, pueden reconocer un teorema o fallar en el intento de alcanzar cualquier decisin.

Friedman mismo trabaj en la lnea de esta tercera orientacin, llegando a las conclusiones de Church y Ackermann.

El fondo de estas investigaciones reposa sobre H-no-cin de calculabilidad efectiva, dndose pasos decisivos en la dcada de los aos 30, pero sus orgenes se re-montan a 1923 (Skolem). Fueron los trabajos de Godel en 1931 los que le dieron un gran impulso, aunque anteriormente se haban emitido ideas anlogas (M., Finsler y T. Brodn, 1926). Desde diferentes puntos de partida se ha llegado a conclusiones equivalentes, que se pueden resumir as:

a) Funciones computables-/U, ssi funciones computa-' bles-Turing;

b) Funciones computables o algoritmo ssi funciones computables en sentido intuitivo;

c) Funcin recursiya-At ssi funcin recursiva;

d) Funciones definibles 'V -K ssi funciones computa-bles;

e) Funcin recursiva-/u. (computable) ssi funcin de-finible.-7-k

As se ha podido definir con precisin matemtica las nociones de algoritmo, procedimiento efectivo, etc. (Ver Thirty years, de Mostowski).

Entre 1951 y 1955 Beth se mueve en el contexto del tercer tipo de investigaciones del problema de la

88 EL BASILISCO


decisin que apunt antes.En 1955 da publicidad en dos escritos (Remarks on natural deduction, Nederl. Akad. Wetenschap. Proc. Ser. A, 1955, vol. 58, pgs. 322-5; Semantic Entailment and Formal Derivability, ibid., vol. 18, Afdel Letterk. Med., pgs. 309-42) a su mtodo de las tablas semnticas. Al final del primero de estos dos artculos razona la cuestin de la decisin para su siste-ma formal F (al que llama tambin sistema de deduc-cin natural por su similaridad con los sistemas cons-truidos por Gentzen, Ketonen, Schtte, Kleene, Curry, Quine, y por sus estrechas conexiones con una aproxi-macin semntica a los problemas de la lgica): en vis-ta de que no podemos decidir si una tabla es cerrada o no por una interpretacin en la que introdujramos indi-viduos en la serie de frmulas que constituyen la derivacin, busca una salida tomada de la lgica intui-cionista de Heyting. Piensa que restringiendo adecua-damente las reglas del sistema formal F, obtenemos un sistema intuicionista correspondiente F'. Supongamos ahora que tenemos una derivacin D en F, cuyo nme-ro crtico sea n. Entonces el problema de si hay o no una derivacin anloga en F' (es decir^ una derivacin que comience con las mismas premisas y llegue a la mis-ma conclusin) D', qu tenga el mismo nmero crtico n, se reduce a un problema concerniente a la derivabili-dad en el clculo intuicionista sentencial y, por tanto, puede decidirse efectivamente, sobre la base de un resultado de Gentzen.

En 1958 Church escribe An Unsolvahle Problem of Elementary Number Theory (Amer. Jounal of Mathem., pgs. 345-363), de donde se puede concluir que no puede existir procedimiento efectivo para determinar en general, si es verdadero o no que K n > 0 , para todo n; y, en general, que no puede existir procedimiento efec-tivo para la construccin de interpretaciones de sen-tencias.

El mtodo de las TABLAS SEJMANTICAS tiene su base en los contra-ejemplos clsicos, en la entasis aris-totlica. Quine comunica a Beth que Hintikka haba de-sarrollado tambin simultneamente ideas semejantes (Two papers on Symbolic Logic, Acta Phil Fenn, Fase. VIII, Helsinki, 1955). En el postcripto de Semantic Entailment Beth explica sus diferencias con Hintikka: este no usa tablas semnticas y su tcnica consiste en la extensin de cualquier conjunto consistente de fr-mulas (cerradas) a un conjunto 'normal' completo y consistente. Tal tcnica tambin haba sido desarrollada previamente por Beth (e independientemente por Ha-senjaeger y Henkin) en 1951 (A topological Proof of the theorem of Ldwenheim-Skolem-Godel, Proceedings, 54; Some Consequences of the theorem of L'wenheim-Skolem-Godel-Nalcev, ibid., 56, 1953) y lo mismo las conexiones con los resultados de Gentzen y Herbrand {On Padoa's mthod, 1953) y en L'existence en mathematiques, Pars, 1955).

En Semantic Entailment (pgs. 9-10) presenta las ca-ractersticas de su mtodo:

1) Est en completa armona con el punto de vista semntico, en cuanto ha sido obtenido por transforma-cin de una tabla, establecida sobre la base de conside-raciones semnticas concernientes al significado de las palabras todo, alguno, no, y, si... entonces.

2) En total acuerdo adems con el punto de vista de una teora formal de la derivabilidad, pudiendo alter-nativamente ser construido como una secuencia de apli-caciones de ciertas reglas de inferencia, que pueden ser formuladas en trminos puramente topogrficos, sin referencia alguna al significado de las sentencias (o fr-mulas) a las que esas reglas se aplican.

3) Sigue muy estrechamente la manera en que ar-gimos, cuando no intentamos adaptarnos a ninguna teora lgica preconcebida. Al construir un cierto siste-ma de Deduccin Natural como el dado, primero por Gentzen y luego por otros autores (Curry, Schtte, Hasenjaeger, Kleene, Feys) obtendramos una sistematizacin de los principios, fortaleciendo su deri-vacin y todas las similares. Curiosamente, sin embargo, esos autores estuvieron guiados en sus construcciones por consideraciones pertenecientes a la teora formal de la derivabilidad ms que por concepciones semnticas. Por su parte, Carnap, Popper, Quine y Scholz constru-yeron la teora de la derivabilidad sobre la base de con-sideraciones semnticas, pero no establecieron las estre-chas conexiones entre la semntica y la teora de la derivabilidad que Beth intentar hacer.

4) Satisface automticamente el principio de las subfrmulas de Gentzen, en cuanto que la construccin de la tabla original consiste en disolver las premisas y la conclusin en subfrmulas ms pequeas. Por tanto, los resultados del Teorema de Herbrand, el Teorema de Lwenheim-Skolem-Gdel, el Teorema de las subfr-mulas y el Hauptsatz extendido de Gentzen, el Teore-ma de Consistencia de Bernays, son obtenidos fcilmen-te desde el punto de vista de Beth. Al mismo tiempo, su aproximacin realiza considerablemente la concep-cin de un mtodo puramente analtico, que ha jugado tan importante papel en la historia de la lgica y la filo-sofa.

En La Crise de la raison et la lgique (Pars, 1957; conferencias en la Universidad de Lige, mayo del 6G) establece un Teorema de frmulas parciales paralelo "al de Gdel, pero que incluye al mismo tiempo el Haup-tsatz, Teilformelnsatz, erweiterter Hauptsatz de Gen-tzen (pg. 38). Sigue preocupado por la aplicacin del mtodo de las tablas a la lgica intuicionista (pg. 44).

En Quelques remarks sur la semantique (1956) indica que un punto de partida para una lgica terica consiste en construir tablas semnticas que, si cierran, son sus-ceptibles de transformarse en deducciones formales per-tenecientes a un cierto sistema de deduccin natural F, semejante al sistema NK de Gentzen.

Posteriormente, en 1959 (Considrations heuristiques sur les mthodes de deduction par sequences, Logique et Ana-lyse, pgs. 153-9), intenta dar una explicacin de la es-tructura de los sistemas LJ y LK de Gentzen, elucidan-do dos puntos: la introduccin de secuencias con varias frmulas en el consecuente y la obtencin de un clculo intuicionista limitando el nmero de frmulas del con-secuente a una (o cero).

Al ao siguiente, aunque todava no ha desarrollado la teora cuanticacional, llega a conclusiones importan-tes desde su mtodo (Logique inferentielle et logique biva-

EL BASILISCO 89


lente de l'implication, Math, du XX sicle, 1960, vol. I, pgs. 11-23). Es, sin embargo, interesante constatar que, ya. al nivel extremadamente elemental en que nos hemos movido e incluso al nivel de la pura lgica de la implicacin, dimos forzosamente con dos sistemas lgi-cos distintos, que hemos llamado lgica inferencial y l-gica bivalente. El desarrollo de la lgica bivalente pro-duce la lgica clsica, mientras que el desarrollo parale-lo de la lgica inferencial da lugar a la lgica intuicio-nista de Brouwer y Heyting. La adjuncin del esquema iij" (V:K/F:L', Z//V:Z), o de un principio equivalente (por ejemplo, la ley de Peirce: 0 /(((A^ B)-^ A)-^ A) bastan para pasar de la lgica intuicionista a la lgica clsica. En consecuencia, la distincin entre lgica intui-cionista y lgica clsica se encuentra, por as decir, al nivel de la pura lgica de la implicacin (pg. 22).

En sntesis, el proceso que sigue Beth es el si-guiente:

1. Tabla deductiva cerrada.

2. La deduccin natural obtenida por la conversin de una tabla deductiva cerrada.

3. La tabla semntica cerrada.

4. La tabla semntica cerrada suplementada.

5. La deduccin natural obtenida por la suplemen-tacin y conversin de una tabla semntica cerrada.

1 y 2 son equivalentes: lgica intuicionista.

3, 4 y 5 son equivalentes: lgica clsica (o de dos valores).

La lgica clsica es ms fuerte que la lgica inferen-cial en el siguiente sentido: toda deduccin que es infe-rencialmente posible es tambin clsicamente posible. Las deducciones correspondientesia la secuencia 0/((A-^ B)^- A)-^ A (ley de Peirce) y a la secuencia 0/(Ex)((Ey)A(y)->A(x)) (ley de Platn) son clsicamente realizables, pero no inferencialmente (Aspects of Modern Logic, Dordrecht, 1970, p. 36).

En la misma pgina del artculo de .1960 citado un poco ms arriba seala adems que la construccin de la lgica por los mtodos discutidos en este estudio constituye una cierta sntesis de tres tendencias dispa-res, a saber:

1) La dea de una lgica pura de la implicacin (Tarski, antes de 1930).

2) La introduccin por Gentzen y Jasjowski (1934) de los mtodos de deduccin por secuencias.

3) Los intentos de relacionar la teora de la deduc-cin formal con la interpretacin semntica de los sm-bolos lgicos por varios autores (Beth, Hintikka, Kan-ger, Schtte, desde 1955) (Hintikka, A New Approach to sentencial Logic, Soc. Se. Fenn. Commentationes physico-mathematicae, vol. 17, n. 2, 1953; Notes on Quantifica-tion Theory, ibid., vol. 17, n. 2, 1955; Two Papers on Symholic Logic, Acta Phil. Fenn., voL 8, Helsinki, 1955;

K. Schtte, Ein System des vernpfendes SchUessens, fr Mathematische Logik und Grundlagenforschung, 2, 1956; Beweistheorie, Berln, 1960; S. Kanger, Provahility in logic, Stockhokn, 1957; tambin la disertacin, no publicada, del discpulo de Shannon, Trenchard More, 1956).

Las primeras axiomatizaciones de la lgica partan de principios aparentemente arbitrarios, cuya base se-mntica se vea despus; ahora, al revs, el mtodo de Beth permite desgajar la deduccin formal partiendo de la interpretacin de los smbolos lgicos (Aspects, pg. 21).

H. Leblanc ya llam la atencin en 1957 acerca de la importancia del razoniiento indirecto como medio de evitar complicaciones al transformar las tablas cebra-das en deducciones formales. Ideas que desarrolla Beth en Observations au sujet du raisonnement indirect (Logic et Analyse, 1961, pgs. 166-173). Hay un prejuicio negati-vo (Schopenhauer, Goblot, R.L. Goodstein, Bouligand y Desgranges, E. Lefebvre, etc.) sobre el razonamiento in-directo, de manera que, incluso en ios casos en los que resulta ms natural, tiende a convertirse en directo: slo servira para establecer una conclusin negativa. En el presente estudio, dice Beth, me propongo analizar las circunstancias que explican por qu, incluso para una conclusin afirmativa, se impone frecuentemente un ra-zonamiento indirecto y su conservacin en un razona-miento directo se vuelve difcil (pg. 166). Esta idea ha sido incorporada en la estrategia de los programas para la prueba de teoremas lgicos.

Antes de resear los artculos en los que Beth hace observaciones acerca de la mecanizacin de la prueba de teoremas har un resumen bibliogrfico, siguiendo el orden cronolgico, de los principales artculos y libros en los que expone el mtodo de las tablas:

1.a. Remarks on Natural Deduction, 1955. b. Semantic Entailment and Formal derivability,

1955 (fundamental).

2. La crise de la raison..., 1956.

3. a. Considerations heuristiques sur les mthodes de deductions par sequences, 1959.

b The Foundations of Mathematique. A Study of philosophy of Science, North-Holland, Amster-dam, 1959 (sda. ed., 1968, pgs. 177-200).

4. Logique infrentielle et logique Bivalente de l'implica-tion, 1960.

5. Observations au sujet du raisonnemaent indirect, 1961.

6. Formal Methods, 1962 (pgs. 9 ss/122 ss).

7. Aspects, 1970 (pgs. 22-62). 8. Quelques remarques sur la smantique, Rev. phil. de

Lou'vain pp. 607-625, 54, 1956.

Seguramente la mejor discusin de las tablas de-ductivas la hizo Beth en Logique infrentielle..., reescrita en Formal Methods.

90 EL BASILISCO


E.M. Barth realiz un arreglo sistemtico de las re-glas de Beth para sus tablas semnticas (On the transfor-mation of closed semantic tableaus into natural and axioma-tic deductions, Logique et Analyse, 1966, pgs. 147-170), donde retoma a Gentzen. En sus libros y artculos E.W. Beth ha subrayado frecuentemente que es siempre posible transformar una tabla semntica cerrada para una secuencia K/Z, con una frmula Z en el consecuen-te, en una deduccin natural de un tipo muy similar a los sistemas N de Gentzen. Con respecto a la lgica implicacional estn suficientemente claras las reglas con las que se puede realizar esta transformacin. Pero cuando salimos de este marco el sistema de reglas nece-sario se presenta en la obra de Beth slo de una forma ms bien embrionaria. La razn de esto se basa en el hecho de que Beth nunca present el mtodo de las ta-blas deductivas sistemticamente, excepto para la lgica implicacional, mientras que la conversin de una tabla semntica en una deduccin natural consistir en gene-ral en aadir ciertas frmulas, de modo que pueda leer-se como una tabla deductiva. Si se hace sto correcta y sistemticamente, la transformacin subsiguiente de una tabla deductiva en una deduccin natural es totalmente trivial. Ms precisamente, una tabla deductiva cerrada es una deduccin natural, presentada en una disposicin grfica especial (pg. 147).

Rafael Beneyto desarroll la transformacin de las tablas semnticas de Beth en las tablas analticas de Smullyan (Smulyan, First-Order Lgic, Berln, Springer-Verlag, 1968) (R. Beneyto, Laberintos analticos, Teore-ma, dic. 1971; Arboles, lgica y mecanismos de decisin, ibid. III/2-3, 1973, pgs. 289-313). En la misma lnea de Beneyto, G. Coray, Intelligence Artificille, Lausanne, Mai, 1973, cap. II, pgs. 82-112).

Intentar ahora resear algunas observaciones de Beth acerca de la mecanizacin de la prueba de teore-mas (On machines which prove theorems, Simn Stevin 32 y Formal methods, cap. VII, pgs. 112-121; On the so-called 'thought machine', Aspects, cap. V, pgs. 63-74; indirecta-mente. Considerations about logical thought, ibid. cap. IX, pgs. 118-139; Observations concerning computacin, deduc-tion, and heuristics, en Computer Programming and For-mal Systems, eds. P. Braffort y D.. Hirschberg, Amster-dam, 1967, pgs. 21-32).

Una lnea de investigacin es la de la INTELIGEN-CIA ARTIFICIAL, que parte de la obra de Newel y Simn (The Logic Theory machine-A complex information processing systems, IR Transactions on information theory, vol. IT-2, n. 3, Sept. 1956, pgs. 61-79; Newel, Shaw, Simn, Empirical explorations of the logic theory-machine. Frac, of the Wester Joint Computer Conf, feb. 1957, pgs. 218-230; Programming the logic theory machine, ib. pgs. 230-240; Report on a general problem-solvifrg program, Proc. of the Intern. Conf. on Inform. Processing, Unesco House, Pars, 1959, pgs. 256-64) y luego la de H. Ge-lernter (& N. Rochester, Intelligent behavior in problem-solving machines, IBM Journal of Research ad Develop-ment, vol. 2, n. 4, Oct. 1958, pgs. 336-345; y varios sobre teoremas de geometra).

Newel y Simn partieron del llamado BRITISH MUSEUM METHOD, que se basa en el principio de sustitucin, pero equipndolo (para evitar excesivo con-

sumo de tiempo y memoria) con recursos heursticos, que permiten seleccionar las sustituciones ms adecua-das de cara al xito de la prueba. Estos recursos se to-man de la manera en que el hombre usa su inteligencia en situaciones similares. Una descripcin de este mto-do se puede encontrar en la obra citada de Newel y Simn, en S. Kanger {A simplified pro'of method for ele-mentary logic, en Computer Programming and Formal Sys-tems, pgs. 7), y en Ana Mara Torres (Los primeros in-tentos de prueba automtica de teoremas en el clculo de enunciados, Teorema, vol. IV/4, 1974, pgs. 490-7). El resultado de tal mtodo fu la prueba de 38 problemas de 52 del captulo 2 de los Principia Mathematica (por el algoritmo de Hao Wang se tarda V2 minuto).

Beth estudia la aportacin de sus tablas semnticas al problema de la mecanizacin de las pruebas, como una investigacin sobre la deduccin formal. Se inclina ms por los mtodos algortmicos que por los heursti-cos, opinando que van ms de acuerdo con la lnea his-trica de la lgica.

Sobre la base de la obra de Kanger y la de Beth, D. Prawitz y N. Voghera (A Mechanical Proof Procedure and its Realization in an Electronic Computer, Journal of ACM, vol. 7, n. 2, Abril, 1960, pgs. 102-128) realiza-ron un programa para una computadora electrnica (Facit EDB de la AB Atvidabergs Industrier de Stock-holm) por el que es posible instruir a esta mquina para que realice deducciones del clculo de predicados. La mquina realiza un nmero simple de deducciones. Lo importante es que ha simplificado bastante los mtodos de deduccin, que pueden ser continuados con mqui-nas ms potentes. Una investigacin similar es la de

EL BASILISCO 91


P.C. Gilmore (A program for the production of proofs of theorems derivable within the first order predcate calculus from axioms, Proceed. of the First Intern. Conf. on Inform. Processing, Unesco House, Pars, 1959, pgs. 265-273), que tiene en cuenta tambin los mtodos de Hintikka y la aplicacin a teoremas de la geometra euclidiana de la investigacin de Gelernter y Rochester (Intelligent beha-vior in prohlem-solving machines, IBM Journal of Research and Development, vol. 2, n. 4, Oct., 1958. Pgs. 336-345).

Beth seala que las tablas semnticas cumplen el principio de las subfrmulas: todas las frmulas que aparecen en una deduccin de una tesis U son subfr-mulas de U. Principios que satisfacen de una forma muy dbil los sistemas de deduccin axiomtica tipo Hilbert (que usaron Newei y Simn), donde las sustitu-ciones se multiplican enormemente (a pesar de recursos como el de Lyndon, que distingue entre subfrmuias positivas y negativas) y los sistemas de deduccin natu-ral tipo Gentzen (NK), que incluyen, en la deduccin de una frmula, adems de sus subfrmuias, las nega-ciones de stas.

Parece claro que el mtodo de las tablas semnticas tiene ventajas sobre los indicados, pero la complicacin principal se relaciona con el teorema de Church (1937): no hay procedimiento de decisin para la lgica ele-mental. Beth razona entonces as:

Est claro que el nmero n (U) de parmetros indi-viduales a, b, c, que tiene que ser introducido al in-tentar deducir una frmula dada U es aqu el factor crucial. Una vez que ha sido fijado n (U), la construc-cin de una tabla semntica se reduce a un procedi-miento finito. Por tanto, el problema de simplificar esta construccin (o, en cualquier caso, de evitar complica-ciones innecesarias) nos lleva a dos problemas parciales:

Por consiguiente, si fijamos, de una vez por todas, n (U), de tal manera que, siempre que una frmula U sea deducible, puede acabarse su deduccin introducien-do a lo ms n (U) parmetros individuales. Sin embar-go, sto implicara la existencia de un procedimiento de decisin efectivo, cosa excluida por el teorema de Church.

La nica solucin es hacer una seleccin inteligente del orden relativo en que hay que hacer las operacio-nes, de modo que se simplifique la construccin.

La aplicacin mecnica (no sistemtica) del mtodo de las tablas har que introduzcamos demasiados par-metros y que se agote la capacidad de la mquina, si la tabla no cierra. Por tanto, hay que evitar operaciones intiles (problema 2). Para ello deben tenerse en cuenta los diferentes tipos de problemas que tiene que manejar la teora lgica de la mquina.

a) Inspeccionar una prueba dada.

b) Probar un teorema dado sobre la base de su-puestos dados.

c) Descubrir teoremas deducibles de los supuestos dados.

Respecto a (a): tenemos que estimar el nmero y tipo de ios parmetros individuales que tienen que ser introducidos. Respecto a (b): tenemos que proporcionar a la mquina recursos heursticos. Hay casos de proble-mas de decisin que son solubles: para ciertas clases de frmulas U pueden ser efectivamente computado un nmero n (U). Es preciso ayudarse de un anlisis esta-dstico de la distribucin de las operaciones, proporcio-nndole a la mquina las ms adecuadas de cara al xito. Y lo mismo para el caso (c): evitar los resultados triviales.

>*

Documents

Bas 10210