哈工大数字逻辑unit 2—逻辑代数

1、 Boolean Algebra张彦航张彦航School of Computer ScienceZUnit 2 Boolean Algebra布尔表达式和真值表布尔表达式和真值表逻辑代数定理及规则逻辑代数定理及规则各种逻辑运算各种逻辑运算代数化简法代数化简法n 基本逻辑运算基本逻辑运算（Basic Operations） 与与（AND） 或或（OR） 非非（NOT） n 复合逻辑运算复合逻辑运算（Other Operations）各种逻辑运算各种逻辑运算1. AND（逻辑逻辑“与与” ” ）F=AB 也称为：也称为： 逻辑逻辑“乘乘”Truth Table 基本运算基本运算（Basic Ope

2、rations） AND gate（与门）（与门） & Typical Chip: 74LS08ABF2. OR（逻辑（逻辑“或或”）F=A+B 也称为：逻辑也称为：逻辑“加加”AB F0 0 0 0 1 1 1 0 1 1 1 1 Truth Table基本运算基本运算（Basic Operations） OR gate（或门）（或门） Typical Chip: 74LS3211+ F=A 3. NOT（逻辑（逻辑“非非”）也称为：反相器也称为：反相器( or F=A)基本运算基本运算（Basic Operations） NOT gate（非门）（非门） Typical Chip:

3、 74LS04n 基本逻辑运算基本逻辑运算（Basic Operations） 与与（AND） 或或（OR） 非非（NOT） n 复合逻辑运算复合逻辑运算（Other Operations）复合运算复合运算（Other Operations）F= AB4. 与非门与非门（NAND gate）复合运算复合运算（Other Operations）n Typical Chip: 74LS00F= A+B5. 或非门或非门（NOR gate）n Typical Chip: 74LS02 复合运算复合运算（Other Operations）n Typical Chip: 74LS51,74LS556.

4、与或非门与或非门（AND-OR-NOT gate）+AB+CDF=复合运算复合运算（Other Operations）7. (Exclusive-OR operation )Truth TableAB=F=AB+AB =1复合运算复合运算（Other Operations） Typical Chip: 74LS86 Applicationsn 全加器（全加器（Full adder）n 半加器（半加器（Half-adder） 复合运算复合运算（Other Operations）8. 同或门同或门 (Equivalence operation )Truth Table=1 or复合运算复合运算（O

5、ther Operations） Typical Chip: 74LS266 Applicationsn 等值比较器等值比较器 复合运算复合运算（Other Operations） 性质性质 A 1 = A A 0 = AA A 0 = A 1 = A A A = 0 A A = 1 A = A1 A = A0复合运算复合运算（Other Operations）Applications复合运算复合运算（Other Operations）Unit 2 Boolean Algebra布尔表达式和真值表布尔表达式和真值表逻辑代数定理及规则逻辑代数定理及规则各种逻辑运算各种逻辑运算代数化简法代数化简法

6、1. 布尔表达式布尔表达式（Boolean Expressions）AB+AB F=Example nBoolean expressions are formed by application of the basic operations (and, or, not) to one or more variables or constants.F=A(C+D)+BE布尔表达式和真值表布尔表达式和真值表逻辑图逻辑图nEach expression corresponds directly to a circuit of logic gatesAB+AB F=Example 布尔表达式和真值表布

7、尔表达式和真值表2. 真值表真值表（Truth Table）nA truth table specifies the values of a Boolean expression for every possible combination of values of the variables in the expression.nn 个输入变量有个输入变量有 2n 种取值组合种取值组合AB+AB F=Example 布尔表达式和真值表布尔表达式和真值表n如果两个逻辑表达式的真值表相等，则这两个如果两个逻辑表达式的真值表相等，则这两个逻辑表达式相等逻辑表达式相等. .AB+C = (A+C)(

8、B+C)布尔表达式和真值表布尔表达式和真值表Unit 2 Boolean Algebra布尔表达式和真值表布尔表达式和真值表逻辑代数定理及规则逻辑代数定理及规则各种逻辑运算各种逻辑运算代数化简法代数化简法1. 公理公理（Axiom） 0 0 =0 0 1= 1 0 = 0 1 1= 1 =1 If A0 then A=10 0+0= 0 1+0 = 0+1=1 1+1 = 1 = 0 If A1 then A=0Laws and Theorems2. 基本定理基本定理（Basic Theorems）Laws and Theorems A 0= 0 A 1= A A = 0 A A = A A

9、A+0=A A+1=1 A+ =1 A+A = AA n single variable is involved2. 基本定理基本定理（Basic Theorems）01 律律重叠率重叠率ApplicationsLaws and Theorems A+B=B+A(A+B)+C=A+(B+C) A (B+C)= AB+AC A B= B A (A B) C= A (B C) A+BC=(A+B) (A+C)交换律交换律结合律结合律分配率分配率普通代数普通代数不支持不支持n 与普通代数相似的定理与普通代数相似的定理Laws and Theoremsn 特殊定理特殊定理摩根定理摩根定理（DeMorg

10、ans Laws）Laws and Theorems=+Applications: 表达式化简表达式化简Laws and Theoremsn 特殊定理特殊定理Applications: Algebraic Simplification变量变量: : 不变不变运算符运算符: :不能改变原不能改变原来的优先级来的优先级Laws and Theoremsn 特殊定理特殊定理对偶规则对偶规则Example F=A( B+C ) 对偶对偶对偶对偶 对偶对偶Laws and Theoremsn 特殊定理特殊定理 两个逻辑表达式相等，它们的对偶也相等两个逻辑表达式相等，它们的对偶也相等FA+BCD = (A

11、+B)(A+C)(A+D)A ( B+C+D) = AB+AC+ADDual RuleDual RuleExample Laws and Theoremsn 特殊定理特殊定理3. . 常用公式常用公式From（18）：AB+ C+BCD=AB+ C+BC+BCD= AB+ C+BC= AB+ CAAAA A+AB=A AB+A = AB A+ B = A+BA AB+ C+BC =AB+ CAA AB+ C+BCD =AB+ CAAAB+ C+(A+ )BC =AB+ C+ABC+ BC= AB+ CAAAAA蕴涵定理蕴涵定理Laws and Theorems” (A+B)(B+C)(A +C

12、 )= (A+B)(A +C ) A + B = +ABBABAA + B = A B=( +B) (A+ )= +ABBABAABBALaws and TheoremsUnit 2 Boolean Algebra布尔表达式和真值表布尔表达式和真值表逻辑代数定理及规则逻辑代数定理及规则各种逻辑运算各种逻辑运算代数化简法代数化简法n 一个逻辑函数有多种不同的表达式一个逻辑函数有多种不同的表达式.与与-或或 .与非与非-与非与非.或或-与非与非.或非或非-或或.或或-与与 .或非或非-或非或非.与与-或非或非.与非与非-与与Algebraic Simplificationn 同一类型的表达式也不是

13、唯一的同一类型的表达式也不是唯一的F=AB+AC =AB+AC+BC= ABC+ABC+ABC+ABC. F1. F2. F3最简，元件少，可靠最简，元件少，可靠最简最简（Minimum Expressions） 与项（和项）的个数最少与项（和项）的个数最少 每个每个与项（和项）中变量的个数最少与项（和项）中变量的个数最少MethodsAlgebraic techniques）n （K. map method） Algebraic Simplificationminimum cost目的：目的： 降低成本降低成本 提高可靠性提高可靠性 F= A+ABC+ACD+CE+DE= A+ACD+CE+DE= A+CD+CE+DE= A+CD+E(C+D)= A+CD+ECD= A+CD+EexampleSimplification MethodsSimp