HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

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

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
generatesnecessarilyoperatoruniversalneginputfor

Problem

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.

Solution

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:

  • $T(x,\ldots,x) = \lnot x$: in this case the claim holds.



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



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



  • $T(x,\ldots,x) = 1$: similar to the preceding case.



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

Context

StackExchange Computer Science Q#99784, answer score: 8

Revisions (0)

No revisions yet.