How to verify if three numbers are equal using logical operators (with a restriction!)?

Question

Please read below, as there is an important restriction to this question.

Think of a number as an array of 0's and 1's. The logical operators I want to use are the usual: AND, OR, XOR, NAND, NOT (negation or "!").

To check if TWO numbers a and b are equal, simply do:

NOT(a XOR b)

This will be an array of 1's only if the two numbers are equal.

Thus to check if three numbers are equal I could simply do:

NOT(a XOR b) AND NOT(b XOR c)

However, the restriction is that I cannot write any of the numbers a,b,c more than once. So I need something similar to this:

(a OPERATOR1 b) OPERATOR2 c,

where each of the numbers a,b,c appear exactly once.

I'd be happy to answer questions on the context of this question. Thanks in advance.

Answer 1

I'm afraid that Not(a XOR b) AND NOT(b XOR c) is as concise as you're going to get.

It's the most compact expression which will return $1$ if and only if $a = b = c$. All other modes of expressing this with the connectives you list involve multiple appearances of one or more of $a, b, c$.

If you can use BOOLE ($\Leftrightarrow$): then you can limit to one occurrence of each of a, b, c:

$$a \Leftrightarrow b \Leftrightarrow c$$

---

See for example: Wolfram's elaboration

Answer 2

Edit: My proof is not valid, as I forgot about $\mathtt{XOR}$. Nevertheless, I will leave it here, it still might be useful for somebody.

Edit 2: As I don't know how to simply fix this issue, I will give a short informal argument based on information theory: with $x_i$ being used only once, we have only 1 bit (the output of some sub-expression) to convey 2 bits of information:

• whether the previous comparison succeed,
• whether we are comparing to $0$ or to $1$.

It is possible for $n = 2$, because we don't need to propagate the "previous comparisons succeeded" bit (there is no previous comparisons). If only we could use every $x_i$ twice, it would be possible for any $n$, because we could implement (0).

---

This is impossible. As different indices/bits of input numbers are treated independently, WLOG we can assume that all the input $x_i \in \{0,1\}$. So we have a sequence $x_i$ and want to construct a logical expression which is equivalent to

$$\left(\forall i.\ x_i = 1\right) \lor \left(\forall i.\ x_i = 0\right), \tag{0}$$

such that every $x_i$ is used at most once. It is doable for $n \leq 1$, but impossible otherwise, i.e. for $n > 1$. Let's assume that a Boolean function $f(x_0,\ldots)$ uses $x_0$ only once, then $f$ is increasing in $x_i$ or $f$ is decreasing in $x$, more formally

$$\forall (x_i)\subset\{0,1\}^n.\ f(0,x_1,\ldots) \leq f(1,x_1,\ldots), \tag{1}$$

or

$$\forall (x_i)\subset\{0,1\}^n.\ f(0,x_1,\ldots) \geq f(1,x_1,\ldots). \tag{2}$$

The reason being, operators $\lor$ and $\land$ are monotonic and if $x_0$ is used only once, then there is a constant number $k_0$ of negations along the way. $\mathtt{NAND}$ is just $\mathtt{NOT} \circ \mathtt{AND}$, and if $k_0$ is even then (1), and for $k_0$ odd we have (2).

By symmetry, it is the same for $x_i$ for any $i$. However, the desired operation $equiv(x_0,x_1,x_2)$ does not fulfill (1) or (2), e.g.

\begin{align} equiv(0,0) &= 1 \\ equiv(1,0) &= 0 \\ equiv(0,1) &= 0 \\ equiv(1,1) &= 1 \end{align}

Concluding, $equiv(x_0,\ldots)$ for $n > 1$ does not fulfill (1) or (2) and thus is not expressible in terms of $\lor, \land,\neg$ with variables being used only once.

I hope it answers your question ;-)

Answer 3

There is no expression of the form $(a *_1 b) *_2 c$ where $a$, $b$ and $c$ are arbitrary bits and $*_1$ and $*_2$ are one of the bitwise operators $and$, $or$, $xor$ or their negations $nand$, $nor$ and $nxor$ that evaluates to true whenever $a = b = c$. I've used a program to test that all possible choices of $*_1$ and $*_2$ will not give the desired output in all cases.

https://gist.github.com/timjb/6587803

Answer 4

(a xor b)'.(b xor c)'
= (a'b+b'a)'(b'c+c'b)'
= (a'b+b'a+b'c+c'b)'
= (b(a'+c')+b'(a+c))'
= (b(a.c)'+b'(a'c')')'
= (b xor (a and c))'