Abstract:

We consider formulas in a basis consisting of disjunction, conjunction, and negation. It is established that in each minimal (having the smallest possible number of occurrences of variables) formula that calculates a linear Boolean function depending on 5, 6 or 7 variables, at least one of the variables is included at least 8 times. The result focuses on the description of classes of minimal formulas for these functions and is an important intermediate step in this description.  But it also has an independent meaning, since it actually represents another way (perhaps the most simple and transparent) to obtain accurate lower estimates of the formula complexity of the specified functions.