Study Notes on Boolean Algebra and Logic Functions

INTRODUCTION

  • Boolean signals represent two states: True (1) and False (0).
  • Boolean algebra enables the manipulation of these signals in physical circuits.
  • Use nand2tetris simulator for circuit simulation.

LOGIC FUNCTIONS

  • Logic circuits have canonical representations via AND, OR, NOT functions.
  • Sum-of-products representation is employed.
  • Two forms of canonical representation: sum-of-products and product-of-sums.

LOGIC EQUATIONS

  • Logic functions expressed mathematically:
    • AND: $A \land B$ (A & B, A•B)
    • OR: $A \lor B$ (A | B, A + B)
    • NOT: $\neg A$ (~A)
  • Different disciplines may use varying symbols.

PRECEDENCE

  • Operator precedence:
    • NOT has highest precedence.
    • Then AND.
    • Finally OR.
  • Example: $A + B \cdot C \equiv A + (B \cdot C)$.

DESIGNING LOGIC CIRCUITS

  • Start with a truth table to determine equations for outputs based on inputs.
  • Sum-of-products used for outputs that result in True values.
  • These can be simplified using Boolean algebra.

SIMPLIFYING

  • Aim for minimal gate usage to reduce costs and propagation delay.
  • Propagation delay: time taken for input changes to affect output.

BOOLEAN ALGEBRA

  • Rules defined by George Boole allow reasoning and simplification of logic functions:
    • Basic operations for two variables:
    • $0 + 0 = 0, \; 0 + 1 = 1, \; 1 + 0 = 1, \; 1 + 1 = 1$
    • $0 \cdot 0 = 0, \; 0 \cdot 1 = 0, \; 1 \cdot 0 = 0, \; 1 \cdot 1 = 1$

DE MORGAN'S THEOREM

  • Two key equations:
    • $A \cdot B = \neg(A + B)$
    • $A + B = \neg(A \cdot B)$
  • Fundamental for building functions using NAND gates.

LOGIC GATES

  • NAND gates can construct any logic circuit.
  • Programmable logic chips composed of arrays of NAND gates.
  • NOT gate can be constructed using a NAND gate when inputs are identical.

GATE CONSTRUCTION

  • AND gate can be built from two NAND gates.
  • OR gate construction requires understanding of De Morgan's Theorem due to its complexity.

ONE AND TWO INPUT FUNCTIONS

  • Logic functions categorized by inputs:
    • One input: Constant zero, NOT A, Constant one.
    • Two input functions have 16 combinations including AND, OR, NAND, NOR, XOR, etc.
  • Important functions derived include AND, OR, and NOT from earlier definitions; foundational to circuit design.