# Evolving Boolean Functions with Conjunctions and Disjunctions via Genetic Programming

arXiv: https://arxiv.org/abs/1903.11936 · HTML: https://mlsanity.com/paper/1903.11936/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Mar 2019.

## Built on by (most cited first, 2 of 2)

- [(1+1) Genetic Programming With Functionally Complete Instruction Sets Can Evolve Boolean Conjunctions and Disjunctions with Arbitrarily Small Error](https://mlsanity.com/paper/2303.07455/) (2023)
- [Runtime Analysis of Cartesian Genetic Programming in Evolving Boolean Functions](https://mlsanity.com/paper/2606.15923/) (2026)

## Abstract (arXiv)

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(ℓ n log2 n) iterations in expectation, where ℓ ≥ 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(log2(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.