CEM337165

Vista previa del material en texto

Instituto Tecnológico y de Estudios Superioires de Monterrey 
Campus Estado de México 
Estrategias Evolutivas para la Programación Lógica Inductiva 
Trabajo de investigación que, para obtener ei grado de 
MAESTRO EN CIENCIAS COMPUTA.CIONALES 
presentó lng. Jorge Adolfo Ramírez Uresti 
Siendo integrado el jurado por 
Dr. Juan Francisco Corona Burgueño: Presidente 
Dr. Héctor Saldaña Aldana: Secretario 
Dr. Isaac Rudomín Goldberg: Sinodal 
Dr. Osear Chavoya Aceves: Sinodal y Asesor 
B; 
Mayo de 1994. 
\ 
\ 
' 
, 
Indice. 
Resumen ...................................................................................................... 1 
Introducción ................................................................................................. 2 
Capítulo 1. Algoritmos Genéticos ................................................................. 5 
Capítulo 2. Programación Genética ............................................................... 15 
Capítulo 3. Cálculo Proposicional ................................................................. 24 
Capítulo 4. Lenguajes de Primer Orden ......................................................... 35 
Capítulo 5. El Sistema de Lógica Inductiva ................................................... 48 
5 .1 El programa F AMIL Y .LSP ......................................................... 50 
5 .2 El programa GAFBFCPl .LSP ......................... : ........................... 54 
5.3 El programa SEMAN.LSP .......................................................... 56 
5.4 El programa EEPPLI.LSP .......................................................... 58 
Capítulo 6. Resultados .................................................................................. 60 
Conclusiones ................................................................................................ 66 
Apéndice A. Resultados del Sistema. 
A. l Utilizando la primera función de mérito ...................................... 68 
A.2 Utilizando la segunda función de mérito ..................................... 72 
Referencias ................................................................................................... 77 
Bibliografia ................................................................................................... 79 
Resumen. 
El presente trabajo de tesis expone un Sistema de Lógica Inductiva mediante el 
cual se hacen evolucionar expresiones dentro de un lenguaje de primer orden. 
Se adapta el modelo de Programación Genética, desarrollado por Koza[4], para 
que utilice fórmulas bien formadas del cálculo de pn!dicados de primer orden 
como estructuras de procesamiento en la población. 
Las fórmulas son evaluadas de acuerdo a una función de mérito, diseñada 
especialmente para esta tesis, que permite obtener expresiones válidas en un 
universo de discurso dado. 
Las relaciones obtenidas por este Sistema de Lógica Inductiva permiten 
describir de una manera sencilla y concreta el universo de discurso analizado. 
Introducción. 
Los lenguajes de programación lógica (PROLOG) permiten manipular 
directamente el conjunto de relaciones y funciones existentes en determinada 
estructura, que se representan mediante fórmulas bien formadas del cálculo de 
predicados de primer orden. Una vez conocido un conjunto suficientemente 
grande de expresiones lógicas válidas (axiomas), e:s posible obtener otras, 
implícitamente contenidas en las expresiones de partida, usando los algoritmos 
de prueba. La definición de un sistema de esta naturaleza requiere del 
conocimiento previo de los axiomas, que se extraen a partir de un conjunto de 
observaciones (hechos), mediante un proceso todavía no muy bien 
comprendido, en el que, a diferencia del proceso común y corriente de 
inferencia lógica se va de lo particular a lo general, conocido como 
razonamiento inductivo. 
El estudio de los procedimientos formales de inducción se remonta a Carnap 
(1952), que desarrolló métodos estadísticos para validar propuestas teóricas 
dentro del cálculo de predicados de primer orden[2]. En las décadas de los 
setentas y los ochentas, Plotkin[6] y Shapiro[l4] desarrollaron sistemas de 
lógica inductiva dentro del cálculo de predicados de primer orden. Sin embargo 
los mayores éxitos fueron obtenidos dentro de los límites del cálculo 
proposicional; tal es el caso del algoritmo ID3[7,8], que utiliza el concepto 
informacional de entropía para la generación de un conjunto de reglas para la 
clasificación de objetos a partir del conocimiento de determinados atributos. 
En 1989 Quinlan describió el programa FOIL[9, 1 O] que es una generalización 
natural de ID3 para la generación de cláusulas de Horn de primer orden. Este 
sistema explota la información de un número muy grande de ejemplos para 
guiar la búsqueda de un programa. Un año después, Muggleton y Feng 
2 
desarrollaron el programa GOLEM[ 5] que genera cláusulas como la 
generalización condicional menos general de dos ejemplos en el contexto del 
conocimiento previo disponible, superando los resultados alcanzados con 
FOIL. A finales de 1991, Quinlan desarrolló su segunda versión de FOIL[ll] 
donde adaptó la estrategia de Muggleton llamada literales determinantes para 
poder desarrollar fórmulas de primer orden a partir de datos estructurados. 
Considerando que el concepto de generalización condicional menos general 
es intrínsecamente poco claro e implica la idea de optimización, el objetivo del 
presente trabajo de tesis es desarrollar un esquema de lógica inductiva basado 
en estrategias evolutivas, concretamente en el modelo de programación 
genética desarrollado por Koza para hacer evolucionar expresiones dentro de 
un lenguaje de programación de alto nivel. 
En el primer capítulo se hace una breve introducción a los problemas de 
optimización, recalcando ventajas y desventajas de las metodologías 
tradicionales para la solución de los mismos. Se describen brevemente a las 
Estrategias Evolutivas[l2,13] desarrolladas en Europa para pasar al modelo de 
Algoritmos Genéticos[3] en donde, se describen, con mayor detalle, los 
operadores de reproducción, cruzamiento y mutación. Finalmente, el capítulo 
termina explicando el teorema de los esquemas, base de los algoritmos 
genéticos. 
En el segundo capítulo, se explica el modelo de Programación Genética 
desarrollado por Koza[ 4]. Principalmente se hace énfasis· en las diferencias de 
este modelo con el de algoritmos genéticos, siendo la más importante, la 
referente al tipo de estructuras utilizadas para encontrar la solución de un 
problema de optimización. 
En el capítulo tercero se habla sobre Cálculo Proposicional haciéndose una 
pequeña introducción sobre la necesidad del mismo. Se define la estructura 
sintáctica, necesaria para la construcción de afirmaciones en un lenguaje lógico, 
y la estructura semántica, utilizada para interpre1¡ar las proposiciones del 
lenguaje. 
En el cuarto capítulo se introducen los Lenguajes de Primer Orden. 
Nuevamente, se hace un pequeño análisis de la nece:sidad de estos lenguajes y 
se definen los procedimientos para la construcción e interpretación de las 
Fórmulas Bien Formadas del Cálculo de Predicados de Primer Orden. Este tipo 
3 
de fórmulas se hacen evolucionar en el sistema desarrollado en este trabajo de 
tesis, para obtener nuevas fórmulas que describen una estructura concreta o 
abstracta. 
En el quinto capítulo se explica el sistema desarrollado: Sistema de Lógica 
Inductiva. Se justifica la selección de LISP como lenguaje de programación de 
alto nivel para la implementación del esquema desarrollado. Cada uno de los 
programas que conforman el sistema, es descrito en cuanto a su función dentro 
del sistema y su modo particular de operación. 
En el sexto capítulo, se describen los resultados obtenidos durante el desarrollo 
del sistema. Se analizan los resultados parciales y se justifican los cambios 
realizados a las primeras versiones del sistema para poder llegar a la solución 
delproblema planteado en esta tesis: desarrollar un. esquema de lógica 
inductiva basado en estrategias evolutivas para hacer evolucionar expresiones 
dentro de un lenguaje de alto nivel. 
Finalmente, se presentan las conclusiones a las que se 1lega con el desarrollo de 
ésta tesis. 
4 
Capítulo 1 
Algoritmos Genéticos. 
En computación, gran parte de los esfuerzos realizados tienen como objetivo la 
búsqueda de soluciones a problemas de optimización. Un problema de 
optimización se define como la búsqueda del mejor punto en un espacio n-
dimensional. Este punto ( o puntos) puede ser un valor máximo ( o mínimo) de 
una función a la que se conoce como función objetivo (función de mérito). 
Existen metodologías tradicionales para la solución de estos problemas de 
optimización que se pueden dividir en tres grandes ramas de acuerdo a la forma 
en la que obtienen la solución a un problema. 
Los procedimientos de búsqueda aleatorios, como su nombre lo indica, basan 
su estrategia en la generación, al azar, de puntos en el. dominio de definición de 
una función guardando aquél que más se acerque al óptimo (ej. en 
maximización se guarda el valor más alto). Naturalmente este tipo de 
algoritmos no son eficientes ya que, aunque pueden llegar a ser eficaces, si el 
espacio de búsqueda es demasiado grande, el tiempo necesario para encontrar 
la solución puede ser excesivo para que los resultados sean útiles. 
Los métodos más utilizados en la optimización de funciones son aquellos que 
utilizan información obtenida de la función objetivo que generalmente implica 
el cálculo de derivadas de primero y segundo orden. Los problemas surgen 
cuando estas nociones matemáticas no están bien definidas en todo el espacio 
5 
de búsqueda o cuando la topología del espacio es demasiado compleja y el 
algoritmo converja a un punto (mínimo o máximo) local. 
Para problemas con dominios discretos, se puede ver el problema de 
optimización como una búsqueda en un espacio finito de estados. Existen 
algoritmos para resolver este tipo de problemas, como el de búsqueda del 
primero en profundidad o el de búsqueda del primero en anchura, que generan 
estados en el espacio de búsqueda, a partir de un conjunto finito de reglas, 
hasta encontrar una solución al problema. La principal desventaja en este tipo 
de métodos es la explosión combinatoria, es decir, si e] dominio de la función a 
optimizar es demasiado amplio, el tiempo de búsqueda de la solución crece 
exponencialmente y por lo tanto los algoritmos dejan de ser eficientes. 
Una solución al problema de explosión combinatoria es utilizar una función 
heurística. Una función heurística permite guiar la búsqueda de la solución 
utilizando algún conocimiento a priori sobre el problema de optimización. Su 
principal desventaja es la posible pérdida de la solución si no se planteó 
correctamente la función heurística. 
En la búsqueda de algoritmos más robustos para la s,olución de problemas de 
optimización definidos sobre dominios discretos, e:n el sentido de que la 
solución sea encontrada en un tiempo aceptable, surgen las estrategias 
evolutivas y los algoritmos genéticos. 
Las estrategias evolutivas son desarrolladas en Europa por Rechenberg[l2] en 
1973, continuando este trabajo Schwefel[l3]. Son algoritmos que intentan 
reproducir los procedimientos naturales de evolución para la solución de 
problemas de optimización de parámetros. En esta metodología, se plantea la 
optimización de una función f:"Rn ~ "R, llamada la función objetivo, sujeta a las 
siguientes restricciones: g/x) ~ o VJ E{l, ... ,m} dondt: g
1
:"Rn ~"R. 
La estrategia más sencilla es la (1 + 1 )-ES. Utiliza una población conformada 
por dos vectores reales n-dimensionales denominados: padre e hijo, 
respectivamente. Inicialmente la población contiene un solo elemento, el padre: 
i' = (x;,---,x~); a partir de él se obtiene, por medio de operaciones de mutación, 
un hijo: x"=(x;+o1,···,x~+bJ=(x{:···,x~'), que junto con su ancestro será 
evaluado de acuerdo a la siguiente regla de selección: 
6 
J(x") ~ J(x') /\ ( Vj g/x") ~ o) 
entonces el hijo será considerado como padre en la siguiente generación, en 
caso contrario, continua el mismo padre. Este procedimiento se reitera hasta 
que se cumpla la condición de terminación. 
Existen otras estrategias llamadas (µ + 1) - ES, (µ + 2) - ES y (µ, 2) - ES que son 
generalizaciones del concepto (1 + 1 )-ES. 
Al tiempo que las estrategias evolutivas eran desarrolladas en Europa, 
surgieron en América los algoritmos genéticos en la Universidad de Michigan 
bajo la dirección de Holland[3]. 
Los algoritmos genéticos son procedimientos de búsqueda para la solución a 
problemas de optimización. Utilizan el principio darwiniano de sobrevivencia 
del individuo mejor adaptado, así como una serie de operaciones de 
intercambio entre estructuras de información para la obtención de la solución 
óptima a un problema determinado. 
A diferencia de otras metodologías de optimización de funciones, los 
algoritmos genéticos utilizan una codificación de los parámetros de la función 
(en vez de los mismos) mediante cadenas de caracteres. 
La codificación se realiza de la siguiente manera: 
• Se define la función objetivo f que se va a analizar. 
• Se determina otra función g, en base a los parámetros de la función, que 
asocie a una cadena de caracteres un punto en el dominio de la función 
objetivo. 
Estas cadenas se determinan entonces, en base a los siguientes lineamentos: 
• Se define un alfabeto L de cardinalidad K. 
• A partir del alfabeto generar cadenas de caracteres C (cromosoma) de 
longitud f que representen el(los) parámetro(s) utilizado(s) en la función 
objetivo f. 
7 
Un ejemplo de los conceptos anteriores es: maximizar la función J(x) = x + I en 
el inteivalo [0,255]. 
La función de codificación para este ejemplo es: 
l-l 
x= g(C) = ¿te; 
i=O 
En donde el parámetro x es representado por cadenas de caracteres 
C = ct_1ct-2 · · · c1c0 de longitud e = 8 definidas sobre el alfabeto binario L = { O, 1}. En 
base a esto, una posible cadena es: 
e= 00101101 
que representa a el punto x = 45 en el dominio de la función objetivo. 
La búsqueda de la solución en este tipo de procedimientos utiliza una población 
de puntos en vez de uno sólo y se guía mediante el valor de la función objetivo 
en cada uno de los puntos de la población. Estos hechos representan ventajas 
de los algoritmos genéticos sobre las metodologías tradicionales de 
optimización: 
1. Al analizar un conjunto de puntos, se reduce la posibilidad de que la 
solución sea un mínimo (máximo) local 
2. No es necesario conocer infonnación adicional de la función objetivo 
(derivadas, gradiente, etc.), que puede no existir. 
El algoritmo genético más simple, utiliza tres operaciones que se basan en la 
copia total, copia parcial e intercambio de infonnación entre los cromosomas. 
Esta operaciones son: 
• Reproducción. 
• Recombinación de la infonnación (Crossover). 
• Mutación. 
8 
El primer paso en un algoritmo genético, es generar una población de n 
cromosomas, de la misma longitud, de manera aleatoria. Esta población es la 
población activa durante todo el proceso de búsqueda. 
Durante el proceso de reproducción, las cadenas son copiadas de la población 
activa a otra población auxiliar del mismo tamaño. No todos los individuos en 
la primera población son copiados a la auxiliar. La copia de cada cromosoma se 
realiza de acuerdo a su valor en la función objetivo; con esta condición, se 
imita el principio de Darwin, de supervivencia del individuo mejor adaptado a 
un medio ambiente dado, y es conocida como: función defitness. 
La implementación de esta operación de reproducción se puede realizar de 
varias maneras de acuerdo a las necesidades de cada caso. Una de las opciones 
más sencillas de codificación resulta al utilizar la probabilidad que cada 
individuo en la población tiene de sobrevivir, de la siguiente forma: 
Sea P = ( x0 , x1,. • ·, x"_2 , x"_Juna población de n individuos. La probabilidad de 
supervivencia de cada individuo x esta dada por la función: 
i=O 
Para seleccionar los individuos a ser copiados a la población auxiliar, se genera 
un número de manera aleatoria y se le va restando el valor de fitness de cada 
cromosoma en la población activa, tomándolos, de manera secuencial. Cuando 
el número sea menor o igual a cero, se copia el individuo actual en la población 
activa a la población auxiliar. El proceso se repite el número de veces que sea 
necesario para que la población auxiliar contengan elementos. De esta manera, 
se tiene una población auxiliar que contiene los mejores individuos de la 
población activa. 
Una vez que se ha realizado la reproducción, el siguiente paso es la 
recombinación de la información. Este proceso consta de dos partes. Primero, 
se seleccionan de manera aleatoria, dos individuos de la población auxiliar 
obtenida durante el proceso de reproducción. Y a elegidos los individuos, se 
escoge al azar una posición J a lo largo de un cromosoma y, segundo, se 
9 
procede a intercambiar los caracteres de la pos1c1on 1 a la J del primer 
individuo en lugar de los del segundo y de la posición J + 1 a la e del segundo 
individuo en lugar de los caracteres del primero. Se: crean así dos nuevos 
cromosomas que reemplazan, a los dos seleccionados P3:fª recombinación, en 
la población auxiliar. Este operador se ilustra en la siguilente figura: 
Padres 
1100 
0001 
1111 
0110 
) 
Hijos 
11000110 
00011111 
La recombinación de información tiene como objetivo la creación de nuevos 
individuos a partir de aquellos que han demostrado ser los mejores de una 
población y de esta manera poder explorar nuevos puntos en el dominio de la 
función a optimizar. Se espera que los nuevos cromosomas sean mejores que 
sus antecesores. El siguiente es un ejemplo de esta opt::ración: 
Se tienen dos cromosomas de longitud e = 8 definidos sobre el alfabeto binario 
L = {0,1}: 
e1 = 11000010 y e2 = 10101000 
y se escoge al azar un punto J = 6 para realizar la recombinación de 
información. De acuerdo con lo anterior, se deben de reemplazar los caracteres 
de e1 de las posiciones 1 a la 6 en lugar de los de C2 , es decir, se toman los 
caracteres 110000 del primer cromosoma y se copian en lugar de los caracteres 
101010 del segundo cromosoma para obtener un nuevo individuo e;= 11000000. 
De igual forma se reemplazan los caracteres oo de e2 en lugar de los caracteres 
10 de e1 creando al individuo e;= 10101010. Finalmente se hace e1 = e; y 
e2 = e;. 
El último de los operadores por explicar es el de mutación. La mutación en los 
algoritmos genéticos es el cambio de un carácter de un cromosoma por otro 
carácter contenido en el alfabeto L. Volviendo al ejemplo anterior, la mutación 
resulta al cambiar un 1 por un o o viceversa. Generalmente esta operación se 
realiza al mismo tiempo que la recombinación de la inforn:iación en el momento 
en que se están copiando los caracteres de un cromosoma a otro. El objetivo de 
este operador es crear nuevos puntos, que no podrían ser obtenidos por simple 
10 
recombinación de la información, y así prevenir la posible convergencia 
prematura del algoritmo genético a un mínimo o máximo local. 
Para terminar de explicar el procedimiento básico de un algoritmo genético, se 
debe de definir la manera en que se desarrollan los eventos: 
1. Se crea una población aleatoria (población activa) de cromosomas de 
tamaño n. 
2. Se aplica el operador de reproducción a la población activa para obtener una 
nueva población (población auxiliar). 
3. Se aplica el operador de recombinación de la información a la población 
auxiliar. Si se desea se puede aplicar al mismo tiempo el operador de 
mutación. 
4. Se reemplaza la población activa por la población auxiliar. Queda por lo 
tanto, la población a la que se le aplicaron los operadores genéticos como 
población activa. 
5. Si se cumple la condición de terminación ir al paso 6, si no ir al paso 2. 
6. Terminar asignando como resultado del algoritmo genético la población 
activa o el(los) mejor(es) individuo(s) en ella. 
Debido a que el algoritmo genético analiza una serie de puntos en un tiempo t, 
se dice que la búsqueda que realiza es en paralelo. 
Hasta el momento se han explicado los operadores básicos de un algoritmo 
genético y se ha dicho que mediante ellos este procedimiento de búsqueda es 
suficientemente robusto. Es entonces el momento de explicar el Teorema de los 
Esquemas, que demuestra la manera en que se realiza el procesamiento de la 
información codificada en los cromosomas y la forma como converge el 
algoritmo genético. 
Las cadenas de caracteres como tales, no son la causa de que el algoritmo 
genético funcione. La evolución en los cromosomas para poder encontrar la 
solución a un problema de optimización, es producida por la explotación de 
11 
similaridades en las cadenas, permitiendo gmar de esta manera el 
procedimiento de búsqueda. 
La idea principal en la búsqueda de similaridades es: encontrar cromosomas 
que sean parecidos a otros, en ciertas posiciones de la cadena. Para poder hacer 
esto, se define el concepto de esquema: un esquema es un patrón que describe 
un conjunto de cadenas similares entre si en ciertas posiciones dentro de ellas, 
es decir, un esquema H = e1 ···en describe a un cromosoma C = c1 ... en si y sólo si 
c1 = e1 siempre y cuando e1 :t:*. Por ejemplo: 
Sean 
C1 = 1000 
c2 = 1101 
C3 = 1111 
tres cromosomas definidos sobre el alfabeto binario L = { o, I}. Un esquema que 
describe estas cadenas es: 
H = 1*** 
Este esquema describe a todas las cadenas de longitud e = 4 cuyo pnmer 
elemento es 1 . 
De acuerdo a lo anterior, para un alfabeto L de cardinalidad K existen (K+ 1l 
esquemas posibles y se pueden crear Ke individuos distintos. Si analizamos una 
población de n cadenas, podemos ver que cada población contiene entre 2e y 
n-2e esquemas diferentes ya que cada cromosoma puede ser representado por 
2t esquemas. Estos datos, permiten ver la magnitud de información que esta 
procesando el algoritmo genético en cada ciclo. 
Obviamente entre los esquemas existen similaridades y diferencias. Para poder 
medirlas se utilizan los conceptos de: orden de un esquema o(H) y longitud de 
definición 8.._H). El orden de un esquema o(H) se define como el número de 
posiciones fijas dentro del patrón. La longitud de definición 8.._H) se define 
como la distancia entre la primera y la última posición fija en el esquema. 
12 
Ya definidas las propiedades de los esquemas, se puedt:: analizar el efecto que 
tienen los operadores de reproducción, recombinación de la información y 
mutación sobre los cromosomas y en general sobre los bloques constructores. 
Estos últimos son esquemas de longitud corta, altamente adaptados al medio en 
el que se desenvuelven. 
Se denota como M(H,t) al conjunto de individuos presentes en la población 
activa de tamaño n, en el tiempo t, que pertenecen al esquema H. El número de 
esquemas representados por el esquema H en el tiempo 1+ 1 es 
M(H,t + 1) = M(H,1)1; = M(H,1/>H) 
n 
donde f(H) es el fitness promedio de los cromosomas representados por el 
esquema H en el tiempo t y¡; es eljitness de un elemenito en población. 
Para tener una noción cualitativa del crecimiento de los esquemas en el tiempo 
t+ 1 se supone que un esquema se encuentra por arriba del promedio en una 
proporción e] donde e es una constante. Esta consideración lleva a la siguiente 
forma exponencial: 
(J +e]) i 
M(H,t) = M(H,O) - = M(H,0)-(1 +e) 
f 
De esta forma, se puede ver el efecto de la reproducción sobre los esquemas; el 
operador de reproducción copia de manera exponencia] un número ( creciente o 
decreciente) de esquemas en la siguiente población dependiendo de su fitness 
promedio (alto o bajo). 
Para ver la forma en que la recombinación de información afecta a los 
esquemas, hay tener en cuenta que esta operación puede destruir un esquema. 
Un esquema es destruidosi se separan la primera y la última posición fija 
dentro de el; la probabilidad de que esto ocurra esta dada por: 
13 
d.._H) 
Pd=~-( -) f-1 
donde ~ es la probabilidad de que ocurra la recombinación de información. 
La mutación también puede destruir un esquema cuando afecta a una de las 
posiciones fijas, esto se da con una probabilidad Pm -o(H) para valores muy 
pequeños de la probabilidad de mutación (Pm << 1). 
Al conocer estas probabilidades, se puede obtener una cota inferior del número 
de copias que un esquema dado, en un tiempo t, recibirá en el tiempo t+ 1 bajo 
el efecto de la reproducción, recombinación de la información y mutación: 
J(H) 
M(H,t + 1) ~ M(H,t)·---[1- Pd -Pm -o(H)] 
f 
De esta formula se obtiene una conclusión, llamada Teorema de los esquemas, 
que es la base de los algoritmos genéticos: esquemas de longitud pequeña, 
orden bajo y fitness arriba del promedio de la población, son copiados de 
manera exponencial en las siguientes generaciones. 
14 
Capítulo 2 
Programación Genétic~a. 
El modelo de programación genética fue desarrollado por Koza[ 4] con el 
objeto de ampliar la aplicabilidad de las estrategias evolutivas en la 
solución de problemas de inteligencia artificial, aprendizaje de máquinas y 
procesamiento simbólico. Koza asegura, que muchos de los problemas 
antes mencionados, requieren del "descubrimiento" de un programa de 
computadora que produzca una salida deseada de acuerdo a una entrada 
dada; es decir, propone buscar un programa, dt entre un conjunto de 
programas posibles (inducción de un programa), que resuelva un problema 
específico. 
Las estructuras de datos utilizadas en el modelo de programación genética, 
difieren de aquellas estructuras especializadas. utilizadas por otras 
metodologías como el algoritmo genético. Esta representación por medio 
de estructuras especializadas, citando a Koza, "limita la ventana a través 
de la cual el sistema mira al mundo". Las limitaciones principales son: 
• Limitación del tamaño de la solución. 
• Limitación de la forma en la que es dada la respuesta. 
• Dificultad para representar jerarquías por medio de estructuras 
especializadas ( cadenas de caracteres de tamaño fijo). 
15 
En lugar de estas estructuras, se propone la utilización de programas que 
pueden estar escritos en, casi, cualquier lenguaje: de programación (C, 
FORTRAN, PASCAL, LISP, etc.). Koza elige LISP para implementar su 
modelo; sus principales razones son: 
• En LISP los programas y los datos tienen la misma forma. 
• LISP evalúa cualquier información que le es presentada. 
• Las expresiones simbólicas (listas o átomos) pueden ser vistas de 
manera gráfica como un árbol etiquetado con raíz. Este árbol es 
equivalente a el árbol de parseo que muchos compiladores utilizan 
internamente para representar un programa de computadora. 
• La programación de estructuras de forma y tamaño variable es sencilla. 
Un ejemplo de las expresiones simbólicas utilizadas en LISP es: 
(AND (> A B) r) 
que puede ser representado de manera gráfica por el siguiente árbol: 
Las estructuras en el modelo de programación genética son el conjunto de 
todas las combinaciones posibles de funciones que pueden ser compuestas 
16 
recursivamente a partir de el conjunto de funciones F = {J;, f 2 , • • ·, Ín-i, fn} y 
del conjunto de terminales T= {t¡,t2 ,··,tm_1,1J. Cada una de las funciones 
acepta un número de terminales z(J) como argumentos. La funciones 
pueden ser: 
• Operaciones aritméticas. 
• Funciones matemáticas. 
• Operaciones booleanas. 
• Operadores lógicos. 
• Funciones recursivas. 
• Operadores iterativos. 
• Funciones de dominio específico. 
El conjunto de terminales generalmente contiene constantes, que pueden 
ser lógicas o numéricas, y variables, que representan las entradas, los 
sensores o las variables de estado de algún sistema. 
Recordando el ejemplo anterior, su conjunto de flll1ciones es F = {AND ,>} 
y el de terminales T= {A,B,T}. Cada una de las funciones acepta como 
parámetros a dos elementos del conjunto T. 
La selección de las funciones y terminales debe de cumplir con las 
condiciones de suficiencia y cerradura. La condición de cerradura 
especifica que cualquier función contenida en F debe de estar bien 
definida para cualquier combinación de argumentos que puedan ser 
generados durante la operación de recombinación de la información. Para 
cumplir con la condición de suficiencia, se deben de _escoger las funciones 
y los terminales que sean necesarios para poder representar la solución del 
problema. 
17 
Claramente se puede ver, que el espacio de búsqueda del modelo está 
compuesto por un conjunto de estructuras válidas, equivalente a un 
espacio de árboles con raíz etiquetados con funciones en sus nodos 
internos y terminales en sus hojas. De esta mane:ra se pueden construir 
estructuras que pueden tener distinto tamaño y forma además de poder 
representar eficientemente jerarquías. 
Al iniciar el modelo de programación genética, se debe de generar una 
población P=(S0 ,S1,--,Sn_2 ,Sn_J que contienen árboles etiquetados con 
raíz. La generación de cada árbol se debe de hacer aleatoriamente a partir 
del conjunto C = Fu T, de la siguiente manera: cada vez que se genera w1 
nodo, se determina si es función o no, si lo es, s{: generan un número de 
nodos igual al número de argumentos que acepta y se expanden hasta que 
ya no sea posible. El caso del primer nodo es especial, ya que se desea 
que la población inicial contenga árboles, no hojas, es decir, si el elemento 
seleccionado como primer nodo es un terminal, éste, no se expande y por 
lo tanto se obtiene una hoja. Pare evitar este inconveniente, se debe de 
seleccionar un elemento del conjw1to F como primer nodo del árbol. 
Durante la generación de la población iniciaL, se puede prevenir la 
existencia de individuos iguales que reducen la diversidad genética de la 
población; de esta manera, se garantiza que la variedad, al iniciar el 
modelo, es de un 100%. 
Al igual que en los algoritmos genéticos, se deh~ de asociar una medida 
de mérito a cada individuo en la población llamada: jitness. Éste valor es 
utilizado para guiar la búsqueda de la solución y permite simular el 
principio de evolución de Darwin. 
La reproducción en la programación genética es un proceso de selección 
similar al de los algoritmos genéticos: se elige al azar un individuo de la 
población P y se copia a otra población auxiliar P' de acuerdo su 
probabilidad de supervivencia. Es decir, es un proceso de reproducción 
asexual en el que de un solo individuo nace otro. 
La operación de recombinación de la información tiene como objetivo la 
creación de nuevos individuos a partir de dos padres. Estos nuevos 
18 
individuos permiten la exploración de nuevos programas en el espacio de 
posibles programas computacionales. La recombinación se lleva acabo de 
la siguiente manera: 
• Se seleccionan aleatoriamente dos individuos de la población P'. 
• Se elige al azar un nodo, que generalmente es la raíz de un subárbol, 
para cada uno de los individuos seleccionados anteriormente. 
• Se reemplaza el subárbol seleccionado en el primer individuo por él 
elegido en el segundo, creando así, el primer h:ijo. La misma operación 
se realiza para el segundo individuo. 
• Se sustituyen los padres por sus hijos en la población. 
Se debe hacer notar, que los nodos elegidos para cruzamiento son 
generalmente distintos, debido a que los individuos en la población son de 
distinta forma y tamaño. Para una mejor comprensión de esta operación, 
se expone el siguiente ejemplo: 
Sean A1 y ~ dos individuos elegidos para cruzamiento (al azar) y 
generados aleatoriamente a partir de los siguientes conjuntos de fórmulas 
y terminales: 
F = {AND ,OR, NOT} 
T= {A,B,C} 
Se enumeran los dos árboles utilizando el método de pnmero en 
profundidad. Gráficamente A1 tiene la siguiente forma: 
19 
3 
6 
3 7 
4 
Se selecciona el nodo 2 del primer árbol y el nodo 6 del segundopara 
recombinación. Los subárboles a reemplazar son entonces: 
3 
20 
55;;L.Oo/ 
4 
para A1, y 
6 
7 
en el caso de A2 • 
Se realiza el cruzamiento en el pnmer árbol dando por resultado el 
siguiente hijo: 
2 4 
3 
De la misma manera, el segundo hijo es: 
21 
3 
4 
Nótese que los árboles obtenidos durante el proceso- de recombinación de 
la información están bien definidos de acuerdo a los lineamientos 
anteriormente establecidos, es decir, debido a que los subárboles son 
reemplazados por otros subárboles y a la propiedad de cerradura, el 
cruzamiento produce expresiones simbólicas legales. 
El operador de mutación en el modelo de programación genética no existe 
como tal, es decir, no se define una operación de mutación. La razón de su 
ausencia es muy simple: al realizarse la recombinación de la infonnación, 
puede darse el caso en que sean seleccionados como nodos de 
cruzamiento dos hojas, y por lo tanto, los respectivos subárboles 
etiquetados con raíz, estarían formados por un solo nodo. Al realizarse el 
reemplazo de un subárbol en lugar de otro, se estaría cambiando un 
terminal por otro terminal contenido en el conju11to T. De esta manera se 
realizaría, durante la operación de recombinación de la información, lo 
que en los algoritmos genéticos se conoce como operación de mutación. 
Una ultima observación sobre el operador de cruzamiento es necesaria. La 
creación de nuevos árboles mediante la recombinación de información 
puede generar estructuras cada vez más grandes, que con el paso de los 
ciclos, llegarían a ser excesivamente profundas. Es necesario entonces 
acotar la profundidad máxima de los árboles así creados para que en el 
caso en el que se detecte un árbol que exceda los límites establecidos, se 
22 
deseche y se genere o escoja, un nuevo árbol con la profundidad adecuada 
que reemplace al árbol no deseado. 
Como se ha mencionado anteriormente, el modelo de programación 
genética es muy parecido al modelo del algoritmo genético, es decir, se 
siguen los mismos pasos en las dos metodologías, para hacer evolucionar 
una población de estructuras, en la búsqueda de una solución aceptable al 
problema que se ha planteado. Falta entonces, mencionar la manera en que 
en programación genética se produce el resultado final. 
La designación de la solución generalmente recae en el mejor individuo de 
la población al terminar el proceso de evolución; sin embargo, puede ser 
que existan varios elementos con el mismo valor ele fitness, en cuyo caso, 
el resultado seria una subpoblación conteniendo los mejores individuos. 
Debido al efecto de los operadores de reproducción y cruzamiento sobre 
la población, es posible que el mejor individuo encontrado durante todo el 
procesamiento haya sido eliminado. En este caso, se puede llevar una 
bitácora que contenga los mejores individuos encontrados a lo largo de 
toda la búsqueda. 
23 
Capítulo 3 
Cálculo Proposicional. 
Todo sistema lógico incluye un lenguaje formal, mediante el cual se representan 
un conjunto de afirmaciones y razonamientos acerca de objetos, de cualquier 
clase, definidos en un universo de discurso. La estructura de estas afirmaciones 
debe ser tal, que permita su manipulación y la obtención de nuevas propiedades 
del universo de discurso de una manera sencilla, concisa y precisa. 
Aunque existen muchos lenguajes definidos en el mundo, como el español, se 
necesita la creación de un nuevo lenguaje para la construcción de las 
afirmaciones lógicas, debido, a tres razones principaks: 
1. Cualquier lenguaje natural contiene una gran cantidad de símbolos, lo que 
hace imposible su descripción formal. 
2. La semántica de estos lenguajes puede resultar ambigua debido a las 
diferentes interpretaciones que se pueden dar a una oración de acuerdo al 
contexto o tema que se esté tratando y a lo que se asuma durante una plática 
o escrito. 
3. Para la representación de afirmaciones matemáticas en un lenguaje natural, 
es necesaria una oración, u oraciones, demasiado largas y poco claras. 
24 
En cálculo proposicional, los elementos del lenguaje formal representan 
oraciones declarativas elementales y a partir de ellas se pueden construir 
nuevas proposiciones compuestas mediante la utilización de los conectivos 
lógicos (and, or, not, implicación y equivalencia). Por ejemplo, sean las 
siguientes oraciones: 
• Jaime es joven. 
• La comida está lista. 
si abreviamos la primera oración con la letra P y la.siegunda con Q, podemos 
construir la siguiente proposición compuesta: 
(Q OR (NOT P)). 
A causa de las razones expuestas en los puntos anteriores, la construcción de 
las afirmaciones en un lenguaje lógico, se debe de realizar a partir de un 
conjunto de reglas llamadas reglas sintácticas. 
El conjooto de proposiciones PROP es un conjooto recursivamente generado a 
partir del alfabeto L que contiene: 
• Un conjunto numerable PS de símbolos proposicionales: 
PS= {F;,P2 ,-··,Pn-1>~} . 
• Un conjunto CS formado por símbolos que representan conectivos lógicos: 
CS={A,v,-.,:::::i,=,..l}, and, or, not, implicación, equivalencia y la constante 
lógica FALSE, respectivamente. 
• Un conjunto de AS de símbolos auxiliares usados como delimitadores: 
AS ={<,)},paréntesis izquierdo y derecho respectivamente. 
25 
El conjunto PROP es la cerradura inductiva del conjunto formado por la w1ión 
del conjunto PS con el conjunto que contiene a la constante lógica FALSE bajo 
las funciones definidas a continuación: 
CjA) = -,A 
CjA,B)=(AAB) 
CjA,B) =(Av B) 
C:)(A,B) =(A::) B) 
CJA,B) =(A= B) 
es decir, PROP es el conjunto mínimo de cadenas de caracteres sobre el 
alfabeto :E = PS u es u AS de tal forma que: 
1. Cada símbolo proposicional P¡ se encuentra en PROP, al igual que _1_. 
2. Si A esta en PROP, -,A también. 
3. Si A y B están contenidos en PROP entonces: 
se encuentran en P ROP. 
(AAB) 
(Av B) 
(A::) B) 
(A= B) 
4. Una cadena de caracteres se encuentra en PROP si y sólo si cumple las 
condiciones anteriores. 
Los símbolos auxiliares contenidos en AS, facilitan la lectura de las 
proposiciones y eliminan la ambigüedad. Sin embargo, para simplificar la 
escritura de las mismas, se define un orden de precedencia de los conectivos 
lógicos que, salvo que se especifique lo contrario, aplica cada conectivo a la 
26 
proposición(es) más cercana(s) a él en el siguiente orden, de mayor a menor: 
-,; A; v; ::J, =. Un ejemplo de proposiciones contenidas en PROP que utilizan 
precedencia en los conectivos es: 
[ P ::J -,Q v R] = [ P ::J ( -,Q) v R] = [ P ::J ( ( -,Q) v R)] = [ ( P ::J ( ( -,Q) v R))] 
En el caso en el que, una proposición aparezca flanqueada por dos conectivos 
de igual precedencia, ésta se asocia al operador de la izquierda (regla de 
asociación a la izquierda). Por ejemplo: P ::J Q ::J R se interpreta como 
(P ::J Q) ::J R y no como P:::) (Q ::J R). 
El objetivo de la introducción de los paréntesis en las proposiciones es asegurar 
una única manera de leerlas, es decir, asegurar que PROP sea libremente 
generado y así poder definir el significado del lenguaje (semántica), definido 
recursivamente sobre PROP, a partir del significado asociado a cada símbolo 
proposicional. La demostración de que PROP es libremente generado por los 
símbolos proposicionales contenidos en PS, los conectivos lógicos y la 
constante lógica FALSE ( 1- ), se basa en las demostración del siguiente lema: 
Lema. Para todo elemento de PROP, el número de paréntesis izquierdos es 
igual al número de paréntesis derechos. 
Pasando ahora a la definición de la semántica del lenguaje, es necesario definir 
el significado de los conectivos lógicos. Cada conectivo lógico X adquiere su 
valor de verdad mediante la función Hx con rango en el conjunto 
BOOL = {TRUE, FALSE}, de la siguiente manera: 
HjFALSE) = TRUE 
HjTRUE) = FALSE 
HjFALSE ,FALSE)= FALSE 
H/\(FALSE ,TRUE)= FALSE 
H/\ (TRUE, FALSE) = FALSE 
H/\(TRUE,TRUE) = TRUE 
27 
Hv(FALSE ,FALSE)= FALSE 
H)FALSE, TRUE)= TRUE 
HJTRUE,FALSE)= TRUE 
H)TRUE, TRUE)= TRUE 
H~(FALSE ,FALSE)= TRUE 
H~(FALSE, TRUE)= TRUE 
H ~ (TRUE, FALSE) = FALSE 
H~(TRUE, TRUE)= TRUE 
H,,(FALSE ,FALSE)= TRUE 
HJFALSE, TRUE)= FALSE 
HjTRUE ,FALSE)= FALSE 
H=(TRUE,TRUE) = TRUE 
en donde H:r: nos permite distinguir entre el conectivo lógico X y su significado. 
La constante lógica 1- es interpretada como FALSE. 
Los símbolos proposicionales adquieren su significado al asociárseles oraciones 
declarativas, relativas a un universo de discurso. Algunos ejemplos son: 
P ~ Jaime es joven 
Q ~ El libro es de lógica 
R ~ El poster es rojo 
Una vez realizada esta asociación, se les puede asignar un valor de verdad en el 
conjunto BOOL, proceso conocido como valuación. 
Una valuación es una función v: PS ~ BOOL, que asigna un valor de verdad a 
cada símbolo proposicional. Esta interpretación de las proposiciones atómicas, 
se puede extender a las compuestas, debido a que PROP es libremente 
generado, a través de la función v: PROP ~ BOOL de acuerdo a las siguientes 
especificaciones: 
v(1-) = FALSE 
v(P) = v(P) 
v( --A) = H ~ ( v( A)) 
v((A v B)) = Hv( v(A), v(B)) 
v((A /\ B)) = H" ( v(A), v(B)) 
v( ( A :::) B)) = H ~ ( v( A)' v( B)) 
v((A = B)) = HJ v(A), v(B)) 
28 
donde A,B EPROP y p EPS. 
De acuerdo a la definición anterior, es necesario asignar valores de verdad a 
todos los símbolos proposicionales para poder determinar el valor de verdad de 
una proposición, lo que es imposible en la práctica, ya que el conjunto PS 
tendría una cardinalidad excesiva. Sin embargo, para cualquier proposición 
compuesta A y para cualquier valuación v, el valor v(A) solamente depende de 
los símbolos proposicionales en la fórmula A. 
Una proposición A E PROP es satisfacible si y sólo si existe una asignación de 
valores de verdad a cada una de los símbolos proposicionales en ella que 
satisfacen v(A) =TRUE, se denota vi =A; en caso contrario se dice insatisfacible 
vi =tA. Si A es satisfacible con independencia de la valuación se le llama 
tautología y se escribe 1 =A, si es insatisfacible, se denota 1 :t:A. Algunos 
ejemplos de tautologías son: 
Las definiciones de tautología y satisfacibilidad plantean los problemas de: 
determinar si una proposición es satisfacible y detem1inar si es una tautología. 
Estos problemas son los más importantes dentro del cálculo proposicional. 
Otro problema, equivalente al de tautología, es el siguiente: 
Dado un conjunto de proposiciones re PROP, llamadas premisas, y una 
proposición A E PROP, se dice que A es una consecuencia semántica de r, 
denotado por r¡ =A, si para todas las evaluaciones de v, si v(B) = TRUE para 
toda B en r, necesariamente v(A) =TRUE. El problema es determinar si dado 
A E PROP y el conjunto de premisas re PROP, es A una consecuencia 
semántica de r. Esto se reduce al problema de tautología si y sólo si: 
l=((P¡AFi···APn_1 APJ::::>A) donde PS={P¡,···,E:} es el conjunto de símbolos 
proposicionales. 
29 
Existen dos métodos para la solución del problema de tautología. El primero de 
ellos, determina el valor de verdad de la proposición a partir de la asignación 
de valores de verdad a cada uno de los símbolos proposicionales que la 
componen. Si para toda asignación a los símbolos proposicionales, la 
proposición es verdadera, entonces se dice que es una tautología. 
Como ejemplo, se demostrará que P ~ (Q ~ P) es una tautología. Considerando 
las posibles asignaciones a P y Q, se tiene: 
Para v(P) =FALSE; v(Q) =FALSE: 
v(P) =FALSE; v(Q) =TRUE: 
v(P) = TRUE;v(Q) =FALSE: 
v(P) = TRUE;v(Q) =TRUE: 
v(Q ~ P) = TRUE 
v(P ~(Q ~ P)) = TRUE 
v(Q ~ P) = FALSE 
v(P~(Q~P))= TRUE 
v(Q ~ P) = TRUE 
v( P ~ ( Q ~ P)) = TRUE 
v(Q ~ P) = TRUE 
v( P ~ (Q ~ P)) = TRUE 
Como se puede apreciar, el valor de verdad de P ~(Q ~ P) es TRUE con 
independencia de la asignación de valores de verdad a los símbolos 
proposicionales, por lo tanto, la proposición es una tautología. 
30 
La desventaja de este método, es que la solución del problema de tautología 
requiere de un tiempo exponencial, dependiendo del número de símbolos 
proposicionales contenidos en la proposición que se quiere probar. Por esta 
razón, se tiene un segundo método, para probar si una proposición es o no una 
tautología. La idea es buscar una asignación de valores de verdad, a los 
símbolos proposicionales, que falsifiquen la proposición, es decir, que la 
valuación de la proposición sea FALSE. 
Utilizando nuevamente la proposición del ejemplo anterior P => ( Q => P), para 
probar que esta sea una tautología, mediante este nuevo método, se debe de 
asignar un valor de verdad TRUE al símbolo proposicional P porque 
H~(FALSE ,x) = TRUE \fx EBOOL. La valuación de (Q=> P) debe de ser 
entonces FALSE para que H~(TRUE ,FALSE)= FALSE. Debido a que 
v(P) =TRUE, el valor de verdad de (Q => P) ~:s siempre TRUE, con 
independencia de la valuación de Q, ya que H~(x,TRUE)= TRUE;\fx EBOOL y 
por lo tanto, como no se puede falsificar P => (Q => P), la proposición es una 
tautología. 
Este método, en el que se resuelve el problema de tautología al tratar de 
falsificar la proposición en cuestión, constituye la base de los sistemas Gentzen 
que se definen a continuación. Se escogen estos sistemas porque son más 
intuitivos, más fáciles, su manera de resolver el probl.ema es algorítmica, lo que 
permite una implementación computacional rápida y sencilla. Finalmente, la 
construcción de los árboles de prueba en este sistema es más natural, se 
empieza a expander de la raíz a las hojas, a diferencia del sistema de Hilbert, 
donde la construcción va de las hojas a la raíz. 
Un sequent es un par ordenado (r,~) de listas finitas de proposiciones, en 
donde la primera la lista r = (G"G2 ,···,Gn-1'Gn) es llamada antecedente y la 
segunda lista~= (D"D2 ,-··,Dm_1,Dm) es llamada consecuente; estas listas pueden 
ser vacías. Una notación alternativa, comúnmente usada, es: r ~ ~- Si r o ~ es 
la lista vacía, el sequent correspondiente se denota ~ ~ o r ~ 
respectivamente. En el caso en el que ambas listas no contengan elemento 
alguno, el sequent ~ es conocido como el sequent inconsistente. 
31 
Se dice que la valuación v: PS -t BOOL satisface al sequent r --t ~ si y sólo si: 
v[ =(GAG A···AG) :::)(D v D v···vD ) 1 2 n 1 2 in • 
Si no existe alguna valuación que cumpla la condición anterior, el sequent se 
dice insatisfacible. Un sequent se dice válido si y sólo si: 
l =(G AG /\···/\G ):::)(D vD V···VD) 1 2 n 1 2 m , 
y falsificable si existe una valuación v: PS -t BOOL tal que: 
Para detenninar si un sequent es falsificable, se utiliza un procedimiento 
sistemático, que pennite ir descomponiendo el problema en problemas más 
sencillos. La definición de este procedimiento, se basa en las llamadas reglas de 
inferencia, que se presentan a continuación utilizando los símbolos r, ~, A para 
representar listas de proposiciones y A, B para las proposiciones: 
Reglas not: 
Reglas and: 
Reglas or: 
r,~--t A,A 
r,--,,4,~ --t A 
r,A,B,~-t A 
r,AAB,~-tA 
r,A,~--tA r,B,~--tA 
r,AvB,~--tA 
32 
A,f--t~,A 
r --t ~,--,A, A 
f--t ~,A,A f----)- ~,B,A 
f-t~,AAB,A 
r-tA,A,B,A 
r--t ~.,Av B,A 
Reglas condicionales: 
r,Li~A,A B,r,Li~A 
r,A::::iB,Li~A 
A,r~B,Li,A 
r ~ il,A ::::iB,A 
Cada una de estas reglas consiste de uno o dos sequent~ en la parte superior 
llamados premisas y un sequent en la parte inferior llamado conclusión. Las 
reglas pueden ser vistas como árboles etiquetados con premisas en sus hojas y 
conclusiones en su raíz. 
Nótese que no existe regla para la equivalencia y para la constante lógica 
FALSE. La razón de esto es que (A= B) es una abreviación de (A ::::i B) A(B ::::i A) 
y _1_ es una abreviación de (PI\ .P). 
Para demostrar que un sequent es falsificable se construye un árbol de 
inferencia, al que se le aplican las reglas de inferencia a partir de la raíz, 
etiquetada con el sequent que se pretende falsificar. 
Los axiomas en este sistema son hojas etiquetadas con sequents r ~ Li tales 
que r y Licontienen alguna proposición en común~ no son falsificables, por lo 
que no se necesita aplicárseles regla alguna, al igual que a las hojas etiquetadas 
con sequents que solamente contienen símbolos terminales. 
La generación del árbol de inferencia termina cuando no se pueden seguir 
aplicando reglas de inferencia a las hojas, es decir, cuando las hojas están 
terminadas. Si todas las hojas en el árbol son axiomas, se le denomina árbol de 
prueba, en caso contrario, se le llama árbol de contraejemplo. 
Como ejemplo del uso de sequents para resolver el problema de tautología, se 
probará que i= A ::::i (B ::::i (A I\ B)). 
33 
A,B----),A A,B----),B 
A,B----),AAB 
Á----)-B=>(AAB) 
----)- A =i(B=i(AAB)) 
En este árbol se aprecian dos hojas (A,B----), A y A,B----), B) que son axiomas, por 
lo tanto, A => ( B => (AA B)) es una tautología y se tiene un árbol de prueba. 
34 
Capítulo 4 
Lenguajes de Primer Orden. 
El cálculo proposicional no es suficiente para expresar afinnaciones acerca de 
elementos de una estructura. Esto se debe a que generalmente, cuando se 
describe un conjunto de sucesos en el mundo real, se usan oraciones 
declarativas como las siguientes: 
• Todos los autos son confortables. 
• El BMW es un auto. 
• Por lo tanto, el BMW es confortable. 
Sin embargo, en el cálculo proposicional no se pueden expresar este tipo de 
oraciones, razón por la cual se introducen símbolos proposicionales con 
argumentos llamados predicados. Los predicados penniten representar 
relaciones como: "Jorge es padre de Adolfo" de la siguiente manera: 
Padre(Jorge,Adolfo). Se obtienen así los llamados lenguajes de primer orden 
mediante los cuales se pueden expresar las oraciones anteriores de la siguiente 
manera: 
Vx(Auto(x) ::J Confortable{x)) 
Auto(BMW) 
Confortable{ BMW) 
35 
Usando los lenguajes de primer orden es posible fonnalizar y organizar el 
conocimiento declarativo sobre estructuras, que pm:den ser concretas o 
abstractas, de manera que a partir de un conjunto de fórmulas bien formadas, 
válidas en el universo de discurso, es posible obtener otras fórmulas, también 
válidas, por aplicación de reglas de inferencia. 
La definición de la estructura sintáctica de los lenguajes de primer orden, se 
hace a partir de dos tipos de elementos básicos: los símbolos lógicos, que son 
fijos, y los símbolos no lógicos, que varían de acuerdo al mundo ( estructura) al 
que se refieran. 
Los símbolos lógicos son: 
• Conectivos Lógicos: --, (not), /\ (and), v (or), :::> (implicación), -
( equivalencia) y ..L (falsedad). 
• Cuantificadores: V (universal) y :l ( existencial). 
• Símbolo de igualdad: =. 
• Un conjunto finito de símbolos de variables: VS = { x1, x2 , • • ·, xJ. 
• Símbolos auxiliares: "(" y ")". 
Por su parte, los símbolos no lógicos son: 
• Símbolos de función: Conjunto FS = {Ji, / 2 ,. • ·, /J, sobre el que se define una 
función de rango r1 : FS ~ N que asocia a cada elemento de FS un número 
entero no negativo. 
• Símbolos de constante: Conjunto es= {c¡,c2 ,-··,cJ, cuyos elementos tienen 
rango nulo. 
36 
• Símbolos de predicado: Conjunto PS= {P¡,P2 ,···,PJ, sobre el que se define 
una función de rango rp: PS-+ N que asocia a cada elemento de PS un 
número entero no negativo. 
Se asume que FSnCSnPSnVS =0. 
Si se asignan símbolos a los conjuntos FS, CS y PS se obtienen lenguajes de 
primer orden denotados por la letra L. 
Con el objeto de que los lenguajes de primer orden puedan ser computables, es 
decir, puedan representar el conocimiento declarativo y ser manipulables, se 
define su estructura a partir de dos conjuntos, que se construyen 
recursivamente. 
El conjunto de términos TERM se define de la siguiente manera: 
1. Todo símbolo de constante y de variable es w1 término. 
2. Si 11, 12,. · ·, t n son términos y n es el rango de un símbolo de función f, 
entonces ft1l2···tn es un término. 
Un ejemplo de términos en el lenguaje definido al asignar símbolos de función, 
símbolos de constante y símbolos de predicado es: 
1 
h01 
ghl 10 
hh10g00 
donde: FS={g,h} cuyos símbolos tienen rango 2, CS={o.1} y PS={P} con 
rango l. 
37 
Para definir el conjunto de fónnulas FORM es necesario definir primero el 
conjunto de fónnulas atómicas AFORM: 
1. .l es una fónnula atómica. 
2. Todo símbolo de predicado de rango cero es una fómmla atómica. 
3. Si 11, 12 , • • ·, t,, son ténninos y P es un símbolo de predicado de rango n, 
entonces Pt1t2 .. • t,, es una fónnula atómica. 
4. Si 11 y 12 son ténninos, entonces== 1i12 es una fónnula atómica. 
Ejemplos de fónnulas atómicas utilizando la asignación de símbolos no lógicos 
del ejemplo anterior son: 
PO 
== hl 10 
== gxihhOOx 
El conjunto de fórmulas FORM se construye ahora en la forma: 
1. Toda fónnula atómica es una fónnula. 
2. Para cualquiera dos fónnulas A y B, .A,(AAB),(AvB),(A:::iB),(A=B) son 
fónnulas. 
3. Si A es una fónnula y x EVS, entonces 'v'xA,:lxA son fórmulas. 
Siguiendo con la utilización de las asignaciones de símbolos de los ejemplos 
anteriores, las siguientes son fónnulas: 
38 
(=xxv1-) 
(vx(hlx = gOO)) 
( vx(~y((1-A ,(= ly))::) Po)v Px)) 
Antes de poder definir la semántica de los lenguajes de primer orden, es 
necesario definir los conceptos de: conjunto de variabl,~s libres y conjunto de 
variables ligadas. 
Dado un término t, el conjunto de variables libres en t, FV(t) se define 
recursivamente de la siguiente manera: 
1. Si t es una constante, entonces FV( t) = 0 . 
2. Si t es un símbolo de variable x, entonces FV( t) = { x}. 
3. Si jt 1t2 ···tn es un término t, entonces FV(t) = FV(tJu- .. uFV(tJ. 
De las misma manera se puede definir el conjunto de variables libres FV( A) en 
una fórmula A: 
l. Si A= 1-, entonces FV(A) = 0. 
2. Si A = P donde P es un predicado de rango cero, entonces FV( A) = 0. 
3. Si A= Pt1• .. tn, entonces FV(A) = FV(t¡)u .. ·uFV(tJ, donde Pes un predicado 
de rango n. 
4. Si A== t¡t2 , entonces FV(A) = FV(ti}uFV(tJ. 
5. Si A = -,B, entonces FV( A) = FV( B), donde B es una formula. 
39 
6. Si A=(B*C), entonces FV(A)=FV(B)uFV(C), donde *E{A,v,:J,=} y B, C 
son fórmulas. 
7. Si A= VxB o A= 3xB, entonces FV(A) = FV(B)-{x}, donde Bes una fórmula 
y X EVS. 
En base a esta definición del conjunto de variables libres, se dice que un 
término t o una fórmula A es cerrado(a) si: FV(t) = 0 o FV(A) = 0, 
respectivamente. Una fórmula cerrada es conocida también como sentencia. Si 
la fórmula no tiene cuantificadores se le llama abierta. 
El conjunto de variables ligadas BV(A) en una fórmula A se define de manera 
similar: 
l. Si A= 1_, entonces BV(A) = 0. 
2. Si A= P donde Pes un predicado de rango cero, entonces BV(A) = 0. 
3. Si A = Pt1 •• • t n, entonces B V (A) = 0, donde P es un predicado de rango n. 
4. Si A== 1112 , entonces BV(A) = 0. 
5. Si A= -,B, entonces BV(A) = BV(B), donde Bes una fórmula. 
6. Si A=(B*C), entonces BV(A)=BV(B)uBV(C), donde *E{A,v,:J,=} y B, C 
son fórmulas. 
7. Si A=VxB o A=?ixB, entonces BV(A)=BV(B)u{x}, donde B es una 
fórmula y x E VS . 
Una última definición es necesana antes de pasar a la definición de la 
semántica: 
40 
Sean t y s términos. La sustitución de una variable libre x por un término t en s 
se denota por s[t I x] y se define recursivamente como sigue: 
{
y si y :;t: X 
• Si s=y, entonces y[tlx]= 
1 
.-1e , donde y EVS. 
u, otra manera 
• Si s=c, entonces c[tlx]=c, donde cECS. 
• Si s = jt1 ···t,,, entonces ft 1 • • ·t,,[t I x] = ft 1[t I x ]- · ·t,,[t I x ], donde jt1 • ··t,, E TERM. 
En el caso de una formula A, A[t I x] se define: 
• l_[tlx]=l_. 
• (-.A)[tlx]=-.A[tlx]. 
• (A*B)[t / x] = (A[t / x]•B[t / x]). 
( )[ ] {
VyA[t / x] si 
• VyA t / X = 
VyA de otra manera 
( )[ ] {
:lyA[tlx] si 
• :lyA t / X = 
:lyA de otra manera 
Esta definición de la sustitución, permite que algunas sustituciones se vuelvan 
inapropiadas, es decir, algunas sustituciones pueden hacer que una fórmula 
41 
satisfacible ya no lo sea. Para evitar este tipo de situaciones, antesde sustituir 
un término t por x en A se deben de cumplir las siguientes condiciones: 
• Que A sea atómica. 
• Que A = (B* e) y t se pueda sustituir por x en By en C .. 
• Si A= VxB o A= ?ixB y x=y o, x ~ y y y 'lFV(t) y t se puede sustituir por x 
en B. 
Debido a que las fórmulas representan el conocumento declarativo sobre 
estructuras, para la definición de la semántica de los lenguajes de primer orden 
se necesita un conjunto M, llamado dominio de la estrrnctura, y una función de 
interpretación 1, que asigna funciones y predicados definidos en M a los 
símbolos en el lenguaje L de la siguiente manera: 
• Ve ECS,(I(c) EM) . 
• Vf EFS,(I(J) E(Mn ~ M)), donde n es el rango del símbolo de funciónf 
• VP E PS,(¡(P) E(Mn ~ BOOL)), donde n es el rango de P . 
La terna (L,M,J) es conocida como una L-estructura. 
Al definir la semántica de una fórmula, su valor de verdad depende de la 
asignación de valores en M a los símbolos de variable, por lo tanto, se debe de 
especificar la función de interpretación para los términos y para las fórmulas. 
Una función de asignación s: VS ~ M, asigna elementos del conjunto M a los 
símbolos de variable contenidos en VS. 
42 
La definición de la interpretación de los términos es: 
• Si t es un término que es una constante e, entonces Is ( t) = 1( e). 
• Si t es un término que es una variable x, entonces Is ( t) = s( x). 
• Si tes un término de la forma ft 1t2 • • ·tn, entonces ls(t) = 1(¡)(1s(t¡),- .. ,1,(1J). 
que se puede extender a las fórmulas: 
• Si A= .1, entonces !,{A)= FALSE. 
• Si A= P, entonces J,(A) = l(P), donde P es un símbolo de predicado de 
orden cero. 
• Si A=Pt1···tn, entonces J,(A)=l(P)(l,(tJ,-··,ls(tJ), donde Pes un símbolo 
de predicado de orden n. 
• Si A== t1t2 , entonces ls(A) = TRUE s1 (1s(t1) = J,(1 2 )), de otra forma, 
ls(A) =FALSE. 
• Si A= -,B, entonces J,(A) = Hjls(B)). 
• Si A= (B /\e), entonces 1,(A) = H(\ (1,(B),J,( e)). 
• Si A= (Bv e), entonces ls(A) = Hjls(B),1,(c)). 
• Si A= (B ::::i C), entonces J,(A) = HjJ,(B),Js(C)). 
• Si A= (B = C), entonces ls(A) = HJJ,(B),J,(C)). 
43 
. {FALSE si (:3a E M(I,¡.,rx](B) =FALSE)) 
• S1 A= VxB, entonces I,(A) = 
TRUE de otra forma 
• Si A= :3xB' entonces I,(A) = {TRUE si (:3a E M(Is[ar,J(B) = TRUE)) 
FALSE de otra forma 
Donde s[ a I x ](y)= a si y=x, de otra fonna, s[ a I x ](y)= s(y). 
Ante esta interpretación de las fónnulas, debe de hacerse notar que la 
interpretación de aquellas que contienen cuantificad9res, puede ser no 
computable debido a que el conjunto M puede llegar a ser infinito. 
Una fónnula A del lenguaje de primer orden L con la interpretación (L,M,1) se 
dice satisfacible si existe una asignación s: VS ~ M de elementos del conjunto 
Malos símbolos de variable tal que I,(A) = TRUE y se denota: (L,M,I) 1 =A[s]. 
Si en cambio, \Is E(VS ~ M)I,(A) = FALSE se dice que A es insatisfacible y se 
escribe (L,M,J) 1-:t:-A. 
Una fónnula A es válida con la interpretación (L,Af.l) si para cualquier 
asignación de elementos del conjunto M a los símbolos de variable, A se 
satisface, denotándolo (L,M,1) 1 =A; (L,M,1) constituye un modelo para la 
fonnula. Si la fónnula es válida con independencia de la interpretación (1 =A), 
se dice válida. 
Los conceptos de satisfacibilidad y validez se amplían a conjuntos de fónnulas 
de la siguiente manera: dado un lenguaje de primer ordc~n-L, una interpretación 
(L,M,J) y un conjunto r de fónnulas, se dice que r es satisfacible si existe una 
asignación s: VS ~ M que satisface a cada fonnula en r, se denota 
(L,M,J) 1 = r [s]. En el caso, en el que para toda asignación de elementos del 
conjunto M a los símbolos de variable, I,(A) =FALSE, se dice que r es 
insatisfacible ((L,M,J) 1 -:t:- r). La L-estructura (L,M,J) es un modelo para r si 
44 
constituye W1 modelo para cada W1a de las fórmulas en r y se escribe 
(L,M,I) 1 = r. Si lo anterior se cumple con independencia de la interpretación se 
dice que r es válida (l=r). Por último, con la L-estructura (L.M,I), W1a fórmula 
A es W1a consecuencia semántica de r si para toda asignación s: VS ~ M se 
cumple: (vs Ef(I.(B)= TRUE))==>l.(A)= TRUE. 
Al igual que en el cálculo proposicional, se desea tener W1 método que permita 
probar si W1a fórmula es válida o no. Nuevamente, se tienen dos listas de 
fórmulas: W1a de fórmulas por satisfacer y otra de fórmulas por falsificar, por lo 
que se vuelve a utilizar la estrategia de subdividir W1 problema en problemas 
cada vez más sencillos. Se puede entonces extender el sistema Gentzen, 
utilizado en el cálculo proposicional, mediante la generalización del concepto 
de sequent. 
En W1 lenguaje de primer orden L con W1a interpretación (L,M,I), W1 sequent 
r ~ ~ es W1 par ordenado de listas de fórmulas (re L,~ e L). Si existe W1a 
asignación s: VS ~ M para la cual se cumple 
VA Ef(l.(A) = TRUE) 
y 
VA E ~(!.(A)= FALSE) 
el sequent r ~ ~ es falsificable en la interpretación. Si es falsificable con 
independencia de la interpretación se dice que es falsilficable. En cambio, w1 
sequent r ~ ~ es válido con la interpretación (L,M,I) si para toda asignación de 
elementos del conjW1to M a los símbolos de variable 
( VA E r(l.(A) =TRUE))==> (:is E ~(I.(B) =TRUE)) 
es verdadero y se dice válido si y sólo si es válido en cualquier interpretación. 
Las reglas de inferencia, a partir de las cuales se va descomponiendo una 
fórmula, se presentan a continuación utilizando los símbolos r, ~, A para 
denotar secuencias arbitrarias de fórmulas y A,B para las fórmulas: 
45 
Reglas not: 
Reglas and: 
Reglas or: 
r,L\~A,A 
r,-.A,L\ ~ A 
r,A,B,L\ ~ A 
r,AAB,L\~A 
r,A,L\ ~ A r,B,L\ ~ A 
r,AvB,L\~A 
Reglas condicionales: 
r,L\ ~ A,A B,r,L\ ~ A 
r,A::iB,L\~A 
Reglas universales: 
r,A[t / x], 'dxA,L\ ~ A 
r, 'dxA,L\ ~ A 
Reglas existenciales: 
r,A[yl x],L\ ~ A 
r,:lxA,.1 ~ A 
A,r-~ L\,A 
r ~ L\,-.A,A 
r ~ L\,A,A r ~ ~,B,A 
r ~L\,AAB,A 
r -~ L\, A, B, A 
r-~L\,AvB,A 
A,r~B,L\,A 
r -~ L\, A ::i B, A 
r -) L\, A[y I x ], A 
r ~L\,'dxA,A 
r ~ .1,A[t I x],:lxA,A 
r ~ l'.\,:lxA,A 
Como se puede ver, al igual que en al cálculo proposicional, las reglas se 
pueden ver como árboles etiquetados con sequents: en su raíz constituyen la 
46 
conclusión y en las hojas las premisas. Los axiomas en este sistema son todas 
las hojas etiquetadas con sequents que tienen la siguiente forma: 
f,A.~ ~ A,A,0 
es decir, que contienen la misma fórmula (A) en sus miembros. 
Un ejemplo de la aplicación de este sistema es el siguiente: 
p~ P,3zQz P,Qy~Qy,3zQz 
P,Qy~ 3zQz 
P,(P::) Qy) ~ :lzQz 
(P::) Qy) ~ (P::) :lzQz) 
3x(P::) Qx) ~ (P::) 3zQz) 
~ 3x(P::) Qx)::) (P::) 3zQz) 
donde Pes un símbolo proposicional y Q es un predicado de rango uno. 
47 
Capítulo 5 
El Sistema de Lógica lnt(iuctiva. 
En la introducción del presente trabajo de tesis se mencionó que su objetivo es 
desarrollar un sistema de lógica inductiva basado en estrategias evolutivas para 
hacer evolucionar expresiones dentro de un lenguaje de primer orden. 
Para cumplir el objetivo, se planteó el siguiente esquema: 
1. Definir los conjuntos de símbolos de función FS, de símbolos de predicado 
PS y de símbolos de constante CS, necesarios para la representación del 
universo de discurso que se pretenda analizar. 
2. Definir la función de interpretación 1 que asigne :funciones y predicados 
definidos en M a los símbolos en el lenguaje de primer orden definido en el 
punto anterior. 
3. A partir de los símbolos lógicos y no lógicos utilizados por el lenguaje de 
primer orden definido en los pasos 1 y 2 del esquema, crear, de manera 
aleatoria, fórmulas bien formadas del cálculo de predicados de primer orden 
de acuerdo a las definiciones dadas en el capítulo cuarto, acerca de la 
construcción de los conjuntos de términos y de fórmulas. 
4. Utilizar las fórmulas creadas, en el punto número tres, como elementos de 
procesamiento en la población inicial de un programa, genético. 
48 
5. El programa genético debe de permitir la evolución de expresionesen un 
lenguaje de primer orden, es decir, la función de mérito debe de premiar, 
con los valores más altos, a aquellas fórmulas que describan el universo de 
discurso de una manera concreta. Con esto se asegura su selección para 
reproducción y cruzamiento, con el objeto de obtener cada vez "mejores" 
individuos (fórmulas). 
6. Debido a que la operación de cruzamiento puede llevar a la creación de 
fórmulas que no estén bien formadas, se debe de tener un procedimiento que 
verifique cada una de las fórmulas en la población resultante después de 
aplicar los operadores genéticos. Si se detecta una fórmula mal formada, 
ésta, se desecha. 
7. El programa genético termina al llegar a un número max1mo de 
generaciones. Se necesita que sea así debido a que,· generalmente, no se 
conoce de antemano el número de fórmulas que describen al universo de 
discurso de una manera sencilla. 
8. Al terminar la ejecución del programa genético, el resultado estará 
compuesto por la población final de expresiones que, se supone, son las 
mejores describiendo al universo analizado. 
Se desarrollaron 4 programas para cumplir con el esquema antes definido. Los 
programas son: gafbfcpl .lsp, eeppli.lsp, seman.lsp y family.lsp, siendo los dos 
primeros los más importantes. 
Para la codificación de estos programas, se eligió el lenguaje de programación 
LISP debido a las siguientes razones: 
1. Permite la evaluación de las estructuras de datos mediante la instrucción 
EVAL. 
2. La facilidad en el manejo de listas. 
3. La gran cantidad de funciones implementadas en e:l lenguaje ( creación de 
tablas de hash, estructuras, objetos, etc.). 
49 
4. La sugerencia realizada por Koza en su libro: Genetic Programming sobre 
el manejo de las estructuras como expresiones simbólicas representadas 
como árboles etiquetados con raíz. 
5. El previo conocimiento del lenguaje. 
5.1 El programa FAMILY.LSP 
En este programa se definen las estructuras de datos que utilizaran los demás 
programas para accesar la información referente al mundo que se esta 
analizando, es decir, se define la estructura del conjunto M definido en el 
capítulo de Lenguajes de Primer Orden. 
El programa se llama family.lsp porque, en especial, este programa define la 
estructura de un universo de discurso en el que sólo existen relaciones padre e 
hijo. Esto no significa que no se puedan utilizar otros programas que definan 
otro tipo de universo; en realidad el sistema esta codificado de una forma que 
permite una fácil codificación de nuevos programas con la estructura de otro 
mundo, sin que se tenga la necesidad de realizar modificaciones o se afecten a 
los demás programas del sistema. 
Lo primero a definir cuando se crea un programa de este tipo, es la tabla de 
símbolos. La tabla de símbolos consta de: 
1. Definición de los símbolos de función del lenguaje de primer orden. 
2. Definición de los símbolos de constante. 
3. Definición de los símbolos de variable. 
4. Símbolo de falsedad (NIL para LISP). 
50 
5. Definición de los símbolos de predicado. 
6. Símbolo de igualdad(=). 
7. Conectivos lógicos ( A, v, -,, ::i, = ). 
8. Cuantificadores (V,3). 
Este orden de definición se debe de respetar al declarar la tabla de símbolos. 
Un ejemplo de este tipo de tabla es: 
(setf symboltable '( (father 1 (E E)) (abuelop 1 (E E)) 
) 
) 
('Mario O) ('David O) ('Jose O) ('Martin O) ('Ernesto O) 
(xi O) (x2 O) (x3 O) (x4 O) (x5 O) (x6 O) (x7 O) (x8 O) 
(x9 O) (xi O O) (xi 1 O) (xl2 O) (xl3 O) (xl4 O) (xl5 O) 
(xl6 O) (xl7 O) (xl8 O) (xl9 O) (x20 O) (x21 O) (x22 O) 
(x23 O) (x24 O) (x25 O) (x26 O) (x27 O) (x28 O) (x29 O) 
(x30 O) (x31 O) (x32 O) (x33 O) (x34 O) (x35 O) (x36 O) 
(x37 O) (x38 O) (x39 O) (x40 O) (x41 O) (x42 O) (x43 O) 
(x44 O) (x45 O) (x46 O) (x47 O) (x48 O) (x49 O) (x50 O) 
(x5 l O) (x52 O) (x53 O) (x54 O) (x55 O) (x56 O) (x57 O) 
(x58 O) (x59 O) (x60 O) (x61 O) (x62 O) (x63 O) (xM O) 
(NILO) 
(parentp 2 (E E E)) (grandp 2 (E E E)) 
(= 2) 
(ANO 2) (OR 2) (NOT 1) (IMP 2) (EQV 2) 
(UNIV 1) (EXIST 1) 
Nótese que todos los elementos de esta tabla son listas. Todas ellas contienen, 
como segundo elemento, un átomo numérico que corresponde al rango del 
símbolo que le precede. En el caso de los símbolos de función y de predicado, 
las listas contienen además, otra lista, en donde se especifica el tipo de 
parámetros que recibe o manda la función o predicado; e:sto último se explicará 
más adelante. 
51 
Después de definir la tabla de símbolos, se deben d1~ definir las siguientes 
constantes: 
1. Symbolnumber. Número de símbolos en la tabla de símbolos. 
2. Functionnumber. Número de símbolos de función. 
3. Constantnumber. Número de símbolos de constante. 
4. Variablenumber. Número de símbolos de variable. 
5. Atomicpredicatenumber. Número de símbolos de predicados de rango 
cero. 
6. Atomiclogicnumber(fijo ). Número: 1, correspondiente al símbolo de 
falsedad. 
7. Predicatenumber. Número de símbolos de predicado de rango mayor que 
cero. 
8. Logicnumber(fijo). Número: 1, correspondiente al símbolo de igualdad. 
9. Connectivenumber(fijo ). Número de conectivos lógicos. 
10.Quantifiernumber(fijo). Número de cuantificadores. 
Una vez definidas las constantes, se declaran las estn1cturas de datos, que 
definen las relaciones, que a su vez, serán accesadas por las funciones y los 
predicados. Obviamente las funciones y predicados que se declaren deben de 
coincidir con los nombres de los símbolos de función y predicado definidos en 
la tabla de símbolos. 
Un ejemplo, de la declaración de las estructuras de datos de las relaciones, en 
donde se definen los padres e hijos de una persona, es: 
(setf (get 'Tonio 'Parents) '(Alex Adriana)) 
(setf (get 'Tonio 'Siblings) '(Tere)) 
52 
(setf (get 'Silvia 'Parents) '(Ricardo Alicia)) 
(setf (get 'Silvia 'Sihlings) '(Tere)) 
una función que las accese podría ser: 
( defmacro father ( person ) 
'(if (ANO (ATOM ,person) ,person) 
( do 
( 
(result NIL) 
(i personnumber) 
) 
((OR (NOT (NULL result)) (= i O)) result) 
(setf i (- i 1)) 
( setf result ( first (get ,person 'Parents))) 
) 
NIL 
) 
) 
y un predicado: 
(defun parentp ( parent sibling) 
(when (equal parent (father sibling)) T) 
) 
Finalmente se deben de inicializar, a un valor fijo o aleatorio, los símbolos de 
variable que se vayan a utilizar para que LISP no marque ningún error. 
53 
5.2 El programa GAFBFCPl.LSP 
El programa tiene como objetivo: generar aleatoriamente fórmulas bien 
formadas del cálculo de predicados de primer orden. 
La generación de los términos y fórmulas se realiza siguiendo el procedimiento 
descrito en el capítulo de Lenguajes de Primer Orden. 
Las fórmulas y términos son vistos por el programa como expresiones 
simbólicas que pueden ser representadas por árboles etiquetados con raíz, 
hecho que permite la generación aleatoria de árboles completos y árboles 
incompletos. Un árbol se dice completo si la profundidad (longitud de una rama 
medida desde la raíz hasta una de sus hojas) es la misma para todas sus hojas. 
En caso contrario, se dice incompleto. 
La razón de obtener estos dos tipos de árboles es: poder decidir el número de 
árboles completos e incompletos, al inicializar la población utilizada por el 
programa genético ( eeppli.lsp) y seguir, en caso que se desee, la 
recomendación de Koza de crear 50% de los árboles de manera completa y 
50% de manera incompleta. 
Los conectivos lógicos A, v,-.,::::,,= son representados 1~n el programa por las 
funciones AND, OR, NOT, IMP y EQV respectivamente. Las últimas dos 
funciones no se encuentran definidas en LISP por lo que se declararon de la 
siguiente manera: 
; Definición de la implicación lógica. 
( defun imp ( a b ) 
(or (nota) b) 
) 
; Definición de la equivalencia. 
( defun eqv ( a b ) 
(ANO (IMP a b) (IMP b a)) 
) 
54 
En el caso de los cuantificadores, su definición se hace de 'manera similar: 
; Definición del cuantificador universal 
( definacro univ ( variable formula ) 
'(do 
) 
) 
( 
) 
( counter1 constantnumber) 
(result T) 
((or (NULL result) (zerop counterl)) result) 
( setf counterl (- counter 1 1 ) ) 
(setf ,variable (EVAL(first (getconstant counterl)))) 
(setf result (eval ,formula)) 
; Definición del cuantificador existencial 
( definacro exist ( variable formula ) 
'(do 
) 
) 
( 
) 
(counter2 constantnumber) 
(result NIL) 
((or result (zerop counter2)) result) 
(setf counter2 (- counter2 1 )) 
(setf ,variable (EVAL(first (getconstant counter2)))) 
(setf result (eval ,formula)) 
Es importante recalcar que este programa, como todos los demás, depende 
completamente de la previa declaración de la tabla de símbolos descrita 
anteriormente. 
55 
5.3 El programa SEMAN.LSP 
El programa seman.lsp tiene como propósito compilar una fórmula, que se 
supone bien formada, del calculo de predicados de primer orden para verificar 
que su estructura sintáctica y su semántica sean las corr,ectas. 
Para lograr el objetivo, se programó un parser de descenso recursivo al que 
después se le agrego la semántica, utilizando atributos sintetizados para obtener 
un evaluador recursivo. Una explicación detallada sobre los conceptos 
anteriores se puede encontrar en [ 1]. 
La gramática que se utilizó para el desarrollo fue: 
G = [{CS,VS ,FS,PS,and,or,imp,eqv,not,univ,exist ,=, 1-}, {T, A,F},F, P] 
donde P esta formado por: 
r ~ cs 
r~vs 
T~FSnTn 
A~l_ 
A~PSnr 
A~=TT 
F~A 
F~or F F 
F~and F F 
F~imp F F 
F~eqv F F 
F~not F 
F~univ VS F 
F ~exist VS F 
CS, VS, FS y PS son los conjuntos de símbolos descritos en el capítulo de 
Lenguajes de Primer Orden. 
56 
Se obtiene entonces, la siguiente tabla de parseo para la programación del 
evaluador recursivo: 
- l. es vs FS PS and or imp eqv not uruv exist 
T T¡ ½ ½ 
A A) A1 A2 
F F; F; F; F; F; ~ F's ~ F, F'g 
Para que el evaluador funcione correctamente, es necesario que, tanto los 
símbolos de función, como los símbolos de predicado, estén declarados en la 
tabla de símbolos de la siguiente manera: 
• Por cada símbolo de función, o predicado, crear una lista. 
• El primer elemento de la lista es el nombre del símbolo. 
• El segundo elemento de la lista es el rango de la función o predicado. 
• El último elemento de la lista es una lista que contiene: como primer 
elemento, el tipo de expresión que regresa la función o predicado; los demás 
elementos, definen el tipo de expresiones que recibe como parámetros. 
• Los tipos de expresiones son: E para los elementos atómicos y L para las 
listas. 
Por ejemplo: (father 2 (E E)), es una función de rango 2 que recibe como 
parámetro una expresión atómica y regresa otra expresión del mismo tipo. 
Finalmente, la salida del generador aleatorio de fórmulas es dada como entrada 
al compilador que, después de analizar la fórmula, nos regresa un valor 
Booleano: T (true) si la fórmula no contiene errores sintácticos o semánticos, o 
NIL (false), en el caso de que los contenga. 
57 
5.4 El programa EEPPLI.LSP 
Programa principal del sistema de lógica inductiva. En él, se implementa una 
estrategia evolutiva, basada en la programación genética, para hacer 
evolucionar fórmulas bien fonnadas del cálculo de predicados de primer orden. 
El primer paso en el algoritmo, es la inicialización de la población con fórmulas 
bien formadas, obtenidas del generador aleatorio. Como una de las entradas del 
programa, se pide el porcentaje de árboles completos en la población inicial. 
Cumplido el paso anterior, se procede a hacer evolucionar la población 
mediante las operaciones de reproducción y cruzamiento. Durante la selección 
de los individuos a ser copiados a la nueva población, se utiliza reescalamiento 
de la función objetivo para prevenir convergencia prematura del algoritmo. 
Una función muy importante en este programa, es la que calcula el .fitness de 
los elementos en la población. Como primera opción se utilizó una función que 
premiara a las fórmulas de la siguiente manera: 
• Un punto si la fórmula es evaluada con TRUE en el evaluador recursivo. 
• Dos puntos más, si la fórmula al evaluarse ( con EV Al) se le asigna un valor 
de TRUE, en caso contrario, se le suma un sólo punto. 
• Un punto más, si la fórmula contiene algún cuantificador. 
Como se puede observar, el valor máximo que se le puede asignar a una 
fórmula con esta evaluación es: cuatro. La razón de este tipo de evaluación es 
la necesidad de obtener fórmulas que sean válidas en d universo de discurso, 
que se define en la tabla de símbolos, siendo las más interesantes, aquellas que 
contienen algún cuantificador (preferentemente universal) .. 
Debido a los resultados obtenidos al utilizar la función de mérito anteriormente 
descrita, se decidió redefinirla (por razones que se explicarán más adelante en 
el manuscrito) de la siguiente manera: 
58 
l. Se crean nuevos Wliversos (que constituyen contraejemplos) en donde se 
definen las mismas relaciones, que existen en el universo que se desea 
analizar, pero de manera aleatoria. 
2. Las fónnulas son pasadas al evaluador recursivo. Si se consideran fórmulas 
bien fonnadas, continua su evaluación con las condiciones 3 y 4. 
3. Las fórmulas que son falsifica.bles en todos los mW1dos y las que son válidas 
en el universo analizado, pero que no contienen cuantificadores, son 
premiadas con un valor intermedio. Esta condición ,~s necesaria para poder 
mantener en la población, individuos que contengan símbolos lógicos y no 
lógicos. 
4. A las fónnulas, que solamente son válidas en el W1iverso de análisis, y que 
contienen cuantificadores, se les premia con el valor más alto de la función 
objetivo. 
Durante todo el proceso de evolución se lleva acabo ell mantenimiento de una 
bitácora que contiene los mejores individuos, en las distintas generaciones, para 
poder obtener el mejor individuo durante toda la ejecución del programa. 
Finalmente el programa termina cuando se llega a un número máximo de 
generaciones, definido al inicio del programa. 
59 
Capítulo 6 
Resultados 
El sistema de lógica inductiva fue probado utilizando la definición de un 
universo de discurso formado de la siguiente manera: 
• Un conjunto de símbolos de variable VS = {x1,···,x64 }. 
• Un conjunto de símbolos de constante CS={Mario, David, Jose, Martin, 
Ernesto}. Cada elemento del conjunto representa una persona en el mundo 
real. 
• Un conjunto de símbolos de función FS={father, abuelop}. La función 
father regresa el nombre del padre de la persona que se le manda como 
argumento. De igual manera, la función abuelop regresa el nombre del 
abuelo paterno de la persona. 
• Un conjunto de símbolos de predicados PS={parentp, grandp}. El 
predicado parentp recibe como parámetros dos constantes y regresa T si el 
primer argumento es padre del segundo argumento; de otra forma contesta 
NIL. Al predicado grandp se le mandan dos constantes como argumento y 
contesta T si la primera persona es abuelo paterno de la segunda~ de otra 
manera contesta NIL. 
60 
Con la asignación de elementos a los conjru1tos de símbolos anteriores se 
define W1 lenguaje de primer orden en el que sólo se encuentra definidas dos 
relaciones: padre y abuelo paterno. 
De ru1a manera inductiva, ru1a persona podría, a partir de los conjru1tos 
anteriormente descritos, obtener ru1a relación que describiera la relación que 
guardan el padre de ru1a persona y su abuelo paterno, es decir, llegaría a la 
conclusión de que para todo individuo el padre del padre es el abuelo paterno 
del mismo. 
Al alimentar estos datos a el sistema de lógica inductiva, se espera que este 
llegue a ru1a conclusión parecida. Para probarlo se hicieron varias pruebas 
utilizando los siguientes datos para ejecutar el programa. eeppli.lsp: 
• Tabla de símbolos: family5 .lsp ( contiene la definición del ru1iverso definido 
anteriormente). 
• Número de generaciones: 120. 
• Tamaño de la población: 1024. 
• Probabilidad de cruzamiento: 0.9 
• Coeficiente de reescalamiento: 4. 
• Profundidad máxima de los árboles: 7. 
Durante estas