XOR

 BBS: Inland Empire Archive
Date: 08-20-92 (14:12)             Number: 194
From: ED BEROSET                   Refer#: NONE
  To: ERAN GRANOT                   Recvd: NO  
Subj: XOR                            Conf: (1) 80xxx

In a message to All <14 Aug 92 15:37> Eran Granot wrote:

 EG> HI.
 EG> I need to write a procedure that cnvert the XOR gate.

 EG> Does anyone know how can I write this procedure without use the XOR
 EG> statment ?

Assuming that you mean, "How do I calculate an XOR using
only OR, NOT, and AND operations?" there are many answers.
(If we use ~ as the unary NOT operator, it's easier to
write.)

X xor Y = (X and ~Y) or (~X and Y)

alternatively stated, this is:

X xor Y = (X or Y) and ~(X and Y)

Assuming X and Y are in the AL and AH registers, we can code this as:

mov bl,al      ; bl = X
or  bl,ah      ; bl = bl or Y = X or Y
and al,ah      ; al = X and Y
not al         ; al = ~(X and Y)
and al,bl      ; al = al and bl = ~(X and Y) and (X or Y) = X xor Y

There are other transformations which require only OR and
NOT operations, or AND and NOT operations.  For information
on these transformations, any elementary book on Boolean
algebra should cover this --

X xor Y = (X and ~Y) or (~X and Y)

Law of negation says that ~(~A) = A, so

X xor Y = ~(~( (X and ~Y) or (~X and Y) ))

DeMorgan's Law states: ~(A or B) = ~A and ~B, so

X xor Y = ~( ~(X and ~Y) and ~(~X and Y) )

Now you have the XOR function stated using only AND and NOT
operations.  Similarly,

X xor Y = (X or Y) and ~(X and Y)
X xor Y = ~(~( (X or Y) and ~(X and Y) ))     ; law of negation
X xor Y = ~( ~(X or Y)   or  (X and Y)  )     ; DeMorgan again
X xor Y = ~( ~(X or Y) or ~(~(X and Y)) )     ; law of negation
X xor Y = ~( ~(X or Y) or ~( ~X or ~Y ) )     ; DeMorgan again

And that's XOR using only OR and NOT operations.  Coding
these is left as an exercise for the reader.  ;-)

-> Ed <-

--- QT via QMX/XRS
 * Origin: > The Paradoxicon < 919-850-9289 > USR DS V42 < (1:151/143)