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.