Techniques

Defining symmetric relations in Prolog

Consider the Prolog program:

road(sf, la).
road(sf, portland).
road(la, denver).
road(denver, nyc).
road(chicago, denver).

road(X, Y) :- road(Y, X).

Obviously if there is a road from Chicago to Denver, then the same road connects Denver back to Chicago (unless it's one-way). To save the work of adding a bunch more facts like:

road(denver, chicago)

I simply created a rule that says the road relationship is symmetric. This makes sense logically, but computationally it leads the Prolog interpreter into an infinite loop:

road(sf, Y)
road(Y, sf)
road(sf, Y)
road(Y, sf)
etc.

To avoid this we introduce a new relationship as the symmetric closure of road:

roadTo(X, Y) :- road(X, Y); road(Y, X).

Note that semi-colon means "or". This could be rewritten as two rules:

roadTo(X, Y) :- road(X, Y).
roadTo(X, Y) :- road(Y, X).

Defining transitive relations in Prolog

The following KB is meant to define the prerequisite graph from a course catalog.

prereq(cs152, cs151).
prereq(cs151, cs46B).
prereq(cs46B, cs46A).
prereq (X, Y) :- prereq(X, Z), prereq(Z, Y).

The prerequisite relationship is transitive, meaning that if A is a prerequisite of B and B is a prerequisite of C, then A is a prerequisite of C. So the last rule makes sense, but computationally it leads the Prolog interpreter into another infinite loop:

prereq(cs152, X)
prereq (X, Y)
prereq(cs152, Z)
prereq (X, Y)
prereq(cs152, Z)
prereq (X, Y)
prereq(cs152, Z)
etc.

To fix this problem define prerequisite as the transitive closure of a simpler relationship:

prerequisite (X, Y) :- prereq(X, Y).
prerequisite (X, Y) :- prereq(X, Z), prerequisite(Z, Y).