Prolog - Negation In Prolog

Author

Negation In Prolog

samuel.kelly@gmail.com

2005-10-18, 9:56 pm

[Last post was titled wrong. Don't let the subject
confuse you; it is not the question I am asking!]

Hi,

I have been looking at Prolog over the last w

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

Hi,

I have been looking at Prolog over the last w

Mauro Di Nuzzo

2005-10-19, 6:59 pm

> Hi,
>
> I have been looking at Prolog over the last w

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 w

Duncan Patton

2005-10-19, 9:56 pm

Negation is a dodgy subject. I use the following hack:

not(Goal):-Goal,!, fail.
not(_):-true.

Which claims something is false if you can't prove it so, which is,
of course, an unsupportable contention. In fact, it is best to
avoid using truth by negation in programming for the reason that
constructive proofs do not suffer this infirmity.

Dhu

On 18 Oct 2005 19:44:45 -0700
samuel.kelly@gmail.com wrote:

> [Last post was titled wrong. Don't let the subject
> confuse you; it is not the question I am asking!]
>=20
> Hi,
>=20
> I have been looking at Prolog over the last w

or so and have a
> question about negation.
>=20
> 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?:
>=20
> ----------
>=20
> The logical statement
>=20
> not(p(X1, X2, ..., Xn))
>=20
> basically means "No X1, X2, ..., and Xn exist where p(X1, ... Xn)."
>=20
> However, in Prolog, this only works if all of Xi are first given a
> finite universe of possible values, before not(p(...)) is considered.
>=20
> Is this true?
>=20
> As a practical example, in a "family tree" Prolog program/database,
> you might try to include the rule
>=20
> single(X) :- not(married(X)).
>=20
> but this won't work with the query single(Q) because you have not
> established a finite universe for Q. You could instead say:
>=20
> single(X) :- person(X), not(married(X)).
>=20
> and make sure that person(X) is true for all the "people" you are
> concerned about.
>=20
> ----------
>=20
> Is that correct?
>=20
> 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.
>=20
> For example, in
>=20
> negative(X) :- X < 0.
> nonnegative(X) :- not(negative(X).
>=20
> nonnegative can just be written:
>=20
> nonnegative(X) :- X >=3D 0.
>=20
> Are they any examples you know of where an easy rewrite like this is
> not possible?
>=20
> Thanks,
> Sam
>=20
>=20
>=20
>=20
> Hi,
>=20
> I have been looking at Prolog over the last w

or so and have a
> question about negation.
>=20
> 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?:
>=20
> ----------
>=20
> The logical statement
>=20
> not(p(X1, X2, ..., Xn))
>=20
> basically means "No X1, X2, ..., and Xn exist where p(X1, ... Xn)."
>=20
> However, in Prolog, this only works if all of Xi are first given a
> finite universe of possible values, before not(p(...)) is considered.
>=20
> Is this true?
>=20
> As a practical example, in a "family tree" Prolog program/database,
> you might try to include the rule
>=20
> single(X) :- not(married(X)).
>=20
> but this won't work with the query single(Q) because you have not
> established a finite universe for Q. You could instead say:
>=20
> single(X) :- person(X), not(married(X)).
>=20
> and make sure that person(X) is true for all the "people" you are
> concerned about.
>=20
> ----------
>=20
> Is that correct?
>=20
> 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.
>=20
> For example, in
>=20
> negative(X) :- X < 0.
> nonnegative(X) :- not(negative(X).
>=20
> nonnegative can just be written:
>=20
> nonnegative(X) :- X >=3D 0.
>=20
> Are they any examples you know of where an easy rewrite like this is
> not possible?
>=20
> Thanks,
> Sam
>=20

--=20
???????????????????????????????????????

Can't get good help? =20

Contact Fubar the Hack: fubar AT neotext.ca

Area code seven eight zero, Exchange four six six, Local zero one zero nine

Highland terms, Canadian workmanship.

All persons named herein are purely fictional victims
of the Canidian Bagle Breeder's Association.

Save the Bagle!=20

Sun =D0hu

???????????????????????????????????????

Torkel Franzen

2005-10-20, 4:03 am

Duncan Patton <campbell@neotext.ca> writes:

> Negation is a dodgy subject. I use the following hack:
>
> not(Goal):-Goal,!, fail.
> not(_):-true.

Your comment is somewhat odd, since this is how the ISO predicate
\+ is defined, not any personal hack of yours.

> Which claims something is false if you can't prove it so, which is,
> of course, an unsupportable contention.

It is perfectly supportable, depending on what you're talking about.

> In fact, it is best to
> avoid using truth by negation in programming for the reason that
> constructive proofs do not suffer this infirmity.

What do you mean by "truth by negation"? And what do you take to be
the relevance of constructive proofs?

russell kym horsell

2005-10-20, 4:03 am

Torkel Franzen <torkel@sm.luth.se> wrote:
> Duncan Patton <campbell@neotext.ca> writes:
> Your comment is somewhat odd, since this is how the ISO predicate
> \+ is defined, not any personal hack of yours.
> It is perfectly supportable, depending on what you're talking about.
[...]

I treat these as jokes.

OT1H subject comments its "unsafe" to base the proof of a negative
on what is not known.

OTOH the claim is the nearest example of what is complained of. ;-)

Duncan Patton

2005-10-20, 4:03 am

On Thu, 20 Oct 2005 04:17:11 +0000 (UTC)
russell kym horsell <kym@otaku.freeshell.org> wrote:

> Torkel Franzen <torkel@sm.luth.se> wrote:
> [...]
>=20
> I treat these as jokes.
>=20
> OT1H subject comments its "unsafe" to base the proof of a negative
> on what is not known.
>=20
> OTOH the claim is the nearest example of what is complained of. ;-)

Had we but world enough and time, a better canard would be mine ;)

Dhu

--=20
???????????????????????????????????????

Can't get good help? =20

Contact Fubar the Hack: fubar AT neotext.ca

Area code seven eight zero, Exchange four six six, Local zero one zero nine

Highland terms, Canadian workmanship.

All persons named herein are purely fictional victims
of the Canidian Bagle Breeder's Association.

Save the Bagle!=20

Sun =D0hu

???????????????????????????????????????

Torkel Franzen

2005-10-20, 4:03 am

russell kym horsell <kym@otaku.freeshell.org> writes:

> I treat these as jokes.

Alas, I have become a stodgy grumbler.

Sponsored Links