In Answer Set Programming, what is the difference between a model and a least model?

I'm taking an artificial intelligence class and we are working with Answer Set Programming (Clingo specifically). We're talking mostly theory at the moment and I am having some trouble differentiating between models and least models. I have the following definitions:

Satisfying rules, models, least models and answer sets of definite program

A program is called definite if it does not have “not” in the body of its rules.

A set S is said to satisfy a rule of the form a :- b1, …, bm, not c1, …, not cn. if its body is satisfied by S (I.e., b1 … bm are in S and none of c1 ... cn are in S) implies that its head must be satisfied by S (i..e, a is in S).

A set S is said to satisfy a program if it satisfies all rules of that program.

A set S is said to be an answer set of a definite program P if (a) S satisfies P (also referred to as S is a model of P) and (b) No strict subset of S satisfies P (i.e., S is the least model of P).

With the question (pulled from the lecture slides, not homework):

P is defined as:
a :- b,e.
b. 
c :- d,b.
d.

Which of the following are models and least models?
{}, {b}, {b,d}, {b,d,c}, {b,d,c,e}, {b,d,c,e,a}

Can anyone let me know what the answer to the above question is? I can probably figure out the difference from there, although if someone could explain the difference in common speak (rather than text-book definition), that would be wonderful. I'm not sure which forum to post this question under - please let me know if it should be posted somewhere else.

Thanks

Solution

First of all, note that this section of your slides is talking about the answer sets of a positive program P (also called a definite program), even though it mentions also not. The positive program is the simple case, as for a positive program P there always exists a unique least model LM(P), which is the intersection of all it's models.

Allowing not rules in the rule bodies makes things more complex. The body of a rule is the right side of :-.

The answer to the question would be, set by set:

S={} is not a model, since b and d are facts b. d.
S={b} is not a model, since d is a fact d.
S={b,d} is not a model, since c is implied by c :- d,b. and c is not in S
S={b,d,c} is a model
S={b,d,c,e} is not a model, since a is implied by a :- b,e. and a is not in S
S={b,d,c,e,a} is a model

So what is the least model? It's S={b,c,d} since no strict subset of S satisfies P.

We can arrive to the least model of a positive program P in two ways:

Enumerate all models and take their intersection (here {b,c,d}∩{a,b,c,d,e}={b,c,d}).
Starting with the facts (here b. d.) and iteratively adding implied atoms (here c :- b,d.) to S, repeating until S is a model and stopping at that point.

Like your slides say, the definition of an answer set for a positive program P is: S is an answer set of P if S is the least model of P. To be stricter, this is actually if and only if, since the least model LM(P) is unique.

As a last note, so you are not later confused by them, a constraint :- a, b is actually just shorthand for x :- not x, a, b. Thus programs containing constraints are not positive programs; though they might look like they are at first, since the body of a constraint seemingly doesn't contain a not.