数字逻辑2：逻辑代数基础.ppt

第二章逻辑代数基础,计算机科学学院朱勇zhudz_1964zhudz_1964,数字逻辑第二章逻辑代数基础,1/81,逻辑代数基本规则,逻辑变量取值只能是0和1，且0和1不表示具体数量的大小，只表示两种不同的逻辑状态。逻辑代数中基本运算只有“与”、“或”、“非”三种。,数字逻辑第二章逻辑代数基础,2/81,逻辑代数公理,数字逻辑第二章逻辑代数基础,3/81,逻辑代数定理,数字逻辑第二章逻辑代数基础,4/81,代入规则（SubstitutionRule）,已知如果用h替换等式两边的Xi，则等式仍然成立。即,数字逻辑第二章逻辑代数基础,5/81,反演规则（InversionRule）,若则变量和常量（0和1）取反，并将运算符“+”变为“”、“”变为“+”。,数字逻辑第二章逻辑代数基础,6/81,反演实例,数字逻辑第二章逻辑代数基础,7/81,对偶规则（DualityRule）,若则所有的“+”变为“”、“”变为“+”，“0”变为1”、“1”变为“0”，而逻辑变量保持不变。,数字逻辑第二章逻辑代数基础,8/81,对偶实例,数字逻辑第二章逻辑代数基础,9/81,逻辑函数的表示方法,逻辑函数的常见表示方法有逻辑表达式、真值表、卡诺图和逻辑图四种，各种表示方法之间可以相互转换。,数字逻辑第二章逻辑代数基础,10/81,逻辑表达式（LogicExpression）,逻辑表达式由逻辑变量及“与”、“或”、“非”三种运算符构成的式子。例如,数字逻辑第二章逻辑代数基础,11/81,真值表（TruthTable）,真值表是一种表格表示法。真值表实际上是利用穷举法描述逻辑函数。n个变量有2n个最小项。,数字逻辑第二章逻辑代数基础,12/81,真值表实例,数字逻辑第二章逻辑代数基础,13/81,逻辑图（LogicDiagram）,逻辑函数表示的逻辑关系可以用逻辑电路来实现。用逻辑符号画出的电路图称为逻辑图。,数字逻辑第二章逻辑代数基础,14/81,逻辑函数表达形式,函数可以表达为,数字逻辑第二章逻辑代数基础,15/81,积之和（SOP，SumofProducts）,所谓“积之和”也叫“与或”表达式，是指一个函数表达式由若干个积项的和组成，即若干个与项（ANDterm）进行或运算形成的表达式。例如：式中，都是积项（与项）。,数字逻辑第二章逻辑代数基础,16/81,和之积（POS，ProductofSums）,所谓“和之积”也叫“或与”表达式，是指一个函数表达式由若干个和项的积组成，即若干个或项（ORterm）进行与运算形成的表达式。例如：式中，都是和项（或项）。,数字逻辑第二章逻辑代数基础,17/81,最小项（Minterm）,设有n个逻辑变量，它们组成的与项中每个变量或以原变量形式或以反变量形式出现一次，且仅出现一次，此与项称之为n个变量的最小项。,数字逻辑第二章逻辑代数基础,18/81,三变量最小项,数字逻辑第二章逻辑代数基础,19/81,最小项性质,任意一个最小项，相应变量有且只有一组取值使这个最小项的值为1。任意两个最小项之积必为0，记为n个变量的全部最小项之和为1，记为,数字逻辑第二章逻辑代数基础,20/81,函数的最小项标准形式,如果构成函数的积之和表达式中每一个乘积项（与项）均为最小项，则称之为最小项之和标准式。如：是一个最小项之和标准式，为了书写方便，上式可记为：,数字逻辑第二章逻辑代数基础,21/81,与或式转换成最小项标准式,数字逻辑第二章逻辑代数基础,22/81,由真值表导出最小项标准式,数字逻辑第二章逻辑代数基础,23/81,逻辑函数的化简方法,逻辑函数的化简方法有三种：代数法、卡诺图法和蕴涵法。,数字逻辑第二章逻辑代数基础,24/81,与或式化简常用公式,数字逻辑第二章逻辑代数基础,25/81,吸收法,利用公式消去多余变量。,数字逻辑第二章逻辑代数基础,26/81,并项法,利用公式两项合并为一项且消去一个变量。,数字逻辑第二章逻辑代数基础,27/81,消去法,利用多余项定理消去多余项。,数字逻辑第二章逻辑代数基础,28/81,或与式化简常用公式,数字逻辑第二章逻辑代数基础,29/81,或与式化简方法,二次对偶法：利用对偶规则，先求出对偶式，再将对偶式化简为最简与或式，最后再求一次对偶，则得到最简或与式。二次求反法：利用反演规则，先求出反函数，再将反函数化简成最简与或式，再求一次反，则得到最简或与式。,数字逻辑第二章逻辑代数基础,30/81,卡诺图（KarnaughMap）,卡诺图是逻辑函数真值表的一种图形表示。利用卡诺图可以有规律地化简逻辑函数表达式，并能直观地写出逻辑函数的最简式。,数字逻辑第二章逻辑代数基础,31/81,二变量卡诺图构成,数字逻辑第二章逻辑代数基础,32/81,三、四变量卡诺图的构成,数字逻辑第二章逻辑代数基础,33/81,相邻最小项,把彼此只有一个变量不同，且这个不同变量互为反变量的两个最小项称为相邻最小项。,数字逻辑第二章逻辑代数基础,34/81,相邻关系,几何相邻：即几何位置上相邻的最小项，如四变量卡诺图中m0的相邻最小项m1和m4，这些最小项对应的小方格与m0对应的小方格分别相连。相对相邻：如四变量卡诺图中m0的相邻最小项中的m2和m8。m0和m2处在同一列的两端，m0和m8处在同一行的两端，它们之间的位置都是“相对的”。,数字逻辑第二章逻辑代数基础,35/81,卡诺圈,把用来覆盖那些能由一个简单“与”项代替的若干最小项的“圈”称为卡诺圈。,数字逻辑第二章逻辑代数基础,36/81,两变量卡诺圈,只有一个最小项m0。,数字逻辑第二章逻辑代数基础,37/81,两变量卡诺圈,最小项m1和m3几何相邻，可以画圈合并。,数字逻辑第二章逻辑代数基础,38/81,两变量卡诺圈,最小项m0和m1几何相邻，可以画圈合并。,数字逻辑第二章逻辑代数基础,39/81,两变量卡诺圈,最小项m1和m0几何相邻，可以画圈合并，同时最小项m1和m3几何相邻，也可以画圈合并。,数字逻辑第二章逻辑代数基础,40/81,两变量卡诺圈,所有4个最小项都相邻，可以画圈合并。,数字逻辑第二章逻辑代数基础,41/81,三变量卡诺圈,最小项m0和m4相对相邻，可以画圈合并。,数字逻辑第二章逻辑代数基础,42/81,三变量卡诺圈,最小项m0和m1几何相邻又与m4、m5相对相邻，可以画圈合并。,数字逻辑第二章逻辑代数基础,43/81,三变量卡诺圈,最小项m0、m2、m6和m4处于一行为几何相邻，可以画圈合并。,数字逻辑第二章逻辑代数基础,44/81,三变量卡诺圈,最小项m0、m2、m6和m4处于一行为几何相邻，可以画圈合并。同时m2和m3几何相邻，可以画圈合并。,数字逻辑第二章逻辑代数基础,45/81,三变量卡诺圈,最小项m0、m2、m6和m4处于一行为几何相邻，可以画圈合并。同时m2、m3、m6和m7都相邻，可以画圈合并。,数字逻辑第二章逻辑代数基础,46/81,三变量卡诺圈,最小项m0、m2、m6和m4处于一行为几何相邻，可以画圈合并。同时m0、m1、m2和m3及m2、m3、m6和m7都分别相邻，可以画圈合并。,数字逻辑第二章逻辑代数基础,47/81,三变量卡诺圈,最小项m1、m3、m5和m7处于一行为几何相邻，可以画圈合并。同时m0和m1几何相邻又与m4、m5相对相邻，可以画圈合并。,数字逻辑第二章逻辑代数基础,48/81,三变量卡诺圈,最小项m0和m4相对相邻，可以画圈合并。同时m3和m7几何相邻，可以画圈合并。,数字逻辑第二章逻辑代数基础,49/81,三变量卡诺圈,所有8个最小项都相邻，可以画圈合并。,数字逻辑第二章逻辑代数基础,50/81,四变量卡诺圈,最小项m0、m1、m3和m2几何相邻又与m8、m9、m11和m10相对相邻，可以画圈合并。,数字逻辑第二章逻辑代数基础,51/81,四变量卡诺圈,最小项m0、m4、m12和m8几何相邻又与m2、m6、m14和m10相对相邻，可以画圈合并。,数字逻辑第二章逻辑代数基础,52/81,四变量卡诺圈,最小项m0和m2相对相邻又与m8、m10相对相邻，可以画圈合并。同时m5、m7、m13和m15几何相邻，可以画圈合并。,数字逻辑第二章逻辑代数基础,53/81,四变量卡诺圈,最小项m0、m1、m4、m5、m12、m13、m8和m9几何相邻，可以画圈合并。同时m4、m5、m7和m6几何相邻，可以画圈合并。,数字逻辑第二章逻辑代数基础,54/81,四变量卡诺圈,最小项m1、m3、m5、m7、m13、m15、m9和m11几何相邻，可以画圈合并。同时m4、m12、m5、m13、m7、m15、m6和m14几何相邻，可以画圈合并。,数字逻辑第二章逻辑代数基础,55/81,四变量卡诺圈,最小项m1、m3几何相邻又与m9、m11相对相邻，可以画圈合并。同时m4、m12几何相邻又与m6、m14相对相邻，可以画圈合并。,数字逻辑第二章逻辑代数基础,56/81,四变量卡诺圈,最小项m0、m1、m3、m2、m4、m5、m7和m6几何相邻，可以画圈合并。同时m4、m12、m5、m13、m7、m15、m6和m14几何相邻，可以画圈合并。,数字逻辑第二章逻辑代数基础,57/81,四变量卡诺圈,最小项m0、m1、m3、m2、m4、m5、m7和m6几何相邻，可以画圈合并。同时m0、m1几何相邻又与m8、m9相对相邻，可以画圈合并。,数字逻辑第二章逻辑代数基础,58/81,四变量卡诺圈,所有16个最小项都相邻，可以画圈合并。,数字逻辑第二章逻辑代数基础,59/81,卡诺图法化简逻辑函数实例,数字逻辑第二章逻辑代数基础,60/81,卡诺图法化简逻辑函数实例,数字逻辑第二章逻辑代数基础,61/81,无关项,无关项，又称任意项或约束项。这里的“无关”有两个含义：（1）这些输入组合在正常操作中不会出现；（2）即使这些输入组合可能出现，但输出实质上与它们无关。换句话说，就是当输入出现这些组合时，其所对应的输出值可以为0，也可以为1。约束条件或称约束方程表示为N=di=0。,数字逻辑第二章逻辑代数基础,62/81,无关项化简实例,数字逻辑第二章逻辑代数基础,63/81,知识点,逻辑代数公理,数字逻辑第二章逻辑代数基础,64/81,知识点,逻辑代数定理,数字逻辑第二章逻辑代数基础,65/81,知识点,逻辑代数规则代入规则：任何一个含有变量Xi的等式，若将所有出现Xi的位置都代之以统一逻辑函数h，等式仍然成立。反演规则：从原函数求反函数得过程称为反演。求任何函数得反函数时，可将该函数得所有变量和常量（0和1）取反，并将运算符“+”变为“”、“”变为“+”，即可得反函数。对偶函数的定义是：将逻辑函数表达式f中所有的“+”变为“”、“”变为“+”，“0”变为“1”、“1”变为“0”，而逻辑变量保持不变，则所得的新函数称为原函数的对偶函数，记为f。,数字逻辑第二章逻辑代数基础,66/81,知识点,逻辑代数表示方法逻辑表达式由逻辑变量及“与”、“或”、“非”三种运算符构成的式子。真值表是一种表格表示法。真值表实际上是利用穷举法描述逻辑函数。由于任意逻辑变量只有两种取值可能，故n个逻辑变量共有2n种有限的可能取值组合。用逻辑符号画出的电路图称为逻辑图。卡诺图是逻辑函数真值表的一种图形表示。,数字逻辑第二章逻辑代数基础,67/81,知识点,逻辑函数表达形式积（或与）表达式，是指一个函数表达式由若干个和项的积积之和（与或）表达式，是指一个函数表达式由若干个积项的和组成，即若干个与项进行或运算形成的表达式。和之组成，即若干个或项进行与运算形成的表达式。如果构成函数的积之和表达式中每一个乘积项（与项）均为最小项，则称之为最小项之和标准式。,数字逻辑第二章逻辑代数基础,68/81,知识点,与或式化简常用公式：与或式化简常用方法：吸收法、并项法、消去法、配项法、综合法。,数字逻辑第二章逻辑代数基础,69/81,知识点,或与式化简中常用公式：或与式常用化简方法：常规法、二次对偶法、二次求反法。,数字逻辑第二章逻辑代数基础,70/81,知识点,两变量卡诺图,数字逻辑第二章逻辑代数基础,71/81,知识点,三、四变量卡诺图,数字逻辑第二章逻辑代数基础,72/81,知识点,相邻关系几何相邻：即几何位置上相邻的最小项。相对相邻：处在同一行或列的两端，它们之间的位置都是“相对的”。,数字逻辑第二章逻辑代数基础,73/81,知识点,卡诺图法化简逻辑函数的基本步骤：将逻辑函数表示在卡诺图上；画出所有的极大圈，确定全部实质最小项并选出所有的必要极大圈；如果所选出的所有必要极大圈已覆盖了卡诺图上所有的1方格，那么所有必要极大圈的集合就是卡诺图上的最小覆盖；如果还有1方格未被必要极大圈覆盖，那么再选