Boolean Algebra

Introduction
Boolean Operators
Rules of Precedence
Boolean Functions
Identities of Boolean Algebra
The Laws of Boolean Algebra
Duality
Representing Boolean Functions
1. Minterms
2. Sum-of-Products
Two-Bit by Two-Bit Multiplier

Introduction

Claude Shannon (1939) showed how the basic rules of logic could be used to design circuits. The logic of George Boole forms the basis of boolean algebra.
Steps in constructing a circuit:
1. Represent the boolean function of the circuit with a boolean expression using the basic operations of boolean algebra.
2. Perform a minimization to find an expression with the minimum number of operations, thus creating an efficient circuit.

Boolean Operators

The boolean operators are:
1. Complement
  - NOT or Inverter
  - ~0 = 1 and ~1 = 0
2. Product
  - AND
  - 0 · 0 = 0, 0 · 1 = 0, 1 · 0 = 0, 1 · 1 = 1
3. Sum
  - OR
  - 0 + 0 = 0, 0 + 1 = 1, 1 + 0 = 1, 1 + 1 = 1

Rules of Precedence

The rules of precedence for boolean operators :
1. complements
2. products
3. sums

Example

       ~(1+0) + 1 · 0 
     = ~(1)   + 1 · 0 
     =   0    + 1 · 0 
     =   0    + 0 
     =   0

Boolean Functions

Boolean Variable
- x is a boolean variable if it assumes values only from the set B={0,1}.
Boolean Function
- A boolean function can be represented using a boolean expression of boolean varibles and operators.
An example of a boolean function is F(x,y,z) = xy + ~z where xy + ~z is a boolean expression.

The truth table for F(x,y,z) = xy + ~z is

     x  y  z   F
     -----------
     0  0  0   1
     0  0  1   0
     0  1  0   1
     0  1  1   0
     1  0  0   1
     1  0  1   0
     1  1  0   1
     1  1  1   1

A boolean function of degree n is a function from the set

{ (x ,x ,...,x ) | x  in B, 1 <= i <= n } to the set B={0,1}.
    1  2      n     i

Boolean functions F and G of degree n are equal if and only if

F(b ,b ,...,b ) = G(b ,b ,...,b ) whenever b , b , ..., b  
   1  2      n       1  2      n            1   2        n

are members of {0,1}.

For example, the functions F(x,y) = xy and G(x,y) = xy + 0 are equal and their expressions are said to be equivalent.

Identities of Boolean Algebra

Name	Identity
Complement Laws	x + ~x = 1 x · ~x = 0
Law of the Double Complement	~(~x) = x
Idempotent Laws	x + x = x x · x = x
Identity Laws	x + 0 = x x · 1 = x
Dominance Laws	x + 1 = 1 x · 0 = 0
Commutative Laws	x + y = y + x x · y = y · x
Associative Laws	x + (y + z) = (x + y) + z x · (y · z) = (x · y) · z
Distributive Laws	x + (y · z) = (x + y) · (x + z) x · (y + z) = (x · y)+(x · z)
DeMorgan's Laws	~(x · y) = ~x + ~y ~(x + y) = ~x · ~y
Absorption Law	x · (x + y) = x

The Laws of Boolean Algebra

Each law can be proved using a truth table or by the use of other laws.

Example : the distributive law x · (y + z) = x · y + x · z

     x  y  z   y + z   xy   xz   x(y + z)   xy + xz
     ----------------------------------------------
     0  0  0     0      0    0       0         0
     0  0  1     1      0    0       0         0
     0  1  0     1      0    0       0         0
     0  1  1     1      0    0       0         0
     1  0  0     0      0    0       0         0
     1  0  1     1      0    1       1         1
     1  1  0     1      1    0       1         1
     1  1  1     1      1    1       1         1

Prove the absorption law x(x + y) = x using the laws of boolean algebra.

     x(x + y) = (x + 0)(x + y)     Identity law
              = x + (0 · y)        Distributive law
              = x + (0)            Dominance law 
              = x                  Identity law
         OR

     x(x+y) = (xx) + (xy)  Distributive law
            = x + (xy)     Idempotent law
            = x(1 + y)     Distributive law
            = x(1)         Dominance law
            = x            Identity law

Duality

The dual of a boolean expression is obtained by interchanging boolean sums and products and interchanging 0's and 1's.
Examples
- the dual of x(y + 0) is x + (y · 1)
- the dual of (~x · 1) + (~y + z) is (~x + 0) · (~y · z)

Construct the dual of the absorption law, x(x + y) = x

the dual is x + (xy) = x

     x  y   xy    x + (xy)
     ---------------------
     0  0    0      0
     0  1    0      0
     1  0    0      1
     1  1    1      1

Representing Boolean Functions

Any boolean function may be represented by a boolean sum of boolean products of the variables and their complements.
For all entries in the truth table where the output is one, construct a product term which consists of the input variables if they are one or their complements if they are zero.

Minterms

For example, if F(x,y,z) = 1 when x = 0, y = 1 and z = 0 then the product term is ~x · y · ~z.
All these product terms are then summed to give a sum-of-products expansion.

A minterm of the boolean variables

x ,x ,...,x  is a boolean product y  y  ... y  where y  = x  or y  = ~x . 
 1  2      n                       1  2      n        i    i     i     i

Sum-of-Products

     x  y  z   F
     -----------
     0  0  0   0
     0  0  1   0
     0  1  0   0
     0  1  1   0
     1  0  0   0
     1  0  1   1 *
     1  1  0   0
     1  1  1   0

F(x,y,z) = x ~y z

     x  y  z   F
     -----------
     0  0  0   0
     0  0  1   0
     0  1  0   1 *
     0  1  1   0
     1  0  0   0
     1  0  1   0
     1  1  0   1 *
     1  1  1   0

F(x,y,z) = ~xy · ~z + xy · ~z

Find the sum-of-products expansion for F(x,y,z)=(x+y) · ~z

     x  y  z   F
     -----------
     0  0  0   0
     0  0  1   0
     0  1  0   1 *
     0  1  1   0
     1  0  0   1 *
     1  0  1   0
     1  1  0   1 *
     1  1  1   0

Two-Bit by Two-Bit Multiplier

Construct the truth table using 4 inputs and 4 outputs where both the inputs and outputs represent binary numbers.
Find a sum-of-products expansion for this truth table.
Minimize the sum-of-products expansion using boolean algebra.

                X X  Y Y  Z Z Z Z   Z  Z  Z  Z
                 1 0  1 0  3 2 1 0   3  2  1  0
     -------------------------------------------
     0 X 0 = 0   00   00    0000 
     0 X 1 = 0   00   01    0000
     0 X 2 = 0   00   10    0000
     0 X 3 = 0   00   11    0000
     1 X 0 = 0   01   00    0000
     1 X 1 = 1   01   01    0001              *
     1 X 2 = 2   01   10    0010           *
     1 X 3 = 3   01   11    0011           *  *
     2 X 0 = 0   10   00    0000
     2 X 1 = 2   10   01    0010           *
     2 X 2 = 4   10   10    0100        *
     2 X 3 = 6   10   11    0110        *  * 
     3 X 0 = 0   11   00    0000
     3 X 1 = 3   11   01    0011           *  * 
     3 X 2 = 6   11   10    0110        *  * 
     3 X 3 = 9   11   11    1001     *        *

Sum-of-Products

Z
 0

               X X  Y Y  Z Z Z Z  Z  Z  Z  Z
                1 0  1 0  3 2 1 0  3  2  1  0
     ----------------------------------------
     1 X 1 = 1  01   01     0001            *
     1 X 3 = 3  01   11     0011         *  *
     3 X 1 = 3  11   01     0011         *  *
     3 X 3 = 9  11   11     1001   *        *

     Z = ~X X ~Y Y + ~X X Y Y + X X ~Y Y + X X Y Y 
      0    1 0  1 0    1 0 1 0   1 0  1 0   1 0 1 0

Z
 1

               X X  Y Y  Z Z Z Z  Z  Z  Z  Z
                1 0  1 0  3 2 1 0  3  2  1  0
     ----------------------------------------
     1 X 2 = 2  01   10     0010         *   
     1 X 3 = 3  01   11     0011         *  *
     2 X 1 = 2  10   01     0010         *   
     2 X 3 = 6  10   11     0110      *  *   
     3 X 1 = 3  11   01     0011         *  *
     3 X 2 = 6  11   10     0110      *  *   

     Z =  ~X X Y ~Y + ~X X Y Y + X ~X ~Y Y + X ~X Y Y + X X ~Y Y + X X Y ~Y 
      1     1 0 1  0    1 0 1 0   1  0  1 0   1  0 1 0   1 0  1 0   1 0 1  0

Z
 2

                X X  Y Y  Z Z Z Z   Z  Z  Z  Z
                 1 0  1 0  3 2 1 0   3  2  1  0
     ------------------------------------------
     2 X 2 = 4   10   10     0100       *     
     2 X 3 = 6   10   11     0110       *  * 
     3 X 2 = 6   11   10     0110       *  *

     Z = X ~X Y ~Y + X ~X Y Y + X X Y ~Y
      2   1  0 1  0   1  0 1 0   1 0 1  0

Z
 3

                X X  Y Y  Z Z Z Z   Z  Z  Z  Z
                 1 0  1 0  3 2 1 0   3  2  1  0
     ------------------------------------------
     3 X 3 = 9   11   11     1001    *        *
     
     Z = X X Y Y
      3   1 0 1 0

Minimization

Z  =  ~X X ~Y Y  + ~X X Y Y  + X X ~Y Y  + X X Y Y
 0      1 0  1 0     1 0 1 0    1 0 1 0     1 0 1 0

   =  ~X X Y (~Y  + Y ) + X X Y (~Y  + Y )    distributive
        1 0 0   1    1     1 0 0   1    1

   =  ~X X Y  + X X Y      complement and identity
        1 0 0    1 0 0

   =  X Y ( ~X  + X )      distributive
       0 0    1    1

   =  X Y                  complement and identity
       0 0


Z  =  ~X X Y ~Y  + ~X X Y Y  + X ~X ~Y Y  + X ~X Y Y  + X X ~Y Y  + X X Y ~Y
 1      1 0 1  0     1 0 1 0    1  0  1 0    1  0 1 0    1 0  1 0    1 0 1  0

   =  ~X X Y (~Y + Y ) + X ~X Y ( ~Y + Y ) + X X ~Y Y + X X Y ~Y   distributive
        1 0 1   0   0     1  0 0    1   1     1 0  1 0   1 0 1  0

   =  ~X X Y + X ~X Y  + X X ~Y Y  + X X Y ~Y   complement and identity
        1 0 1   1  0 0    1 0  1 0    1 0 1  0

   =  ~X X Y  + X ~X Y  + (X ~X ~Y Y ) + X X ~Y Y  + (~X X Y ~Y ) + X X Y ~Y   idempotent
        1 0 1    1  0 0     1  0  1 0     1 0  1 0      1 0 1  0     1 0 1  0

   =  ~X X Y  + X ~X Y  + X ~Y Y (~X + X ) + X Y ~Y (~X + X )      distributive 
        1 0 1    1  0 0    1  1 0   0   0     0 1  0   1   1
     
   =  ~X X Y  + X ~X Y  + X ~Y Y  + X Y ~Y      complement and identity
        1 0 1    1  0 0    1  1 0    0 1  0


Z  =  X ~X Y ~Y  + X ~X Y Y  + X X Y ~Y
 2     1  0 1  0    1  0 1 0    1 0 1  0

   =  X ~X Y ( ~Y + Y ) + X X Y ~Y           distributive
       1  0 1    0   0     1 0 1  0

   =  X ~X Y  + X X Y ~Y                     complement and identity
       1  0 1    1 0 1  0

   =  X ~X Y  + ( X ~X Y ~Y ) + X X Y ~Y     idempotent
       1  0 1      1  0 1  0     1 0 1  0

   =  X ~X Y  + X Y ~Y (~X + X )             distributive
       1  0 1    1 1  0   0   0

   =  X ~X Y  + X Y ~Y                       complement and identity
       1  0 1    1 1  0


Z  =  X X Y Y 
 3     1 0 1 0

Z  =  X ~X Y  + X Y ~Y
 2     1  0 1    1 1  0

Z  =  X ~Y Y  + X ~X Y  + ~X X Y  + X Y ~Y
 1     1  1 0    1  0 0     1 0 1    0 1  0

Z  =  X Y
 0     0 0

The NAND Gate Multiplier

Some gates are intrinsically better than others.
NAND gates are both faster and cheaper than AND gates.
To construct a circuit solely out of NAND gates, the double complement law and de Morgan's law can be used: ~~X = X and ~(X+Y) = ~X · ~Y
```
     F = A + B + C
       = ~~( A + B + C )
       = ~( ~A · ~B · ~C )
```
A NAND gate can also be used to perform as an inverter.
- To invert the input X, use this one input as both of the inputs to the NAND gate.

     X  Y  F=~(X · Y)
     ---------------------
     0  0  1  
     0  1  1   
     1  0  1   
     1  1  0  

Z  =  X X Y Y
 3     1 0 1 0

   =  ~( ~( X X Y Y ) )
             1 0 1 0


Z  =  X ~X Y  + X Y ~Y
 2     1  0 1    1 1  0

   =  ~( ~( X ~X Y  + X Y ~Y ) )
             1  0 1    1 1  0

   =  ~( X ~X Y · X Y ~Y )
          1  0 1   1 1  0


Z  =  X ~Y Y  + X ~X Y  + ~X X Y  + X Y ~Y
 1     1  1 0    1  0 0     1 0 1    0 1  0

   =  ~( ~( X ~Y Y  + X ~X Y  + ~X X Y  + X Y ~Y ) )
             1  1 0    1  0 0     1 0 1    0 1  0

   =  ~( X ~Y Y · X ~X Y · ~X X Y · X Y ~Y ) 
          1  1 0   1  0 0    1 0 1   0 1  0


Z  =  X Y 
 0     0 0

   =  ~( ~( X Y ) )
             0 0

Return to Digital Syllabus

Boolean Algebra

Table of Contents

Introduction

Boolean Operators

Rules of Precedence

Boolean Functions

Identities of Boolean Algebra

The Laws of Boolean Algebra

Duality

Representing Boolean Functions

Minterms

Sum-of-Products

Two-Bit by Two-Bit Multiplier

Sum-of-Products

Minimization

The NAND Gate Multiplier