Re: Negation In Prolog


> Hi,
>
> I have been looking at Prolog over the last week or so and have a
> question about negation.
>
> I have been trying to write a question and in the process have thought
> a little about negation in Prolog. Am I off the mark in my
> understanding?:
>
> ----------
>
> The logical statement
>
> not(p(X1, X2, ..., Xn))
>
> basically means "No X1, X2, ..., and Xn exist where p(X1, ... Xn)."
>
> However, in Prolog, this only works if all of Xi are first given a
> finite universe of possible values, before not(p(...)) is considered.
>
> Is this true?
>
> As a practical example, in a "family tree" Prolog program/database,
> you might try to include the rule
>
> single(X) :- not(married(X)).
>

In SWI Prolog not/1 is defined in terms of \+/1, that is

not(Goal) :- \+ Goal.

If a predicate (e.g. p/1) is not defined (has not a finite universe of
values) a call like this

?- \+ p(x).

raise an existence error. To implement a negation that fails even though a
predicate is not yet defined could be

not(Goal) :- catch(\+ Goal, error(existence_error(procedure, _), _), fail).
% a better implementation is possible, but the principle is this

This is a practice that I use often for dynamically defined predicates.

>
> but this won't work with the query single(Q) because you have not
> established a finite universe for Q. You could instead say:

I did not understand this... sorry.

>
> single(X) :- person(X), not(married(X)).
>
> and make sure that person(X) is true for all the "people" you are
> concerned about.
>
> ----------
>
> Is that correct?
>
> I cannot think of a situation where you would need an infinite
> universe. I have thought about, for example, the natural numbers as an
> infinite universe for an argument to NOT(p(...)) but it seems the
> rule can always be rewritten to not us NOT.
>
> For example, in
>
> negative(X) :- X < 0.
> nonnegative(X) :- not(negative(X).
>
> nonnegative can just be written:
>
> nonnegative(X) :- X >= 0.
>
> Are they any examples you know of where an easy rewrite like this is
> not possible?

Yes, in theory I think you are right. If you know how you can assess that a
particular object (number) has a property (negative, odd, integer, etc...),
I think you should know also how you can assess the contrary. But sometimes,
this can become very expensive. Think, for example, to implement both
is_prime/1 and is_not_prime/1 predicates, not defined one in terms of the
other. Take this as an exercise.

I am writing this, but I am late now. Sorry if I wrote something wrong.
Regards,
M

>
> Thanks,
> Sam
>
>
>
>
> Hi,
>
> I have been looking at Prolog over the last week or so and have a
> question about negation.
>
> I have been trying to write a question and in the process have thought
> a little about negation in Prolog. Am I off the mark in my
> understanding?:
>
> ----------
>
> The logical statement
>
> not(p(X1, X2, ..., Xn))
>
> basically means "No X1, X2, ..., and Xn exist where p(X1, ... Xn)."
>
> However, in Prolog, this only works if all of Xi are first given a
> finite universe of possible values, before not(p(...)) is considered.
>
> Is this true?
>
> As a practical example, in a "family tree" Prolog program/database,
> you might try to include the rule
>
> single(X) :- not(married(X)).
>
> but this won't work with the query single(Q) because you have not
> established a finite universe for Q. You could instead say:
>
> single(X) :- person(X), not(married(X)).
>
> and make sure that person(X) is true for all the "people" you are
> concerned about.
>
> ----------
>
> Is that correct?
>
> I cannot think of a situation where you would need an infinite
> universe. I have thought about, for example, the natural numbers as an
> infinite universe for an argument to NOT(p(...)) but it seems the
> rule can always be rewritten to not us NOT.
>
> For example, in
>
> negative(X) :- X < 0.
> nonnegative(X) :- not(negative(X).
>
> nonnegative can just be written:
>
> nonnegative(X) :- X >= 0.
>
> Are they any examples you know of where an easy rewrite like this is
> not possible?
>
> Thanks,
> Sam
>


.

Relevant Pages

  • Re: Negation In Prolog
    ... Negation is a dodgy subject. ... > a little about negation in Prolog. ... > finite universe of possible values, ... > Are they any examples you know of where an easy rewrite like this is ...
    (comp.lang.prolog)
  • Negation In Prolog
    ... a little about negation in Prolog. ... finite universe of possible values, ... infinite universe for an argument to NOT) but it seems the ... Are they any examples you know of where an easy rewrite like this is ...
    (comp.lang.prolog)
  • How to express (NOT A) AND (NOT B)
    ... a little about negation in Prolog. ... finite universe of possible values, ... Are they any examples you know of where an easy rewrite like this is ...
    (comp.lang.prolog)
  • Re: predicate in a predicate
    ... Prolog is somehow from Horn Clauses, they can have at most one ... how can I convert the FOL that have two positive ... With negation as failure you can go beyond horn clauses. ...
    (sci.logic)
  • Re: predicate in a predicate
    ... Prolog is somehow from Horn Clauses, they can have at most one ... how can I convert the FOL that have two positive ... With negation as failure you can go beyond horn clauses. ... positivity check is ok, so this amounts to prolog as: ...
    (sci.logic)