# Is Datalog negation and the built-in predicate $\neq$ similar?

I was reading "Principles of Database & Knowledge-Base Systems, Vol. 1" by Jeffrey D. Ullman. There is a chapter about Datalog negation and as I was seeing the problems of negation I kept thinking that using the predicate $\neq$ would solve those problems but then I see the following:

p(X) :- r(X) & ¬q(X).

q(X) :- r(X) & ¬p(X).

The problem is this has 2 minimal models and if I'm not mistaken so does this:

p(X) :- r(X) & q(Y) & X $\neq$ Y.

q(X) :- r(X) & p(Y) & X $\neq$ Y.

Is there an equivalence between these 2 operators? If so, did I miss it or is it not mentioned that it's unsafe to use $\neq$ with recursion?

• Doesn't choosing $p,q$ to be the empty set satisfy the second clause set? I would expect that to be the least fixed point. – chi Jun 29 '17 at 8:36
• I've answered your same q on lambda-the-ultimate. – AntC Jul 4 '17 at 12:04

There was a misunderstanding in regards to the evaluation algorithm/minimal model.

The derivation of new values is atomic e.g.:

step 1:

• p = {}
• q = {}

step 2:

• p = r
• q = r

In step 2 p and q only see the value that each other had at step 1(the old value). I thought p and q would have access to the value of the current step and thus, the order of evaluation would produce different results.