3 ms·
You need a function of more inputs than outputs in order to compose into a function of multiple inputs and a single output. This rules out NOT. Then, we just
by amalcon 5y ago
You need a function of more inputs than outputs in order to compose into a function of multiple inputs and a single output. This rules out NOT.
Then, we just need to rule out all functions that can't build NOT (i.e. invert one of their inputs). AND and OR obviously can't do this. XOR and XNOR can, but only if you can guarantee a consistent synthetic input, which is not a good requirement from either a theoretical or practical perspective. NAND and NOR can implement NOT by just repeating the same input twice.