  We consider the problem of learning rules from a data set that support a
proof of a given query, under Valiant's PAC-Semantics. We show how any backward
proof search algorithm that is sufficiently oblivious to the contents of its
knowledge base can be modified to learn such rules while it searches for a
proof using those rules. We note that this gives such algorithms for standard
logics such as chaining and resolution.
