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

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.

-
idk if this will help, but i got- a'b'+bc+ac' as simplest form in AND & OR form. which is nothing close to NAND or XOR, i think. – tvamsisai Feb 18 '13 at 17:15
got it! will post soon. i might be wrong... – tvamsisai Feb 18 '13 at 17:33

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.

-
please verify my answer. thanks. – tvamsisai Feb 18 '13 at 17:48

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

-
You are missing a parenthesis. – wircho Feb 18 '13 at 16:35
About $\Leftrightarrow$: Not really, since this is properly written as $(a\Leftrightarrow b)\mathbf{AND}(b\Leftrightarrow c)$, then you are still using one of them twice. – wircho Feb 18 '13 at 17:04
wircho, it is considered a valid (and standard) minimal form. It's expansion involves AND, but then so does XOR: the expansion of XOR involves (a OR b) AND NOT (a AND b) – amWhy Feb 18 '13 at 17:06
I know it is right in mathematical language but my point is that you cannot write it like that in any programming language. The expression (a==b==c) is understood as (a==b)==c which just compares c to a boolean value. – wircho Feb 18 '13 at 17:08
Thanks for sayin so that i am near 15k. – Babak S. Feb 21 '13 at 13:55

(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))'

-
btw someone pls edit it properly... im on mobile. thank you! :) – tvamsisai Feb 18 '13 at 17:42
Your final expression is just $\neg (b \oplus (a \wedge c))$, or $b \equiv (a \wedge c)$. This isn't the same as $(b \equiv a) \wedge (b \equiv c)$. For instance, they differ when $a=1$ and $b=c=0$. – mjqxxxx Feb 18 '13 at 17:49
As mjqxxxx pointed out, this is not correct, e.g. for $(a,b,c) = (1,0,0)$ it outputs $1$. – dtldarek Feb 18 '13 at 17:52
hmm... true. where might be the glitch? – tvamsisai Feb 18 '13 at 18:00
i understand the last step i did is wrong, when i change it to xor format. :/ wrong lead... – tvamsisai Feb 18 '13 at 18:15

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

-