  Recently it has been proved that simple GP systems can efficiently evolve the
conjunction of $n$ variables if they are equipped with the minimal required
components. In this paper, we make a considerable step forward by analysing the
behaviour and performance of the GP system for evolving a Boolean function with
unknown components, i.e., the function may consist of both conjunctions and
disjunctions. We rigorously prove that if the target function is the
conjunction of $n$ variables, then the RLS-GP using the complete truth table to
evaluate program quality evolves the exact target function in $O(\ell n \log^2
n)$ iterations in expectation, where $\ell \geq n$ is a limit on the size of
any accepted tree. When, as in realistic applications, only a polynomial sample
of possible inputs is used to evaluate solution quality, we show how RLS-GP can
evolve a conjunction with any polynomially small generalisation error with
probability $1 - O(\log^2(n)/n)$. To produce our results we introduce a
super-multiplicative drift theorem that gives significantly stronger runtime
bounds when the expected progress is only slightly super-linear in the distance
from the optimum.
