# Can we pick a basis for synchronous circuits which coarsens towards the target partition at every layer?

Given a Boolean function $$f : \{0, 1\}^n \rightarrow \{0, 1\}$$ and a Boolean basis for circuit gates $$B$$ (for instance $$B = \{AND, OR\}$$), we can construct the set of size optimal synchronous (Harper 1977) circuits for computing $$f$$, what I'll call $$\mathcal{C}(f)$$, on that basis. Given some circuit $$C \in \mathcal{C}(f)$$, we can slice it at each layer and, where the width of layer $$i$$ is $$w_i$$ and the depth of the circuit is $$d$$, we induce functions $$g_0, g_1, \cdots, g_i, \cdots, g_d$$ where $$g_i : \{0, 1\}^n \rightarrow \{0, 1\}^{w_i}$$. These functions can each be seen as inducing a new partition, or equivalence relation, of $$\{0, 1\}^n$$, which I'll define

$$P_i = \{\{ x \mid x \in \{0, 1\}^n, f(x) = y \} \mid y \in range(g_i) \}.$$

Sanity check: it should be clear that $$P_0 = \{ \{x\} \mid x \in \{0, 1\}^n \}$$ and that $$P_d = f^{-1}(range(f))$$.

We say that equivalence relation $$P$$ refines equivalence relation $$Q$$ when $$\forall p \in P, \exists q \in Q, p \subseteq q$$. We denote this by $$P \leq Q$$. Given the setup above, it is not hard to show that

$$\forall i \in \{1 \cdots d\}, P_{i-1} \leq P_i.$$

My question is: Does there exist a basis $$B$$ such that for all $$f$$, $$C \in \mathcal{C}(f)$$, $$P_{i-1} \neq P_i$$?