Regularity of balanced binary strings

Question

How can one tell which number of propositional variables is necessary to express a Boolean function given as a sequence of 0s and 1s (a binary string) of length $2^n$ as a Boolean formula?

The extremal cases are clear: if no 0s or no 1s are present, we need no variables at all, if there is exactly one 0 or one 1, we need all $n$ variables. I am especially interested in the case that there are equally many 0s and 1s (balanced binary strings). This is the only case, where one variable may suffice – but also all may be necessary.

I start from the assumption that it's a matter of regularity or complexity of the binary string.

Assign to each binary string $\sigma$ of length $2^n$ recursively a sequence of symbols:

1. a + when $\sigma = xx$

2. a - when $\sigma = x\overline{x}$ with $\overline{x}$ the "negation" of $x$.

3. an S otherwise (S for stop)

4. Proceed with $x$ in the first two cases.

One needs exactly one variable if the sequence has length $n$ and contains only +'s with one single -. This corresponds to maximal regularity.

Conjecture: One needs $n - n_+$ variables, $n_+$ the number of +'s in the sequence.

Is this approach of a "recursively defined regularity" sensible, and if so: under which name is it already known, eventually?

Answer 1

The first rule corresponds to checking if the first variable is needed in the formula or not... but not whether any of the others might be redundant.

As a simple counter-example, consider the function $f(A,B,C,D)=AB \vee \bar{A}C$. The corresponding binary string should be 0011001100001111, which is neither of the $xx$, nor of the $x\bar{x}$ form (so $n_{+}=n_{-}=0$). Yet, only three variables are needed to represent it.

Of course, the rules can be amended to check for additional types of redundancies (e.g. checking if every digit is doubled corresponds to checking if the last variable is relevant), but doing so pretty much boils the problem down to a tautology -- if the function value does not depend on a variable, we don't need to use that variable :-)

Answer 2

Consider the string as a binary tree with distinguished left and right subtrees at every level. If at a level $i$ each left subtree is equal to its right sibling, the corresponding propositional $p_i$ is redundant (= not needed to express the Boolean function).

I am afraid there is no essentially different and more efficient way to check this.