/*************************************************************/
/* */
/* Universidad de Alicante */
/* */
/* LOGICA DE PRIMER ORDEN */
/* Prolog */
/* */
/* */
/* S. O. : MS-DOS (Windows) */
/* Interprete : SWI-Prolog */
/* Fichero : EJ08.PL */
/* Programa : " FORMAS NORMALES " */
/* Proposiciones, comprueba si es una */
/* a Forma Normal Conjuntiva (FNC) y a */
/* Forma Normal Disyuntiva (FND). */
/* */
/* Se lanza con : */
/* ?- menu. */
/* */
/*************************************************************/
?- op(10,fx,no).
?- op(100,yfx,o).
?- op(100,yfx,y).
?- op(200,yfx,imp).
?- op(200,yfx,coimp).
/*-----------------------------------------------------------*/
/* PROGRAMA PRINCIPAL */
/* */
menu :- cabecera,
repeat,
leer(Formula),
hacer(Formula).
hacer(X) :- integer(X), X=0.
hacer('A') :- cabecera, ayuda, !, fail.
hacer('a') :- cabecera, ayuda, !, fail.
hacer(Formula) :- fbf(Formula),
formaNormal(Formula,FNC,FND),
escribirFormasNormales(FNC,FND),
pausa,!, fail.
hacer(_) :- pausa,!,fail.
/* */
/* Fin Programa Principal */
/* */
/*-----------------------------------------------------------*/
/*-----------------------------------------------------------*/
/* Determinar si es una Formula Bien Formada */
fbf((no P)) :- !,fbf(P).
fbf((P y Q)) :- !,fbf(P),fbf(Q).
fbf((P o Q)) :- !,fbf(P),fbf(Q).
fbf((P imp Q)) :- !,fbf(P),fbf(Q).
fbf((P coimp Q)) :- !,fbf(P),fbf(Q).
fbf(P) :- atom(P),!,proposicion(P).
nl, nl, !, fail.
/* proposicion(Prop) <- Prop es una variable proposicional */
proposicion(X) :- miembro(X,[p0,p1,p2,p3,p4,p5,p6,p7,p8,p9]),!.
ional'),
nl,nl,!,fail.
literal(X) :- X=..[Op,_,_],
miembro(Op,[y,o,imp,coimp]),!,fail.
literal(no X) :- literal(X).
literal(X) :- atom(X),proposicion(X).
/*-----------------------------------------------------------*/
/* Transformar a Forma Normal */
/* formaNormal(Form,Fnc,Fnd) <- Fnc es la Forma Normal Conjuntiva
y Fnd es la Forma Normal Disyuntiva
de Form */
formaNormal(Formula,FNC,FND) :- quitarImplicadores(Formula,F1),
normalizarNegadores(F1,F2),
exteriorizarConjuntor(F2,F31),
exteriorizarDisyuntor(F2,F32),
!, /* corte para liberar memoria */
ordenarFNC(F31,L41),
simplificar(L41,FNC),
ordenarFND(F32,L42),
simplificar(L42,FND).
/* quitarImplicadores(Form,Form1) <- Form1 es la fbf resultado de
eliminar implicadores y coimplicadores a la fbf Form */
quitarImplicadores((P imp Q),((no P1) o Q1)) :- !,quitarImplicadores(P,P1),
quitarImplicadores(Q,Q1).
quitarImplicadores((P coimp Q),(((no P1) o Q1) y ((no Q1) o P1))) :- !,
quitarImplicadores(P,P1),
quitarImplicadores(Q,Q1).
quitarImplicadores((P o Q),(P1 o Q1)) :- !,quitarImplicadores(P,P1),
quitarImplicadores(Q,Q1).
quitarImplicadores((P y Q),(P1 y Q1)) :- !,quitarImplicadores(P,P1),
quitarImplicadores(Q,Q1).
quitarImplicadores((no P),(no P1)) :- !,quitarImplicadores(P,P1).
quitarImplicadores(P,P).
/* normalizarNegadores(Form,Form1) <- Form1 es la fbf resultado de
normalizar los negadores a la fbf Form */
normalizarNegadores((no P),P1) :- !,negar(P,P1).
normalizarNegadores((P y Q),(P1 y Q1)) :- !,normalizarNegadores(P,P1),
normalizarNegadores(Q,Q1).
normalizarNegadores((P o Q),(P1 o Q1)) :- !,normalizarNegadores(P,P1),
normalizarNegadores(Q,Q1).
normalizarNegadores(P,P).
/* negar(Form,Form1) <- Form1 es la fbf resultado de negar la
fbf Form, pero teniendo en cuenta la
leyes de De Morgan */
negar((no P),P1) :- !,normalizarNegadores(P,P1).
negar((P y Q),(P1 o Q1)) :- !,negar(P,P1), negar(Q,Q1).
negar((P o Q),(P1 y Q1)) :- !,negar(P,P1), negar(Q,Q1).
negar(P,(no P)).
/* exteriorizarConjuntor(Form,Form1) <- Form1 es la fbf resultado
de exteriorizar los conjuntores de la fbf Form */
exteriorizarConjuntor((P o Q),R) :- !, exteriorizarConjuntor(P,P1),
exteriorizarConjuntor(Q,Q1),
fnc1((P1 o Q1),R).
exteriorizarConjuntor((P y Q),(P1 y Q1)) :- !, exteriorizarConjuntor(P,P1),
exteriorizarConjuntor(Q,Q1).
exteriorizarConjuntor(P,P).
fnc1(((P y Q) o R),(P1 y Q1)) :- !, exteriorizarConjuntor((P o R),P1),
exteriorizarConjuntor((Q o R),Q1).
fnc1((R o (P y Q)),(P1 y Q1)) :- !, exteriorizarConjuntor((R o P),P1),
exteriorizarConjuntor((R o Q),Q1).
fnc1(P,P).
/* exteriorizarDisyuntor(Form,Form1) <- Form1 es la fbf resultado
de exteriorizar los Disyuntores de la fbf Form */
exteriorizarDisyuntor((P y Q),R) :- !, exteriorizarDisyuntor(P,P1),
exteriorizarDisyuntor(Q,Q1),
fnd1((P1 y Q1),R).
exteriorizarDisyuntor((P o Q),(P1 o Q1)) :- !, exteriorizarDisyuntor(P,P1),
exteriorizarDisyuntor(Q,Q1).
exteriorizarDisyuntor(P,P).
fnd1(((P o Q) y R),(P1 o Q1)) :- !, exteriorizarDisyuntor((P y R),P1),
exteriorizarDisyuntor((Q y R),Q1).
fnd1((R y (P o Q)),(P1 o Q1)) :- !, exteriorizarDisyuntor((R y P),P1),
exteriorizarDisyuntor((R y Q),Q1).
fnd1(P,P).
/* ordenarFNC(Form,Form1) <- Form1 es la fbf resultado de ordenar las
variables proposicionales de las disyunciones */
ordenarFNC(F,L) :- crearListasFNC(F,Lista),
ordenarListas(Lista,L).
crearListasFNC(F,Lista) :- F=..[y,F1,F2],
crearListasFNC(F1,L1),
crearListasFNC(F2,L2),
concatena(L1,L2,Lista).
crearListasFNC(F,[Lista]) :- crearListaFNC(F,Lista).
crearListaFNC(F,[F]) :- literal(F),!.
crearListaFNC(F,Lista) :- F=..[o,F1,F2],
crearListaFNC(F1,L1),
crearListaFNC(F2,L2),
concatena(L1,L2,Lista).
ordenarListas([],[]).
ordenarListas([L1|L2],[LO1|LO2]) :- ordenarLista(L1,LO1),
ordenarListas(L2,LO2).
orden(E1,E2) :- atom(E1),atom(E2),!,E1@<E2.
orden(no E1,no E2) :- atom(E1),atom(E2),!,E1@<E2.
orden(E1,no E2) :- atom(E1),atom(E2),!,E1@=<E2.
orden(no E1,E2) :- atom(E1),atom(E2),!,E1@<E2.
/* ordenarFND(Form,Form1) <- Form1 es la fbf resultado de ordenar las
variables proposicionales de las conjunciones */
ordenarFND(F,L) :- crearListasFND(F,Lista),
ordenarListas(Lista,L).
crearListasFND(F,Lista) :- F=..[o,F1,F2],
crearListasFND(F1,L1),
crearListasFND(F2,L2),
concatena(L1,L2,Lista).
crearListasFND(F,[Lista]) :- crearListaFND(F,Lista).
crearListaFND(F,[F]) :- literal(F),!.
crearListaFND(F,Lista) :- F=..[y,F1,F2],
crearListaFND(F1,L1),
crearListaFND(F2,L2),
concatena(L1,L2,Lista).
/* simplificar(Form,Form1) <- Form1 es la fbf resultado de simplificar
y ordenar la fbf Form (formato listas)*/
simplificar(F,FS) :- simplifica1(F,F1),
simplifica2(F1,F2),
inversa(F2,F2I),
simplifica2(F2I,F3I),
inversa(F3I,FS).
simplifica1([],[]).
simplifica1([L|Resto],[L1|Resto1]) :- idempotencia(L,L1),
simplifica1(Resto,Resto1).
simplifica2([],[]).
simplifica2([L|Resto],Resto1) :- absorcion(L,Resto),!,
simplifica2(Resto,Resto1).
simplifica2([L|Resto],[L|Resto1]) :- simplifica2(Resto,Resto1).
/* Idempotencia: A o A = A , A y A = A */
idempotencia([],[]).
idempotencia([A|[A|Resto]],F) :- idempotencia([A|Resto],F).
idempotencia([A|Resto],[A|F]) :- idempotencia(Resto,F).
/* Absorcion e idempotencia */
absorcion(_,[]) :- !,fail.
absorcion(L1,[L2|_]) :- subconjunto(L2,L1).
absorcion(L1,[_|Resto]) :- absorcion(L1,Resto).
/*-----------------------------------------------------------*/
/* Pantalla de Ayuda */
ayuda :- nl,
write(' El programa lee una formula del Calculo de Proposiciones, comprueba que es'),nl,
write('una Formula Bien Formada (fbf), y la transforma a Forma Normal Conjuntiva'),nl,
write('(FNC) y a Forma Normal Disyuntiva (FND)'),nl,nl,
write(' Las connectivas usadas son:'),nl,
tab(10),write('no negacion'),
tab(10),write('imp implicador'),nl,
tab(10),write('y conjuncion'),
tab(8),write('coimp coimplicador'),nl,
tab(10),write('o disyuncion'),nl,nl,
write(' El Alfabeto utilizado es:'),nl,
tab(10),write('Proposiciones p0,...,p9'),nl,
nl.
/*-----------------------------------------------------------*/
/* Procedimientos diversos */
cabecera :- borraPantalla,
tica y Computacion'),nl,nl,
write('Practicas PROLOG_______________________________________________FORMAS NORMALES'),
nl,nl.
pausa :- nl,write('Pulsa <return> para continuar '),
skip(10).
/* borraPantalla <- borra la pantalla */
borraPantalla :- borraLinea(25).
borraLinea(1) :- !,nl.
borraLinea(N) :- nl,N1 is N-1,borraLinea(N1).
/**** LEER lee una formula del Calculo de proposiciones ****/
leer(F) :- nl,write(' Introduce la formula terminada en punto (.)'),
nl,write(' ( 0 Terminar / A Ayuda )'),nl,
nl,write(' FORMULA : '),
read(F).
/**** ESCRIBIR la formula en FNC y FND ****/
escribirFormasNormales(FNC,FND) :- nl,write('FORMA NORMAL CONJUNTIVA:'),nl,
escribeFNC(FNC),nl,
write('FORMA NORMAL DISYUNTIVA:'),nl,
escribeFND(FND).
escribeFNC([D|[]]) :- write('('),escribeDisyuncion(D),write(')'),nl.
escribeFNC([D|Resto]) :- write('('),escribeDisyuncion(D),
write(') y '),
escribeFNC(Resto).
escribeDisyuncion([A|[]]) :- write(A).
escribeDisyuncion([A|Resto]) :- write(A),write(' o '),
escribeDisyuncion(Resto).
escribeFND([C|[]]) :- write('('),escribeConjuncion(C),write(')'),nl.
escribeFND([C|Resto]) :- write('('),escribeConjuncion(C),
write(') o '),
escribeFND(Resto).
escribeConjuncion([A|[]]) :- write(A).
escribeConjuncion([A|Resto]) :- write(A),write(' y '),
escribeConjuncion(Resto).
/**** RUTINAS DE MANIPULACION DE LISTAS ****/
miembro(X,[X|_]).
miembro(X,[_|Y]) :- miembro(X,Y).
dando lugar a la lista L3 */
concatena([],L,L).
concatena([X|L1],L2,[X|L3]) :- concatena(L1,L2,L3).
/* ordenarLista(Lista,ListaOrdenada) <- ListaOrdenada es la lista
orden(E1,E2) */
ordenarLista([],[]).
ordenarLista([E|L],LO) :- ordenarLista(L,LO1),
insertar(E,LO1,LO).
insertar(E,[Y|L],[Y|L1]) :- orden(Y,E),!,insertar(E,L,L1).
insertar(E,L,[E|L]).
/* inversa(Lista,Inver) <- Inver es la inversa de la lista Lista */
inversa([],[]).
inversa([X|Y],L) :- inversa(Y,Z),
concatena(Z,[X],L).
/* subconjunto(L1,L2) <- la lista L1 es un subconjunto de la lista L2 */
subconjunto([X|Y],Z) :- miembro(X,Z),
subconjunto(Y,Z).
subconjunto([],_).
:- cabecera,ayuda,tab(4),write('El programa se lanza con :'),nl,
tab(20),write('?- menu.'),nl,nl.
/***************** FIN DEL PROGRAMA ************************/