# A universal operator necessarily generates $\neg x$ for input $x,…,x$

I originally posted this on math.stackexchange, but then deleted it and moved it here since I think it would fit this site more.

I saw a claim in a slideshow from a basic computer architecture course that given some boolean operator $$T(x_1,...,x_n)$$, if it is universal then necessarily: $$T(x,...,x)=\neg x$$ However, I found no explicit mention of this claim anywhere else, including here. Is it correct? And if so can one please provide a proof or a proof-idea? Because it was provided as a fact completely unrelated to the rest of the slides I have no idea how to approach it, and I am not sure I even have the right tools to do so.

I have already seen this question, for example, but there the proof is tailored towards a specific function. My problem is with proving the general case.

• If you’re allowed to plug in constants, the claim is false. Let $T(x,y,z,w)$ be the NAND of $x$ and $y$ if $z\neq w$, and zero otherwise. – Yuval Filmus Nov 8 '18 at 21:31
• In this case the course treated constants as separate functions and we are not allowed to plug them in – Dean Gurvitz Nov 8 '18 at 21:32
• If you’re not allowed to plug in constants, the claim does hold, though. – Yuval Filmus Nov 8 '18 at 21:33

## 1 Answer

There are two ways to define a universal operator: when constants are allowed, and when they are not allowed. If constants are allowed, then one can define a universal operator which doesn't satisfy the claim, as follows: $$T(x,y,z) = \overline{x \land y} \land z.$$ This is universal since $$T(x,y,1)$$ is the NAND operator, but $$T(0,0,0) = 0$$.

Now suppose that constants are not allowed. Since $$T$$ is universal, there is a $$T$$-circuit which computes the NOT function $$x \mapsto \lnot x$$. Let us now consider the possible values that $$T(x,\ldots,x)$$ takes:

1. $$T(x,\ldots,x) = \lnot x$$: in this case the claim holds.
2. $$T(x,\ldots,x) = x$$: in this case, induction shows that every $$T$$-circuit in which the only inputs are copies of $$x$$ necessarily computes the value of $$x$$; in particular, no $$T$$-circuit computes NOT.
3. $$T(x,\ldots,x) = 0$$: in this case, when $$x = 0$$, induction shows that every $$T$$-circuit always computes 0; in particular, it doesn't compute NOT.
4. $$T(x,\ldots,x) = 1$$: similar to the preceding case.

This shows that $$T(x,\ldots,x)$$ must compute $$\lnot x$$.