UNIVERSIDAD DE LOS ANDES
COORDINACION GENERAL DE ESTUDIOS INTERACTIVOS A DISTANCIA
MERIDA - VENEZUELA
Curso de Lógica y Matemática
Postgrado en Modelado y Simulación de Sistemas
MANUAL de PROLOG - BRATKO
EXPRESIONES BOOLEANAS
Este capítulo extiende el trabajo con expresiones en una dirección diferente, pero muy interesante para la computación fundamental. Primero, escribimos un programa para evaluar una expresión booleana el cual es similar a la evaluación de expresiones aritméticas. En la segunda parte, trabajaremos con la expresión en una manera simbólica y escribiremos un programa para transformar una expresión booleana en forma normal conjuntiva.
DEFINICIÓN DE OPERADORES
Antes de comenzar a trabajar con expresiones booleanas (lógicas), definimos algunos operadores los cuales simplifican la entrada de tales expresiones.
:- op(720,fy,non).
:- op(730,yfx,and).
:- op(740,yfx,or).
Ahora, podemos escribir (non a and b) en lugar de and(non(a),b) que es más voluminoso.
Podemos definir meta-operaciones las cuales pueden ser completamente transformadas hacia operaciones clásicas and, or, non.
:- op(710,yfx,implica).
:- op(710,yfx,equiv).
:- op(740,yfx,xor).
EVALUACIÓN
Durante la evaluación de una expresión aritmética explotamos el evaluador incorporado is el cual calcula el valor de una expresión numérica. Ahora, tenemos que definir procedimientos para evaluar las operaciones and, or, not en PROLOG.
and_d(false,true,false).
and_d(false,false,false).
and_d(true,false,false).
and_d(true,true,true).
or_d(false,true,true).
or_d(false,false,false).
or_d(true,false,true).
or_d(true,true,true).
non_d(true,false).
non_d(false,true).
Deberiamos también indicar cuales valores puden ser usados en las expresiones.
logic_const(true).
logic_const(false).
Ahora, es fácil escribir un evaluador para expresiones booleanas.
eval_b(X,X) :- logic_const(X).
eval_b(X and Y,R) :- eval_b(X,XV),eval_b(Y,YV),and_d(XV,YV,R).
eval_b(X or Y,R) :- eval_b(X,XV),eval_b(Y,YV),or_d(XV,YV,R).
eval_b(non X,R) :- eval_b(X,XV),non_d(XV,R).
La evaluación de meta-operaciones es transformada hacia la evaluación de operaciones clásicas en forma obvia.
eval_b(X implica Y,R) :- eval_b(Y or non X, R).
eval_b(X equiv Y,R) :- eval_b(X implica Y and Y implica X, R).
eval_b(X xor Y,R) :- eval_b((X and non Y) or (Y and non X), R).
NORMALIZACIÓN
En
esta sección, escribiremos un programa PROLOG para la
transformación de expresiones booleanas a la
forma normal conjuntiva.
La forma normal conjuntiva es una
expresión en la siguiente forma:
(a or non b) and c and
(b or d or non c).
Notar, que trabajamos con átomos arbitrarios en expresiones booleanas ahora y esos átomos no son interpretados, es decir, no conocemos su valor (true o false).
Primero, removemos las meta-expresiones, es decir, implica, equiv y xor las cuales son sustituidas por or, and y non.
ex2basic(X implica Y, R) :- ex2basic(Y or non X,R).
ex2basic(X equiv Y,R) :- ex2basic(X implica Y and Y implica X, R).
ex2basic(X xor Y,R) :- ex2basic((X and non Y) or (Y and non X), R).
ex2basic(X or Y, XB or YB) :- ex2basic(X,XB),ex2basic(Y,YB).
ex2basic(X and Y, XB and YB) :- ex2basic(X,XB),ex2basic(Y,YB).
ex2basic(non X, non XB) :- ex2basic(X,XB).
ex2basic(X,X) :- atomo(X).
Segundo, movemos la negación non a las fórmulas átomicas.
non2basic(non (X and Y),XN or YN) :- non2basic(non X,XN),non2basic(non Y,YN).
non2basic(non (X or Y),XN and YN) :- non2basic(non X,XN),non2basic(non Y,YN).
non2basic(non non X, XB) :- non2basic(X,XB)
non2basic(non X,non X) :- atomo(X).
non2basic(X and Y,XB and YB) :- non2basic(X,XB),non2basic(Y,YB).
non2basic(X or Y,XB or YB) :- non2basic(X,XB),non2basic(Y,YB).
non2basic(X,X) :- atomo(X).
Finalmente, podemos construir una forma normal conjuntiva.
ex2conj(X and Y,XC and YC) :- ex2conj(X,XC),ex2conj(Y,YC).
ex2conj(X or Y, R) :- ex2conj(X,XC),ex2conj(Y,YC),join_disj(XC,YC,R).
ex2conj(non X,non X).
ex2conj(X,X) :- atomo(X).
join_disj(X and Y,Z,XZ and YZ) :- join_disj(X,Z,XZ),join_disj(Y,Z,YZ).
join_disj(X,Y and Z,XY and XZ) :- X\=(_ and _),join_disj(X,Y,XY),join_disj(X,Z,XZ).
join_disj(X,Y,X or Y) :- X\=(_ and _),Y\=(_ and _).
Ahora, enlazamos los tres procedimientos de arriba hacia una forma compacta la cual transforma una expresión arbitraria a su forma normal conjuntiva. Nosotros llamamos este proceso normalización.
normalize(Ex,Norm) :-
ex2basic(Ex,Bas),
non2basic(Bas,NonBas),
ex2conj(NonBas,Norm).
Intenta optimizar la forma normal conjuntiva resultante removiendo las disyunciones que contiene un literal y su negación (ejemplo, a or non a, lo cual se sabe es true). Escribir procedimientos similares para la transformación a forma normal disyuntiva.
PROLOG es el lenguaje ideal para la computación simbólica.