  Recently it has been proven that simple GP systems can efficiently evolve a
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 a GP system for evolving a Boolean conjunction or
disjunction of $n$ variables using a complete function set that allows the
expression of any Boolean function of up to $n$ variables. First we rigorously
prove that a GP system using the complete truth table to evaluate the program
quality, and equipped with both the AND and OR operators and positive literals,
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.
Additionally, we show that when a polynomial sample of possible inputs is used
to evaluate the solution quality, conjunctions or disjunctions with any
polynomially small generalisation error can be evolved with probability $1 -
O(\log^2(n)/n)$. The latter result also holds if GP uses AND, OR and positive
and negated literals, thus has the power to express any Boolean function of $n$
distinct variables. To prove 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.
