[Boolean] formula sizes
There are a total of 22n possible Boolean functions of n variables. The maximum number of terms needed to represent any of these functions in DNF is 2n - 1. The actual numbers of functions which require 0, 1, 2, ... terms is for n = 2: {1, 9, 6}; for n = 3: {1, 27, 130, 88, 10}, and for n = 4: {1, 81, 1804, 13472, 28904, 17032, 3704, 512, 26}. The maximal length turns out always to be realized for the simple parity function Xor, 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 for n ≤ 4.)