REVISTA DE LIBROS

KORFHAGE,ROBERT: Lgica y Algoritmos. Con aplicacionesa lascienciasde la computacine informacin.Mxico,Limusa-Winley,1970,222pp.

El presentelibro aborda una importante tarea dentro de la bi-bliografa de las ciencias de la computacin,ya que pretendehaceraccesible, a estudiosos no especializados,grandes parcelas de lalgica constructiva y de la teora de conjuntos.

En su totalidad podramos calificado de pedaggico-intuitivo,aunque a veces (por ejemplo en el captulo 2) efectaun desarrolloque no resulta ser ninguna de las dos cosas. En el mismo sentidodiremosque grandespartesde la obra que se comentasehallan salpi-cadasde alusionesinteresantes-a las paradojasde conjuntos,cap. 1,p. 14; a la denominacinde funcin por Leibniz, Apndice, p. 178;Y al uso del sistema numrico binario por los antiguosmatemticoschinos, p. 178- que le concedencierto dinamismo.

En el captulo 1, titulado "Conjuntos, relaciones y mapeos".ofrece en una apretada presentacin,los conceptos bsicos de lateora de conjuntos, primero de forma intuitiva y a continuacindesarrollndolos en un sistemaalgebraico.No nos pareceafortuna-da la denominacin del traductor "combinacin de conjuntos" paradesignarla definicin de las operacioneselementales-unin, inter-seccin,diferencia simtrica-, del mismo modo que en la aritmticaal conjunto de las operacioneselementalesno se les denomina glo-balmente "combinaciones de nmeros".

En el captulo 2 presentael autor un lgebra booleanaal modode la mayora de los tratadistas,definiendo a continuacin recursi-vamentelas funciones booleanaspara obtener una forma cannicade las mismas. Habra que subrayar que en el libro, que contieneuna amplia bibliografa, y referenciasa la misma, en este captulono se cita ni a Gdel ni a Kleene. Adems, contiene la descripcinde los mapas de Karnaugh aunque no su desarrollo completo, losmtodos de simplificacin de Quine y McKluskey y la aplicacin a,modelosfsicos -circuitos de distribucin- del lgebrabooleana.

En el captulo 3 el autor presentala lgica de enunciados,dondeincluye los teoremasde deducciny completud del clculo. En este

135

- - - --

,

136 Revistadelibros

,1'1 'I

captulo se atiende tanto el aspecto sintctico -axiomatizacin yderivacin-, como el semntico -consecuencia lgica y equiva-lencia-; y se le aade entre otras cosas la descripcin de la nota-cin de Lukasiewicz y del rbol de una frmula, ambos tpicos deespecial inters en el tratamiento de computadores.

En el captulo cuarto, se presenta brevemente la nocin den-tuplo ordenado de bits o vector binario con las operacionesarit-mticasusuales,y una referenciaa la codificacin, nocin importantecon vistas al almacenamiento de la informacin en las mquinaselectrnicas.

A travs de estos captulos que hemos comentado, el autorlogra escalonaradecuadamenteuna coleccin de conceptosanlogos-operaciones con conjuntos, operacionesbooleanas,clculo de co-nectivas- que llevan por buen camino al lector en una tarea tanimportante como es establecer, en su apreciacin, las relacionesentre varias reas de la lgica y las matemticas.

En el captulo cinco, parte primeramentede una definicin intui-tiva de algoritmo y de la descripcin de diagramas de flujo, paradespusdescendera un estudio corto, pero sistemticode dos con-ceptos no intuitivos de algoritmo -algoritmos de Markov y m-quinas de Turing ; finaliza con la presentacin del lenguaje deprogramacin MAD (Michigan Algorthm Decoder). Subrayaremosla ausenciaen este captulo de cualquier comentario sobre funcio-nes recursivas,de crucial inters tanto para la teora de algortmosen s, como para el hardware y software de los computadores.

En el captulo seis, se desarrolla un clculo de predicados deprimer orden, que contiene adems de los tpicos fundamentales-simbologa, validez, satisfacibilidad, forma normal prenex-, unsistema axiomtico, p. 163. En el captulo se hacen referencias alproblemade la indecidibilidad y, adems,incluye una versin divul-gatora del teorema de deduccin.

En el captulo siete, se presenta de manera sucinta la nocinde "sistema cannico de Post", a nuestro juicio demasiadoalejadoespacialmentede los restantes conceptos formalizadores de la no-cin de algoritmo. En la presentacinno se hace ninguna alusina la equivalenciaentre estos conceptosy por otra parte no queda,como en la mayora de los libros de lingstica, lo suficientementesubrayadala importancia de Post para la lingstica matemtica.Sse destaca en cambio la importancia de los Sistemas Cannicospara los lenguajes formales en general.

El libro se cierra con un breve pero bien trazado recorrido his-trico de los tpicos estudiados y con una coleccin de soluciones

--- -

Revistade libros 137

casi exhaustiva,de la gran cantidadde ejerciciosimportantesquecontiene.

En general,el libro logra cumplir el propsitodel autor en lamayoradesuspartes; y su edicinen castellanonospareceacerta-dsima ya que llena un hueco en el escasocampobibliogrficosobrela materia.

Julia Blasco

J. BARKLEY ROSSER: Simplified 1ndependencePro Of s.Booleanvaluedmodelsof set theory.New York andLondon: AcademicPress,1969,xi + 217pp.

J. Barkley Rosser es, sin duda, uno de los grandes lgicos denuestro tiempo. Su labor ha estado ntimamente ligada a la teorade modelos, donde su poderosaimaginacin creadora,aunada a superfecto dominio del instrumental lgico y matemtico,le ha con-ducido a obtener notables resultados.Baste recordar a este respectolos contenidosen sus diversostrabajossobre las "New Foundations"de W. V. O. Quine. 1

La presenteobra constituyeel primer intento de sistematizacinen la teora de modelos de valoresbooleanos(booleanvaluedmodel)oAntes de ella slo haba trabajos,debidos principalmentea Solovayy D. Scott, a los que, dado su carcter indito, era sumamentedi-fcil acceder.Por otra parte en ellos el objeto de atencin era msel modelo que sus posibles aplicaciones,en particular la referentea una pruebade la independenciadel Axioma de Eleccin (abreviadoen lo sucesivopor AE) y de la Hiptesis Generalizadadel Continuo(abreviado en lo sucesivo por HGC) que complementasela laborde K. G6del, 1940.2

Ya exista ciertamente una prueba de independenciatal, la deCohen;3 peroel mtodopor l empleado-el "forcing"(forzamien-to)-- iba revestido de una carga de complejidad que dificultaba

I Roser, J. B. "On the consistencyof Quine'sNew Foundationfor mathematicallogic", JSL, vol. 4 (1939), pgs. 15-24.

"The Burali-Forti paradox", JSL. vol. 7 (1947),pgs.1-17."The axiom of infinity in Quine's New Foundations",

JSL, vol. 17 (1952), pgs. 238-242.Wang, H. "Non-standard models for formal logics",

JSL, vol. 15 (1950), pgs. 115-129.2 G6del, K. The consistencyo{ the axiom o{ choice... Princeton

Univ. Press, 1940.3 Cohen,P. J. Set theoryandthe continuumhypothesis.New

York: W. A. Benjaminlnc., 1966.

-- -

f