In circuit complexity theory, a branch of computation complexity theory, a theorem is that any Boolean circuit without NOT gates can be written equivalently as a hierarchical structure, in which the first layer consists of OR (or AND) gates, then the second layer consists of AND (or OR) gates, the third layer consists of OR(AND) gates, and so on, what is the proof of this conclusion? Or any reference? I remember the proof that the PARITY problem needs exponential circuit complexity used this fact when using Hstad switching Lemma. Thanks!Note: we don't need CNF(or DNF) here, because that corresponds to 2 layers and exponential number of gates. In general, the circuit above can be arranged as multiple layers, so CNF(DNF) is not necessary.
What is the proof that boolean circuit (no negation gate) can be arranged as alternating OR and AND gates
complexity theory;computability;circuits