Lower bounds on the size of Boolean formulas
Michael J. Fischer, Albert R. Meyer, Michael Stewart Paterson · 1975
Let C(n)k be the Boolean function of n variables that equals one iff the number of arguments equal to one is a multiple of k. It is shown that every Boolean expression for C(n)k, allowing all of the 16 binary connectives, has size exceeding εn log n/log log n, ε> 0. This result follows from a general criterion relating the minimum size expression for a Boolean function to the kinds of subfunctions obtainable through restriction. Lower bounds on formula size for several other functions are obtained. In some cases, the lower bounds are nearly achievable by known constructions.