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.

I'm not sure whether this is the best place to ask this, but is the XOR binary operator a combination of AND+NOT operators?

share|improve this question
    
Do you also allow OR? –  Aryabhata May 11 '11 at 14:58
7  
@Moron: Of necessity you do, thanks to our friend De Morgan... –  Nate Eldredge May 11 '11 at 15:00
4  
So with a nick like yours, all your messages seem to be insults... –  GEdgar May 11 '11 at 18:13
1  
@GEdgar: Now all the other messages seem to be insults :-) (That was one reason why I was reluctant to change it). –  Aryabhata May 12 '11 at 16:59
1  
@Dark: If what you really want to know is how to partition a two-dimensional input space with one line to represent an XOR decision boundary, that is a very different question--it can't be done. Since the input space is two-dimensional, you can draw it on a sheet of paper. If you draw all four results that XOR needs to produce, you will get a square where two diagonally opposite corners would need to be separated from the other two by the line. If two corners are on the same side of the line, then so is their midpoint. So the square's center must be on both sides of the line. Impossible. QED. –  Matt Nov 26 '11 at 16:55
show 11 more comments

7 Answers

up vote 18 down vote accepted

Yes. In fact, any logical operation can be built from the NAND operator, where

A NAND B = NOT(A AND B)

See for instance http://en.wikipedia.org/wiki/NAND_logic, which gives

A XOR B = (A NAND (A NAND B)) NAND (B NAND (A NAND B))

Digression: There is a story about certain military devices being designed using only NAND gates, so that only one part needs to be certified, stocked as spares, etc. I don't know whether it's actually true.

share|improve this answer
3  
AKA, Sheffer stroke. –  lhf May 11 '11 at 16:12
2  
Of course, that can be simplified to (NOT(A AND B)) AND (NOT(NOT A AND NOT B)) :p –  IainM May 11 '11 at 16:31
    
Which, of course, actually gives you an obvious pattern to convert an arbitrary binary operator into a combination of ANDs and NOTs, without having to go through NAND. –  IainM May 11 '11 at 16:33
2  
Another way to determine A XOR B is A != B. –  Peter Lawrey May 11 '11 at 20:10
2  
Most flash drives are made entirely from NAND gates: tech-faq.com/nand-drive.html –  BlueRaja - Danny Pflughoeft May 11 '11 at 20:43
add comment

Meanwhile, let me add the fact that XOR is not expressible by any expression whose operations use only AND, OR, IMPLIES, ConverseImplies and IFF.

To see this, observe merely that True XOR True is False, but the other operations always take True input to True output, a feature that would be inductively preserved in complex expressions.

share|improve this answer
1  
Or, "you cannot NOT have NOT." –  J. M. May 12 '11 at 1:09
2  
I was tempted to say that that I couldn't disagree less! But actually, you can not have NOT, since it has already been observed that NAND suffices, as does NOR. –  JDH May 12 '11 at 1:56
add comment

enter image description here

share|improve this answer
add comment

Here are two similar but different versions derived using a OR b = NOT(NOT a AND NOT b), though there are others

p XOR q   =             ( p AND NOT q )  OR     ( NOT p AND q ) 
          =   NOT ( NOT ( p AND NOT q ) AND NOT ( NOT p AND q ) )

or

p XOR q   =       (     p  OR     q ) AND NOT ( p AND q )  
          =   NOT ( NOT p AND NOT q ) AND NOT ( p AND q )  
share|improve this answer
    
one too many NOTs for my liking.. But thanks for the detailed reply –  Dark Star1 May 11 '11 at 16:51
    
@Dark Star1: The first has the same number of NOTs as Nate Eldredge has NANDs, while the second has the same number of NOTs as IainM has NOTs. –  Henry May 11 '11 at 17:15
add comment

$\{AND, NOT\}$ is a complete set of operators, i.e. you can express any boolean function $f:\{0,1\}^n \to \{0,1\}$ using them:

$$f(x_1,\cdots,x_n) = \lnot \bigwedge_{w\in f^{-1}(1)} \lnot \big(\bigwedge_{w_i=1}x_i \land \bigwedge_{w_i=0}\lnot x_i \big)$$

share|improve this answer
add comment

In words, XOR means "one or the other but not both." So if I specify that I want to get a pet who is either furry or affectionate, but not both, I could say, symbolically, that I require (furry XOR affectionate) to be true.

Another way of stating this is that the two truth values put into the XOR have to be different. If both are true or both are false, their XOR is false. Only if one is true and the other false is their XOR true.

share|improve this answer
2  
Great, but the OP was asking to express XOR with just a bunch of NOTs and ANDs... –  J. M. May 12 '11 at 0:53
1  
I didn't vote you down but thanks I already understood what the XOR is in plain english, I just needed an alternate logical confirmation of thought in which I'm trying the express it in another way. –  Dark Star1 May 12 '11 at 15:21
add comment

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.