Trouble with XORs

[If this web page is unreadable your brouser may be defective. Try Mozilla.]

Background:

All boolean non-memory and non-timing logic elements can be derived from a few simple precursors. (Actually the ones with memory can also derived with this same set, but for simplicity I will ignore elements with memory.) For instance, given an adequate supply of 2 input NAND gates, all other gates can be derived. Alternately 2 input NOR gates could also be used to derive all other gates. I will call such precursors "fundamentals".

Not all simple gates are fundamentals. For instance you cannot get a inverting gate starting with just 2 input AND gates.

What is less clear is whether a XOR gate is fundamental. This document will demonstrate that the XOR is not fundamental. While this document will not be a formal proof, it should be clear how to make a formal proof from what is shown here.

I will not attempt to prove that 2 input NAND gates and 2 input NOR gates are fundamentals. But for the purpose of illustration I will show how to derive one from the other. For sucinctness, from now on I will refer to a 2 input NAND as a NAND2. And a 2 input NOR will be a NOR2.

I will use both function format (NOT(a)) and equation format (!a). Because of the limits of HTML I will use the following mapping.

Inversion of 'a' NOT(a) ! a
And of 'a' and 'b' AND(a,b) a * b
Or of 'a' and 'b' OR(a,b) a + b
Exclusive or of 'a' and 'b' XOR(a,b) a (+) b



Before proceeding further it will be helpful to review the descriptions of various simple logic gates.

NOT (1 input logic inversion) in=0 in=1
NOT(a) == ! a 1 0
.
AND2 (2 input logic AND) in 1=0 in 1=1
AND(a,b) == a * b in 2=0 0 0
in 2=1 0 1
.
NAND2 (2 input logic AND with inverted output) in 1=0 in 1=1
NAND2(a,b) == !( a * b ) in 2=0 1 1
in 2=1 1 0
.
OR2 (2 input logic OR) in 1=0 in 1=1
OR2(a,b) == a + b in 2=0 0 1
in 2=1 1 1
.
NOR2 (2 input logic OR with inverted output) in 1=0 in 1=1
NOR2(a,b) == !( a + b ) in 2=0 1 0
in 2=1 0 0
.
XOR2 (2 input exclusive OR. Also known as parity.) in 1=0 in 1=1
XOR2(a,b) == a (+) b in 2=0 0 1
in 2=1 1 0


From this you can easily show a few simple equivalencies:
NOT(a) == NAND2(a,1) ! a == !( a * 1 )
NOT(a) == NOR2(a,0) ! a == !( a + 0 )
AND2(a,b) == NOR2( NOR2(a,0), NOR2(b,0) ) a * b == !( !(a + 0) + !(b + 0) )
NAND2(a,b) == NOR2( NOR2( NOR2(a,0), NOR2(b,0) ), 0 ) !(a * b) == !( !( !(a + 0) + !(b + 0) ) + 0 )
NOR2(a,b) == NAND2( NAND2( NAND2(a,1), NAND2(b,1) ), 1 ) !(a + b) == !( !( !(a * 1) * !(b * 1) ) * 1 )
XOR2(a,b) == NAND2( NAND2( NAND2(a,1), b ), NAND2( a, NAND2(b,1) ) ) a (+) b == !( !( !(a * 1) * b ) * !( a * !(b * 1) ) )
NOT(a) == XOR2(a,1) !a == a (+) 1

This is not intended to be a complete list. Its purpose is to show some of the most useful equivalencies. We can use these in our demonstration.

Before showing that XOR2 is not fundamental, lets first show that AND2 is not fundamental. Using a simple case, this will show the general outline of how to prove a gate is not fundamental.

If we accept that a NOR2 is fundamental, then if we demonstrate we can derive a NOR2 from some other gate, then that other gate must be fundamental. To prove a gate is not fundamental we merely need to demonstrate that at least one of the gates cannot be derived from it. In the case of the AND2, the easiest target is the NOT.

Demonstrating that AND2 Is Not Fundamental

Define:
na == NOT(a) . na == !a
Which is to say if 'a' is 0, then 'na' is 1. If 'a' is 1, then 'na' is 0. Since 'a' can only have one of these two values, this constitutes a complete definition of NOT(). But we can also use it as a shorthand, where 'na' represents the inversion of 'a'. Alternately we can say that 'a' represents the inversion of 'na'.

At the inputs of our AND2 gates we can supply 0, 1, 'a', or values derived from those via other AND2 gates. Below lets list all possible combinations along with their derived values:
0 == AND2(0,0) . 0 == 0 * 0
0 == AND2(0,1) . 0 == 0 * 1
0 == AND2(1,0) . 0 == 1 * 0
1 == AND2(1,1) . 1 == 1 * 1
a == AND2(a,1) . a == a * 1
a == AND2(1,a) . a == 1 * a
0 == AND2(a,0) . 0 == a * 0
0 == AND2(0,a) . 0 == 0 * a
a == AND2(a,a) . a == a * a
Since all the outputs that can be derived from a single AND2 are still in the set of 0, 1, or 'a' it is clear that combining multiple AND2 gates will not expand this set. Therefore we cannot reach the 'na' value which is the output of the NOT(a). Therefore AND2 is not fundamental.

The demonstration for XOR2 is similar altho more lengthy.

Demonstrating that XOR2 Is Not Fundamental

We start with the same set of inputs: 0, 1, 'a'.
0 == XOR2(0,0) . 0 == 0 (*) 0
1 == XOR2(0,1) . 1 == 0 (*) 1
1 == XOR2(1,0) . 1 == 1 (*) 0
0 == XOR2(1,1) . 0 == 1 (*) 1
na == XOR2(a,1) . na == a (*) 1
na == XOR2(1,a) . na == 1 (*) a
a == XOR2(a,0) . a == a (*) 0
a == XOR2(0,a) . a == 0 (*) a
0 == XOR2(a,a) . 0 == a (*) a

Here is a difference from the AND2. We have derived a NOT gate. But now lets see if we can derive an AND2 gate from an XOR2. Remember that we only have to show one case of a gate that is not derivable from XOR2 to show that it is not fundamental.

Now that we have derived 'na', this becomes a possible input to our XOR2. Expanding the table above:
a == XOR2(na,1) . a == na (*) 1
a == XOR2(1,na) . a == 1 (*) na
na == XOR2(na,0) . na == na (*) 0
na == XOR2(0,na) . na == 0 (*) na
0 == XOR2(na,na) . 0 == na (*) na
1 == XOR2(na,a) . 1 == na (*) a
1 == XOR2(a,na) . 1 == a (*) na

This time the set of outputs has not expanded. And since the AND2 function has not appeared in the two tables we have also demonstrated that AND2 cannot be derived from XOR2. Therefore XOR2 is not fundamental.


Last modified 10 Dec 2006
http://brown.armoredpenguin.com/~abrown/contact.html
http://brown.armoredpenguin.com/~abrown/XOR/index.html