19
$\begingroup$

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?

$\endgroup$
25
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ AKA, Sheffer stroke. $\endgroup$ – lhf May 11 '11 at 16:12
  • 3
    $\begingroup$ Of course, that can be simplified to (NOT(A AND B)) AND (NOT(NOT A AND NOT B)) :p $\endgroup$ – reavowed May 11 '11 at 16:31
  • $\begingroup$ 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. $\endgroup$ – reavowed May 11 '11 at 16:33
  • 2
    $\begingroup$ Another way to determine A XOR B is A != B. $\endgroup$ – Peter Lawrey May 11 '11 at 20:10
  • 3
    $\begingroup$ Most flash drives are made entirely from NAND gates: tech-faq.com/nand-drive.html $\endgroup$ – BlueRaja - Danny Pflughoeft May 11 '11 at 20:43
9
$\begingroup$

enter image description here

$\endgroup$
6
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ Or, "you cannot NOT have NOT." $\endgroup$ – J. M. is a poor mathematician May 12 '11 at 1:09
  • 2
    $\begingroup$ 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. $\endgroup$ – JDH May 12 '11 at 1:56
  • $\begingroup$ Since NAND(p,p) is equivalent to NOT(p) as well as NOR(p,p) is equivalent to NOT(p), it still holds that "you cannot NOT have NOT". Since logical functions are simply defined by their truth table, The meaning of that sentence can be paraphrased as "you cannot not have a unary function that inverts its input". $\endgroup$ – wolfmanx Apr 11 at 16:25
4
$\begingroup$

Yes, see http://en.wikipedia.org/wiki/Exclusive_or#Equivalencies.2C_elimination.2C_and_introduction

$\endgroup$
4
$\begingroup$

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 )  
$\endgroup$
  • $\begingroup$ one too many NOTs for my liking.. But thanks for the detailed reply $\endgroup$ – Dark Star1 May 11 '11 at 16:51
  • $\begingroup$ @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. $\endgroup$ – Henry May 11 '11 at 17:15
2
$\begingroup$

$\{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)$$

$\endgroup$

protected by user99914 Oct 10 '17 at 21:15

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

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