Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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

4 Answers 4

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 ;-)

share|improve this answer
    
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

share|improve this answer
    
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))'

share|improve this answer
    
btw someone pls edit it properly... im on mobile. thank you! :) –  tvamsisai Feb 18 '13 at 17:42
2  
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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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