# how to do incremental construction of the minimal model in logic programming?

I was reading a book titled "Essentials of Logic Programming.", most parts of the book are easy to understand. but now having a problem with Theme 45: incremental constructions of the minimal model. The relevant parts are shown below.

Some notations: $$P$$ is a definite program, $$B(P)$$ is the Herbrand base of $$P$$, $$G(P)$$ is a ground instantiation of $$P$$, $$MM(P)$$ is a minimal model of $$P$$.

Theme 45 explains the incremental constructions of the minimal model as follows.

The method starts by choosing some interpretation $$I_1 \subseteq B(P)$$. Later on, we shall see that there is a preferred choice of $$I_1$$ and that not all choices are adequate. Choosing $$I_1$$ can be viewed as guessing which atoms have to be true in any model of $$P$$. Now consider any clause in $$G(P)$$ kind(Chris) q if body

if our guess assigns true to all atoms in this body then an immediate consequence of that guess is that q should also be made true, for otherwise the clause as a whole would be made false. Our next iterate $$I_2$$ comprise just those heading atoms q made true by this argument. This new iterate will not necessarily contain all those body atoms which justified the introduction of the new atoms q; this does not matter - successive iterates will eventually introduce and retain all of these atoms which must be true in any model of the program. Consider this example of a program $$P$$ on the domain $$H=\{ dov,chris\}$$:

kind(X) if nice (X)

nice(X)

whose ground instantiation $$G(P$$ is highly abbreviated form is

kind(dov) if nice(dov)

kind(Chris) if nice(Chris)

nice(dov)

(where K=kind, N=nice, D=dov,C=Chris)

and suppose we choose $$I_1= \{ kind(dov),nice(Chris)\}$$. Applying the above method yields $$I_2= \{ nice(dov), kind(Chris)\}$$ and $$I_3= \{ nice(dov), kind(dov)\}$$ All further iterates merely replicates $$I_3$$, which is accordingly referred to as a fixpoint. We have, in fact, converged upon the minimal model $$MM(P)$$.

Let me explain how I understand or did not understand this example.

1. is $$I_1$$ a guess? why not just make $$I_1 = \{ nice(Chris)\}$$?
2. nice(Chris) leads to kind(Chris) is true, so "kind(Chris) if nice(Chris)" is true. So, we have kind(Chris) in $$I_2$$. But why there is nice(dov) in $$I_2$$?
3. as said further iterates will replicate $$I_3$$, but I did not see how this works because I did not see the iterate from $$I_1$$ to $$I_2$$.

I just did not get this example. Could anyone clarify it to me?

• Please expand all the abbreviations. Sep 30, 2023 at 3:26
• @ShyPerson abbreviations are given: where K=kind, N=nice, D=dov, C=Chris. This is exactly what is written in the book.
– alim
Oct 3, 2023 at 14:43

this paragraph describes the immediate consequences operator $$T_P(I) = \{ a \mid \text{there exists a rule } r \in G(P) \text{ with } head(r)=a \text{ and } body(r) \subseteq I \}$$ for some interpretation $$I$$ modelled as a set of ground terms.

What is the significance of this operator ? We start from an interpretation and try to find a model. Now it might be the case that there are rules where the body is true, but the head is not yet true. In order to create a model we have to add the new head to the interpretation which is done by $$T_P$$. Since we are especially interested in the least model, we also don't want unnecessary items, i.e. elements for which is no rule with a true body. This is the second effect of this operator.

Now we look at the example. They start with $$I_1 = \{ kind(dov),nice(Chris)\}$$ and we will check every rule from $$G(P)$$ to compute $$I_2 = T_P(I_1)$$

1. kind(dov) if nice(dov): nice(dov) is not in $$I_1$$, so we don't need kind(dov) in $$I_2 = \emptyset$$
2. kind(Chris) if nice(Chris): nice(Chris) is inside $$I_1$$ we need kind(Chris) in $$I_2 = \{ kind(Chris)\}$$
3. nice(dov): This rule has no body so is always true. So we also need this in the body. Now $$I_2 = \{kind(Chris), nice(dov) \}$$

Now we repeat this process with $$I_2$$ and compute $$I_3 = T_P(I_2)$$. At the start $$I_3 = \emptyset$$ as previously.

1. kind(dov) if nice(dov): Now nice(dov) is in $$I_2$$, so $$I_3 = \{kind(dov) \}$$
2. kind(Chris) if nice(Chris): nice(Chris) is not in $$I_2$$ so $$I_3$$ stays the same.
3. nice(dov): is the same as previously

So $$I_3 = \{ kind(dov), nice(dov) \}$$. Try it with this again and you will notice that $$I_4 = T_P(I_3)$$ equals $$I_3$$ is a fixed-point of $$T_P$$. This is significant as we can now stop our computation.

Now is this dependent on the program and we were lucky ? If you analyse the operator $$T_P$$ on interpretations, you will notice that it is monotonouos and by the Knaster-Tarski-fixed-point-theorem exists always a least fixed point. This can be proven to be the same as the minimal model of a definite logic program.

The interpretation $$I_1$$ was choosen arbitrarly. Does it matter which interpretation we start with ? Consider the following logic program $$P_2$$ (which is already grounded):

$$p \leftarrow q \\ q \leftarrow p$$

You will notice that it has two fixed-points $$\emptyset$$ and $$\{ p,q\}$$. Each of them is a model, but $$\emptyset$$ is the least model. This is the result by starting with $$\emptyset$$. In fact, the Kleene-fixed-point-theorem tells us that starting with the minimum element is the way to calculate the least fixed-point (if some conditions hold).

If you would start however with $$\{p\}$$ you would alternate between $$\{p\}$$ and $$\{q\}$$ and would never reach a fixed-point, so the choice matters.

• Now I realize that I missed that "nice(dov)" is always true, because it is just a fact (correct me if I am mistaken). The second example is a very nice one. It is clear now, Thank you!
– alim
Oct 8, 2023 at 5:03