Prolog (Horn clauses) vs. First Order Logic (FOL)

[Dan]

Hi, 

Not a strict swi-prolog question, but perhaps i can ask anyway. 

I am trying to understand in what way Prolog / Horn clauses is/are more limited in expressiveness than First Order Logic (FOL). Is there something that can be expressed in FOL that can not be expressed in Prolog?

thank you,

Daniel

[Samer Abdallah]

Oops - I just replied to this thinking it was from my colleague Daniel,

who is learning about using the Prolog-based system we are building.

I'm afraid my answer was not a SWI Prolog mailing list grade answer

so please ignore it!

Samer

On 17 Jul 2015, at 15:43, Dan <gros...@gmail.com>

 wrote:

--
You received this message because you are subscribed to the Google Groups "SWI-Prolog" group.
To unsubscribe from this group and stop receiving emails from it, send an email to swi-prolog+...@googlegroups.com.
Visit this group at http://groups.google.com/group/swi-prolog.
For more options, visit https://groups.google.com/d/optout.

[Alan Baljeu]

First order logic on finite terms is fully expressible in Prolog.  In fact, pure Prolog pretty much is a notation (and an evaluation scheme) for first order logic over Hilbert-space terms.  Horn clauses are a restricted form of FOL that can be solved very quickly, but any FOL can be rewritten as a horn clause.  The downside is it can be extremely expensive (NP complete) to compute a Horn clause from a FOL clause.

--

[Dan]

Hi Alan, 

Thank you for your insightful response. 

Could you elaborate on the "restriction" you mentioned: "first order logic over Hilbert-space terms" -- over Hilbert-space terms. 

Are there FOL over any terms and then those that are over Hilbert-space terms. I assume "over" refers to the mapping of variables in FOL terms. These are assumed to map to some domain. 

re: Horn clauses are as expressive as FOL just structured better for computation

So I guess a logic programmer would not feel limited in any way to express logic ideas using Horn clauses. I.e. once the translation from FOL to horn clauses is done by humans rather than machines then the issue of expense in automatic translation can be disregarded. 

Is this correct?

thank you,

Dan

[Jan Burse]

Hi,

Most probably the OP means Hebrand Universum. Although Hilbert
is also famous in math, Hebrand is one of the other guys that has
a name starting with H.

Hebrand is famous since he already established some important
results in 1930, which were only redone in 1947 by Leon Henkin.
(Disclaimer Years might not be 100% correct).

Bye

You find for example a section on Herbrand Universum and Logic
Programming in the following text book on Logic:
(XI Free Models and Logic Programming)
http://www.amazon.com/Mathematical-Logic-Edition-Undergraduate-Mathematics/dp/0387942580

[Gernot Salzer]

Hi Dan,

> I am trying to understand in what way Prolog / Horn clauses is/are
> more limited in expressiveness than First Order Logic (FOL). Is there
> something that can be expressed in FOL that can not be expressed in
> Prolog?

These are many questions, and the answer depends on which one picks and
how one interprets the terms "expressiveness" and "Prolog".

Prolog is a programming language with Horn logic as its philosophical
background, but going beyond it in expressiveness. E.g., you have
negation (as finite failure) which goes beyond Horn logic. Prolog is
Turing complete (=computationally universal), which means that it can
compute everything that can be computed by any other programming
language or computation model.

From the logical point of view (e.g. when interested in representing
knowledge) Horn logic is clearly less expressive than full first-order
logic. Consider e.g. the formula "A v B" (v ... disjunction, with A
and B atomic formulas). There is no Horn formula equivalent to it.

Best regards,
Gernot

[Michael BEN YOSEF]

Hi Dan,

See Gernot Salzer's reply for a good answer.

I just want to recommend a very nice free book about Prolog that explains the relationship between horn clauses, full clausal logic and first-order logic in the first two chapters:

Simply Logical: Intelligent Reasoning by Example - Peter Flach

Hope that helps!

Michael

[Dan]

Thank you Gernot, Michael for your responses. 

I hope its ok to mention in this list my higher-level interest in the question:

What I am actually after is to develop a "forest" view on the many logic based knowledge representation and reasoning approaches (i.e. the "trees"), as well as non-logic based ones which seem to go by the term computational intelligence. 

There appear to a numerous approaches that have been looked at in the past and that are currently being further investigated. From FOL, modal logic, to Prolog, Datalog, various variants of description logic, numerous extensions and more detailed applications (such context modeling and reasoning). Also prolog, including swi-prolog has been extended to support addtional approaches including DL, constraint programming, and more. 

As an "end user" of such approaches I have difficulty overviewing and understanding the fine grained differences such as logic expressiveness, strengths and limitation of approaches, as well as applicability to develop real world systems (what is in use already in applications (on the web or perhaps even in mobile/embedded systems), what could be in use but has significant expressive and/or comptuational limitations, what approaches are pure (non-applied) logic - to advance the theoretical aspects of the field without application in mind. 

I am wondering, are there any reviews that tackle such questions. 

thank you,

Dan

[Jan Burse]

Hi,

Since you refer to real world systems, I suggest to attend an artificial intelligence
lecture somewhere. For example a lecture such as this gives you quite a good
first glimps to takle your quest:
http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-034-artificial-intelligence-fall-2010/lecture-videos/

Bye