Prologue - which sentences cannot be expressed

Question

I was wondering what suggestions you cannot express in Prolog? I studied logical programming in general and found that first-order logic is more expressive than the specific sentence logic (Horn sentence) on which Prolog is based. This is a difficult topic for me to lower my head.

So, for example, the following sentence can be expressed:

For all cars, there does not exist at least 1 car without an engine 

If so, are there any other suggestions that CANNOT be expressed? If not, why?

Answer 1

The most problematic definitions in Prolog are those that are left recursive. Type definitions

 g(X) :- g(A), r(A,X). 

most likely, it will fail, because of the Prolog search algorithm, which is a simple search of the search depth and will work indefinitely.

However, a common problem with Horn's proposals is that they have no more than one positive element. However, you can find a position that is limited by these conditions, for example:

 A ∨ B 

As a result, facts like ∀ X: cat(X) ∨ dog(X) cannot be expressed directly. There are ways around these issues, and there are ways to resolve such claims (see below).

Reading material:

• These slides (page 3) provide an example of what kind of proposal you cannot create using Prolog.

• This work (p. 10) also explains the Horny Claus and their consequences and introduces a method that allows the "invalid" Claus Horn.

Answer 2

You can express a sentence directly using Prolog using negation ( \+ ).

eg:.

 car(bmw). car(honda). ... car(toyota). engine(bmw, dohv). engine(toyota, wenkel). no_car_without_engine:- \+( car(Car), \+(engine(Car, _)) ). 

The no_car_without_engine/0 procedure will succeed if each car has an engine, and it will not work otherwise.

Answer 3

Prolog is a programming language, not an interface with a natural language.

Your suggestion is expressed in such a confusing way that it was difficult for me to understand it. In fact, I have to thank the gusbro who took the pain to express it in an understandable way. But he completely ignored the problems of knowledge representation, which any programming language represents when applied to a natural language, or even simply denial in first-order logic. These problems are so relevant that the selected language is often perceived as "non-essential."

Due to programming in Prolog, there is no possibility of access to O (1) (time constant) to any linear data structure (i.e. arrays). Then QuickSort, for example, which requires access to the array elements in O (1), cannot be effectively implemented.

But it is, nevertheless, Turing's complete language, for which it is worth. Then there are no statements that cannot be expressed in Prolog.

Answer 4

So, you are looking for sentences that cannot be expressed in clause logic, which can be expressed in first-order logic.

Strictly speaking, there are many of them, simply because clausal logic is a limitation of FOL. So the truth is by definition. However, you can rewrite any set of FOL sentences into a logical program that is not equivalent but has good properties. For example, if you want to know if p is a consequence of your theory, you can use an equivalently transformed logic program.

A few comments on the other answers:

• Denial in Prolog (\ +) denial as denial, not denial of first-order logic
• Prolog is a programming language, as correctly indicated, we should talk about clause logic.
• Left recursion is not a problem. You can easily use another selection rule or some other inference mechanism.