The problem of learning universally quantified function free first order Ho
rn expressions is studied. Several models of learning from equivalence and
membership queries are considered, including the model where interpretation
s are examples (Learning from Interpretations), the model where clauses are
examples (Learning from Entailment), models where extensional or intention
al background knowledge is given to the learner (as done in Inductive Logic
Programming), and the model where the reasoning performance of the learner
rather than identification is of interest (Learning to Reason). We present
learning algorithms for all these tasks for the class of universally quant
ified function free Horn expressions. The algorithms are polynomial in the
number of predicate symbols in the language and the number of clauses in th
e target Horn expression but exponential in the arity of predicates and the
number of universally quantified variables. We also provide lower bounds f
or these tasks by way of characterising the VC-dimension of this class of e
xpressions. The exponential dependence on the number of variables is the ma
in gap between the lower and upper bounds.