CODEWITHSUNDEEP
prolog
Andreas_Lng
Andreas_Lng

Reputation: 1197

Minimal Herbrand model

Given the following prolog program:

way(a,b,c).
way(a,d,e).
way(b,f,g).
way(f,h,i).
way(h,j,k).
way(l,j,m).
reachable(a, []).
reachable(X, [W|WS]) :- reachable(Y, WS), way(Y,X,W).

What is the minimal herbrand model using T-operator?

Let I be an interpretation, then:

I_0 = \emptyset
I_1 = T_P(I_0) = {a,b,c,d,e,f,g,h,I,j,k,l,m} // all constants
I_2 = T_P(I_1) = I_1 \cup {way(a,b,c), way(a,d,e), way(b,f,g), way(f,h,i), way(h,j,k), way(l,j,m), reachable(a, [])}

But now I don't know how to continue. Can anyone please help?

Upvotes: 0

Views: 388

Answers (1)

Dima Chubarov
Dima Chubarov

Reputation: 17179

reachable/2 is a recursive predicate. What you have to do is to apply the last rule until the interpretation remains the same after the application. 

I_3 = T_P(I_2) = I_2 \cup {reachable(b, [c]),reachable(d, [e])}
I_4 = T_P(I_3) = I_3 \cup {reachable(f, [g,c])}
....
I_6 = T_P(I_5) = I_5 \cup {reachable(j, [k,i,g,c])}
I_7 = T_P(I_6) = I_6

Intuitively an element X is reachable if there exists Y that is reachable and there is a way(Y,X,W) for some W. This W is added to the second argument after the application of the rule.

You may now explicitly enumerate all elements in I_6 to obtain the minimal model.

Upvotes: 1

Related Questions