Chapter 2

1 Chapter 2. Combinational Logic Circuits Shann Chapter Overview 2-1 binary Logic and Gates 2-2 Boolean Algebra 2-3 Standard Forms 2-4 Two-Level Circuit Optimization 2-5 Map Manipulation Quine-McCluskey Method 2-6 Multiple-Level Circuit Optimization 2-7 Other Gate Types 2-8 Exclusive-OR Operator and Gates 2-9 High-Impedance Outputs 2-10 Chapter Summary Shann 2-2. 2-1 binary Logic and Gates Digital circuits: hardware components that manipulate binary information are implemented using transistors and interconnections in integrated circuits. Logic gate: basic ckt that performs a specific logical op Shann 2-3. A. binary Logic binary logic: deals w/ binary variables and the ops of mathematical logic applied to these variables. binary variable: variable that take on two discrete values resembles binary arithmetic, but should no be confused w/.

2 Each other. Shann 2-4. Basic Logic Operations Basic logical ops: , Table 2-1. AND: , . identical to binary multiplication OR: + , . resemble binary addition In binary logic, 1 + 1 = 1. In binary arithmetic: 1 + 1 = 10. NOT: complement; , Shann 2-5. Truth Table Truth table: a table of combinations of the binary variables showing the relationship b/t the values that the variables take on and the values of the result of the op. 2n rows, n: # variables : truth table for AND op Shann 2-6. B. Logic Gates Logic gate: is an electronic ckt that operate on one or more input signals to produce an output signal. The input terminals of logic gates accept binary signals within the allowable range and respond at the output terminals w/ binary signals that fall within a specified range. : transition region Shann 2-7. Graphic symbols of 3 basic logic gates: Timing diagram: Shann 2-8.

3 Multiple-input logic gates: AND and OR gates may have 2 inputs. : Shann 2-9. 2-2 Boolean Algebra Boolean algebra: is an algebra dealing w/ binary variables and logic ops binary variables: are designated by letters of the alphabet logic ops: AND, OR, NOT. Boolean expression: an algebraic expression formed by using binary variables, the constants 0 and 1, the logic op symbols, and parentheses. Shann 2-10. Boolean Function Boolean function: can be described by a Boolean equation, a truth table, or a logic ckt diagram Single-output Boolean function Multiple-output Boolean function Shann 2-11. Boolean Equation Boolean equation: consists of a binary variable identifying the function followed by an equal sign and a Boolean expression. expresses the logical relationship b/t binary variables can be expressed in a variety of ways * Obtain a simpler expression for the same function.

4 : F ( X , Y , Z ) = X + YZ. terms Shann 2-12. Truth table for a function: is unique a list of all combinations of 1's and 0's that can be assigned to the binary variables and a list that shows the value of the function for each binary combination. : F ( X , Y , Z ) = X + Y Z. Shann 2-13. Logic circuit diagram: An algebraic expression for a Boolean function A ckt diagram composed of logic gates Circuit gates are interconnected by wires that carry logic signals. : F ( X , Y , Z ) = X + Y Z. Combinational logic circuits Shann 2-14. Example Present a set of requirements under which an insurance policy will be issued: The applicant must be 1. a married female 25 years old or over, or 2. a female under 25, or 3. a married male under 25 who has not been involved in a car accident, or 4. a married male who has been involved in a car accident, or 5.

5 A married male 25 years or over who has not been involved in a car accident. Shann 2-15. <Ans.>. Define variables: 4; w, x, y, z w = 1 if applicant has been involved in a car accident x = 1 if applicant is married y = 1 if applicant is a male z = 1 if applicant is under 25. Find a Boolean expression which assumes the value 1 whenever the policy should be issued: x y z 1. a married female 25 years old or over y z 2. a female under 25. w x y z 3. a married male under 25 who has not been involved in a car accident wxy 4. a married male who has been involved in a car accident w x y z 5. a married male 25 years or over who has not been involved in a car accident F = x y z + y z + w x y z + w x y + w x y z . Shann 2-16. Simplify the expression and suggest a simpler set of requirements: F = x y z + y z + w x y z + w x y + w x y z.

6 = x + y z w=1 if applicant has been involved in a car accident x=1 if applicant is married y=1 if applicant is a male z=1 if applicant is under 25. The applicant must be 1. married or 2. a female under 25. Shann 2-17. A. Basic Identities of Boolean Algebra Basic identities of Boolean Algebra: X, Y, Z: binary variable Shann 2-18. dual Duality Principle Dual: The dual of an algebraic expression is obtained by interchanging OR and AND ops and replacing 1's by 0's and 0's by 1's (OR AND, 0 1). : . X + 0 . X 1. dual Duality principle: A Boolean equation remains valid if we take the dual of the expressions on both sides of the equals sign. : 1. X + 0 = X. 2. X 1 = X. Shann 2-19. Verification of Identities Verification of an identity: by truth table or verified identities : X + 0 = X X X+0. X = 0, X + 0 = 0 + 0 = 0 0 0+0=0.

7 X = 1, X + 0 = 1 + 0 = 1 1 1+0=1. : DeMorgan's theorem (X + Y) = X Y . Shann 2-20. General DeMorgan's Theorem DeMorgan's theorem: X + Y = X Y. X Y = X + Y. General DeMorgan's theorem: X 1 + X 2 + .. + X n = X 1 X 2 .. X n X 1 X 2 .. X n = X 1 + X 2 + .. + X n Shann 2-21. B. Algebraic Manipulation Simplification of Boolean functions: Boolean algebra is a useful tool for simplifying digital ckts. : F = XYZ + XYZ + XZ. F = XYZ + XYZ + XZ. = XY ( Z + Z ) + XZ 14 : x( y + z ) = xy + xz = XY 1 + XZ 7: x + x =1. = XY + XZ 2 : x 1 = x Shann 2-22. Shann 2-23. Implementing Boolean Equations When a Boolean equation is implemented w/ logic gates: each term requires a gate each variable within the term designates an input to the gate literal: a single variable within a term that may or may not be complemented : F = XYZ + XYZ + XZ 3 terms & 8 literals 2 terms & 4 literals F = XY + XZ.

8 * Reduce # of terms, # of literals, or both in a Boolean expression is often possible to obtain a simpler ckt Shann 2-24. Reducing Expressions by Boolean Algebra Boolean algebra may be applied to reduce an expression for obtaining a simpler ckt: Computer tools for synthesizing logic ckt Manual method: cut-and-try : 1. X + XY = X (1 + Y ) = X. 2. XY + XY = X (Y + Y ) = X. 3. X + XY = ( X + X )( X + Y ) = X + Y. dual 4. X ( X + Y ) = X + XY = X. 5. ( X + Y )( X + Y ) = X + YY = X. 6. X ( X + Y ) = XX + XY = XY Shann 2-25. Consensus Theorem xy + x z + yz = xy + x z (x + y) (x + z) (y + z) = (x + y) (x + z). xy + x z + yz = xy + x z + yz(x + x ). = xy + x z + xyz + x yz = xy + xyz + x z + x yz = xy (1 + z) + x z (1 + y). = xy + x z can be used to eliminate redundant terms from Boolean expressions. * Venn diagram Shann 2-26.

9 : Simplify the expression ( ). F = x y z + y z + w x y z + w x y + w x y z . = x + y z Shann 2-27. C. Complement of a Function Complement of a function F: interchange of 1's to 0's and 0's to 1's for the values of F. in the truth table can be derived algebraically by applying DeMorgan's theorem interchange AND and OR ops and complement each variable and constant take the dual of the function equation and complement each literal Shann 2-28. Examples Complementing functions by applying DeMorgan's theorem: : F1 = XYZ + XY Z F1 = ( XYZ + XY Z ) . = ( XYZ ) ( XY Z ) . = (X +Y + Z) (X +Y + Z ). F2 = X (Y Z + YZ ) F2 = ( X (Y Z + YZ )) . = X + (Y Z + YZ ) . = X + (Y Z ) (YZ ) . = X + (Y + Z ) (Y + ) Shann 2-29. Complementing functions by using duals: : F1 = XYZ + XY Z. dual of F1 ( X + Y + Z ) ( X + Y + Z ). complement each literal ( X + Y + Z ) ( X + Y + Z ).

10 = F1. F2 = X (Y Z + YZ ). dual of F2 X + (Y + Z ) (Y + Z ). complement each literal X + (Y + Z ) (Y + Z ). = F2 Shann 2-30. 2-3 Standard Forms Standard forms: Contain product terms & sum terms Two types: sum-of-products form product-of-sums form Product term: a logical product consisting of an AND op among literals : XY Z. Sum terms a logical sum consisting of an OR op among literals : X+Y+Z . Shann 2-31. A. Minterms and Maxterms Minterm: mj a product term in which all the variables appear exactly once, either complemented or uncomplemented represents exactly one combination of the binary variables in a truth table has the value 1 for that combination and 0 for all others There are 2n distinct minterms for n variables. Symbol: mj, j: denotes the decimal equivalent of the binary combination for which the minterm has the value 1.