Boolean algebra cheat sheet

Submitted by olaf on 2016-02-21

I saw a lecture on Youtube about Digital Circuit Design from The University of New South Wales, Australia. It is mostly about Boolean algebra. Even though I am familiar with the basics, it contains enough I don’t know. So here’s my small cheat sheet.

  • Precedence (from highest to lowest)

      () (grouping, parenthesis)
      *  (logical and)
      +  (logical or)
      '  (logical not)
    
  • Identity

      X + 0 = X
      X * 1 = X
    
  • Null

      X + 1 = 1
      X * 0 = 0
    
  • Idempotence

      X + X = X
      X * X = X
    
  • Complementarity

      X + X' = 1
      X * X' = 0
    
  • Involution

      X'' = X
    
  • Commutativity

      X + Y = Y + X
      X * Y = Y * X
    
  • Associativity

      X + (Y + Z) = (X + Y) + Z
      X * (Y * Z) = (X * Y) * Z
    
  • Distributivity

      X * (Y + Z) = X * Y + X * Z
      X + Y * Z = (X + Y) * (X + Z)
    
  • DeMorgan’s Theorem

      (X + Y)' = X' * Y'
      (X * Y)' = X' + Y'
    
  • Duality Theorem

      0 <-> 1
      + <-> *
    

    If you prove a theorem, its dual theorem (replacing 0 with 1, + with *, and vice versa) is also true.

  • Absorption

      X + X * Y = X
      X * (X + Y) = X
    
  • Minimization

      X * Y + X * Y' = X
      (X + Y) * (X + Y') = X
    
  • Simplification

      X + X' * Y = X + Y
      X * (X' + Y) = X * Y
    
  • Consensus

      X * Y + X' * Z + Y * Z = X * Y + X' * Z
      (X + Y) * (X' + Z) * (Y + Z) = (X + Y) * (X' + Z)
    
  • Perfect Induction

    Proving a theorem with perfect induction just means, spell out each side of an equation in a truth table and compare the results. If the results match, the theorem is valid.

Post a comment

All comments are held for moderation; Markdown and basic HTML formatting accepted. If you want to stay anonymous, leave name, e-mail and website empty.