A curious new result in switching theory (Q582260)

A network receiving three binary inputs x, y, and z is presented. It yields the complements \(x'\), \(y'\), and \(z'\), but only two inversions are used internally. In honour of Edward F. Moore, who had found the first similar solution, it is called Moore's circuit: Let \(A=NOT(x\cdot y+x\cdot z+y\cdot z)\) and \(B=NOT(x\cdot A+y\cdot A+z\cdot A+x\cdot y\cdot z)\), then \(x'=y\cdot A+z\cdot A+B\cdot y\cdot z+A\cdot B\), \(y'=x\cdot A+z\cdot A+B\cdot x\cdot z+A\cdot B\), \(z'=x\cdot A+Y\cdot A+B\cdot x\cdot y+A\cdot B.\) Note that only AND's and OR's (``\(\cdot ''\) and \(``+''\), resp.) are used, but no NAND, NOR, EXOR etc. Further a recursive nesting procedure is described to produce N negations from two inverters for every finite N. This is not a contradiction to a result of \textit{A. A. Markov} [J. Assoc. Comput. Mach. 5, 331-334 (1958; Zbl 0085.116)], who had found the inversion complexity to be at least \([\log_ 2N]+1\). For \(N\geq 4\) the resulting circuit involves feedback loops and so it becomes a finite state machine instead of a combinational circuit.