20
$\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?

6 Answers 6

27

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.

  • 3
    Most flash drives are made entirely from NAND gates: http://www.tech-faq.com/nand-drive.html2011-05-11
10

enter image description here

7

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.

5

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 )   
  • 0
    @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.2011-05-11
4

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

2

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