rels.pro
Matemáticas Discretas: Relaciones
Alberto Pacheco, apacheco@itch.edu.mx, Nov'98, Ago'99
Amzi! 16-bit Logic Explorer Prolog 3.3
EJERCICIOS: [1] [2] [3]
1. ¿Cómo se usa el programa? ¿Cómo se corre paso-a-paso?
% Desde el Listener consulte 'rels.pro' y ejecute:
?- debug.
% Seleccione format = 'off'
% Escriba en el Listener:
?- listing(a).
?- reflexiva.
% Corra paso a paso con el boton 'Creep' del Debugger
% Borre el símbolo de comentario % de la última relacion a(), grabe y reconsulte.
?- listing(a).
?- reflexiva.
?- listing(b).
?- simetrica.
% Elimine comentario ultima relacion b(), salve programa, y reconsulte.
?- listing(b).
?- simetrica.
Repita el procedimiento para las sigs. propiedades:
transitiva (c), irreflexiva (d), asimetrica (e)
2. ¿Por qué es necesario el misterioso código !,fail. ("cut & fail") ?
% Ver 1.0: Modifique las claúsulas de la propiedad "irreflexiva"
(una sóla claúsula sin las operaciones "cut & fail"):
irreflexiva(X,X) :-not(d(X,X)).% Grabe, consulte y anote el query:
?- irreflexiva(X,Y).X=1, Y=2; % Obtenga cada resultado escribiendo punto-y-coma;..% Ver 2.0: Usando "fail" se produce el "backtracking"
irreflexiva(X,X) :-not(d(X,X)),fail.?- irreflexiva(X,Y).X=1, Y=2;..% Ver 3.0: Demostración por contradicción o contraejemplo
% Usando cut (!) se termina el backtracking al encontrar un contraejemplo
% La segunda claúsula regresa "cierto" si no se demostra el contraejemplo
irreflexiva :- % regresa "falso"d(X,X),!, fail.irreflexiva. % regresa "cierto"?- irreflexiva.true.3. En el caso de la propiedad reflexiva ¿Por qué es necesaria la segunda claúsula?
Si recuerda en el ejercicio 1 al agregar el par ordenado a(11,9), la propiedad reflexiva regresaba falso. Modifique el programa encerrando entre comentarios la segunda claúsula de "reflexiva" y observe que regresa al ejecutar el query:?- reflexiva.¿Qué valor regresa?.. ¿es correcto?.. explique..*/
%-- R es reflexiva si para toda x
S, existe xRxa(1,1).
a(3,3).
a(5,5).
a(7,7).
% a(11,9). % switch
reflexiva :-
a(X,_),
not(a(X,X)),
!, fail.
reflexiva :-
a(_,X),
not(a(X,X)),
!, fail.
reflexiva.
%-- R es simetrica, si para cada xRy existe yRx
b(1,3).
b(3,1).
b(5,7).
b(7,5).
% b(11,9). % switch
simetrica :-
b(X,Y),
X\=Y,
not(b(Y,X)),
!, fail.
simetrica.
%-- R es transitiva si siempre que se tiene xRy y yRz existe xRz
c(1,3).
c(3,5).
c(1,5).
c(2,4).
c(4,6).
% c(2,6). % switch
transitiva :-
nr(X,Y),
nr(Y,Z),
not(c(X,Z)),
!, fail.
transitiva :-
nr(X,Y),
nr(Y,Z),
c(X,Z).
nr(X,Y) :-
c(X,Y),
X\=Y.
%-- R es irreflexiva si para toda x, no existe xRx
d(1,2).
d(3,4).
d(5,6).
d(7,8).
d(9,9). % switch
irreflexiva :-
d(X,X),
!, fail.
irreflexiva.
%-- R es asimetrica, si para cada xRy no existe yRx
e(1,3).
e(3,2).
e(5,7).
e(7,6).
% e(7,5). % switch
asimetrica :-
e(X,Y),
X\=Y,
e(Y,X),
!, fail.
asimetrica.