prolog - transitivas - Cómo expresar una relación transitiva

relaciones reflexivas simetricas y transitivas

Question

Quiero expresar una relación transitiva. Si A hace referencia B y B hace referencia a C, A se refiere a C. Tengo esto:

proj(A).
proj(B).
proj(C).
ref(A,B).
ref(B,C).

Cuando consulto usando proj(A) obtengo:

[46]? -proj (A).
A = _639

¿Qué significa "_639"? Esperaba un sí o un no y obtuve esa extrañeza. Necesito agregar una regla para decir:

ref(A,C). y obtener SÍ. Idealmente, si es posible, me gustaría mostrar cómo se produjo esta relación: (A => B => C).

Answer 1

El _639 es una variable anónima _639 . Tus "hechos" tienen variables en lugar de átomos. Por ejemplo:

proj(A).   % This has a variable A and means "any A is a project"

Entonces si pregunto:

:- proj(X).
X = _blah    % anonymous variable: anything is a project!

Necesitas átomos:

proj(a).
proj(b).

Que resulta en la consulta:

:- proj(X).
X = a ;
X = b 

Si usted tiene:

ref(a,b).
ref(b,c).

Entonces, la forma más simple en Prolog para expresar una propiedad transitiva es declarando una regla (o lo que se conoce como un predicado en Prolog):

ref(A,C) :- ref(A,B), ref(B,C).

Esto dice que, ref(A,C) es verdadero si ref(A,B) es verdadero, Y ref(B,C) es verdadero. . Ejecutando la consulta:

:- ref(a,c).
true ;
Out of stack

O:

:- ref(a,X).
X = b ;
X = c ;
Out of stack

Entonces suena lógico pero tiene un problema: puede entrar en un ciclo debido a la autorreferencia. Una forma sencilla de evitar esto es hacer que el nombre de la regla sea diferente al hecho:

refx(A, B) :- ref(A, B).
refx(A, C) :- ref(A, B), refx(B, C).

Ahora si consulto:

:- refx(a, b).
true ;
no

:- refx(a, c).
yes

:- refx(a, X).
X = b ;
X = c
yes

Etc.

Todavía hay casos en que esto podría tener problemas de terminación, sin embargo, si los hechos contienen relaciones reflexivas o conmutativas. Por ejemplo:

ref(a,b).
ref(b,a).
ref(b,c).

En este caso, una consulta a refx(a, b) produce:

| ?- refx(a, b).
true ? ;
true ? ;
true ? ;
...

Como señala @ lambda.xy.x, esto podría resolverse rastreando dónde hemos estado y evitando repetir "visitas":

refx(X, Y) :-
    refx(X, Y, []).

refx(X, Y, A) :-
    ref(X, Y),
    /+ memberchk((X, Y), A).   % Make sure we haven''t visited this case
refx(X, Y, A) :-
    ref(X, Z),
    /+ memberchk((X, Z), A),   % Make sure we haven''t visited this case
    refx(Z, Y, [(X,Z)|A]).

Ahora terminamos con refx(a,b) y lo conseguimos una vez:

| ?- refx(a,b).
true ? ;
no
| ?-

Y refx(X, Y) produce todas las soluciones (aunque, algunas repeticiones debido a tener éxito más de una vez):

| ?- refx(X, Y).

X = a
Y = b ? ;

X = b
Y = a ? ;

X = b
Y = c ? ;

X = a
Y = a ? ;

X = a
Y = c ? ;

X = b
Y = b ? ;

X = b
Y = c ? ;

(2 ms) no