Lecture 5: Boolean Expressions (Combinational Logic Gates)

Lecture 5 Chapter 3 Combinational Logic Gates_2 3.6 Standard Forms of Boolean Expressions The Sum-of-Products (SOP) Form 10/30/2024 When two or more product terms are summed by Boolean...

Lecture 5 Chapter 3 Combinational Logic Gates_2 3.6 Standard Forms of Boolean Expressions The Sum-of-Products (SOP) Form 10/30/2024 When two or more product terms are summed by Boolean addition, the resulting expression is a sum-of-products (SOP). Some examples are AB + ABC ABC + CDE + 𝐵ത C𝐷 ഥ Digital Circuit and Systems BEDC 202 𝐴ҧ B + 𝐴ҧ B𝐶ҧ + AC SOP expression can have the term 𝐴ҧ 𝐵ത 𝐶ҧ but not 𝐴 𝐵 𝐶. AND/OR Implementation of an SOP NAND/NAND Implementation of an Expression SOP Expression SOP expression can be implemented by The NAND and negative-OR AND-OR logic in which the outputs of a inversions cancel and the result is effectively number of AND gates connect to the inputs of an OR gate an AND/OR circuit. 1  Lec 5 _Chapter 3 Combinational Logic Gates_2 Conversion of a General Expression to SOP Form Any logic expression can be changed into SOP form by applying Boolean algebra techniques. A (B + CD) = AB + ACD 10/30/2024 Example 3.10 Convert each of the following Boolean expressions to SOP form: Digital Circuit and Systems BEDC 202 (a) AB+ B(CD + EF) (b) (A + B)(B + C + D) (c) 𝐴 + 𝐵 + 𝐶 Solution (a) AB + B(CD + EF) = AB + BCD + BEF (b) (A + B)(B + C + D) = AB + AC + AD + BB + BC + BD (c) 𝐴 + 𝐵 + 𝐶 = 𝐴 + 𝐵 𝐶ҧ = A𝐶ҧ + B𝐶ҧ 2 Lec 5 _Chapter 3 Combinational Logic Gates_2 The Standard SOP Form The expression 𝐴ҧB𝐶ҧ + A𝐵ത D + 𝐴ҧB𝐶ҧ D has a domain made up of the 10/30/2024 variables A, B, C, and D. However, notice that the complete set of variables in the domain is not represented in the first two terms of the Digital Circuit and Systems BEDC 202 ഥ is missing from the first term and C or 𝐶ҧ is expression; that is, D or 𝐷 missing from the second term. A standard SOP expression is one in which all the variables in the domain appear in each product term in the expression. For example, A𝐵ത CD + 𝐴ҧ𝐵ത C 𝐷 ഥ + AB𝐶ҧ 𝐷 ഥ is a standard SOP expression. Converting Product Terms to Standard SOP As stated in the following steps, a nonstandard SOP expression is converted into standard form using Boolean algebra rule 6 (A + 𝐴ҧ = 1) 3 A variable added to its complement equals 1.  Lec 5 _Chapter 3 Combinational Logic Gates_2 The Standard SOP Form Example 3.11 Convert the following Boolean expression into standard SOP form: 10/30/2024 A𝐵ത C + 𝐴ҧ𝐵ത + AB𝐶ҧ D Solution The domain of this SOP expression is A, B, C, D. The first term, A𝐵ത C, is missing Digital Circuit and Systems BEDC 202 ഥ so multiply the first term by D + 𝐷 variable D or 𝐷, ഥ as follows: A𝐵ത C = A𝐵ത C (D + 𝐷) ഥ = A𝐵ത CD + A𝐵ത C𝐷 ഥ The second term, 𝐴ҧ𝐵,ത is missing variables C or 𝐶ҧ and D or 𝐷, ഥ so first multiply the second term by C + 𝐶ҧ as follows: 𝐴ҧ𝐵ത = 𝐴ҧ𝐵ത (C+𝐶)ҧ = 𝐴ҧ𝐵ത C + 𝐴ҧ𝐵ത 𝐶ҧ The two resulting terms are missing variable D or 𝐷, ഥ so multiply both terms by D +𝐷ഥ as follows: 𝐴ҧ𝐵ത = 𝐴ҧ𝐵ത C + 𝐴ҧ𝐵ത 𝐶ҧ = 𝐴ҧ𝐵ത C (D +𝐷 ഥ ) + 𝐴ҧ𝐵ത 𝐶ҧ (D +𝐷) ഥ = 𝐴ҧ𝐵ത CD + 𝐴ҧ𝐵ത C𝐷 ഥ + 𝐴ҧ𝐵ത 𝐶ҧ D + 𝐴ҧ𝐵ത 𝐶ҧ 𝐷 ഥ The third term, AB𝐶ҧ D, is already in standard form. The complete standard SOP form of the original expression is as follows: 4 A𝐵ത C + 𝐴ҧ𝐵ത + AB𝐶ҧ D = A𝐵ത CD + A𝐵ത C𝐷 ഥ + 𝐴ҧ𝐵ത CD + 𝐴ҧ𝐵ത C𝐷 ഥ + 𝐴ҧ𝐵ത 𝐶ҧ D + 𝐴ҧ𝐵ത 𝐶ҧ 𝐷 ഥ+ AB𝐶ҧ D Lec 5 _Chapter 3 Combinational Logic Gates_2 The Product-of-Sums (POS) Form When two or more sum terms are multiplied, the resulting expression is a product-of-sums (POS). Some examples are 10/30/2024 (𝐴ҧ + B)(A + 𝐵ത + C) (𝐴ҧ + 𝐵ത + 𝐶)( ҧ C+𝐷 ഥ + E)( 𝐵ത + C + D) (A + B)(A + 𝐵ത + C)( 𝐴ҧ + C) Digital Circuit and Systems BEDC 202 A POS expression can contain a single-variable term, as in 𝐴ҧ (A + 𝐵ത + C) ( 𝐵ത + 𝐶ҧ + D). In a POS expression, a single overbar cannot extend over more than one variable; however, more than one variable in a term can have an overbar. For example, a POS expression can have the term 𝐴ҧ + 𝐵ത + 𝐶ҧ but not 𝐴 + 𝐵 + 𝐶. Implementation of a POS Expression Implementing a POS expression simply requires ANDing the outputs of two or more OR gates. A sum term is produced by an OR operation, and the product of two or more sum terms is produced by an AND operation. (A + B) 5 (B + C + D) (A + C).  Lec 5 _Chapter 3 Combinational Logic Gates_2 3.7 Karnaugh Map SOP Minimization Karnaugh map is used for simplifying Boolean expressions to their minimum form. 10/30/2024 Mapping a Standard SOP Expression For an SOP expression in standard form, a 1 is placed on the Karnaugh map for each product term in the expression. Each 1 is placed in a cell corresponding to the value of a product term. For example, for the product term A𝐵ത C, a 1 goes in the 101 Digital Circuit and Systems BEDC 202 cell on a 3-variable map. The cells that do not have a 1 are the cells for which the expression is 0. Usually, when working with SOP expressions, the 0s are left off the map. Step 1: Determine the binary value of each product term in the standard SOP expression. After some practice, you can usually do the evaluation of terms mentally. Step 2: As each product term is evaluated, place a 1 on the Karnaugh map in the cell having the same value as the product term. 6 Lec 5 _Chapter 3 Combinational Logic Gates_2 3.7 Karnaugh Map SOP Minimization Karnaugh map is used for simplifying Boolean expressions to their minimum form. 10/30/2024 Example 3.12 Map the following standard SOP expression on a Karnaugh map: ABC + ABC + ABC + ABC Digital Circuit and Systems BEDC 202 Solution Place a 1 on the 3-variable Karnaugh map for each standard product term in the expression. ABC + ABC + ABC + ABC 001 010 110 111 7 Lec 5 _Chapter 3 Combinational Logic Gates_2 3.7 Karnaugh Map SOP Minimization Example 3.13 10/30/2024 Map the following standard SOP expression on a Karnaugh map: 𝐴ҧ𝐵ത CD + 𝐴ҧB𝐶ҧ 𝐷 ഥ + AB𝐶ҧ D + ABCD + AB𝐶ҧ 𝐷ഥ + 𝐴ҧ𝐵ത 𝐶ҧ D + A𝐵ത C𝐷 ഥ Solution Place a 1 on the 4-variable Karnaugh map for each standard product term in Digital Circuit and Systems BEDC 202 the expression. 𝐴ҧ𝐵ത CD + 𝐴ҧB𝐶ҧ 𝐷 ഥ + AB𝐶ҧ D + ABCD + AB𝐶ҧ 𝐷 ഥ + 𝐴ҧ𝐵ത 𝐶ҧ D + A𝐵ത C𝐷 ഥ 0011 0100 1101 1111 1100 0001 1010 8  Lec 5 _Chapter 3 Combinational Logic Gates_2 Mapping a Nonstandard SOP Expression A Boolean expression must first be in standard form before you use a Karnaugh map. 10/30/2024 Example 3.14 Map the following SOP expression on a Karnaugh map: 𝐴ҧ + A𝐵ത + AB𝐶ҧ. Digital Circuit and Systems BEDC 202 Solution The SOP expression is obviously not in standard form because each product term does not have three variables. The first term is missing two variables, the second term is missing one variable, and the third term is standard. First expand the terms numerically as follows: 𝐴ҧ + A𝐵ത + AB𝐶ҧ 000 100 110 001 101 010 011 9 Lec 5 _Chapter 3 Combinational Logic Gates_2 Mapping a Nonstandard SOP Expression Example 3.15 Map the following SOP expression on a Karnaugh map: 10/30/2024 𝐵ത 𝐶ҧ + A𝐵ഥ + AB𝐶ҧ + A𝐵ത C𝐷 ഥ + 𝐴ҧ𝐵ത 𝐶ҧ D + A𝐵ത CD Solution The SOP expression is obviously not in standard form because each product Digital Circuit and Systems BEDC 202 term does not have four variables. The first and second terms are both missing two variables, the third term is missing one variable, and the rest of the terms are standard. First expand the terms by including all combinations of the missing variables numerically as follows: 𝐵ത 𝐶ҧ + A𝐵ഥ + AB𝐶ҧ + A𝐵ത C𝐷 ഥ + 𝐴ҧ𝐵ത 𝐶ҧ D + A𝐵ത CD 0000 1000 1100 1010 0001 1011 1001 1101 10 0 0 01 1 0 1 0 1 0 0 10 1 0 1 10 1001 1011 10  Lec 5 _Chapter 3 Combinational Logic Gates_2 Karnaugh Map Simplification of SOP Expressions The process that results in an expression containing the fewest possible terms 10/30/2024 with the fewest possible variables is called minimization. After an SOP expression has been mapped, a minimum SOP expression is obtained by grouping the 1s and determining the minimum SOP expression from the map. Digital Circuit and Systems BEDC 202 Grouping the 1s You can group 1s on the Karnaugh map according to the following rules by enclosing those adjacent cells containing 1s. The goal is to maximize the size of the groups and to minimize the number of groups. 1. A group must contain either 1, 2, 4, 8, or 16 cells, which are all powers of two. In the case of a 3-variable map, 23 = 8 cells is the maximum group. 2. Each cell in a group must be adjacent to one or more cells in that same group, but all cells in the group do not have to be adjacent to each other. 3. Always include the largest possible number of 1s in a group in accordance with rule 1. 4. Each 1 on the map must be included in at least one group. The 1s already in a 11 group can be included in another group as long as the overlapping groups include noncommon 1s. Lec 5 _Chapter 3 Combinational Logic Gates_2 Karnaugh Map Simplification of SOP Expressions Example 3.16 Group the 1s in each of the Karnaugh maps in Figure 10/30/2024 Digital Circuit and Systems BEDC 202 Solution The groupings are shown. In some cases, there may be more than one way to group the 1s to form maximum groupings. 12 Lec 5 _Chapter 3 Combinational Logic Gates_2 Karnaugh Map Simplification of SOP Expressions Example 3.17 10/30/2024 Determine the product terms for the Karnaugh map in Figure and write the resulting minimum SOP expression. Digital Circuit and Systems BEDC 202 Solution The product term for the 8-cell group is B because the cells within that group contain both A and 𝐴,ҧ C and 𝐶,ҧ and D and 𝐷 ഥ , which are eliminated. ത D, and 𝐷, The 4-cell group contains B, 𝐵, ഥ leaving the variables 𝐴ҧ and C, which form the product term 𝐴ҧ C. The 2-cell group contains B and 𝐵ത , leaving variables A, 𝐶,ҧ and D which form the product term A𝐶ҧ D. Notice how overlapping is used to maximize the size of the groups. The resulting minimum SOP expression is the sum of these product terms: 13 B + 𝐴ҧC + A𝐶ҧ D Lec 5 _Chapter 3 Combinational Logic Gates_2 Karnaugh Map Simplification of SOP Expressions Example 3.17 10/30/2024 Determine the product terms for the Karnaugh map in Figure and write the resulting minimum SOP expression. Digital Circuit and Systems BEDC 202 Solution The minimum SOP expressions for each of the Karnaugh maps in the figure are (a) AB + BC + 𝐴ҧ𝐵ത 𝐶ҧ (b) 𝐵ത + 𝐴ҧ𝐶ҧ + AC (c) 𝐴ҧB + 𝐴ҧ𝐶ҧ + A𝐵ത D 14 (d) 𝐷ഥ + A𝐵ത C + B𝐶ҧ  Lec 5 _Chapter 3 Combinational Logic Gates_2 Karnaugh Map Simplification of SOP Expressions Example 3.19 10/30/2024 Use a Karnaugh map to minimize the following SOP expression: 𝐵ത 𝐶ҧ 𝐷 ҧ 𝐶ҧ 𝐷 ഥ +𝐴𝐵 ഥ +AB𝐶ҧ 𝐷 ഥ +𝐴ҧ𝐵𝐶𝐷 ത ത +𝐴𝐵𝐶𝐷 +𝐴ҧ𝐵𝐶 ത 𝐷 ҧ 𝐷 ഥ + 𝐴𝐵𝐶 ഥ + AB𝐶 𝐷 ഥ +𝐴𝐵𝐶 ത 𝐷 ഥ Digital Circuit and Systems BEDC 202 Solution The first term 𝐵ത 𝐶ҧ 𝐷 ഥ must be expanded into A𝐵ത 𝐶ҧ 𝐷 ഥ and 𝐴ҧ𝐵ത 𝐶ҧ 𝐷 ഥ to get the standard SOP expression, which is then mapped; the cells are grouped as shown in Figure Notice that both groups exhibit “wrap around” adjacency. The group of eight is formed because the cells in the outer columns are adjacent. The group of four is formed to pick up the remaining two 1s because the top and bottom cells are adjacent. The product term for each group is shown. The resulting minimum SOP expression is 15 ഥ 𝐵ത C 𝐷+ Lec 5 _Chapter 3 Combinational Logic Gates_2 Karnaugh Map Simplification of SOP Expressions Mapping Directly from a Truth Table Recall that a truth table gives the output of a Boolean expression for all 10/30/2024 possible input variable combinations. An example of a Boolean expression and its truth table representation is shown. Notice in the truth table that the output X is 1 for four different input variable combinations. Digital Circuit and Systems BEDC 202 “Don’t Care” Conditions Sometimes a situation arises in which some input variable combinations are not allowed. For example, recall that in the BCD code, there are six invalid combinations: 1010, 1011, 1100, 1101, 1110, and 1111. Since these un allowed states will never occur in an application involving the BCD code, they can be treated as “don’t care” terms with respect to their effect on the output. That is, for these 16 “don’t care” terms either a 1 or a 0 may be assigned to the output.  Lec 5 _Chapter 3 Combinational Logic Gates_2 Karnaugh Map Simplification of SOP Expressions The “don’t care” terms can be used to advantage on the Karnaugh map. For each “don’t care” term, an X is placed in the cell. When grouping the 1s, the Xs 10/30/2024 can be treated as 1s to make a larger grouping or as 0s if they cannot be used to advantage. The larger a group, the simpler the resulting term will be. Digital Circuit and Systems BEDC 202 17 (a) Truth table (b) Without “don’t cares” Y = A𝐵ത 𝐶ҧ + 𝐴ҧBCD With “don’t cares” Y = A + BCD  Lec 5 _Chapter 3 Combinational Logic Gates_2 Karnaugh Map Simplification of SOP Expressions Example 3.20 In a 7-segment display, each of the seven segments is activated for various 10/30/2024 digits. For example, segment a is activated for the digits 0, 2, 3, 5, 6, 7, 8, and 9, as illustrated in Figure. Since each digit can be represented by a BCD code, derive an SOP expression for segment a using the variables ABCD and then minimize the Digital Circuit and Systems BEDC 202 expression using a Karnaugh map. Solution The expression for segment a is a =𝐴ҧ𝐵ത 𝐶ҧ 𝐷 ഥ +𝐴ҧ𝐵𝐶 ഥ 𝐴ҧ𝐵ത CD +𝐴𝐵 ത 𝐷+ ҧ 𝐶𝐷 ҧ +𝐴𝐵𝐶 ҧ 𝐷 ഥ +𝐴ҧBCD +𝐴𝐵ത 𝐶ҧ 𝐷+𝐴 ഥ 𝐵ത 𝐶𝐷ҧ Each term in the expression represents one of the digits in which segment a is used. The Karnaugh map minimization is shown. X’s (don’t cares) are entered for those states that do not occur in the BCD code. 18 The minimized expression for segment a is a = A + C + BD + 𝐵ത 𝐷ഥ  Lec 5 _Chapter 3 Combinational Logic Gates_2 3.8 Karnaugh Map POS Minimization The approaches are much the same except that with POS expressions, 0s representing the standard sum terms are placed on the Karnaugh map instead of 1s. 10/30/2024 Mapping a Standard POS Expression For a POS expression in standard form, a 0 is placed on the Karnaugh map for each sum term in the expression. For example, for the sum term A + 𝐵ത + C, a 0 Digital Circuit and Systems BEDC 202 goes in the 010 cell on a 3-variable map. There will be a number of 0s on the Karnaugh map equal to the number of sum terms in the standard POS expression. The cells that do not have a 0 are the cells for which the expression is 1. Step 1: Determine the binary value of each sum term in the standard POS expression. This is the binary value that makes the term equal to 0. Step 2: As each sum term is evaluated, place a 0 on the Karnaugh map in 19 the corresponding cell. Lec 5 _Chapter 3 Combinational Logic Gates_2 3.8 Karnaugh Map POS Minimization Example 3.21 Map the following standard POS expression on a Karnaugh map: 10/30/2024 (𝐴ҧ +𝐵ത +C +D) (𝐴ҧ +B +𝐶ҧ +𝐷 ഥ ) (A +B +𝐶ҧ +D) (𝐴ҧ +𝐵ത +𝐶ҧ +𝐷 ഥ ) (A +B +𝐶ҧ +𝐷 ഥ) Solution Digital Circuit and Systems BEDC 202 Evaluate the expression as shown below and place a 0 on the 4-variable Karnaugh map for each standard sum term in the expression. (𝐴ҧ +𝐵ത +C +D) (𝐴ҧ +B +𝐶ҧ +𝐷) ഥ (A +B +𝐶ҧ +D) (𝐴ҧ +𝐵ത +𝐶ҧ +𝐷) ഥ (A +B +𝐶ҧ +𝐷 ഥ) 1100 1011 0010 1111 0011 20 Lec 5 _Chapter 3 Combinational Logic Gates_2 Karnaugh Map Simplification of POS Expressions The process for minimizing a POS expression is basically the same as for an SOP expression except that you group 0s to produce minimum sum terms instead of grouping 1s to 10/30/2024 produce minimum product terms. Example 3.22 Use a Karnaugh map to minimize the following standard POS expression: (A + B + C)(A + B + 𝐶ҧ )(A + 𝐵ത + C)(A + 𝐵ത + 𝐶ҧ )(𝐴ҧ + 𝐵ത + C) Digital Circuit and Systems BEDC 202 Also, derive the equivalent SOP expression. Solution The combinations of binary values of the expression are (0 + 0 + 0)(0 + 0 + 1)(0 + 1 + 0)(0 + 1 + 1)(1 + 1 + 0) Map the standard POS expression and group the cells as: Notice how the 0 in the 110 cell is included into a 2-cell group by utilizing the 0 in the 4-cell group. The sum term for each blue group is shown the resulting minimum POS expression is A (𝐵ത + C) Keep in mind that this minimum POS expression is equivalent to the original standard POS expression. Grouping the 1s as shown by the gray areas yields an SOP expression that is equivalent to grouping the 0s. 21 AC + A𝐵ത = A (𝐵ത + C)  Lec 5 _Chapter 3 Combinational Logic Gates_2 Karnaugh Map Simplification of POS Expressions Example 3.23 Use a Karnaugh map to minimize the following POS expression: 10/30/2024 (B +C +D) (A +B +𝐶ҧ +D) (𝐴ҧ +B +C +𝐷 ഥ ) (A +𝐵ത +C +D) (𝐴ҧ +𝐵ത +C +D) Solution Digital Circuit and Systems BEDC 202 The first term must be expanded into 𝐴+ҧ B + C + D and A + B + C + D to get a standard POS expression, which is then mapped; and the cells are grouped as shown in Figure. The sum term for each group is shown and the resulting minimum POS expression is (C + D) (A + B + D) (𝐴ҧ + B + C) Keep in mind that this minimum POS expression is equivalent to the original standard POS expression. 22 10/30/2024 Digital Circuit and Systems BEDC 202 23