Rules

First-order predicate logic (calculus) formalizes statements using predicates (boolean functions) and functions. Both can have variables.
A rule set can look like
IF Parent(x,y) THEN Ancestor(x,y)
IF Parent(x,z) ∧ Ancestor(z,y) THEN Ancestor(x,y)
Here, Parent(x,y) is a predicate that indicates that y is the parent of x.
These two rules form a recursive function which would be very hard to represent using a decision tree or propositional representation.
In Prolog, programs are set of first-order rules with the form as above (known as Horn clauses).
We can view the learning of rules as the learning of Prolog programs.