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 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 at 21:32
  • If you’re not allowed to plug in constants, the claim does hold, though. – Yuval Filmus Nov 8 at 21:33
up vote 7 down vote accepted

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

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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