Prolog - Problem with SWI Prolog

Author

Problem with SWI Prolog

RuiSilva

2005-06-06, 8:57 am

Hi,

I have a doubt in logic to prolog (SWI Prolog).

the problem with the predicates (p,q,r,z) is:

if p then q.
or r or not q.
p.
if p then z
not z

Prove f.

In prolog:

q :- p.
????? How can we represent that expression?
p.
z :- p.
z :- fail,!. Is this correct????

Thank you very much for your help!!!

Rui Silva

Nick Wedd

2005-06-06, 3:58 pm

In message <42a40966$0$8843$a729d347@news.telepac.pt>, RuiSilva
<msmr@netcabo.pt> writes
>Hi,
>
>I have a doubt in logic to prolog (SWI Prolog).

( all this is the same for all Prolog systems, not only SWI Prolog )

>the problem with the predicates (p,q,r,z) is:

( those are not predicates, they are atoms )

>if p then q.
>or r or not q.
>p.
>if p then z
>not z
>
>Prove f.
>
>In prolog:

>if p then q.
can be written as
q :- p.

>or r or not q.
means, I think, "either r or not q", which could be written as
r :- q.

>p.
can be written as
p.

>if p then z
can be written as
z :- p.

>not z
Cannot be written directly in Prolog.

>Prove f.
could be written as ?- f.

If you want to represent logical deductions, using "facts" like "not z",
you can't do it directly in Prolog. But if you want to write some code
to handle such facts and use them to make deductions, Prolog is a good
language to write it in.

Nick
--
Nick Wedd nick@maproom.co.uk

goodrich_ms@yahoo.com

2005-06-06, 3:58 pm

RuiSilva wrote:
> Hi,
>
> I have a doubt in logic to prolog (SWI Prolog).
>
> the problem with the predicates (p,q,r,z) is:
>
> if p then q.
> or r or not q.
> p.
> if p then z
> not z
>
> Prove f.
>
> In prolog:
>
> q :- p.
> ????? How can we represent that expression?
> p.
> z :- p.
> z :- fail,!. Is this correct????
>
> Thank you very much for your help!!!
>
> Rui Silva

'if p then q' can be expressed as:

p :- q.

'if p then q or r or not q' can be expressed as:

p :-
( q
; r
; not(q)
).

Note that this assumes that the predicate 'q' is suitably defined
elsewhere.

Also 'not(z)' is not explictly defined; in Prolog 'z' is defined and
then Prolog is capable of deciding if 'not(z)' is true or false.

Finally to prove 'f', one simply asked Prolog to compute the following:

f.

Hope this helps,

-Mike Goodrich

Torkel Franzen

2005-06-06, 3:58 pm

goodrich_ms@yahoo.com writes:

> 'if p then q' can be expressed as:
>
> p :- q.

You have it backwards.

goodrich_ms@yahoo.com

2005-06-06, 3:58 pm

oops, you are right.

goodrich_ms@yahoo.com

2005-06-06, 3:58 pm

Well I pretty much botched the whole post, sorry.

As was pointed out, I have this backwards; as written what I have is:

q->p (if q then p)

Also the second one makes no sense, since it would always be true (q ^
~q)

And so Prolog clauses are witten with the consequent stated in the head
and the antecedents in the body.

So consider

p -> q 'p implies q' or 'if p then q':

Prolog:
q :- p % literally 'q if p'

r V s V ~q -> p 'if [r or s or not(q)] then p'

Prolog:

p :-
( r
; s
; not(q)
). % literally 'p if r or s or not(q)'

And so on.

-mg

Bert.VanNuffelen+google@cs.kuleuven.ac.be

2005-06-08, 8:58 am

your reading as if-then-else is "almost right".
It is often used, yet not totally precise. Actually you read Prolog
clauses

p:-q.
p:-r.

better as "p is defined as q or r".
When p is a not recursive it is equivalent with the reading

"p if and only if q or r".

This is because Prolog includes the Closed World Assumption in its
inference process.
By this reading it follows that Prolog can derive that p is false if
both q and r are false.

If it was classical First Order Logic implication, Prolog should be
able to derive that p is true if q and r are false (because from false
anything can follow...), which is not the case.

In case of negation and recursion, the if and only if reading/inference
breaks down and yields non-intuitive answers. (e.g. Prolog loops.) The
better declarative reading for the neck symbol ":-" is "is defined
by", and which can be given a precise mathematical formal semantics.
[See papers by M. Denecker on inductive definitions for technical
reading on this]

If you try a "Prolog with better declarative readings and formal
semantics" try any of the answer set programming systems or abductive
reasoning systems (DLV,sModels,Asystem,... see the website of the
Workgroup on Answer Set Programming (WASP))

best regards,

Bert

ps. The confusion between "Classical FOL" and "Prolog view on FOL" can
lead to heated debates, in which people defend their view on "logic" as
the right one, but fail to understand that they are talking about a
different logic. (see deductive databases track in this newsgroup) By
this again: Prolog is not FOL and FOL is not Prolog.

Torkel Franzen

2005-06-08, 8:58 am

Bert.VanNuffelen+google@cs.kuleuven.ac.be writes:

> If it was classical First Order Logic implication, Prolog should be
> able to derive that p is true if q and r are false (because from false
> anything can follow...),

p is not a logical consequence of "p if and only if q or r",
"not-r", "not-q".

> In case of negation and recursion, the if and only if reading/inference
> breaks down and yields non-intuitive answers.

The use of the completion in interpreting a Prolog program works
just as well with recursive as with non-recursive clauses. What
"breakdown" do you have in mind?

Bert.VanNuffelen+google@cs.kuleuven.ac.be

2005-06-08, 8:58 am

Hi,

Lets explain it by the classical transitive closure example.

ancestor(X,Y):- parent(X,Y).
ancestor(X,Y):- ancestor(X,Z), ancestor(Z,Y).

You intend to write the transitive closure of the parent relation which
is a finite relation for a acyclic graph. Every person can construct
that without any problem.
However Prolog goes into an infinite loop. Even more, the completion
semantics have models for the ancestor relation that are not the
transitive closure. Hence, Prolog and the completion semantics break
down the relation between our intentions of the program and what we
actually get by Prolog.

This is *very* unnatural behavior in the context that one tried
(tries?) to sell Prolog as a "declarative specification language: write
what you intend and the system will do the reasoning for you".
In the case of the transitive closure it is clearly not the case.
(Negation makes it even worse.)

On the completion:

The FOL theory

{p <-> q or r} has the models {p,q,r} {p,q},{p,r} and {}

The FOL theory
{p<- q, p<-r} has the models {r,p,q} {q,p}, {r,p}, {} and {p}

The last model is due to the fact that if q and r are false you didn't
restrict the value of p.

As you pointed out, indeed p is not a logical consequence of any of
these FOL theories. because there is each time one model that does not
contain p.

Bert

Torkel Franzen

2005-06-08, 8:58 am

Bert.VanNuffelen+google@cs.kuleuven.ac.be writes:

> However Prolog goes into an infinite loop.

Prolog will loop in non-recursive cases as well. A logical interpretation
of Prolog programs only guarantees that *if* Prolog produces a
solution, the corresponding statement is a logical consequence of the
program.

Bert.VanNuffelen+google@cs.kuleuven.ac.be

2005-06-09, 8:57 am

Torkel Franzen schreef:
> Bert.VanNuffelen+google@cs.kuleuven.ac.be writes:
>
>
> Prolog will loop in non-recursive cases as well. A logical interpretation
> of Prolog programs only guarantees that *if* Prolog produces a
> solution, the corresponding statement is a logical consequence of the
> program.

I do not understand the intention of your comment.
The example shows that the operational semantics of Prolog are not good
enough to compute a finite transitive closure. Moveover the completion
semantics as formal semantics of the logic program is not suffient to
characterize uniquely the transitive closure. Thus better formal
semantics (e.g. the Well-founded) are needed.

My original comment was on the reading of the logic program as FOL
implications in the context of Classical FOL.
This reading is clearly not the intented reading of the ancestor
program.
I think that instead of telling novice people to Prolog, that you write
FOL implications, you write definitions of a certain concept. That
comes in my opinion closer to the practice and the declarative reading
of the rules we often write.
I've written a lot of Prolog code over the years, yet I'll think almost
none of my Prolog was a pure First Order Implication. (Actually, most
of the code was not interpretable as a logic theory (due to cut,
corouting, io, ...). And in that case, the "is defined as"
interpretation is even more better because it is closer to the
imperative languages notion of a procedure.)

Bert

ps. I like to see your looping, non-recursive Prolog program.

goodrich_ms@yahoo.com

2005-06-09, 3:58 pm

Yes, I see your point.

I did have in mind both the closed-world assumption, and that Prolog
clauses are better viewed inductively vice dedeuctively. While I did
not mention the former, it would have been good to have framed my
comments in light of the latter.

cheers,

-mg

Torkel Franzen

2005-06-10, 8:57 am

Bert.VanNuffelen+google@cs.kuleuven.ac.be writes:

> I do not understand the intention of your comment.

My comment was wrong in that directly or indirectly recursive clauses
are indeed needed for looping, contrary to my comment.

> My original comment was on the reading of the logic program as FOL
> implications in the context of Classical FOL.
> This reading is clearly not the intented reading of the ancestor
> program.

We read definitions such as that of transitive closure as inductive
definitions, just as we do in mathematics. In other words, the
intended model is the smallest model. But the logic programming part
of Prolog consists only in this, that we can often, by introducing
a set of statements S as an interpretation of the program, verify
that any answer found by Prolog is a logical consequence of the
program. This may or may not be helpful in programming, and often is.

Sponsored Links