Search code examples
logic-programminganswer-set-programming

Why DLV finds an answer set rather than another, in this ASP example program?

I tried two simple programs in ASP(Answer Set Programming) and then i used the answer set solver DLV to find the answer sets (also referred as stable models); the programs are

P1:

b :- c.  
c.

P2:

b :- c.  
f.

in P1 dlv finds {c, b} as answer set, in P2 the answer set found is {f}; i can't understand why the answer set is {c,b} in P1, and is only {f} in P2; is not enough {c} in P1 as (minimal) model?

Thank you

Solution

  • That's because {c} is not a model of P1.

    In the case of ground (no variables) positive (all bodies positive) programs, the constraints are pretty simple:

    1. For an interpretation to be a model of a ground positive program, every applicable rule must also be applied, where:

      • applicable: for ground positive programs, all literals in the body are contained in the interpretation,
      • applied: a head atom is contained the interpretation.
    2. For a model to be an answer set, it has to be minimal among the set of all models of this program.

    So, in P1 you have this rule:

    b :- c.

    which, for the interpretation {c}, is applicable (since c is in the interpretation), but not applied (because b isn't).

    As for P2, we have the fact f., implying you have to have f in any answer set (since f. is the same f :-, meaning it's always applicable). However, f does not render the rule b :- c applicable, and there are no other rules, so {f} is a model of P2, and obviously also a minimal one - an answer set.

    Because of that, e.g. {c,b,f} is not an answer set of P2, since it's not minimal when compared with {f}.