Addition

Home > Lecture Notes > Addition

Exclusive OR means "one or the other, but not both" and is written XOR. When constructing Boolean expressions from English statements the words "but" and "and" mean the same thing. Using P and Q as variables we can say P XOR Q is equivalent to ( P OR Q ) AND ( NOT (P AND Q) ). Written as a Boolean expression:

( P + Q ) · ( P · Q )'

The expression ( P · Q )' is equivalent to ( P' + Q' ), so you may also see XOR expanded as

( P + Q ) · ( P' + Q' )

Exercise:

Construct truth tables to verify that the expressions ( P · Q )' and ( P' + Q' ) are equivalent.
Construct a second set of truth tables to verify that ( P + Q )' is equivalent to ( P' · Q' ). This pair of logical equivalencies were first formally stated in mathematical terms by the British mathematician Augustus De Morgan, contemporary of George Boole (and also tutor to Ada Lovelace on the recommendation of Charles Babbage), and are known as "De Morgan's laws."

The truth table for ( P + Q ) · ( P · Q )'

P	Q	(P + Q)	(P · Q)	(P · Q)'	(P + Q) · (P · Q)'
1	1	1	1	0	0
1	0	1	0	1	1
0	1	1	0	1	1
0	0	0	0	1	0

The XOR truth table

P	Q	P XOR Q
1	1	0
1	0	1
0	1	1
0	0	0

[ TOP ]

Addition

For all their perceived power, computers essentially only add, compare, and remember.

Consider addition of 2 single-digit binary numbers; there are 4 possibilities:

          0              0              1              1
       +  0           +  1           +  0           +  1
     ------         ------         ------         ------
       0  0           0  1           0  1           1  0
   carry][sum     carry][sum     carry][sum     carry][sum

Note that all four sums have been separated into 2 parts: the result of the sum without regard to the carry, and the result of the carry by itself.

Now look at the truth tables for P AND Q and P XOR Q:

     P    Q    P AND Q             P    Q    P XOR Q
     -----------------             -----------------
     0    0       0                0    0       0
     0    1       0                0    1       1
     1    0       0                1    0       1
     1    1       1                1    1       0

If P and Q are binary digits, logical XOR describes their sum (disregarding the carry) and logical AND describes the result of the carry!

              P plus Q                      P plus Q
     P    Q    (Carry)             P    Q     (Sum)
     -----------------             -----------------
     0    0       0                0    0       0
     0    1       0                0    1       1
     1    0       0                1    0       1
     1    1       1                1    1       0

Applying the above logic to a circuit using AND, OR, and NOT gates we can construct a "half adder." Use of the XOR gate becomes very handy to simplify the circuit. It is called a half adder because it does not take into account the possible carry in of an earlier addition. So we wire two half adders together to build a full adder.

A full adder has 3 input lines: carry in from a previous addition, and 2 "single-digit binary numbers". The 2 numbers go into a half adder, just like the half adder on its own. The sum output of the half adder becomes one of the input "numbers" to the next half adder along with the carry in. The carry out of the second half adder is combined with the carry out of the second half adder and becomes carry out for the full adder. The sum output of the second half adder is the sum output of the full adder.

To "combine" two bits we simply logically OR them. Which is probably as good an explanation as any why the traditional arithmetic plus symbol is used for the OR symbol in Boolean algebra.

[ TOP ]

Revised: 26 JAN 2002 17:00