Prolog negation with more solutions

Question

I've got a little problem and don't know where to find a solution. You probably heard of problem of flying birds:

bird(eagle).
bird(penguin).
can_fly(penguin):-!,fail.
can_fly(X):-bird(X).

I tried to modify and use this knowledge for some "love story". Imagine this

maried(a, b).
maried(c, d).
lovers(a, d).
likes(X, Y):-maried(X, Y).

Now I want to say something like "If X is maried with Y, but X is Z's lover, then X doesn't like Y, but likes Z". I tried this:

likes(X, Y) :- lovers(X, Y).
likes(X, Y) :- maried(X, Y), lovers(X, _),!,fail.
likes(X, Y) :- maried(X, Y).

It works unless I want to evaluate a goal

likes(A, B).

If there is more facts in the database and Prolog finds first cheater, it will stop backtracking and I can't find any other solution. Maybe it will be obvious after, but now I have nothing on my mind..

Thanks in advance (and maybe sorry for my English :))

Answer 1

The cut-fail thing is an antipattern that's misleading you. It would be much better to say something in the original like this:

bird(eagle).
bird(penguin).

flightless(penguin).

can_fly(X) :- bird(X), \+ flightless(X).

See @boris's answer for an excellent and much more detailed discussion of this problem.

So, you have this database. I'm going to put names in so that I can comprehend it a little better.

married(bill,   hillary).
married(barack, michelle).

lovers(bill, michelle).

Now what you want to say is that married people like each other, unless they're cheating. Well, it would be better to define these terms in Prolog so we can reason with them. Create the language we need to use to define our domain. That's going to look like this:

cheating(Cheater, SpitedSpouse, Lover) :-
  married(Cheater, SpitedSpouse),
  lovers(Cheater, Lover),
  SpitedSpouse \= Lover.

Now it's much easier to define likes/2!

 likes(Husband, Wife)  :- married(Husband, Wife), \+ cheating(Husband, Wife, _).
 likes(Husband, Lover) :- cheating(Husband, _, Lover).

We can even define dislikes properly:

 dislikes(SpitedSpouse, Lover) :- cheating(_,       SpitedSpouse, Lover).
 dislikes(Cheater, Spouse)     :- cheating(Cheater, Spouse,       _).

Look at what we've learned: what you really have is a marriage relationship between two people, or a cheating relationship between three people, and of your other predicates are just projections of these two fundamental relationships. That's pretty neat, yeah? :) cheating/3 is basically the classic "love triangle." That suggests ways we could evolve the program to be more potent: handling love quadrilaterals, of course! And so forth.

Notice something interesting? This code can't "catch" michelle—isn't she just as culpable as bill? This underscores a bigger problem: the gender/orientation limitation of the predicates. I think it helps to have concrete nouns like these to see the logical relationships, but it's a dangerous shortcut that should be resolved. An easy way to handle the logic would be to create a predicate like this:

 spouse(X, Y) :- married(X, Y)
 spouse(X, Y) :- married(Y, X).

Of course you then have to do more checks to make sure you don't have the same people repeated, but it's not hard, and then change your variables to be less gender-specific.

Answer 2

Already your first example is not too useful. You can ask:

• is the eagle a bird?
• is the penguin a bird?
• can the eagle fly?
• can the penguin fly?

but you can't even ask, "which birds can fly?":

?- can_fly(Bird).
false.

If you would want to be able to ask more general question, like, "which birds can fly?", or "which birds cannot fly?", you would need to either explicitly list the flying or non-flying birds. As most birds can fly, let's list explicitly the non-flying birds:

bird(eagle).
bird(penguin).
bird(ostrich).
bird(dodo).
bird(sparrow).
bird(pigeon).

flightless_bird(penguin).
flightless_bird(ostrich).
flightless_bird(dodo).

bird_of_pray(eagle).

extinct(dodo).
extinct(wooly_mammoth).

can_fly(Bird) :-
    bird(Bird),
    \+ flightless_bird(Bird).

extinct_bird(Bird) :-
    bird(Bird),
    extinct(Bird).

Note the use of the ISO predicate for negation, \+/1. It is true if the goal cannot be proven. It is much cleaner than the fail-cut combination you are using.

How you organize your knowledge is a totally different question. The example I have given is incomplete and not necessarily the best way to do it. As a general rule, you should try to keep your data in a normalized form, with facts and clauses of facts playing the role of tables and table rows.

Hopefully this answer points in the right direction.