Skip to main content
edited tags
Link
Asaf Karagila
  • 39.7k
  • 8
  • 134
  • 282
Source Link

An inequality concerning formulas and Boolean functions

We define $S(\phi)$ of formula $\phi$ to be the number of computational gates in a minimal $\{\neg, \wedge, \vee\}$-formula computing $\phi$.

Conjecture. If $\phi_1(a_{11}, \dots, a_{1y_1})$, $\dots$, $\phi_x(a_{x1}, \dots, a_{xy_x})$ are arbitrary Boolean functions with pairwise disjoint sets of variables, then it follows that$$S\left(\phi_1\left(a_{11}, \dots, a_{1y_1}\right) \oplus \ldots \oplus \phi_x\left(a_{x1}, \dots, a_{xy_x}\right)\right) \ge {1\over2}\sum_{i = 1}^x S(\phi_i).$$Is this true or not? If so, how do we show this? Or does there exist a counterexample?