Grupo Editorial Ediciones Futuro Serie Científica de la Universidad de las Ciencias Informáticas (SC-UCI) Vol.: 3, No. 9, Año 2010 http://publicaciones.uci.cu/index.php/SC

Artículo original

Sistema para generar ejercicios de simplificación de tablas de la verdad y sus soluciones System for generate exercises of true table simplifications and its solutions Reynel Fals de Pedro1, Yenisleidy Piloto Lastra2 y Ronald Ugas Lago3 1

Departamento de Sistemas Digitales. Facultad 7. Universidad de las Ciencias Informáticas

2

Departamento de Programación e Ingeniería de Software. Facultad 4. Universidad de las Ciencias Informáticas

3

Departamento de Sistemas Digitales. Facultad 7. Universidad de las Ciencias Informáticas

{rfals, ypiloto, rugas}@uci.cu

Resumen Este sistema brinda la posibilidad de crear un conjunto de formas normales o tablas de la verdad de manera aleatoria y los soluciona paso a paso. Los ejercicios y sus soluciones quedan plasmados en un fichero LaTeX y pdf. El objetivo es dotar a los profesores de una herramienta para generar nuevos ejercicios y tener las soluciones detalladas. El programa está diseñado para que un profesor cree de manera automática una guía de problemas de circuitos lógicos y su solución. Se puede además dar soluciones a problemas específicos a partir de la tabla de la verdad, por lo que puede ser usado como herramienta para escribir libros de Matemática Discreta, Lógica, Electrónica Digital, Máquinas o Arquitectura de Computadoras, gracias al empleo de una salida en el lenguaje de marcado LaTex.

Palabras clave: circuitos lógicos, desarrollo de herramientas, generación automática de ejercicios de clase, lenguajes de marcado LaTex, mapas de karnaugh, procesador de textos LaTeX, redacción de textos

Grupo Editorial Ediciones Futuro Serie Científica de la Universidad de las Ciencias Informáticas (SC-UCI) Vol.: 3, No. 9, Año 2010 http://publicaciones.uci.cu/index.php/SC

Abstract This system offers the possibility of creating a set of normal forms and truth tables randomly and solved step by step. The exercises and their solutions are embedded in a LaTeX file, and / or pdf. The aim is to give teachers a tool to generate new exercises and have detailed solutions. The program is designed for a teacher to automatically create a troubleshooting guide and solution logic circuits. It can also provide solutions to specific problems from the truth table, so it can be used as a tool for writing books on Discrete Mathematics, Logic, Digital Electronics, Machines and Computer Architecture, through the use of an output LaTex markup language. The program is developed in PHP in four main blocks, the first to create all the exercises, the second resolves, the third writes the file and the fourth gives the user the possibility to interact with the presentation and content of the exercises and results. Keywords: Application development, automatic generation of class exercises, Karnaugh maps, LaTex markup languages, LaTeX word processor, logic circuits, text editing

Introducción En varias ocasiones el profesor se enfrenta al reto de crear diferentes ejercicios para repartir entre los estudiantes, en las distintas modalidades de evaluación. La principal dificultad reside en que si se aplican muchos ejercicios el profesor debe de resolver cada uno y contemplar las diferentes vías de solución. El otro problema, en el momento de crear múltiples ejercicios, es que corremos el riesgo de volver a generar uno que ya teníamos creado. En ciertos casos podemos resolver estos problemas asistiéndonos de una computadora: generando ejercicios de manera aleatoria y resolviéndolos de manera automática. Uno de estos casos favorables es la generación de ejercicios en forma de tablas de la verdad y formas normales, para su resolución en forma de expresiones simplificadas, circuitos lógicos y mapas de Karnaugh simplificados.

La forma de presentar los ejercicios y sus soluciones es mediante un pdf o código fuente en LaTeX que permite que sea distribuido de manera electrónica o impresa. Los fuentes (LaTeX) pueden ser modificado con posterioridad para refinar la presentación final a gusto del usuario.

Grupo Editorial Ediciones Futuro Serie Científica de la Universidad de las Ciencias Informáticas (SC-UCI) Vol.: 3, No. 9, Año 2010 http://publicaciones.uci.cu/index.php/SC

El LaTeX es un conjunto de macros escritas en lenguaje TeX que permite presentar documentos con alta calidad tipográfica [Knuth, 1991].

Metodología Computacional El sistema que se propone genera varios ejercicios del orden variables, hasta el momento

donde

es la cantidad de

, se toma la mitad (0.5) para rechazar la creación de los

ejercicios más obvios de resolver. Por ejemplo esto evita que existan ciertas combinaciones para como (0, 0, 0, 0) o (1, 1, 1, 1). La base 3 indica que se tienen en cuenta también las combinaciones opcionales.

Fig. 1. Entrada del cliente para una solución particular.

El sistema se compone de cuatro bloques principales: el primer bloque genera los ejercicios mediante la generación al azar de un número que se almacena en una lista donde este no puede estar previamente, este ciclo se repetirá hasta alcanzar la lista el tamaño correspondiente a la

Grupo Editorial Ediciones Futuro Serie Científica de la Universidad de las Ciencias Informáticas (SC-UCI) Vol.: 3, No. 9, Año 2010 http://publicaciones.uci.cu/index.php/SC

cantidad de ejercicios deseados. Luego cada número es codificado en base 3 obteniéndose una secuencia de 0, 1 y 2 de tamaño

donde 0 representa las salidas "apagadas", 1 las salidas

"encendidas" y 2 las salidas en las que no importa su estado. Tabla 1. Tabla de la Verdad generada por el sistema.

Fig. 2. Forma disyuntiva normal abreviada generada por el sistema sobre la base de la Tabla 1.

Fig. 3. Forma conjuntiva normal abreviada generada por el sistema sobre la base de la Tabla 1.

El segundo bloque resuelve un ejercicio determinado pasándole una lista de números entre 0 y 2 (la salida del bloque 1). También se debe decir si la vía de solución es a partir de una forma disyuntiva (1) o conjuntiva (0), por defecto se toma la primera. A partir de estos datos se explora de manera recursiva las vecindades de un mapa de Karnaugh mediante la obtención de nuevas posiciones donde cada nueva posición es igual a la posición actual en O exclusivo (⊕) con un donde

, se observa si esa posición contiene algún valor igual a la actual o igual

a 2 (salida opcional), si es así esté será la nueva posición actual y se adicionará la posición al posible clúster, se repetirá el proceso hasta que

; entonces se comprobará si ese posible

clúster (o lista de posiciones) es un clúster en realidad, en caso afirmativo se adiciona a la lista de

Grupo Editorial Ediciones Futuro Serie Científica de la Universidad de las Ciencias Informáticas (SC-UCI) Vol.: 3, No. 9, Año 2010 http://publicaciones.uci.cu/index.php/SC

clústeres en caso contrario se extrae del posible clúster la última posición añadida (pop de la pila). En un paso posterior se remueven los clústeres internos, es decir, se borran los clústeres que son subconjuntos de otros mayores. El objetivo principal de este bloque es obtener los clústeres que simplifican al mapa de Karnaugh, a partir de estos se pueden formar las ecuaciones que se simbolizan mediante dos listas de números que son las variables y las posiciones de las negaciones.

Fig. 4. Forma disyuntiva normal generada por el sistema sobre la base de la Tabla 1.

Fig. 5. Forma conjuntiva normal generada por el sistema sobre la base de la Tabla 1.

El tercer bloque manipula las secuencias obtenidas en el bloque 1 y los clústeres y ecuaciones del bloque 2 y escribe en un fichero los códigos LaTeX que permiten representar las tablas de la verdad, formas normales, mapas de Karnaugh, expresiones simplificadas y circuitos de compuertas básicas. Las tablas y los mapas se representaron mediante el array de LaTeX y los circuitos mediante la generación de código LaTeX para dibujar circuitos a partir de las macros m4 escrito por Dwight Aplevich (Aplevich, 2009). La representación de los clústeres en los mapas de Karnaugh se realiza a partir de escribir superíndices (*, \dag, \ddag, \S, etc.) en los elementos de las celdas del mapa y su coloreado para identificar rápidamente las agrupaciones o clústeres (Goossens, y otros, 1997).

Grupo Editorial Ediciones Futuro Serie Científica de la Universidad de las Ciencias Informáticas (SC-UCI) Vol.: 3, No. 9, Año 2010 http://publicaciones.uci.cu/index.php/SC

Fig. 6. Dos maneras de simplificar un mismo Mapa de Karnaugh generado por el sistema a partir de la Tabla 1.

El cuarto bloque permite interactuar con los restantes dejando que el usuario establezca la cantidad de variables, el número de ejercicios a generar, si desea resolver un ejercicio en particular, le da la posibilidad al usuario de organizar el orden o la existencia de determinadas representaciones, por ejemplo: ver la tabla de la verdad primero que la expresión simplificada, o ver sólo la expresión simplificada, le permite al usuario escribir encabezados de los ejercicios, y decidir si será un solo texto con ejercicios y soluciones intercalados (en un esquema ejercicio 1solución1, ...,ejerciciom-soluciónm) o diferenciados (en un esquema ejercico1-...-ejerciciom, solución1-...-soluciónm), provechoso para la escritura de guía de ejercicios o libros, o dos separados donde uno contenga los ejercicios en diferentes variantes y el otro sus soluciones, útil para evaluar a los estudiantes entregando la primera y conservando la otra el evaluador. El sistema está realizado en PHP 5, usando el IDE Zend Studio version 5.5.0, también se utilizó JavaScript. Se probó en una PC como servidor con sistema operativo Debian que tiene instalado m4, las Macros M4 para circuitos eléctricos, apache2 y latex.

Grupo Editorial Ediciones Futuro Serie Científica de la Universidad de las Ciencias Informáticas (SC-UCI) Vol.: 3, No. 9, Año 2010 http://publicaciones.uci.cu/index.php/SC

Fig. 7. El usuario puede seleccionar y ordenar que será escrito en el documento final.

Fig. 8. Dos expresiones simplificadas equivalentes a partir de las dos vías de simplificación representadas en la Figura 6.

Resultados y discusión El sistema se ha probado en la creación de 27 ejercicios asignando uno a cada estudiante de un aula. El pdf generado luego fue enviado por correo a la lista de distribución del grupo. Los estudiantes cumplieron la tarea asignada enviando las simplificaciones de los mapas, las expresiones finales y los circuitos que pudieron ser comprobados rápidamente con el fichero solución en poder del profesor. En otro grupo se efectuó una comprobación donde el profesor generó sólo las formas disyuntivas normales abreviadas de 4 variables. Distribuyó el material impreso en el aula, uno por estudiante, con la orden de simplificar el Mapa de Karnaugh. Los resultados se pudieron dar a medida que entregaban porque el profesor contaba con las dos variantes de respuestas para cada ejercicio.

Grupo Editorial Ediciones Futuro Serie Científica de la Universidad de las Ciencias Informáticas (SC-UCI) Vol.: 3, No. 9, Año 2010 http://publicaciones.uci.cu/index.php/SC

Usando esta herramienta se garantiza que cada estudiante tenga un ejercicio independiente del resto de los examinados y que el profesor pueda reconocer fácilmente un error en la solución ofrecida, aún teniendo un número alto de ejercicios diferentes que revisar.

Conclusiones El sistema posee la potencialidad de poder generar varios ejercicios que luego el profesor puede descartar si descubre que la solución es trivial con sólo ver la parte de la solución al ejercicio, esto promueve la velocidad a la hora de escoger uno o varios ejercicios para determinada evaluación, y brinda la facilidad que podemos pedir al programa que nos brinde las dos vías posibles de solución optima del ejercicio. Podremos imprimir directamente baterías a aplicarle al estudiante de este tema, o conformar un fichero fuente base en LaTeX que podremos usar en futuras publicaciones o presentaciones, sin necesidad de acudir a software específicos para diseño de circuitos. Y esto sin preocuparnos de nada excepto de cual es la tabla de la verdad origen del circuito a dibujar. La principal ventaja está en que no necesita fotografiar esta zona de la pantalla ni exportarla como imagen, porque ya está lista para ser usada en un pdf o para imprimir. También pudiera usarse como auto-examen, donde el estudiante genere sus preguntas en fichero aparte de las respuestas, las responda y compruebe.

Referencias APLEVICH, DWIGHT. M4 Macros for Electric Circuit Diagrams in LATEX Documents. [Documento] Massachusetts: MIT Press, 2009. ISBN 0-201-71993-3. BAKKEN, STIG SÆTHER, et al. Manual de PHP. Madrid: MediaFormación, 2001. ISBN: 4-201150520-1. BIGNELL, JAMES W. Y DONOVAN, ROBERT L. Electrónica digital. Azcapotzalco: Continental S.A., 1997. ISBN: 968-26-1307-8. CLEMENTS, ALAN. Principles of Computer Hardware 4th edition. New York: Oxford University Press Inc., 2006. ISBN: 0-19-927313-8.

Grupo Editorial Ediciones Futuro Serie Científica de la Universidad de las Ciencias Informáticas (SC-UCI) Vol.: 3, No. 9, Año 2010 http://publicaciones.uci.cu/index.php/SC

CONVERSE, TIM, PARK, JOYCE Y MORGAN, CLARK. PHP5 and MySQL Bible. Indianapolis: Wiley Publishing, Inc., 2004. ISBN: 0-7645-5746-7. CORMEN, THOMAS H., et al. 2003. Introduction to Algorithms. Massachusetts: MIT Press, 2003. ISBN: 0-262-03293-7. G. HARTKE, STEPHEN. A Survey of Free Math Fonts for TEX and LATEX. [en línea] 5 de Mayo de 2006. [Consultado el: 10 de julio de 2010]. Disponible en: [http://ctan.tug.org/texarchive/info/Free_Math_Font_Survey. ISBN: 6-9001-668903-8]. GOODMAN, DANNY. JavaScript Bible. Indianapolis: Hungry Minds, 2001. ISBN: 0-7645-4718-6. GOOSSENS, MICHEL, RAHTZ, SEBASTIAN Y MITTELBACH, FRANK. The LATEX Graphics Companion. Menlo Park: Addison-Wesley, 1997. ISBN 0-201-85469-4. GRAHAM, RONALD L., KNUTH, DONALD E. Y PATASHNIK, OREN. Concrete Mathematics. Massachusetts: Addison-Wesley, 1989. FGHIJK-HA-943210. ISSI CAMY, LÁZARO. JavaScript. Madrid: Anaya Multimedia, 2002. ISBN: 84-415-1384-8. KNUTH, DONALD E. 1998. The Art Of Computer Programming 3rd ed Vol. 2. California : AddisonWesley, 1998. ISBN: 0-201-89684-2. KNUTH, DONALD ERVIN. The TEXbook. New York: Addison-Wesley, 1991. ISBN 0-201-13448-9. LAMPORT, LESLIE. LATEX A Document Preparation System. California: Addison-Wesley, 1994. 2 3 4 5 6 7 8 9 10-CRW-97969594. SEDGEWICK, ROBERT. Permutation Generation Methods. New York: ACM, 1977, ACM Comput. Surv., Vol. 9, p. 137-164. ISSN: 0360-0300. PETERSEN, RICHARD. Fundamentos de programación en Linux. Bogotá: McGraw-Hill/Osborne, 2001. ISBN: 958-41-0230-3. RAMOS MONSO, MARTIN. Programación PHP Sitios web dinámicos e interactivos. Ciudad de Buenos Aires: MP Ediciones S.A., 2000. ISBN: 4-3330-5782-5. SEDGEWICK, ROBERT. Algorithhms. Massachusetts: Addison-Wesley, 1983. ISBN: O-20106672-6. SKIENA, STEVEN S. The Algorithm design manual. New York: Springer Verlag, 1998. ISBN: 0387-94860-0.

Grupo Editorial Ediciones Futuro Serie Científica de la Universidad de las Ciencias Informáticas (SC-UCI) Vol.: 3, No. 9, Año 2010 http://publicaciones.uci.cu/index.php/SC

VASWANI, VIKRAM. How to Do Everything with PHP & MySQL. New York: McGraw-Hill/Osborne, 2005. DOI: 10.1036/0071466541. VEERARAGHAVAN, SRIRANGA. Sams Teach Yourself Shell Programming in 24 Hours. New Delhi: Macmillan Computer Publishing, 1999. ISBN: 0672314819. WELLING, LUKE Y THOMPSON, LAURA. Desarrollo web con PHP y MySQL. Madrid: Anaya Multimedia, 2002. ISBN: 84-415-1578-7.