how to use forall X in answer set programming (dlv) (answer set prolog)

Question

I have the following facts in dlv, knows (X,Y) means X knows Y.

knows(adam,  dan).
knows(adam,alice).
knows(adam,peter).
knows(adam,eva).
knows(dan,   adam).
knows(dan,alice).
knows(dan,peter).
knows(eva,   alice).
knows(eva,peter).
knows(alice, peter).
knows(peter, alice).

I have defined the following predicates,

person(X) :- knows(X, _).

This will give all the persons from the facts. I am trying to find a predicate popular(X). that will give the popular person. It is defined such that if all persons knows X then X is popular. The answer for the above list of facts is alice and peter. I defined it as below,

popular(X):-person(X),knows(_,X).

X is popular if its a person and everyone knows X. But I am getting all persons as the result when I run it. Where am I making a mistake?

Answer 1

As said in lurker's comment (with slight modification and emphasis by me), the reason you get all persons as a result is

You have defined person as: X is a person if X knows someone. And you've defined popular as: X is popular if X is a person and someone knows X.

But you wanted to define: X is popular if X is a person and everyone knows X.

The following is an ASP solution for clingo 4. DLV might have slight differences in syntax.

% Project
person(P) :- knows(P, _).

% Separate helper predicate knows2/2.
% Not needed if polluting knows/2 with knows(X, X) is OK.
knows2(O, P) :- knows(O, P).
knows2(P, P) :- person(P).

% Everybody knows a popular person.
% When there is a person O that doesn't know P, #false is active.
% I.e. all rule instantiations where some O doesn't know P are discarded.
popular(P) :- person(P), #false : person(O), not knows2(O, P).

% Popular person knows only other popular persons.
% Redundant at this point, since the above rule already results
%   in correct answer without further integrity constraints.
:- person(P), person(O), popular(P), not popular(O), knows(P, O).

#show popular/1.

Answer 2

As per the comment string on the original post, you have defined popular to be "a person that is known by someone". Since - in your knowledge base - everyone is known by someone, everyone is popular.

Assuming "a popular person is one whom everyone knows but the popular person knows only other popular persons"; if we want to know if X is popular:

• We either need to count all the people that know X and then compare that to the number of people;
• Or we need to verify that it is never the case that someone doesn't know X.

I'll focus on the second way to do this, using forall. Take sometime and run some tests on your own to understand how that works. Here's an example of what you might do:

popular(X): - person(X),
              forall(  
                 (   person(Y), 
                     X \= Y
                 ),
                 knows(Y,X)
              ).

If you run this, you get Alice and Peter as answers.

But if we include the other condition:

popular(X): - person(X),
              forall(  
                 (   person(Y), 
                     X \= Y
                 ),
                 knows(Y,X)
              ),
              forall(
                 knows(X,Z),
                 popular(Z)
              ).

That last line says X needs to know people that are popular exclusively... and now, if you run this, you're most likely going to get a 'out of local stack' - it's a bottomless recursive definition.

You always need to check if someone is popular to know if someone is popular to know if someone is popular... Try to think about the problem and why that is. Is there a way to check if someone is popular without needing to check if someone else is popular? What if someone 'knows' themselves? What if two people know each other? This might take a slightly more complex approach to solve.

---

By the way, notice that your definition of person returns multiple people - everyone is a person for every person they know. Besides making every check take a lot longer (since there are more 'people' to check), this might be a problem if you decide to go with the firs approach (the counting one).

Wouldn't it make sense to define explicitly who are the people and then define 'knowing' as a relation between people?

person('Alice').
person('Bob').

knows('Alice','Bob').