In our seminar for the Computational Logic Group at Iowa, we have been studying Logic Programming for the past couple semesters. We are continuing this semester, and have been reading “The Stable Model Semantics for Logic Programming” by Gelfond and Lifschitz (available on Citeseer here), which is a classic paper describing a semantics for logic programs with negation. I was interested to read this paper, as I am interested in datatypes in type theory and programming languages with negative occurrences (in the types of the constructors) of the type being defined. I am hoping that maybe some ideas from LP could possibly carry over to semantics for such datatypes. This is intellectually a bit of a longshot, but the paper is quite nice reading for anyone interested in computational logic.

Anyway, I want to record here a few notes from the discussion this past Friday, of Alain Mebsout, Nestan Tsiskaridze, Ruoyu Zhang, Baoluo Meng, and myself. First, some background from the paper. A clause is an implication where there is a conjunction, possibly empty, of literals (either atomic formulas or negated atomic formulas) in the antecedent of the implication, and a single atomic formula as the consequent. The authors work just with ground (i.e., variable-free) clauses, since a set of nonground clauses can be modeled as the (possibly infinite) set of all its ground instances. A program Pi is a set of clauses. The authors define an operation which I will denote here Pi/M, where M is a set of atomic formulas. The operation drops “not A” from the formula for every atom A which is not in M. And it drops every clause that contains “not A” (in the antecedent) where A is in M. The intuition is that we can pretend M is exactly the set of atoms we know to be true, and then simplify the clauses of Pi by looking at negated literals. If you negate an atom which is in M, then you are negating something which we are pretending is true, and hence the negation is definitely false. A clause containing such a literal is satisfied if we view M as determining a model (namely, the term model where exactly the atoms in M are made true by the interpretations of the predicates used in the atoms). So those clauses do not add any further information and can be dropped. From an operational perspective, such clauses would give rise to unsatisfiable (in M) subgoals, and so cannot possibly help to prove anything. Similarly, if a clause contains “not A” where A is not in M, then the literal “not A” is true in M, and hence cannot contribute anything as an antecedent of an implication. So that is why it is dropped from the clause.

If after performing this simplification the minimal set of atoms satisfying Pi is exactly M, then M is called a stable set for Pi. If we suppose the atoms in M are exactly the true ones and simplify away all negated literals, then the resulting formula’s minimal model is again M. So our assumed knowledge M is consistent with what we can deduce from it from the program. The paper gives examples of programs which have no stable sets, and which have more than one minimal stable set (i.e., a stable set none of whose subsets is stable).

On Friday, we worked through the proof of Theorem 1 of the paper, which states that if M is a stable set of Pi, then it is also a minimal model of Pi. This led us to consider a pair of propositions (which we did not take from the paper). Suppose M is a stable set of Pi, and suppose M’ is another set of atoms.

Proposition 1: if M’ satisfies Pi/M, then M’ satisfies Pi.

Proposition 2: if M’ satisfies Pi, then M’ satisfies Pi/M.

We delighted ourselves by managing to refute Proposition 2 and prove Proposition 1. For the refutation: a counterexample is if M is { p }, M’ is { q }, and Pi is {“p if not q”}. Pi/M is then just { p }, since we will drop the “not q” from the antecedent of “p if not q”. So M is stable, since the minimal model of Pi/M is M. M’ does satisfy Pi, because by making q true, M’ makes “p if not q” vacuously true (since “not q” is false). But M’ does not satisfy Pi/M, since it does not make “p” true.

For the proof of Proposition 1, we considered an arbitrary clause “A if As and not Bs” in Pi (where I am writing As for a vector of atoms and “not Bs” for a vector of negated atoms Bs). Suppose that clause does not have a corresponding one in Pi/M. This means that some Bi must be in M, since the operation Pi/M drops a clause if it contains a literal “not B” where B is in M. Since M is a stable model, Pi/M must entail Bi. If not, M would not contain Bi. Since M’ satisfies Pi/M by assumption for Proposition 2, this means Bi is also in M’, and hence M’ also satisfies the clause we are considering from Pi.

Now suppose that the clause “A if As and not Bs” from Pi does have a corresponding clause in Pi/M. The clause in Pi/M must be just “A if As”, since the transformation which retains a clause going from Pi to Pi/M just drops all negated literals from the clause. Since M’ satisfies Pi/M by assumption, it satisfies this clause “A if As”. Weakening the antecedent by conjoining in some more literals cannot change that fact. So M’ satisfies the original clause “A if As and not Bs” from Pi. So M’ satisfies every clause in Pi, as required by Proposition 2.