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

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 2

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.