CP1300 Boolean Algebra

• History
  • Named after George Boole, who first introduced it in 1854
  • A formal system of logic used as the basis for computer circuitry
  • Used to design and analyse the function of computer circuitry

• Boolean Operators
  • NOT: NOT X is 0 if X is 1, is 1 otherwise (X')
  • AND: X AND Y is 1 if X and Y are 1, is 0 otherwise (X*Y or X.Y)
  • NAND: X NAND Y is 0 if X and Y are 1, is 1 otherwise
  • OR: X OR Y is 0 if X and Y are 0, is 1 otherwise (X+Y)
  • NOR: X NOR Y is 1 if X and Y are 0, is 0 otherwise
  • XOR: X XOR Y is 0 if X and Y are the same, is 1 otherwise
  • XNOR: X XNOR Y is 1 if X and Y are the same, is 0 otherwise

• Evaluating Boolean Expressions
  • Precedence: NOT > AND > OR
  • The format is called Truth Tables
  • Example, F = (X'+Y)*Y*Z+Z'

    X Y Z X' X'+Y (X'+Y)*Y (X'+Y)*Y*Z Z' (X'+Y)*Y*Z+Z'
    0 0 0  1    1        0          0  1             1
    0 0 1  1    1        0          0  0             0
    0 1 0  1    1        1          0  1             1
    0 1 1  1    1        1          1  0             1
    1 0 0  0    0        0          0  1             1
    1 0 1  0    0        0          0  0             0
    1 1 0  0    1        1          0  1             1
    1 1 1  0    1        1          1  0             1
    

  • Example, F = X+(X*(Y'+Y))*Z+(Y'+Y)'

• Laws of Boolean Algebra
  • Some laws you should know
    • X + 0 = X
    • X + X' = 1
    • X + X = X
    • X + 1 = 1
    • (X')' = X
    • X + Y = Y + X
    • X + (Y + Z) = (X + Y) + Z
    • X * (Y + Z) = (X * Y) + (X * Z)
    • (X + Y)' = X' * Y'
    • X + (X * Y) = X
    • X * 1 = X
    • X * X' = 0
    • X * X = X
    • X * 0 = 0
    • X * Y = Y * X
    • X * (Y * Z) = (X * Y) * Z
    • X + (Y * Z) = (X + Y) * (X + Z)
    • (X * Y)' = X' + Y'
    • X * (X + Y) = X
  • The laws can be verified using truth tables
  • Boolean expressions can be simplified (like mathematical ones) using laws of Boolean algebra
  • Example, F = (X'+Y)*Y*Z+Z' = Y*Z+Z'
  • Example, F = X+(X*(Y'+Y))*Z+(Y'+Y)'

• Karnaugh Maps
  • A different form of truth table
  • Shows the relationships between the function variables
  • Example, F = X * (Y + (X + (Z * X)))

    X Y Z  F             Z|     
    0 0 0  0          X Y | 0 1
    0 0 1  0          ----+----
    0 1 0  0          0 0 | 0 0
    0 1 1  0          0 1 | 0 0
    1 0 0  1          1 1 | 1 1
    1 0 1  1          1 0 | 1 1
    1 1 0  1
    1 1 1  1
    

  • Note
    • One or two variables per axis
    • Two variable axis values change one bit at a time
  • Simplification using Minterms
    • A minterm is a group of cells whose values are 1
    • Must be of size 2^N, e.g. 1, 2, 4, 8, ...
    • Minterms can overlap
    • They can be wrapped around the edges of the map
    • The minterms need to cover all 1's in the map
    • A minterm's value is the AND of the non-changing variables
      • The plain variable if it's always 1 in the minterm
      • The negated variables if it's always 0 in the minterm
    • OR'ing minterms' values provides the simplified result
    • Larger minterms produce simpler circuits
  • Examples
    • 
    • X'*Y'*Z + X'*Y*Z + X*Y'*Z' + X*Y'*Z + X*Y*Z' + X*Y*Z

Self assessments

• Boolean Algebra
• Karnaugh Maps (Q1 to Q9)

Tutorial Questions

• Boolean Algebra (Answers)
• Karnaugh Maps (Q1 to Q5) (Answers)

Exam style questions

1. Who introduced Boolean algebra, and when? Briefly explain what it is.
2. State the definitions of four basic Boolean operators.
3. What is the result of F = (X * Z') + (Y * Z), when X = Y = 1, Z = 0 ?
4. Write out the truth table for F = (X * Z') + (Y * Z)
5. Simplify the expression: Z' * X * (X + ((Y * Z) + X) (Hint: you should end up with an expression of the form: A * B)
6. What is a K-Map?
7. What are Minterms?
8. Determine if F = (X * Z') + (Y * Z) is the simplest Boolean expression for calculating F.