Home > Archive > Prolog > March 2004 > Can all clauses be represented as Horn Clauses?
You are viewing an archived Text-only version of the thread.
To view this thread in it's original format and/or if you want to reply to
this thread please [click here]
| Author |
Can all clauses be represented as Horn Clauses?
|
|
| Minti 2004-03-27, 12:10 am |
| Hi,
I was reading about horn's clauses, I would like to know if every
fact that can be represented as clause [non Horn] can be represented
as a Horn clause. I know the answer would be yes [ probably ]. But I
would also like to know about the logical proof that proves the
equivalence.
--
Imanpreet Singh Arora
isingh AT acm DOT org
| |
| Torkel Franzen 2004-03-27, 12:10 am |
| mintiSPAMBLOCK@yahoo.com (Minti) writes:
>I was reading about horn's clauses, I would like to know if every
> fact that can be represented as clause [non Horn] can be represented
> as a Horn clause. I know the answer would be yes [ probably ].
P v Q
| |
| David C. Ullrich 2004-03-27, 12:10 am |
| On 20 Mar 2004 11:32:20 +0100, Torkel Franzen <torkel@sm.luth.se>
wrote:
>mintiSPAMBLOCK@yahoo.com (Minti) writes:
>
>
> P v Q
Assuming I'm reading the somewhat vague definitions I found on
Google correctly, that's an extremely clever example.
Is it correct that a "clause" is something of the form A1 v ... An,
where each Ai is either an atomic formula or the negation of
an atomic formula, and a clause is a Horn clause if at most
one Ai is not a negation? (That's the impression I get from
MathWorld; otoh I can't believe that's the actual definition
because if so it's hard to see how anyone could be unable
to come up with an example of a clause that's not
equivalent to a Horn clause.)
************************
David C. Ullrich
| |
| Minti 2004-03-27, 12:10 am |
| Torkel Franzen <torkel@sm.luth.se> wrote in message news:<vcbn06breq3.fsf@beta19.sm.ltu.se>...
> mintiSPAMBLOCK@yahoo.com (Minti) writes:
>
>
> P v Q
My Bad. Thanks however , but I am interested in the inherent
limitations of using Horns clauses, I mean the limitations in
representing the world in pure Horn clauses, I mean prolog uses Horn
clauses does it cause any limitations in the world that can be
represented.
--
Imanpreet Singh Arora
| |
| Torkel Franzen 2004-03-27, 12:10 am |
| mintiSPAMBLOCK@yahoo.com (Minti) writes:
> I mean prolog uses Horn
> clauses does it cause any limitations in the world that can be
> represented.
Yes, you can only postulate properties expressible in Horn clauses -
and indeed in definite clauses, since we can't have purely negative
clauses in Prolog.
| |
| George Greene 2004-03-27, 12:11 am |
| : >mintiSPAMBLOCK@yahoo.com (Minti) writes:
: >
: >>I was reading about horn's clauses, I would like to know if every
: >> fact that can be represented as clause [non Horn] can be represented
: >> as a Horn clause. I know the answer would be yes [ probably ].
No, not even probably.
: >
: > P v Q
That's the classic counterexample. That is not a Horn clause.
David C. Ullrich <ullrich@math.okstate.edu> writes:
: Assuming I'm reading the somewhat vague definitions I found on
: Google correctly, that's an extremely clever example.
You're about to contradict that.
: Is it correct that a "clause" is something of the form A1 v ... An,
: where each Ai is either an atomic formula or the negation of
: an atomic formula, and a clause is a Horn clause if at most
: one Ai is not a negation?
At 0th order, yes.
: (That's the impression I get from
: MathWorld; otoh I can't believe that's the actual definition
: because if so it's hard to see how anyone could be unable
: to come up with an example of a clause that's not
: equivalent to a Horn clause.)
Yet you yourself, despite its being "hard to see how anyone could
be unable to come up with" an example, praised the trivial example
as "extremely clever". You can't have it both ways. If examples
are easy to come up with then TF's 2-atom clause is surely the
easiEST. It cannot at the same time be "extremely clever".
Don't be unnecessarily cold.
It is easy to overlook simple basic things WHILE one is new to a field
and being overwhelmed by a huge torrent of other new facts at the same time.
--
--- The history of our nation has demonstrated that separate is seldom, if ever, equal.
--- (Feb.3,2004) Supreme Judicial Court of Massachusetts (4-3), adv.Sen.#2175
| |
| David C. Ullrich 2004-03-27, 12:11 am |
| On 22 Mar 2004 14:43:41 -0500, George Greene
<greeneg@greeneg-cs.cs.unc.edu> wrote:
> : >mintiSPAMBLOCK@yahoo.com (Minti) writes:
> : >
> : >>I was reading about horn's clauses, I would like to know if every
> : >> fact that can be represented as clause [non Horn] can be represented
> : >> as a Horn clause. I know the answer would be yes [ probably ].
>
>No, not even probably.
> : >
> : > P v Q
>
>That's the classic counterexample. That is not a Horn clause.
>
>David C. Ullrich <ullrich@math.okstate.edu> writes:
> : Assuming I'm reading the somewhat vague definitions I found on
> : Google correctly, that's an extremely clever example.
>
>You're about to contradict that.
Warning: malfunctioning irony detector.
> : Is it correct that a "clause" is something of the form A1 v ... An,
> : where each Ai is either an atomic formula or the negation of
> : an atomic formula, and a clause is a Horn clause if at most
> : one Ai is not a negation?
>
>At 0th order, yes.
>
> : (That's the impression I get from
> : MathWorld; otoh I can't believe that's the actual definition
> : because if so it's hard to see how anyone could be unable
> : to come up with an example of a clause that's not
> : equivalent to a Horn clause.)
>
>Yet you yourself, despite its being "hard to see how anyone could
>be unable to come up with" an example, praised the trivial example
>as "extremely clever". You can't have it both ways. If examples
>are easy to come up with then TF's 2-atom clause is surely the
>easiEST. It cannot at the same time be "extremely clever".
>Don't be unnecessarily cold.
>It is easy to overlook simple basic things WHILE one is new to a field
>and being overwhelmed by a huge torrent of other new facts at the same time.
************************
David C. Ullrich
| |
| Remko Troncon 2004-03-27, 12:11 am |
| > representing the world in pure Horn clauses, I mean prolog uses Horn
> clauses does it cause any limitations in the world that can be
> represented.
Well, actually, prolog tries to remove some of those limitations by
introducing NAF (negation as finite failure).
So, instead of
A \/ B <- D
you could write it in prolog as
A <- D /\ not(B)
which is not really a horn clause anymore, but not really the full
predicate logic either.
cheers,
Remko
|
|
|
|
|