数字电路与逻辑设计.ppt

第二章 逻辑代数基础,21 逻辑代数的基本概念 22 逻辑代数的基本定理和规则 23 逻辑函数表达式的形式与变换 24 逻辑函数的化简,21 逻辑代数(logic algebra)的基本概念,公理1 交换律(Commutative Properties) 公理2 结合律(Associative Properties) 公理3 分配律(Distributive Properties) 公理4 01律（01 Property） 公理5 互补律(Complement Property),A+B=B+A AB=BA,(A+B)+C=A+(B+C) (AB)C=A(BC),A+(BC)=(A+B)(A+C) A(B+C)=AB+AC,A+0=A A1=A A+1=1 A0=0,A+A=1 AA=0,211 逻辑变量及基本逻辑运算 212 逻辑函数及逻辑函数间的相等 213 逻辑函数的表示方法,211 逻辑变量及基本逻辑运算,1 逻辑变量(logic variable) 逻辑代数是一种比普通代数更为简单的代数。 同样用字母表示变量和函数。 不同的是： 在普通代数中，变量的取值可以是任意实数。 而逻辑代数是一种二值代数系统，即任何逻辑变量的取值只有两种可能性取值0和取值1。,逻辑0和逻辑1不再像普通代数具有数量的概念，而是用来表征矛盾的双方和判断事件真伪的形式符号，无大小、正负之分。 在数字系统中，开关的接通与断开，电压的高和低，信号的有和无，晶体管的导通与截止等两种稳定的物理状态，均可用1和0这两种不同的逻辑值来表征。,逻辑0,逻辑1,2 基本逻辑运算( primitive logic operation),与运算 或运算 非运算 学习内容包括定义、逻辑功能描述、开关电路示意图、条件与结果关系表、关系表达式、运算规则、工作波形图等等,1. “与”(AND)运算 与逻辑：在逻辑问题中，如果决定某事件发生的多个条件必须同时具备，事件才能发生，则这种因果关系称之。,问：F灯何时亮？,答：AB都闭合时，灯亮,闭合、灯亮用1，断开、灯不亮用0；真值表,功能：当A与B都为高时，输出F才为高。 表达式：F=AB,2. “或”(OR)运算 或逻辑：在逻辑问题中，如果决定某事件发生的多个条件中，只要有一个或一个以上条件成立，事件便可发生，则这种因果关系称之。,问：F灯何时亮？,答：A闭合或B闭合时，灯亮,闭合、灯亮用1，断开、灯不亮用0；真值表,功能：当A、B中只要有一个为高，输出F就为高。 表达式：F=A+B,3. “非”(NOT)运算 非逻辑：在逻辑问题中，如果某事件的发生取决于条件的否定，则这种因果关系称之。,问：F灯何时亮？,答：A断开时，灯亮,闭合、灯亮用1，断开、灯不亮0；真值表,功能：当A为高时，输出F为低，当A为低时，输出F就为高。 表达式：F=A,212 逻辑函数及逻辑函数间的相等,1逻辑函数(logic function)的定义 逻辑函数具有的特点： 1）逻辑变量和逻辑函数的取值只有0和1两种可能； 2）函数和变量之间的关系是由“或”、“与”、“非”3种基本运算决定的。,逻辑0,逻辑1,或运算,非运算,与运算,逻辑函数的定义：设某一逻辑电路的输入逻辑变量为A1,A2,An，输出逻辑变量为F，如果当A1,A2,An的值确定后，F的值就唯一地被确定下来，则F被称为A1,A2,An的逻辑函数，记为 F=f(A1,A2,An)。 广义的逻辑电路图:,2逻辑函数的相等电路(equivalence),两个逻辑函数相等的定义： 设有两个逻辑函数 F1=f1(A1,A2,An), F2=f2(A1,A2,An),若对应于逻辑变量A1,A2,An的任何一组取值，F1和F2的值都相同，则称函数F1和F2相等。记作F1F2。,判断两个逻辑函数是否相等的方法有多种： 1）真值表； 2）公理、定理和规则进行证明； 3）卡诺图； 4）逻辑图； 5）工作波形图；等等,213 逻辑函数的表示方法,描述逻辑函数的方法并不是唯一的，不同描述方法适合于不同场合。针对某个具体问题而言，它们仅仅是同一问题的不同描述形式 ，它们之间可以很方便地相互转换。 1 逻辑表达式( logic expression) 2逻辑图(Logic diagram) 3逻辑真值表(Truth table) 4卡诺图(Karnaugh Map) 5工作波形图（Timing diagram),1 逻辑表达式( logic expression) 逻辑表达式是由逻辑变量和“或”、“与”、“非”三种运算符所构成的式子。 逻辑表达式书写时要注意优先级问题，从高到低分别是“非”、“与”、 “或”。（即书写规则） 进行“非”运算可不加括号； “与”运算符一般可省略，如AB可写成AB； 在一个表达式中，如果既有“与”运算又有“或”运算，则按先“与”后“或”的规则进行运算，而可省去括号； 由于“与”运算和“或”运算均满足结合律，因此(A+B)+C或者A+(B+C)可用A+B+C代替；(AB)C或者A(BC)可用ABC代替。,2逻辑图(Logic diagram) 由逻辑门电路符号构成的，用来表示逻辑变量之间关系的图形称为逻辑电路图，简称逻辑图。,3逻辑真值表(Truth table) 表格表示法，用穷举法来描述逻辑函数的功能。 对一个函数求出所有输入变量取值下的函数值并用表格形式记录下来，这种表格称为真值表。 它由两部分组成，左边一栏列出变量的所有取值组合，右边一栏为逻辑函数值，为了不发生遗漏，通常各变量取值组合按二进制数码顺序给出。,4卡诺图(Karnaugh Map) 卡诺图是由表示逻辑变量所有取值组合的小方块所构成的平面图，用图形法描述逻辑函数。,5工作波形图（Timing diagram),22 逻辑代数的基本定理和规则,221 基本定理 222 逻辑代数的三个规则 223 复合逻辑,221 基本定理(postulate or theorem),根据逻辑代数的公理，可以推导出逻辑代数的基本定理。 定理2 （重叠律）(Idempotency Property) 定理3*（吸收律）(Absorption Property) 定理4*（吸收律） (Absorption Property) 定理5 （双重否定律）(Double Complement Property) 定理6*（反演律）(DeMorgans Theorems) 定理8*（包含律）(Consensus theorem),A+A=A AA=A,A+AB=A A(A+B)=A,222 逻辑代数的三个规则,1代入规则 定义描述：任何含有变量A的逻辑等式，如果将所有出现A的位置都代之以同一个逻辑函数F，则等式仍然成立。这个规则称为代入规则。 引入代入规则的意义：在推导公式中有重要意义。利用这条规则可以将逻辑代数公理、定理中的变量用任意函数代替，从而推导出更多的等式。这些等式可直接当作公式使用，无需另加证明。 使用时注意的问题：使用代入规则时必须将等式中所有出现同一变量的地方均以同一函数代替，否则代入后的等式将不成立。,2反演规则 如果将逻辑函数表达式F中所有的“”变成“”，“”变成“”，“0”变成“1”，“1”变成“0”，原变量变成反变量，反变量变成原变量，并保持原函数中的运算顺序不变，则所得到的新的函数为原函数F的反函数F。这一规则称为反演规则。 简单描述：已知F，求F。（ 01，+，AA ） 反演规则和反演律的比较；反演规则是反演律的推广，本质是一样，但方法和适用场合有所不同。,3对偶规则,如果将逻辑函数表达式F中所有的“”变成“”，“”变成“”，“0”变成“1”，“1”变成“0”，并保持原函数中的运算顺序不变，则所得到的新的逻辑表达式称为函数F的对偶式，并记作F。 简单描述：已知F，求F。（ 01，+） 若两个逻辑函数表达式F和G相等，则其对偶式F 和G也相等。这一规则称为对偶规则。即若F=G，那么F=G。 引入对偶规则的意义：利用对偶规则可以使定理、公式的证明减少一半。,223 复合逻辑,1、与非门 2、或非门 3、与或非门 4、异或 5、同或,1“与非”(NAND)逻辑,定义：与非逻辑是由与、非两种逻辑复合形成 逻辑表达式：F=ABC 逻辑功能描述:变量ABC中只要一个为0，函数F为1，变量ABC都为1，F才为0。 逻辑门：与非门 真值表 波形图,2“或非”(NOR)逻辑,定义：或非逻辑是由或、非两种逻辑复合形成 逻辑表达式：F=A+B+C+ 逻辑功能描述:变量ABC中只要一个为1，函数F为0，变量ABC都为0，F才为1。 逻辑门：或非门 真值表 波形图,3“与或非”(AND-OR-INVERT)逻辑,定义：与或非逻辑是由与、或、非两种逻辑复合形成 逻辑表达式：F=AB+CD+ 逻辑功能描述:仅当每一个与项均为0时，F为1，否则F为0。 逻辑门：与或非门 真值表 波形图,4“异或”(EX-OR)逻辑,定义：不带进位的加法，又称模2和，是一种两变量逻辑 逻辑表达式：F=AB 逻辑功能描述:变量AB中取值相同，函数F为0，变量AB取值不同，F为1。 逻辑门：异或门 真值表 波形图,F=AB=AB+AB （不考虑进位加法，模2和） 用途：1）加法（半加器） 2）原码/反码输出 当A=0,F=B 原码输出；当 A=1,F=B 反码输出； 3）等同比较器（一位等同，使用时加上反相器） 4）奇偶校验 F=ABC，奇数个1，F=1，偶数个1，F=0,5“同或”(EX-NOR)逻辑,也是一种两变量逻辑，同或与异或既互为相反，又互为对偶 逻辑表达式：F=AB 逻辑功能描述:变量AB中取值相同，函数F为1，变量AB取值不同，F为0。 逻辑门：同或门 真值表 波形图,23 逻辑函数表达式的形式与变换,231 逻辑函数表达式的基本形式 232 逻辑函数表达式的标准形式 233 逻辑函数表达式的转换,231 逻辑函数表达式的基本形式,1“与-或”(Sum of products)表达式 例 F=AB+CD+EF 2“或-与”(Product of sums)表达式 例 F=(A+B)(C+D)(E+F) 逻辑函数的不同表达形式: 与或式 与非-与非式 或-与非式 与或非式 或非-或式 与非-与式 或与式 或非-或非式 最简与或式 举例 F=AB 异或式（如7486）,232 逻辑函数表达式的标准形式,1.最小项和最大项 1）最小项(minterm) 定义:与项，包含全部n个变量文字(Literal)，以原变量、反变量出现，仅出现一次。 A,B两变量的最小项有四个、三变量最小项有八个、四变量最小项有16个的构成） 描述成mi (Designation Symbol)，i的得到：把反变量用0替换，原变量用1替换，,最小项的性质： mi只有一组变量取值使它为1，该值为i的二进制代码； mimj 0 （ij） mi1（i0n-1） n个变量有2n个最小项 n个相邻最小项,2） 最大项(maxterm) （自学最大项的定义、最大项的描述和最大项的5个性质） 定义:或项，包含全部n个变量文字(Literal)，以原变量、反变量出现，仅出现一次。 A,B两变量的最大项有四个、三变量最大项有八个、四变量最大项有16个的构成） 描述成Mi (Designation Symbol)，i的得到：把反变量用1替换，原变量用0替换，,最大项的性质： Mi只有一组变量取值使它为0，该值为i的二进制代码； Mi+Mj 1 （ij） Mi0（i0n-1） n个变量有2n个最大项 n个相邻最大项 3）最小项与最大项的关系 互反 互逆 miMi,2逻辑函数表达式的标准形式,（1） 标准“与或”式（最小项表达式） 与或式（Sum of products）：逻辑变量的逻辑与运算叫与项(Product term)，与项的或运算称之。 最简的与或式：式中含的与项最少，各与项中含的变量数最少。 规范的与或式(Canonical sum of products)：如果函数与或式中全由最小项组成，又称为最小项表达式。,（2） 标准“或与”式（最大项表达式） 或与式(Product of sums)：逻辑变量的逻辑或运算叫或项(Sum term)，或项的与运算称之。 最简的或与式：式中含的或项最少，各或项中含的变量数最少。 规范的或与式(Canonical product of sums)：如果函数或与式中全由最大项组成，又称为最大项表达式。 举例说明一般的、最简的、标准的表达式,233 逻辑函数表达式的转换(convertion of logic function),2331 代数转换法 利用逻辑代数的公理、定理和规则进行逻辑变换，将函数表达式从一种形式变换到另一种形式。 用代数法求一个函数的标准与或式： 对于“与或”式，利用互补律进行展开，缺少什么补上什么。,用代数法求一个函数的标准或与式： 对于“或与”式， 1、利用定理7进行展开，缺少什么补上什么； 2、通过转换成“与或“式，再按“与或”处理。 “与或”“或与”有两种方法： 1)两次求反，一次展开； 2)两次求对偶，一次展开。,2332 真值表转换法,1.表达式真值表 一般按自然二进制码的顺序列出函数所含逻辑变量的所有不同取值组合，再确定相应的函数值。 例、求逻辑函数Z=AB+BC+CA的真值表,0 1 1 1 1 1 1 0,2.真值表表达式 例、已知函数F=ABC的真值表，求标准与或表达式和标准或与表达式。,0 1 1 0 1 0 0 1,F(A,B,C)=m(1,2,4,7) =M(0,3,5,6),24 逻辑函数的化简(reduction of logic function),241 代数化简法 242 卡诺图化简法 *243 列表化简法,241 代数化简法,运用逻辑代数的公理、定理和规则对逻辑函数进行化简的方法；没有固定的步骤可以遵循，主要取决于对逻辑代数中公理、定理和规则的熟练掌握及灵活应用的程度。 优点是不受变量数目的约束，当对公理、定理和规则十分熟练时化简比较方便。 缺点是没有一定的规律和步骤，技巧性很强，而且在很多情况下难以判断化简结果是否最简。这种方法有较大的局限性。,2411 “与或”表达式的化简 最简的“与或”式满足两个条件： 1）式中“与”项个数最少；（相对于门数最少） 2）每个“与”项中的变量个数最少；（门的输入端个数最少）,2412 “或与”表达式的化简 最简的“或与”式满足两个条件： 1）式中“或”项个数最少；（相对于门数最少） 2）每个“或”项中的变量个数最少；（门的输入端个数最少）,2413 化简的方法,化简的方法有以下常用方法： 1、并项法（定理7） 2、消去法（定理3） 3、吸收法 （定理4） 4、配项法（公理4和公理5） 例、求函数F=AB+BC+BC+AB的最简与或表达式,242卡诺图化简法(Karnaugh map),2421 卡诺图的构成与特点 2422 卡诺图的相邻原则 2423 卡诺图的一些几何含义 2424 用卡诺图表示逻辑函数 2425 块的合并 2426 卡诺图化简逻辑函数的步骤 2427 用卡诺图化简逻辑函数的实例 2428 注意点,2421 卡诺图的构成与特点,1）两变量卡诺图(two-variable Karnaugh map) 2）三变量卡诺图(three-variable Karnaugh map) 3）四变量卡诺图(four-variable Karnaugh map) 4）五变量卡诺图(two-variable Karnaugh map),A,B,A,C,B,A,C,B,D,A,C,B,D,E,2422 卡诺图的相邻原则 逻辑相邻的含义 三种相邻情况： 1）相接（几何相邻） 2）相对 3）相重（五变量以上才有）,2423卡诺图的一些几何含义 与（区域重合） 或（区域叠加） 非 异或 同或 最小项的5个性质 最小项和最大项的关系,2424 用卡诺图表示逻辑函数,1）最小项表达式（标准与或式）卡诺图 例：F=m3(1,2,3,7) 2）真值表卡诺图（卡诺图真值表） 3）一般与或式卡诺图 例： F=AB+BCm3(3,6,7) * 4）直接填充（利用几何含义） 例1： F=AB+BC 例2： Z=AC+BA+D+ABCD,2425 块的合并（卡诺图上最小项的合并规律）,只有2i个相邻最小项才能合并，并消去i个变量 卡诺图化简的依据：任何两个几何上相邻的小方块所表示的最小项只有一个变量不同，其余变量均相同，这样将两项并为一项可消去一个变量。,0维块 1个最小项（1个小方块） 1维块 2个最小项（2个小方块） 2维块 4个最小项（4个小方块） 3维块 8个最小项（8个小方块） n维块 2n个最小项（2n个小方块）,n个变量卡诺图中最小项的合并规律： 卡诺圈必须满足2m个方块(m=n) 含有m个不同变量，(n-m)个相同变量 卡诺圈可用(n-m)个变量的与项表示 当m=0时，卡诺圈中只有一个最小项；当m=n时，卡诺圈为1。,两变量卡诺图有两种形式的一维块、一个二维块； 三变量卡诺图有三种形式的一维块、三种形式的二维块和一个三维块； 四变量卡诺图有四种形式的一维块、六种形式的二维块、四种形式的三维块和一个四维块。,2426 卡诺图化简逻辑函数的步骤,蕴涵项（Implicant）：在函数的“与或”表达式中，每个“与”项称之。（一个“1”方块所对应的最小项和卡诺圈的2m个“1”方块所对应的“与”项都是函数的蕴涵项） 质蕴涵项（Prime Implicant）：若函数的一个蕴涵项不是该函数中其他蕴涵项的子集，则此蕴涵项称之，简称质项。(如果某个卡诺圈不可能被其他更大的卡诺圈包含，它对应的“与”项为质蕴涵项。此块即极大块) 必要质蕴涵项（Essential Prime Implicant）：若函数的一个质蕴涵项包含不被其他任何质蕴涵项所包含的最小项，则此质蕴涵项称之，简称必要质项。（某个卡诺圈包含了不可能被其他卡诺圈包含的“1”方块，即有