CS 150 - Spring 2007 – Lec #2: Combinational Logic - 1Combinational Logic (mostly review!)! Logic functions, truth tables, and switches" NOT, AND, OR, NAND, NOR, XOR, . . ." Minimal set! Axioms and theorems of Boolean algebra" Proofs by re-writing" Proofs by perfect induction! Gate logic" Networks of Boolean functions" Time behavior! Canonical forms" Two-level" Incompletely specified functionsCS 150 - Spring 2007 – Lec #2: Combinational Logic - 2X Y 16 possible functions (F0–F15)0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 10 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 11 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 11 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1XYFXYX nor Ynot (X or Y)X nand Ynot (X and Y)10not XX and YX or Ynot YX xor YX = YPossible Logic Functions of TwoVariables! 16 possible functions of 2 input variables:" 2**(2**n) functions of n inputsCS 150 - Spring 2007 – Lec #2: Combinational Logic - 3Cost of Different Logic Functions! Some are easier, others harder, to implement" Each has a cost associated with the number of switches needed" 0 (F0) and 1 (F15): require 0 switches, directly connect output tolow/high" X (F3) and Y (F5): require 0 switches, output is one of inputs" X' (F12) and Y' (F10): require 2 switches for "inverter" or NOT-gate" X nor Y (F4) and X nand Y (F14): require 4 switches" X or Y (F7) and X and Y (F1): require 6 switches" X = Y (F9) and X " Y (F6): require 16 switches" Because NOT, NOR, and NAND are the cheapest they are thefunctions we implement the most in practiceCS 150 - Spring 2007 – Lec #2: Combinational Logic - 4X Y X nand Y0 0 11 1 0X Y X nor Y0 0 11 1 0X nand Y ! not ( (not X) nor (not Y) ) X nor Y ! not ( (not X) nand (not Y) )Minimal Set of Functions! Implement any logic functions from NOT, NOR, and NAND?" For example, implementing X and Yis the same as implementing not (X nand Y)! Do it with only NOR or only NAND" NOT is just a NAND or a NOR with both inputs tied together" and NAND and NOR are "duals", i.e., easy to implement one using the other! Based on the mathematical foundations of logic: Boolean AlgebraCS 150 - Spring 2007 – Lec #2: Combinational Logic - 5Algebraic Structure! Consists of" Set of elements B" Binary operations { + , • }" Unary operation { ' }" Following axioms hold:1. set B contains at least two elements, a, b, such that a # b2. closure: a + b is in B a • b is in B3. commutativity: a + b = b + a a • b = b • a4. associativity: a + (b + c) = (a + b) + c a • (b • c) = (a • b) • c5. Identity: a + 0 = a a • 1 = a6. distributivity: a + (b • c) = (a + b) • (a + c) a • (b + c) = (a • b) + (a • c)7. complementarity: a + a' = 1 a • a' = 0CS 150 - Spring 2007 – Lec #2: Combinational Logic - 6Boolean Algebra! Boolean algebra" B = {0, 1}" + is logical OR, • is logical AND" ' is logical NOT! All algebraic axioms holdCS 150 - Spring 2007 – Lec #2: Combinational Logic - 7X, Y are Boolean algebra variablesX Y X •!Y0 0 00 1 01 0 01 1 1X Y X' Y' X •!Y X' •!Y' ( X •!Y ) + ( X' •!Y' )0 0 1 1 0 1 10 1 1 0 0 0 01 0 0 1 0 0 01 1 0 0 1 0 1( X •!Y ) + ( X' •!Y' ) ! X =!YX Y X' X' • Y0 0 1 00 1 1 11 0 0 01 1 0 0Boolean expression that is true when the variables X and Y have the same valueand false, otherwiseLogic Functions and Boolean Algebra! Any logic function that can be expressed as a truthtable can be written as an expression in Booleanalgebra using the operators: ', +, and •CS 150 - Spring 2007 – Lec #2: Combinational Logic - 8Axioms and Theorems of BooleanAlgebra! Identity1. X + 0 = X 1D. X • 1 = X! Null2. X + 1 = 1 2D. X • 0 = 0! Idempotency:3. X + X = X 3D. X • X = X! Involution:4. (X')' = X! Complementarity:5. X + X' = 1 5D. X • X' = 0! Commutativity:6. X + Y = Y + X 6D. X • Y = Y • X! Associativity:7. (X + Y) + Z = X + (Y + Z) 7D. (X • Y) • Z = X • (Y • Z)CS 150 - Spring 2007 – Lec #2: Combinational Logic - 9Axioms and Theorems of Boolean Algebra(cont’d)! Distributivity:8. X • (Y + Z) = (X • Y) + (X • Z) 8D. X + (Y • Z) = (X + Y) • (X + Z)! Uniting:9. X • Y + X • Y' = X 9D. (X + Y) • (X + Y') = X! Absorption:10. X + X • Y = X 10D. X • (X + Y) = X11. (X + Y') • Y = X • Y 11D. (X • Y') + Y = X + Y! Factoring:12. (X + Y) • (X' + Z) = 12D. X • Y + X' • Z = X • Z + X' • Y (X + Z) • (X' + Y)! Consensus:13. (X • Y) + (Y • Z) + (X' • Z) = 13D. (X + Y) • (Y + Z) • (X' + Z) = X • Y + X' • Z (X + Y) • (X' + Z)CS 150 - Spring 2007 – Lec #2: Combinational Logic - 10Axioms and Theorems of Boolean Algebra(cont’d)! deMorgan's:14. (X + Y + ...)' = X' • Y' • ... 14D. (X • Y • ...)' = X' + Y' + ...! Generalized de Morgan's:15. f'(X1,X2,...,Xn,0,1,+,•) = f(X1',X2',...,Xn',1,0,•,+)! Establishes relationship between • and +CS 150 - Spring 2007 – Lec #2: Combinational Logic - 11Axioms and Theorems of Boolean Algebra(cont’d)! Duality" Dual of a Boolean expression is derived by replacing • by +, + by •, 0by 1, and 1 by 0, and leaving variables unchanged" Any theorem that can be proven is thus also proven for its dual!" Meta-theorem (a theorem about theorems)! Duality:16. X + Y + ... $ X • Y • ...! Generalized duality:17. f (X1,X2,...,Xn,0,1,+,•) $ f(X1,X2,...,Xn,1,0,•,+)! Different than deMorgan’s Law" This is a statement about theorems" This is not a way to manipulate (re-write) expressionsCS 150 - Spring 2007 – Lec #2: Combinational Logic - 12Proving Theorems (Rewriting Method)! Using the axioms of Boolean algebra:" e.g., prove the theorem: X • Y + X • …
View Full Document
Unlocking...