prologlogiclogic-programming

Look for algorithm/research area that determines facts that would make a Prolog query true given a Prolog program

I'm looking for research, algorithms or even terminology for this area of research that take a Prolog program and a query I want to be true and attempt to find the facts that would need to be asserted to make it true. For example:

% Program
hasProperty(Object, Property) :-
   property(Object, hasProperty, Property).

property(apple, hasProperty, red).
property(car, hasProperty, drivable).

% Magic function that determines what Facts would make
% query 'hasProperty(lemon, sour)' true
% in the program above
?- whatFacts(hasProperty(lemon, sour), Facts).
Facts = [property(lemon, sour)]

I'm sure research has been done on this, and certainly it seems unsolvable in the general case, but I'm curious what has been done but am having trouble finding the right terminology to find the work.

Would love any pointers to actual algorithms or names for the area or problem I'm describing.

Solution

  • This is called "abduction".

    For the view from philosophical logic, Stanford Encyclopedia of Philosophy offers this entry: Abduction.

    For the view from logic programming, Wikipedia offers this entry: Abductive Logic Programming.

    A paper that uses Prolog and CHR (Constraint Handling Rules) for Abductive reasoning:

    Henning Christiansen: Abductive reasoning in Prolog and CHR (PDF): A short introduction for the KIIS course, Autumn 2005.

    Christiansen refers to the book

    Abduction and Induction: Essays on their Relation and Integration, edited by Peter A. Flach and Antonis Hadjiantonis (Kluwer Academic Publishers, April 2000), Amazon Link, first chapter at researchgate

    and provides this introductory explainer:

    Deduction, reasoning within the knowledge we have already, i.e.,from those facts we know and those rules and regularities of the world that we are familiar with. E.g., reasoning from causes to effects: If you make a fire here, you will burn down the house.

    In Prolog, the language is structured so as to most naturally find the premise "make a fire here" if your goal happens to be "burn the house down".

    Induction, finding general rules from the regularities that we have experienced in the facts that we know; these rules can be used later for prediction: Every time I made a fire in my living room, the house burnt down ... Aha, the next time I make a fire in my living room, the house will burn down too.

    Abduction, reasoning from observed results to the basic facts from which they follow, quite often it means from an observed effect to produce a qualified guess for a possible cause: The house burnt down, perhaps my cousin has made a fire in the living room again.

    "Abductive Logic Programming" (ALP) is (used to be?) an active area of research.

    Here is a Sprinker Link with search result.

    ALP is a common problem in commonsense reasoning and planning. Examples that come to mind: