Constraint - SWI- Prolog Queries

Question

I have an exam coming up and I'm going through past papers to help my understanding.

I came across the following past paper question:

Consider the following queries and answers. Some answers coincide with what SWI-Prolog would infer whereas others are erroneous. Indicate which answers are genuine and which ones are fake (no explanation of your answer is required).

(i) |?- [A, B, C] ins 0 .. 2, A #= B + C.

A = 0..2 B = 0..2 C = 0..2

(ii) |?- A in 0 .. 3, A * A #= A.

A = 0..2

(iii) |?- [A, B] ins -1 .. 1, A #= B.

A = 1 B = 1

(iv) |?- [A, B] ins 0 .. 3, A #= B + 1.

A = 1..3 B = 1..2 

I'm struggling to see how each one is either true or false. Would someone be able to explain to me how to figure these out please.

Thank you, really appreciate the help.

Answer 1

The key principle for deciding which answers are admissible and which are not is to look whether the residual program is declaratively equivalent to the original query. If the residual constraints admit any solution that the original query does not, or the other way around, then the answer is fake (or you have found a mistake in the CLP(FD) solver). If the shown answer is not even syntactically valid, then the answer is definitely fake.

Let's do it:

1. (i) |?- [A, B, C] ins 0 .. 2, A #= B + C.

   suggested answer: A = 0..2 B = 0..2 C = 0..2

   WRONG! The original query constrains the variables to integers, but this answer is not even a syntactically valid Prolog program.

2. (ii) |?- A in 0 .. 3, A * A #= A.

   suggested answer: A = 0..2

   WRONG! The original query constrains A to integers, but according to this residual program, A = 0..2 is a valid solution. The term ..(0, 2) is not an integer.

3. (iii) |?- [A, B] ins -1 .. 1, A #= B.

   suggested answer: A = 1 B = 1

   WRONG! Not syntactically valid.

4. (iv) |?- [A, B] ins 0 .. 3, A #= B + 1.

   suggested answer: A = 1..3 B = 1..2

   WRONG! Not syntactically valid.

Note that even if all shown answers were syntactically valid and =/2 were replaced by in/2 in the residual goals of (i), (ii) and (iv), these answer would still be all wrong, because you can in each case find solutions that either are not admissible by the original query or the residual goals, but not both. I leave solving these cases as an exercise for you, for example, suppose the respective answers are:

1. A in 0..2, B in 0..2, C in 0..2.
2. A in 0..2.
3. A = 1, B = 1.
4. A in 1..3, B in 1..2.

and find a witness for each case to show that the residual goals are semantically different from the respective original query.

For example, in case (1), A = B = C = 2 would be a valid solution according to the residual constraints, but obviously the original constraints exclude this solution, because 2 #= 2 + 2 does not hold!

Answer 2

A variable is always restricted to get a value contained in its domain, and arithmetic constrains only reduce the domain of involved variables.

So, try to 'label' all variables - that is, assign values from answers reported domains. Of course, if the arithmetic relation is not satisfied, you can say the answer is faked. Take ii). Does it hold for A=0 ? What about A=2 ?

This 'test' of course doesn't suffice to answer all questions. Some reported domains are narrower. For instance, take iii). Can you see any reason that excludes -1, or 0. If you cannot, you should mark the answer as faked.