[Boolean] formula sizes

There are a total of2²ⁿ possible Boolean functions ofn variables. The maximum number of terms needed to represent any of these functions in DNF is2^{n - 1}. The actual numbers of functions which require 0, 1, 2, ... terms is forn = 2:{1, 9, 6}; forn = 3:{1, 27, 130, 88, 10}, and forn = 4:{1, 81, 1804, 13472, 28904, 17032, 3704, 512, 26}. The maximal length turns out always to be realized for the simple parity functionXor, as well as its negation. The reason for this is essentially that these functions are the ones that make the coloring of the Boolean hypercube maximally fragmented. (Other functions with maximal length are never additive, at least forn≤ 4.)