Prolog - what sort of sentences can't be expressed

Question

I was wondering what sort of sentences can't you express in Prolog? I've been researching into logic programming in general and have learned that first-order logic is more expressive compared to definite clause logic (Horn clause) that Prolog is based on. It's a tough subject for me to get my head around.

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

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

If so, are there any other sentences that CAN'T be expressed? If not, why?

Answer 1

The most problematic definitions in Prolog, are those which are left-recursive. Definitions like

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

are most likely to fail, due to Prolog's search algorithm, which is plain depth-first-search and will run to infinity and beyond.

The general problem with Horn Clauses however is, that they're defined to have at most one positive element. That said, one can find a clause which is limited to those conditions, for example:

A ∨ B

As a consequence, facts like ∀ X: cat(X) ∨ dog(X) can't be expressed directly. There are ways to work around those and there are ways to allow such statements (see below).

Reading material:

• These slides (p. 3) give an example of which sentence you can't build using Prolog.

• This work (p. 10) also explains Horn Clauses and their implications and introduces a method to allow 'invalid' Horn Clauses.

Answer 2

You can express your sentence straightforward with Prolog using negation (\+).

E.g.:

car(bmw).
car(honda).
...
car(toyota).

engine(bmw, dohv).
engine(toyota, wenkel).

no_car_without_engine:-
  \+(
    car(Car),
    \+(engine(Car, _))
  ).

Procedure no_car_without_engine/0 will succeed if every car has an engine, and fail otherwise.

Answer 3

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

The sentence you show is expressed in such a convoluted way that I had hard time attempting to understand it. Effectively, I must thanks gusbro that took the pain to express it in understandable way. But he entirely glossed over the knowledge representation problems that any programming language pose when applied to natural language, or even simply negation in first order logic. These problems are so urgent that the language selected is often perceived as 'unimportant'.

Relating to programming, Prolog lacks the ability to access in O(1) (constant time) any linear data structure (i.e. arrays). Then a QuickSort, for instance, that requires access to array elements in O(1), can't be implemented in efficient way.

But it's nevertheless a Turing complete language, for what is worth. Then there are no statements that can't be expressed in Prolog.

Answer 4

So you are looking for sentences that can't be expressed in clausal logic that can be expressed in first order logic.

Strictly speaking, there are many, simply because clausal logic is a restriction of FOL. So that's true by definition. What you can do though is you can rewrite any set of FOL sentences into a logic program that is not equivalent but with good properties. So for example if you want to know if p is a consequence of your theory, you can use equivalently the transformed logic program.

A few notes on the other answers:

1. Negation in Prolog (\+) is negation as failure and not first order logic negation
2. Prolog is a programming language, as correctly pointed out, we should be talking about clausal logic instead.
3. Left recursion is not a problem. You can easily use a different selection rule, or some other inference mechanism.