Help with Prolog: Understanding Which Statement Cannot Be Proven

Help!
1

Hi all,

I’m working on a Prolog task and could use some help understanding a specific problem related to negation and reversals in Prolog. Here’s the setup:

I have the following database defined in Prolog:


p(pelle, lisa).

p(pelle, eva).

p(lisa, eva).

p(eva, lisa).

p(lisa, pelle).

The question asks: Which of the following statements cannot be proven by Prolog?

  1. \+ (p(X, Y), p(Y, X)) when X and Y are unbound at the call, leading to X = pelle and Y = eva.

  2. p(X, Y), p(Y, X) when X and Y are unbound at the call, resulting in X = lisa and Y = eva.

  3. \+ (p(pelle, eva), p(eva, pelle)).

I’m looking to understand how Prolog handles negation and symmetry here. Specifically, I want to know which of these statements cannot be proven by Prolog, and the reasoning behind it.

Any insights or explanations would be greatly appreciated!

2

Hi, I’m by no mean an expert but I will try to answer your question.

First, prolog works under the closed world assumption, meaning that anything that it doesn’t know (i.e. is not asserted as facts in its database) is assumed to be false.
It is under this assumption that prolog implements negation: it will just try the query and fails if it finds a solution or succeed if the tested query fails.
Notice that I used the word “try” because any bindings is undone when leaving the negated query like nothing has ever happend. This means that you cannot expect any bindings from a negated query.

From this, we can already conclude that your first statement cannot be proven by prolog as is since a negation wraps the whole query.
But I also think that your first statement is contradictory, the query and the results don’t match too well.
I translate the query as the following english sentence: “There is no pair X-Y such that p(X, Y) and p(Y, X) is true”. Notice how in my formulation, we would intuitively respond to this query by true or false, and not by finding concrete values for X and Y.
By the look of the results you want to have, let me guess what query you wanted to run: “Find a pair X-Y such that p(X, Y) is true but has no inverse p(Y, X)”.
Now, you can translate it in prolog: p(X, Y), \+ p(Y, X). and obtain the answer you wanted to have.

Both statement 2 and 3 can be proven by prolog, so I won’t explain them.

3

A word of warning, if this was an exam question, and you’d have to answer it: you must figure out what is the expectation of the person reading your answers. Maybe there is a specific terminology they expect you to use, or maybe the answer should contain some specific context.

If you just want to know what happens, you should load the database and run the queries and look at the answers.