Boolean Algebra and Logic Simplification

Presentation on theme: "Boolean Algebra and Logic Simplification"— Presentation transcript:

1 Boolean Algebra and Logic Simplification
重点 1

2 Contents Boolean Operations and Expressions
Law and Rules of Boolean Algebra DeMorgan’s Theorems Boolean Analysis of Logic Circuits Simplification Using Boolean Algebra Standard Forms of Boolean Expressions Boolean Expressions and Truth Tables The Karnaugh Map Karnaugh Map SOP Minimization 2

3 4-4 Boolean Analysis of Logic Circuits （逻辑电路分析）
To derive the Boolean expression for a given combinational logic circuit , begin at the left-most inputs and work toward the final output , writing the expression for each gate. 2.Boolean Expression X=A(B+CD) 3

4 4-4 Boolean Analysis of Logic Circuits
3. Truth Table （真值表） Constructing the truth table from a logic expression. (1) Determine the number of the input and output variables, and the number of the input variable possible combinations. (2) Draw the truth table frame according to the input and output variables. 4

5 4-4 Boolean Analysis of Logic Circuits
(3) List all of the input variable combinations of 1s and 0s in a binary sequence (按序）. (4) Fill the truth table. If the input variable combinations make the output 1, then place a 1 in the corresponding output column, otherwise place a 0. 5

6 4-4 Boolean Analysis of Logic Circuits
Ex. X=A(B+CD) 6

7 4-4 Boolean Analysis of Logic Circuits 4-7 Boolean Expressions and Truth Table
Determining logic expressions from a truth table List the binary values of the input variables for which the output is 1. Convert each binary value to the corresponding product term （积的形式） by replacing each 1 with the corresponding variable and each 0 with the complement. Get the logic expression by summing all the combinations. 7

8 4-7 Boolean Expressions and Truth Table
Ex. Truth Table A B C F  List the binary values where the outputs are “1”  Convert each binary value to the corresponding product  summing all the combinations. 总结：逻辑图 逻辑表达式 真值表 8

9 引出本章的核心问题 通过写出两个逻辑图的表达式和真值表，逻辑功能一样，但结构复杂程度不同，引出化简的好处。 9

10 4-1 Boolean Operations and Expressions
Boolean algebra (布尔代数） is the mathematics of digital systems. Sum term （和的形式）: is a sum of literals (文字) ( a variable or the complement of a variable), produced by an OR gate. A sum term is equal to 1 when one or more of the literals in the term are 1. A sum term is equal to 0 only if each of the literals is 0. 10

11 4-1 Boolean Operations and Expressions
Product term （积的形式）: is the product of literals, produced by an AND gate. A product term is equal to 1 only if each of the literals in the term is 1. A product term is equal to 0 when one or more of the literals are 0. Ex. Only if A=0,C=1, and D=0, then X=1. 11

12 4-2 Laws and Rules of Boolean Algebra 4-2-1 Laws of Boolean Algebra (布尔代数常用公式）
Commutative laws (交换律）for addition and multiplication A+B=B+A; AB=BA Associative laws (结合律） A+(B+C)=(A+B)+C A(BC)=(AB)C Distributive Law (分配律） A(B+C)=AB+AC 12

13 4-2-2 Rules of Boolean Algebra (基本公式）
A variable ORed with 0 is always equal to the variable. A 1 2. A+1= A variable ORed with 1 is always equal to 1. 3. A·0= A variable ANDed with 0 is always equal to 0. A 4. A·1= A variable ANDed with 1 is always equal to the variable. 13

14 4-2-2 Rules of Boolean Algebra
5. A+A= （A+A+A+A+…=A) A variable ORed with itself is always equal to the variable. 6. A·A= (AAA…=A) A variable ANDed with itself is always equal to the variable. A 14

15 4-2-2 Rules of Boolean Algebra
7. A variable ORed with its complement is always equal to 1. 1 8. A variable ANDed with its complement is always equal to 0. 15

16 4-2-2 Rules of Boolean Algebra
9. The double complement of a variable is always equal to the variable. A 10. A+AB= （用真值表证明左右式等价） A 16

17 4-2-2 Rules of Boolean Algebra
11. (A+B)(A+C)=A+BC 注意：根据公式特点进行记忆。 17

18 4-2-2 Rules of Boolean Algebra
X X X X 18

19 4-2-2 Rules of Boolean Algebra
总结 1.用真值表证明等式成立的好方法。 2.以上公式反映了逻辑关系，而不是数量之间的关系。所以，在运算中不能简单套用初等代数的运算规则。 19

20 4-3 Demorgan’s theorem （摩根定理）
The complement of two or more ANDed variables is equivalent to the OR of the complements of the individual variables. 20

21 4-3 Demorgan’s theorem （摩根定理）
The complement of two or more ORed variables is equivalent to the AND of the complements of the individual variables. 21

22 4-3 Demorgan’s theorem （摩根定理） Basic Theorems（基本规则）——补充康华光P41
1. Replacement theorem (代入规则） Any variable in laws or rules of Boolean expressions can also be replaced with a combination of other variables or combinations. ACDE 22

23 4-3 Demorgan’s theorem （摩根定理） Basic Theorems（补充）
2.Inversion Theorem（反演规则） For a given expression X, if 01，10，+，+, AA, AA then (反函数/非函数)got.  X   23

24 4-3 Demorgan’s theorem （摩根定理） Basic Theorems（补充）
Procedure: Step 1: Replace OR with AND, AND with OR; Step 2: Complement each literal. 注意：1.运算优先顺序。括号与或 2.反变量以外的非号应保留不变。 24

25 4-3 Demorgan’s theorem （摩根定理） Basic Theorems（补充）
3. Duality theorem （对偶规则） 01，10，+，+  X  X’ then X’ (对偶式/对偶函数) got For a given expression X, if If X=Y, then X’=Y’ 注意：运算优先顺序。括号与或 思考：反函数和对偶函数之间的关系？ 25

26 4-5 Simplification Using Boolean Algebra
The SOP Form(Sum-of-Products) —与或式 The expression is a sum of two or more products of literals. 最简与或表达式（乘积项最少，且每个乘积项中的变量也最少） 2. The POS Form (Product-of-Sums) ---或与式 The expression is a product of two or more sums of literals. 最简或与表达式（括号最少，且每个括号内相或的变量也最少） 26

27 4-5 Simplification Using Boolean Algebra
3.最简与非-与非表达式（非号最少，且非号下面乘积项中的变量也最少） 4.最简或非-或非表达式（非号最少，且非号下面相或的变量也最少) 5.最简与或非表达式（非号下面相或的乘积项最少，且每个乘积项中的变量也最少) 27

28 4-5 Simplification Using Boolean Algebra
When you design a circuit by a Boolean expression, you have to reduce the expression to the simplest form (for a SOP term(与或式), the fewest sums and the fewest variables per sum) to make the circuit simple and easy to be implemented. Boolean Algebra（公式法） Map（卡诺图法） Simplification method 28

29 4-5 Simplification Using Boolean Algebra
The approach is to use the basic laws, rules and theorems of Boolean algebra to process and simplify an expression. This method depends on a thorough knowledge of Boolean algebra and considerable practice in its application. 29

30 4-5 Simplification Using Boolean Algebra
Ex. Y=ABC+ABD+ABC+CD+BD Y=ABC+ABC+CD+B(AD+D) = ABC+ABC+CD+B(A+D) = ABC+ABC+CD+BA+BD =AB +ABC+CD+BD =B(A+AC)+CD+BD =B(A+C)+CD+BD =BA+BC+CD+BD =BA+B(C+D)+CD =BA+BCD+CD =BA+B+CD =B(A+1)+CD =B+CD 30

31 4-5 Simplification Using Boolean Algebra
EX. As you have seen, the effectiveness of algebraic simplification depends on your familiarity with all the laws, rules, and theorems of Boolean algebra and on your ability to apply them. 公式法的缺点： 不方便不直观，且难以判断结果是否最简。一般适用于表达式较简单的情况。 31

32 最简表达式的形式变换(中文P43） 总结：只要有最简与或表达式，再根据摩根定理进行适当的变换，就可以得到其他几种最简表达式。

33 进行变换，仅用或非门画出该表达式的逻辑图。
中文P45 例 试对逻辑函数表达式 进行变换，仅用或非门画出该表达式的逻辑图。 解： 如同非门

34 4-6 Standard Forms of Boolean Expressions
1. Minterm (最小项） 定义、编号及性质 a.定义：是所有输入变量的乘积，每个变量都以它原变量或反变量的形式出现，且仅出现一次。n个输入变量可组成2n个最小项。 b.编号 表示： 例A、B、C三个逻辑变量的最小项有（23＝）8个，即 、 34

35 4-6 Standard Forms of Boolean Expressions
c.性质：见康书P46-47 2. The Standard SOP Form (标准与或式/最小项表达式） 即： 一个逻辑函数可以表示为一组最小项的和。 注意：表达式形式多样，但最小项表达式有且只有1个 35

36 4-6 Standard Forms of Boolean Expressions
Any nonstandard (非标准的，也即不是最小项) SOP expression can be converted to the standard form . 方法1：配项法——using the equation Multiply each nonstandard product term by a term made up of the sum of a missing variable and its complement (缺的变量及其反变量). Get the standard SOP form by using the distributive rules. 36

37 4-6 Standard Forms of Boolean Expressions
Lack of variables C and D and their complements Lack of variable A and its complement 注意：最小项表达式有且只有1个。 37

38 4-6 Standard Forms of Boolean Expressions
方法2：真值表法（Truth Table) (前面已讲) 思考:根据真值表特点（利用反函数）求原函数? 方法：当真值表中函数值为0的个数明显多于1时，可先写出其反函数，再利用反函数取反求出其原函数。 38

39 4-8 The Karnaugh Map – K Map （卡诺图）
A K-map is similar to a truth table because it presents all of the possible values of input variables and the resulting output for each combination. Instead of being organized into columns（列） and rows（行） like a truth table, the K-map is an array of CELLS (单元) in which each cell represents a minterm of the input variables. 即：把最小项排列成矩阵形式，并且在矩阵的横方向和纵方向上逻辑变量的取值都按照格雷码的顺序排列，这样构成的图形称为~。 39

40 4-8 The Karnaugh Map – K-Map
The cells are arranged in a way so that simplification of a given expression is simply a matter of properly grouping the cells (对单元分组，圈圈). The number of cells (2n) in a K-map is equal to the total number of possible input variable (n) combinations. K-map can be used for expressions with 2,3,4 and 5 variables, but only K-map of 3-variable and 4-variable are often used. 40

41 4-8 The Karnaugh Map - 3-Variable K-Map
Notice the sequence 11 and 10 exchange position A BC 0 1 The standard product term ABC ABC ABC ABC ABC ABC ABC ABC The value of a given cell is the decimal digit of A at the left in the same row combined with B and C at the top in the same column. 注意：有两种卡诺图形式。 41

42 4-8 The Karnaugh Map - 4-Variable K-Map
AB CD The 4-variable K-map is an array of sixteen cells. Binary values of A and B are along the left side and C and D are across the top. ABCD 00 01 11 10 注意：还有另外一种卡诺图形式(AB,CD交换位置）。 42

43 4-8 The Karnaugh Map – Cell Adjacency (逻辑相邻性)
补充：相邻最小项概念 Cell adjacency: cells that differ by only one variable are adjacent. Ex. 010 and 011 are cell adjacency, but 010 and 001 are not. （即：两个最小项中只有一个变量不同） The cells in a K-map are arranged so that there is only a single-variable change ( adjacency 相邻) between adjacent cells (相邻单元). (即：位置上相邻的两个单元一定是相邻最小项。n个变量的卡诺图中，任一个方格一定有n个相邻最小项。） 化简实质：合并了相邻最小项！ 43

44 4-8 The Karnaugh Map – Cell Adjacency
Wrap-around: In a K-map, the cell is adjacent to its four sides. Also the cells in the top row are adjacent to the corresponding cells in the bottom row. (最上一行与最下一行对应方格逻辑相邻) The cells in the outer left column are adjacent to the corresponding cells in the outer right column . (最左列与最右列对应方格逻辑相邻) 注意：四个角也逻辑相邻。 44

45 4-9 K-map SOP Minimization - Procedure of Simplification using K-map
Step 1 ：Draw the K-map 情况1（最直接）：由最小项表达式 卡诺图 For an SOP expression in standard form, a 1 is placed on the K-map for each product term in the expression. A 0 is placed for the cells that aren’t included in the expression. Usually, the 0s are left off the map. (表达式中含有的最小项在卡诺图中填入1，不含有的填入0，通常，0会被省略，而不填入图中） 45

46 4-9 K-map SOP Minimization - Procedure of Simplification using K-map
情况2：有真值表 卡诺图 A B C F A BC 1 46

47 4-9 K-map SOP Minimization - Procedure of Simplification using K-map
情况3（最复杂）： 由一般表达式 与或式 最小项表达式 卡诺图 EX. 注意：最小项的快捷表示方法 47

48 Step 2. Rules of Combining Minterms （合并相邻最小项原则）——Grouping the 1s. (画圈）
4-9 K-map SOP Minimization - Procedure of Simplification using K-map （见英文P140） Step 2. Rules of Combining Minterms （合并相邻最小项原则）——Grouping the 1s. (画圈） A group must contain either 1,2,4,8, or 16 (2n) cells , which are all powers of two. (把方格为1的相邻最小项圈起来，圈内的方格数必定是2n个,n等于0、1、2、3···） 2. Always include the largest possible number of 1s in a group. The larger a group, the simpler the resulting term will be . (圈要尽量地大,圈的个数应尽量少） 48

49 4-9 K-map SOP Minimization - Procedure of Simplification using K-map
3. Each 1 on the map must be included in at least one group. The 1s already in a group can be included in another group as long as the overlapping groups include non-common 1s. (同一方格可以被不同的包围圈重复包围，但新增包围圈中一定要有新的方格，否则该包围圈为多余。）. 49

50 4-9 K-map SOP Minimization - Procedure of Simplification using K-map
4. Determining the product term for each group. Each group of cells containing 1s creates one product term composed of all variables that occur in only one form(either uncomplemented or complemented) within the group . Variables that occur both uncomplemented and complemented within the group are canceled . （写出每个圈对应的与项/乘积项） 5. Summing the resulting product terms. （将所有的乘积项相加） 50

51 4-9 K-map SOP Minimization——Examples
（1） A BC AC 1 1 1 1 1 AB 51

52 4-9 K-map SOP Minimization——Examples
（2） A BC 0 1 错误 52

53 4-9 K-map SOP Minimization——Examples
BC 0 1 AB CD 1 1 1 1 Y= BD 53

54 4-9 K-map SOP Minimization——Examples
（3）When the sum of 8 adjacent CELLS is formed, the 3 different variable can be removed, and only the same variables are left. AB CD 1 1 54

55 4-9 K-map SOP Minimization——Examples
AB CD AB CD Y=A 总结：一个包围圈圈中2n个方格，必定可以消掉n个变量。 55

56 4-9 K-map SOP Minimization - Example
Ex. Y(A,B,C,D) = m(0,2,3,5,6,8,9,10,11, 12,13,14,15) AB CD BD Notice： 1.Check whether there is any redundant group（冗余项）. 2.The sum form may be not unique. CD BCD A BC Ex:康书P (方法巧妙） 56

57 4-9 K-map SOP Minimization - “Don’t Care” Conditions
Sometimes a situation arises in which some input variable combinations are not allowed, or never appear. 实际中会经常遇到这样的问题，在真值表内对应于变量的某些取值下，函数的值可以是任意的，或者这些变量的取值根本不会出现，这些变量取值所对应的最小项称为无关项或任意项。 57

58 4-9 K-map SOP Minimization - “Don’t Care” Conditions
Ex. Recall that in the 8421 BCD code, there are six invalid combinations: 1010,1011,1100,1101,1110,1111. Since these unallowed 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 “don’t care” terms either a 1 or 0 may be assigned to the output; it really doesn’t matter since they will never occur. 58

59 4-9 K-map SOP Minimization - “Don’t Care” Conditions
Expression of Don’t Care Conditions In logic expression term, they can be represented as the following two terms. Y(A,B,C,D) = m(0,2,3,5,6,8)+ d(12,13,14,15) 59

60 4-9 K-map SOP Minimization - “Don’t Care” Conditions
You can express them with an X/ in the corresponding cells on the K-map. The “don’t care” terms can be used to advantage on the K-map. When grouping the 1s, the Xs can be treated as 1s to make a larger grouping or as 0s if they can’t be used to advantage. （无关项的值可以取0或1，具体取什么值，根据使函数尽量化简而定） 60

61 4-9 K-map SOP Minimization - “Don’t Care” Conditions
Ex:

62 ？ Ex: 总 结 1：卡诺图化简后的结果有时不唯一，但最简程度应一样。（举例）
2：卡诺图化简的好处;但当变量多于5个时，卡诺图就不是很直观了。 ？

63 Assignment 作业一 P156 -11(b) -13(c) P157 -21(e) 中间 空5行 作业二
P (c) 63