1Chapter 3 Logic Algebra逻辑代数基础逻辑代数基础Logic Algebra is presented by George Boole in 1849 and is also called Boolean Algebra. Logic algebra constitute a mathematical tool for describing the input-output behavior of the logical gates.逻辑代数描述二值变量(0,1)的运算规律由英国数学家布尔在19 世纪中提出，也称为布尔代数A variable is a symbol used to represent a logical quantity. Any single variable can have a 1 or a 0 value.逻辑代数中变量是表示逻辑量，只能取0或1.Logic algebra and arithmetic are different.逻辑代数与算术运算不同2§§3.1 Operations of Logic Algebra逻辑代数运算法则逻辑代数运算法则1. Fundamental Theorems of Logic Algebra 基本定律基本定律Every theorem is given in two forms: one for addition(加) and another for multiplication(乘). Two forms are equivalent and are called “Dual” each other. (每条定理有两种表达形式：逻辑加及逻辑乘。
对偶式对偶式)OR operation或 Logic addition“+” 0 + 0 = 0 0 + 1 = 1 1 + 0 = 1 1 + 1 = 1AThe complement 非 of A is0110==AND operation 与 Logic multiplication“•” 0•0 = 0 0•1 = 0 1•0 = 0 1•1 = 13基本定律Addition 逻辑加Multiplication 逻辑乘1)Theorem 1 A+B=B+A; AB=BA (交换律交换律)2)Theorem 2 A+(B+C)=(A+B)+C; A(BC)=(AB)C (结合律结合律)3)Theorem 3 A +BC= (A+B)(A+C); A(B+C)=AB+AC; (分配律)(分配律)6) Theorem 6 A+A=A; A•A=A (重叠律重叠律)7) Theorem 7 (还原律还原律)AA=4) Theorem 4 A+0=A, A+1=1;A•0 =0A•1=A5) Theorem 5 A+A=1 A•A=0 (01律/互补01律/互补)8) DeMorgan’s theorems A+B = A•B A•B = A+B (摩根定理摩根定理)CBAABC++=Deductions (推论）A+B+C=A•B•C42. Basic Rules 基本规则基本规则1) Substitution 代入规则等式两侧某一变量都用一个逻辑函数代入，等式仍成立。
等式两侧某一变量都用一个逻辑函数代入，等式仍成立For example:We have used it in the “Deduction” of Morgan’s Theorems.多个变量摩根定理XAAX+=IfBCX =Left:ABCAX =Right:CBABCA++=+SoCBAABC++=52) Complementary Theorem 反演规则反演规则Function is called the complement of the function F. if the function F is valid, the complement of the function, , is also valid.若原函数成立，反函数也成立若原函数成立，反函数也成立F FF1 0 + • uncomplementedcomplemented variable 原变量variable反变量New function F设F为逻辑函数，如果将函数表达式中所有的与(•) 换成或(+),或(+)换成与 (•);0换成1，1换成0；原变量换成反变量，反变量换成原变量，则得到的逻 辑函数是F的反函数FThe complement expression is formed by replacing all + operations with • , all • operations with +, all ones with zeros, all zeros with ones, all variables with inversed variables, and all inversed variables with variables.63) Duality 对偶规则对偶规则设F为逻辑函数，如果将函数表达式中所有的与(•) 换成或(+),或(+) 换成与(•);0换成1，1换成0；则得到的逻辑函数是F的对偶式F’The dual expression is found by replacing all + operation with • , all • operation with +, all ones with zeros, all zeros with ones.New function F’ is called the dual of the function F. If an expression F is valid in logic algebra, the dual of the expression, F’, is also valid.如果如果 F 成立，成立，F’ 也成立也成立•Function F+ 10New function F'7Note: 1. Keep the order of the operations(运算顺序不变运算顺序不变)2. Keep the bar which is on a function(不是一个变量上的反号保持不变不是一个变量上的反号保持不变)Example 1:Given F=A(B+C)CDFind F' and F, respectively+Example 2:XZYXWG+++=G'(WX)Y Z X=+? ?G(WX)Y Z X=+? ?Solution:F'= (A+BC)(C+D)F = (A+BC)(C+D)83. Formula of Boolean Algebra 常用公式常用公式1)A+AB=A; A(A+B)=AAbsorption 吸收律吸收律证明(Proof):A+AB = A (1+B)= AA+AB(AA)(AB)AB=++=+Proof: Using distributive law (分配律(分配律 A+BC=(A+B)(A+C) )2) A+ABAB; A(A+B)=AB =+吸收律吸收律9冗余定理冗余定理Proof:Deduction:ABACBCDEABAC++=+AB+AC+BC =AB+AC+(A+A)BC =AB+AC+ABC+ABC=AB+AC4)AB+AC+BC = AB+AC; (A+B)(A+C)(B+C) = (A+B)(A+C)Proof : AB+ABA(BB)A=+=3）A;BAAB=+A)BB)(A(A=++合并律合并律105) Exclusive-OR (XOR) Formula (异或公式异或公式)多变量异或，运算结果只与变量为多变量异或，运算结果只与变量为1的个数有关，与变量为的个数有关，与变量为0的个 数无关。
变量为的个 数无关变量为 1 的个数为奇数，异或结果为的个数为奇数，异或结果为 1；变量为；变量为 1 的个数为 偶数，结果为的个数为 偶数，结果为 0 变量与变量与1异或一次，相当于取反一次异或一次，相当于取反一次)BABABA)BA)(BA(BAAB⊕=+=++=+Proof:, 0=⊕ AACausality (因果关系）(因果关系）, 1=⊕ AA,0AA=⊕AA=⊕1A⊕B = A⊙B DCBA=⊕⊕6)IfthenC;DBA=⊕⊕ACDB;⊕⊕=BCDA;⊕⊕=11§3.2 Standard Forms of Logic Function逻辑函数的标准形式逻辑函数有两种标准形式：标准与或式（最小项和）标准或与式（最大项积）逻辑函数的标准形式逻辑函数有两种标准形式：标准与或式（最小项和）标准或与式（最大项积） 3.2.1 Minterms and Standard Sum of Products 最小项及标准与或式最小项及标准与或式 1. Minterms (Standard Product Form)最小项最小项：也称为：也称为标准与项标准与项 A product term was defined as a term consisting of the product (logic multiplication) of literals (variables or their complements).与项与项：多个变量(原变量或反变量)的乘积形式：多个变量(原变量或反变量)的乘积形式ABDCBEA12Minterms (Standard Product Terms): For a function withn variables if a product term contains each of the nvariables exactly one time in complemented or uncomplemented form, the product term is called a Minterm or a Standard Product Term. 标准与项(最小项)：标准与项(最小项)：n 变量函数, 变量函数, n 变量组成的与项中, 每个变量都以原变量或反变量形式出现一次, 且只出现一次。
若变量数 为n，则有2变量组成的与项中, 每个变量都以原变量或反变量形式出现一次, 且只出现一次若变量数 为n，则有2n n个最小项个最小项nn variables 2 minterms⇒For example: 3 variables A, B, C, there are 328 minterms:=CBACBACBABCACBACBACABABC132. Truth Table of Minterms最小项真值表Minterm Number01234567m m m m m m m mABC ABC ABC ABC AB。