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.

  • $\begingroup$ 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. $\endgroup$ Nov 8, 2018 at 21:31
  • $\begingroup$ In this case the course treated constants as separate functions and we are not allowed to plug them in $\endgroup$ Nov 8, 2018 at 21:32
  • $\begingroup$ If you’re not allowed to plug in constants, the claim does hold, though. $\endgroup$ Nov 8, 2018 at 21:33

1 Answer 1


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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.