Arguably, the simplest language for representing in intuitive terms any Boolean function is
the class of DNF formulae, which has been extensively studied in machine learning [1]}, [2]}, [3]}.
A DNF formula is a finite disjunction of monomials \(D = t_1 \vee t_2 \vee \cdots \vee t_m\) ,
and its associated concept is \(D(\mathbf {x}) = \max _{i = 1}^m t_i(\mathbf {x})\) .
As usual, the size of a DNF formula is defined by the sum of sizes of its terms,
where the size of a term is simply given by the number of its literals.
