Prolog: deduction given that items can be in exactly one of two sets, with set sizes known

Question

I have 5 people in a room. I'll be writing rules to determine whether the people are happy or sad. However, before I even start with that, I have the overlying knowledge that - of the 5 - exactly 3 are happy and 2 are sad (and none can be both). It should therefore be possible to make deductions based on this: if - by any means - I know who the three happy people are, then I can deduce the two sad people, and vice versa.

What I've got so far is as follows:

person(bob).
person(tim).
person(steve).
person(roy).
person(jack).

sad(bob).
sad(tim).

happy(X) :-
  person(X),
  \+ sad(X),
  findall(Y, sad(Y), YS),
  length(YS, 2).

When asked happy(X), Prolog will give me Roy, Steve and Jack, because it already knows who the two sad people are. Problem: I'm unable to define a sad/1 rule in the same manner, because of the mutual recursion with happy/1. I want to be able to add in rules such that the outcome in the above example remains the same, yet the following initialisation would list Bob and Tim as sad:

person(bob).
person(tim).
person(steve).
person(roy).
person(jack).

happy(steve).
happy(roy).
happy(jack).

Is there a better way I should be thinking about this? It's important that I'll be able to go on to later write more rules for sad/1 and happy/1, adding additional logic beyond the fact that deduction should be possible based on the knowledge that the 5 are split into 3 happy and 2 sad.

Answer 1

Sorting the logic out is a matter of consistency and avoiding conflicting meanings of a given predicate or fact.

Your definition of sad/1 is currently a fact that results in one result for each backtrack to the query, sad(X). But your definition of happy/1 generates a list. That leaves you with how you want to define sad/1 to generate a list, which would be in conflict with your current definition of sad/1 as a query that is true if the argument is a sad person.

A more consistent approach would be define happy/1 to behave the way sad/1 behaves:

happy(X) :-
    person(X),
    \+ sad(X).

Then you can define your list versions:

happy_all(A) :-
    findall(X, happy(X), A).

sad_all(A) :-
    findall(X, sad(X), A).

Now the above assumes you have explicit facts for person/1 which defines the universe of all valid people, and sad/1 which defines who the sad ones are. It also assumes that if a person isn't sad, then they must be happy.

You could flip this around and explicitly define happy people with happy/1 facts, then define sad/1 in terms of people not being happy assuming that a person must be happy if they aren't sad:

sad(X) :-
    person(X),
    \+ sad(X).

And the happy_all/1 and sad_all/1 predicates will still apply.

If you want to mix your facts with happy/1 and sad/1, this can create a consistency issue: (1) cases where a person isn't defined as happy or sad... then what are they? and (2) what if a person is defined as both happy and sad?

Semantically, you may want to define both sad/1 and happy/1 explicitly if you are also allowing for someone not being either happy or sad. You can do this:

person(bob).
person(tim).
person(steve).
person(roy).
person(jack).

sad(bob).
sad(tim).

happy(steve).
happy(roy).

happy_all(A) :-
    findall(X, happy(X), A).

sad_all(A) :-
    findall(X, sad(X), A).

But not define predicates for happy/1 or sad/1 since they are already facts. That keeps things simple. We just don't know if jack is happy or sad.

But what if we want to say that if a person isn't happy or sad, then they must be happy and add that rule back in. To avoid the looping you mentioned, we don't to be mixing rule names with fact names. In that case:

person(bob).
person(tim).
person(steve).
person(roy).
person(jack).

sad(bob).
sad(tim).

happy(steve).
happy(roy).

% A person is happy if they are, in fact, happy
happy_person(X) :-
    happy(X),
% A person is happy if they are neither happy or sad
happy_person(X) :-
    person(X),
    \+ happy(X),
    \+ sad(X).

% A person is sad if they are, in fact, sad
sad_person(X) :-
    sad(X).

% Who are all the happy people?
happy_all(A) :-
    findall(X, happy_person(X), A).

% Who are all the sad people?
sad_all(A) :-
    findall(X, sad_person(X), A).

Answer 2

How about using clpb?

:- use_module(library(clpb)).

Sample query:

?- Hs = [Bob,Tim,Steve,Roy,Jack],
   sat(card([3],Hs)),                               % exactly three are happy.
   ( 
      Who =   sad, sat(~H_bob * ~H_tim)             % specify the sad ones ...
   ;  Who = happy, sat(H_jack * H_roy * H_steve)    %  ... OR the happy ones?
   ),
   labeling(Hs).
   Who =   sad, Bob = 0, Tim = 0, Jack = 1, Roy = 1, Steve = 1, Hs = [0,0,1,1,1]
;  Who = happy, Bob = 0, Tim = 0, Jack = 1, Roy = 1, Steve = 1, Hs = [0,0,1,1,1].