数字逻辑 第二章 逻辑代数基础精品文稿.ppt

《数字逻辑 第二章 逻辑代数基础精品文稿.ppt》由会员分享，可在线阅读，更多相关《数字逻辑 第二章 逻辑代数基础精品文稿.ppt（94页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、数字逻辑课件第二章逻辑代数基础1第1页，本讲稿共94页逻辑代数是数字系统逻辑设计的理论基础和重要数学工具！逻辑代数是数字系统逻辑设计的理论基础和重要数学工具！18471847年年,英国数学家乔治布尔(G.Boole)提出了用数学分析方法表示命题陈述的逻辑结构，并将形式逻辑归结为一种代数演算，从而诞生了著名的“布尔布尔代数代数”。19381938年年，克劳德向农(C.E.Shannon)将布尔代数应用于电话继电器的开关电路，提出了“开关代数开关代数”。随着电子技术的发展，集成电路逻辑门已经取代了机械触点开关，故人们更习惯于把开关代数叫做逻辑代数逻辑代数。2第2页，本讲稿共94页本章知识要点：本章

2、知识要点：基本概念基本概念 ；基本定理和基本定理和规则规则 ；逻辑逻辑函数的表示形式函数的表示形式 ；逻辑逻辑函数的化函数的化简简 。3第3页，本讲稿共94页 逻辑代数L是一个封闭的代数系统，它由一个逻辑变量集K，常量0和1以及“或”、“与”、“非”三种基本运算所构成，记为L=K,+,L=K,+,-,0,1,-,0,1。该系统应满足下列公理。2.1 2.1 逻辑代数的基本概念逻辑代数的基本概念公公 理理 1 1 交交 换换 律律对于任意逻辑变量对于任意逻辑变量A、B，有，有A+B=B+A；AB=B A公公 理理 2 2 结结 合合 律律对于任意的对于任意的逻辑变量逻辑变量A、B、C，有，有(A

3、+B)+C=A+(B+C)(A+B)+C=A+(B+C)(A(AB)B)C=A C=A(B(B C)C)4第4页，本讲稿共94页公公 理理 3 3 分分 配配 律律对于任意的逻辑变量对于任意的逻辑变量A、B、C，有，有A+(BC)=(A+B)(A+C)；A(B+C)=AB+AC公公 理理 4 01 4 01 律律对于任意逻辑变量对于任意逻辑变量A，有，有 A+0=A A+0=A ；A A 1=A 1=A A+1=1 A+1=1 ；A A 0=0 0=0 公理是一个代数系统的基本出发点，无需加以证明。公理是一个代数系统的基本出发点，无需加以证明。公公 理理 5 5 互互 补补 律律对于任意逻辑变

4、量对于任意逻辑变量A，存在唯一的，使得，存在唯一的，使得5第5页，本讲稿共94页2.1.1 2.1.1 逻辑变量及基本逻辑运算逻辑变量及基本逻辑运算逻辑代数和普通代数一样，是用字母表示其值可以变化逻辑代数和普通代数一样，是用字母表示其值可以变化的量，即变量。所不同的是：的量，即变量。所不同的是：1任何逻辑变量的取值只有两种可能性任何逻辑变量的取值只有两种可能性取值取值0 0或或取值取值1 1。2逻辑值逻辑值0 0和和1 1是用来表征矛盾的双方和判断事件真伪是用来表征矛盾的双方和判断事件真伪的形式符号，无大小、正负之分。的形式符号，无大小、正负之分。一、变量一、变量6第6页，本讲稿共94页二、基

5、本逻辑运算二、基本逻辑运算 描述一个数字系统，必须反映一个复杂系统中各开关元件之间的联系，这种相互联系反映到数学上就是几种运算关系。逻逻辑辑代代数数中中定定义义了了“或或”、“与与”、“非非”三三种种基基本本运算。运算。1 1“或或”运算运算 如如果果决决定定某某一一事事件件是是否否发发生生的的多多个个条条件件中中，只只要要有有一一个个或或一一个个以以上上条条件件成成立立，事事件件便便可可发发生生，则则这这种种因因果果关关系系称之为称之为“或或”逻辑。逻辑。例如，用两个开关并联控制一个灯的照明控制电路。7第7页，本讲稿共94页电路中，开关A和B并联控制灯F。可以看出，当开关A、B中有一个闭合或

6、者两个均闭合时，灯F即亮。因此，灯F与开关A、B之间的关系是“或”逻辑关系。可表示为 并联开关电路并联开关电路ABF例如，下图所示电路。F=A+B F=A+B 或者或者F=A BF=A B，读作，读作“F F等于等于A A或或B B”。8第8页，本讲稿共94页假定开关断开用假定开关断开用0表示，开关闭合用表示，开关闭合用1表示；灯灭用表示；灯灭用0表示，灯亮用表示，灯亮用1表表示，则灯示，则灯F与开关与开关A、B的关系如下表所示。的关系如下表所示。即：A、B中只要有一个为中只要有一个为1，则，则F为为1；仅当；仅当A、B均为均为0时，时，F才为才为0。A0111100BF01011“或或”运算

7、表运算表 F 并联开关电路并联开关电路AB“或或”运算的运算法则：运算的运算法则：0+0=01+0=10+1=11+1=1实现“或”运算关系的逻辑电路称为“或或”门门。9第9页，本讲稿共94页 2 2“与与”运算运算如果决定某一事件发生的多个条件必须同时具备，事如果决定某一事件发生的多个条件必须同时具备，事件才能发生，则这种因果关系称之为件才能发生，则这种因果关系称之为“与与”逻辑。逻辑。在逻辑代数中，“与”逻辑关系用“与”运算描述。两变量“与”运算关系可表示为F=AB或者F=AB即：即：若若A A、B B均为均为1 1，则，则F F为为1 1；否则，；否则，F F为为0 0。A0110000

8、BF01011 “与与”运算表运算表 10第10页，本讲稿共94页ABF 串联开关电路串联开关电路 例如，两个开关串联控制同一个灯。显然，仅当两个开关均闭合时，灯才能亮，否则，灯灭。假定开关闭合状态用1表示，断开状态用0表示，灯亮用1表示，灯灭用0表示，则F和A、B之间的关系“与”运算关系。数字系统中，实现“与”运算关系的逻辑电路称为“与与”门门。“与与”运算的运算法则运算的运算法则:0 0=01 0=00 1=01 1=111第11页，本讲稿共94页 3 3“非非”运算运算 如果某一事件的发生取决于条件的否定，即事件与事件如果某一事件的发生取决于条件的否定，即事件与事件发生的条件之间构成矛盾

9、，则这种因果关系称为发生的条件之间构成矛盾，则这种因果关系称为“非非”逻辑。逻辑。在逻辑代数中，“非”逻辑用“非”运算描述。其运算符号为“”，有时也用“”表示。“非”运算的逻辑关系可表示为F=或者 F=A读作“F等于等于A非非”。即：若若A为为0，则，则F为为1；若；若A为为1，则，则F为为0。“非非”运算表运算表 AF010112第12页，本讲稿共94页A开关与灯并联电路F例如，下面开关与灯并联的电路中，仅当开关断开时，灯亮；一旦开关闭合，则灯灭。令令开开关关断断开开用用0表表示示，开开关关闭闭合合用用1表表示示，灯灯亮亮用用1表表示示，灯灯灭灭用用0表表示示，则则电电路路中中灯灯F与与开开

10、关关A的关系即为上表所示的关系即为上表所示“非非”运算关系。运算关系。“非非”运算的运算法则：运算的运算法则：；数字系统中实现“非”运算功能的逻辑电路称为“非非”门门，有时又称为“反相器反相器”。13第13页，本讲稿共94页2.1.2 2.1.2 逻辑逻辑函数及函数及逻辑逻辑函数函数间间的相等的相等逻辑代数中函数的定义与普通代数中函数的定义类似，即即随随自自变变量量变变化化的的因因变变量量。但和普通代数中函数的概念相比，逻辑函数具有如下特点特点：1逻逻辑辑函函数数和和逻逻辑辑变变量量一一样样，取取值值只只有有0和和1两两种种可可能能；2函函数数和和变变量量之之间间的的关关系系是是由由“或或”、

11、“与与”、“非非”三种基本运算决定的三种基本运算决定的。一一、逻辑逻辑函数的定函数的定义义14第14页，本讲稿共94页图中，图中，F被称为被称为A1，A2，An的逻辑函数，记为的逻辑函数，记为F=f(A1，A2，An)逻辑电路输出函数的取值是由逻辑变量的取值和电路本逻辑电路输出函数的取值是由逻辑变量的取值和电路本身的结构决定的身的结构决定的。广义的逻辑电路逻辑电路逻辑电路FA1A2An设某一逻辑电路的输入逻辑变量为设某一逻辑电路的输入逻辑变量为A1，A2，An，输，输出逻辑变量为出逻辑变量为F，如下图所示。，如下图所示。15第15页，本讲稿共94页设有两个相同变量的逻辑函数F1=f1(A1,A

12、2,An)F2=f2(A1,A2,An)若若对对应应于于逻逻辑辑变变量量 A1,A2,An的的任任何何一一组组取取值值，F1和和F2的值都相同，则称函数的值都相同，则称函数F1和和F2相等，记作相等，记作F1=F2。如何判断两个逻辑函数是否相等？如何判断两个逻辑函数是否相等？通常有两种方法：真值表法真值表法，逻辑代数法逻辑代数法。二二、逻辑逻辑函数的相等函数的相等16第16页，本讲稿共94页2.1.3 2.1.3 逻辑逻辑函数的表示法函数的表示法函数函数F和变量和变量A、B的关系是：的关系是：当变量当变量A和和B取值不同时，函数取值不同时，函数F的值为的值为“1”；取值取值相同时，函数相同时，

13、函数F的值为的值为“0”。逻辑表达式是由逻辑变量和“或”、“与”、“非”3种运算符以及括号所构成的式子。例如一一、逻辑逻辑表达式表达式 常用的方法有常用的方法有逻辑表达式、真值表、卡诺图逻辑表达式、真值表、卡诺图3种种。17第17页，本讲稿共94页逻辑表达式的简写逻辑表达式的简写:1.“非非”运算符下可不加括号，如运算符下可不加括号，如，等。等。2.“与与”运算符一般可省略，如运算符一般可省略，如AB可写成可写成AB。高高低低3.在一个表达式中，如果既有“与”运算又有“或”运算，则按按先先“与与”后后“或或”的规则进行运算，可省去括号的规则进行运算，可省去括号,如如 (AB)+(CD)可写为可

14、写为AB+CD。注意注意:(A+B)(C+D):(A+B)(C+D)不能省略括号不能省略括号,即不能写成即不能写成A+BC+DA+BC+D！运算优先法则：运算优先法则：()+4.(A+B)+C或或 者者A+(B+C)可可 用用 A+B+C代代 替替；(AB)C或或 者者A(BC)可用可用ABC代替。代替。18第18页，本讲稿共94页二、真二、真值值表表 依次列出一个逻辑函数的所有输入变量取值组合及其相依次列出一个逻辑函数的所有输入变量取值组合及其相应函数值的表格称为应函数值的表格称为真值表真值表。一个一个n个变量的逻辑函数，其真值表有个变量的逻辑函数，其真值表有2n行。行。例如，真值表由两部分

15、组成：真值表由两部分组成：左边一栏列出变量的所有取值组左边一栏列出变量的所有取值组合，为了不发生遗漏，通常各变量取合，为了不发生遗漏，通常各变量取值组合按二进制数码顺序给出；右边值组合按二进制数码顺序给出；右边一栏为逻辑函数值。一栏为逻辑函数值。19第19页，本讲稿共94页三三、卡卡诺图诺图 卡卡诺诺图图是是由由表表示示逻逻辑辑变变量量所所有有取取值值组组合合的的小小方方格格所所构构成成的平面图的平面图。这种用图形描述逻辑函数的方法，在逻辑函数化简中十分有用，将在后面结合函数化简问题进行详细介绍。描述逻辑逻辑函数的描述逻辑逻辑函数的3 3种方法可用于不同场合。但针对某种方法可用于不同场合。但针

16、对某个具体问题而言，它们仅仅是同一问题的不同描述形式，相个具体问题而言，它们仅仅是同一问题的不同描述形式，相互之间可以很方便地进行变换。互之间可以很方便地进行变换。20第20页，本讲稿共94页2.2 2.2 逻辑逻辑代数的基本定理和代数的基本定理和规则规则 常用的组定理：常用的组定理：2.2.1 2.2.1 基本定理基本定理 定理定理10+0=01+0=10 0=01 0=00+1=11+1=10 1=01 1=1证证明明：在公理4中，A表示集合K中的任意元素，因而可以是0或1。用0和1代入公理4中的A，即可得到上述关系。如果以如果以1和和0代替公理代替公理5中的中的A，则可得到如下推论：，则

17、可得到如下推论：21第21页，本讲稿共94页证明证明A+AB=A1+AB 公理公理4 =A(1+B)公理公理3 =A(B+1)公理公理1 =A1公理公理4 =A公理公理4证明证明A+A=(A+A)1公理公理4 =(A+A)(A+A)公理公理5 =A+(AA)公理公理3 =A+0公理公理5 =A公理公理4定理定理2A+A=A；A A=A定理定理3A+A B=A；A (A+B)=A22第22页，本讲稿共94页定理定理4 A+AB=A+B;A(A+B)=AB证明证明A+AB=(A+A)(A+B)公理公理3 =1(A+B)公理公理5 =A+B公理公理4证明证明令令A=X因而因而 XA=0 X+A=1公

18、理公理5但是但是 AA=0 A+A=1公理公理5由于由于X和和A都满足公理都满足公理5，根据公理，根据公理5的唯一性，得到：的唯一性，得到：A=X由于由于A=X，所以，所以A=A定理定理5=AA23第23页，本讲稿共94页定理定理6证明证明 由于()+(A+B)=(+A)+B公理2=(+A)+B定理4=A+(B+)公理1,2=A+1公理5=1公理4而且()(A+B)=A+B公理3=0+0公理1,5=0定理1所以，根据公理5的唯一性可得24第24页，本讲稿共94页定理定理7AB+A =A(A+B)(A+)=A证明证明 AB+A =A (B+)公理公理3 =A 1 公理公理5 =A 公理公理425

19、第25页，本讲稿共94页定理定理8 A B+C+B C=A B+C (A+B)(+C)(B+C)=(A+B)(+C)证明证明 AB+C+BC =AB+C+BC(A+)公理公理5 =AB+C+BCA+BC 公理公理3 =AB+ABC+C+BC 公理公理1 =AB(1+C)+C(1+B)公理公理3 =AB(C+1)+C(B+1)公理公理1 =AB+C 公理公理426第26页，本讲稿共94页2.2.2 2.2.2 重要重要规则规则 例如，将逻辑等式A(B+C)=AB+AC中的C都用(C+D)代替，该逻辑等式仍然成立，即AB+(C+D)=AB+A(C+D)代入规则的正确性是显然的，因为任何逻辑函数都和

20、逻辑变量一样，只有0和1两种可能的取值。任何一个含有变量任何一个含有变量A的逻辑等式的逻辑等式,如果将所有出现如果将所有出现A的位的位置都代之以同一个逻辑函数置都代之以同一个逻辑函数F，则等式仍然成立。这个规则，则等式仍然成立。这个规则称为代入规则。称为代入规则。一一、代入代入规则规则 27第27页，本讲稿共94页代入规则的意义：代入规则的意义：利用代入规则可以将逻辑代数公理、定理中的变量用任意函数代替，从而推导出更多的等式。这些等式可直接当作公式使用，无需另加证明。注意：注意：使用代入规则时使用代入规则时,必须将等式中所有出现同一变量必须将等式中所有出现同一变量的地方均以同一函数代替，否则代

21、入后的等式将不成立。的地方均以同一函数代替，否则代入后的等式将不成立。28第28页，本讲稿共94页二、反演二、反演规则规则 例如，已知函数，根据反演规则可得到若将若将逻辑逻辑函数表达式函数表达式F中所有的中所有的“”变变成成“+”，“+”变变成成“”,“0”变变成成“1”,“1”变变成成“0”,原原变变量量变变成反成反变变量，反量，反变变量量变变成原成原变变量，并保持原函数中的运算量，并保持原函数中的运算顺顺序不序不变变，则则所所得到的新的函数得到的新的函数为为原函数原函数F的反函数的反函数。即:“”“+”,“0”“1”,原变量原变量 反变量反变量29第29页，本讲稿共94页 注意注意:使用反

22、演规则时，应保持原函数式中运算符号的优先顺序不变！三、对偶规则三、对偶规则如 果 将 逻 辑 函 数 表 达 式 F中 所 有 的“”变变 成成“+”,“+”变成变成“”，“0”变变成成“1”，“1”变变成成“0”，并并保保持持原原函函数中的运算顺数中的运算顺序不变序不变，则所得到的新的逻辑表达式称为函数F的对偶式，并记作F。例如，例如，已知函数，根据反演规则得到的反函数应该是而不应该是！错误！错误30第30页，本讲稿共94页注注意意:求求逻逻辑辑表表达达式式的的对对偶偶式式时时，同同样样要要保保持持原原函函数数的的运算顺序不变。运算顺序不变。显然，利用对偶规则可以使定理、公式的证明减少一半。

23、若两个逻辑函数表达式若两个逻辑函数表达式F和和G相等，则其对偶式相等，则其对偶式F和和G也相等。这一规则称为对偶规则。也相等。这一规则称为对偶规则。根据对偶规则，当已证明某两个逻辑表达式相等时，即可知道它们的对偶式也相等。例如，已知AB+C+BC=AB+C，根据对偶规则对等式两端的表达式取对偶式，即可得到等式(A+B)(+C)(B+C)=(A+B)(+C)31第31页，本讲稿共94页2.2.3 2.2.3 复合复合逻辑逻辑 实际应用中广泛采用“与非”门、“或非”门、“与或非”门、“异或”门等门电路。这这些些门门电电路路输输出出和和输输入入之之间间的的逻逻辑辑关关系系可可由由3 3种种基基本本运

24、运算算构构成成的的复复合合运运算算来来描描述述，故故通通常常将这种逻辑关系称为将这种逻辑关系称为复合逻辑复合逻辑，相应的逻辑门则称为，相应的逻辑门则称为复合门复合门。一、与非逻辑一、与非逻辑与非逻辑是由与、非两种逻辑复合形成的，可用逻辑函数表示为逻辑逻辑功能功能：只要只要变变量量A A、B B、C C、中有一个中有一个为为0 0，则则函数函数F F为为1 1；仅仅当当变变量量A A、B B、C C、全部全部为为1 1时时，函数，函数F F为为0 0。实现实现与非与非逻辑逻辑的的门电门电路称路称为为“与非与非”门门。32第32页，本讲稿共94页只要有了与非门便可组成实现各种逻辑功能的电路，通常称

25、与非门为通用通用门门。与与:或或:非非:使用与非门可以实现与、或、非三种基本运算：33第33页，本讲稿共94页二二、或非或非逻辑逻辑逻逻辑辑功功能能：只要变量A、B、C中有一个为1，则函数F为0；仅当变量A、B、C全部为0时，函数F为1。实现或非逻辑的门电路称为“或非或非”门门。或非逻辑是由或、非两种逻辑复合形成由或、非两种逻辑复合形成的，可表示为 与：与：或或:非非:或非门同样可实现各种逻辑功能，是一种通用通用门门。或非逻辑也可以实现与、或、非3种基本逻辑。34第34页，本讲稿共94页三、与或非三、与或非逻辑逻辑逻辑逻辑功能：功能：仅当每一个“与项”均为0时，才能使F为1，否则F为0。实现与

26、或非功能的门电路称为“与或非与或非”门门。可以仅用与或非门去组成实现各种功能的逻辑电路。但实际应用中这样做一般会很不经济，所以，与或非门主要用与或非门主要用来实现与或非形式的函数来实现与或非形式的函数。必要时可将逻辑函数表达式的形式变换成与或非的形式。与或非逻辑是由3种基本逻辑复合形成的，逻辑函数表达式的形式为 35第35页，本讲稿共94页四、异或四、异或逻辑逻辑及同或及同或逻辑逻辑逻辑逻辑功能：功能：变量变量A A、B B取值相同，取值相同，F F为为0 0；变量；变量A A、B B取值取值相异，相异，F F为为1 1。实现异或运算的逻辑门称为“异或异或门门”。1 1异或逻辑异或逻辑当多个变

27、量进行异或运算时，可用两两运算的结果再运算，也可两两依次运算。异或逻辑是一种两两变变量量逻辑逻辑关系关系，可用逻辑函数表示为 根据异或逻辑的定义可知：A 0=AA 0=AA 1=A 1=A A=0A A=0A =1 A =1 36第36页，本讲稿共94页注注意意：在在进进行行异异或或运运算算的的多多个个变变量量中中，若若有有奇奇数数个个变变量量的的值值为为1 1，则则运运算算结结果果为为1 1；若若有有偶偶数数个个变变量量的的值值为为1 1，则则运运算算结果为结果为0 0。例如，F=A B C D=(A B)(C D)(两两运算的结果再运算)=(A B)C D(两两依次运算)2 2同或同或逻辑

28、逻辑同或逻辑也是一种两变量逻辑关系，其逻辑函数表达式为 功功能能逻逻辑辑：变量A、B取值相同，F为1；变量A、B取值相异，F为0。实现同或运算的逻辑门称为“同或同或门门”。F=A B=+AB F=A B=+AB 式中，“”为同或运算的运算符。37第37页，本讲稿共94页同同或或逻逻辑辑与与异异或或逻逻辑辑的的关关系系既既互互为为相相反反，又又互互为为对对偶偶。即有：由于同或实际上是异或之非，所以实际应用中通通常常用用异或门加非门实现同或运算异或门加非门实现同或运算。注注意意：当当多多个个变变量量进进行行同同或或运运算算时时，若若有有奇奇数数个个变变量量的的值值为为0，则则运运算算结结果果为为0

29、；反反之之，若若有有偶偶数数个个变变量量的的值值为为0，则运算结果为则运算结果为1。38第38页，本讲稿共94页2.3 2.3 逻辑逻辑函数表达式的形式与函数表达式的形式与变换变换任何一个逻辑函数，其表达式的形式都不是唯一的。下面介绍逻辑函数表达式的基本形式、标准形式及其相互转换。基本形式、标准形式及其相互转换。2.3.1 2.3.1 逻辑逻辑函数表达式的函数表达式的两种两种基本形式基本形式 两种基本形式：指两种基本形式：指“与与-或或”表达式和表达式和“或或-与与”表达式表达式。一一、“与与-或或”表达式表达式 “与与-或或”表表达达式式：是是指指由由若若干干“与与项项”进进行行“或或”运运

30、算构成的表达式。例如，算构成的表达式。例如，“与项与项”有时又被称为有时又被称为“积项积项”，相应地，相应地“或或与与”表达式又称为表达式又称为“积之和积之和”表达式。表达式。39第39页，本讲稿共94页二、二、“或或-与与”表达式表达式 “或或项项”有有时时又又被被称称为为“和和项项”，相相应应地地“或或与与”表达式又称为表达式又称为“和之积和之积”表达式。表达式。“或或-与与”表表达达式式：是是指指由由若若干干“或或项项”进进行行“与与”运运算算构成的表达式。例如，构成的表达式。例如，40第40页，本讲稿共94页该函数既不是该函数既不是“与与或或”式？也不是式？也不是“或或与与”式！式！2

31、.3.2 2.3.2 逻辑逻辑函数表达式的函数表达式的标标准形式准形式 逻辑函数表达式可以被表示成任意的混合形式。例如，逻辑函数的基本形式都不是唯一的。逻辑函数的基本形式都不是唯一的。例如为了在逻辑问题的研究中使逻辑功能能和唯一的逻辑表达式对应，引入了逻辑函数表达式的标准形式。逻辑函数表达式的标准形式是建立在最最小小项项和最最大大项项概念的基础之上的。41第41页，本讲稿共94页一、最小一、最小项项和最大和最大项项 （1）定定义义：如果一个具有n个变量的函数的“与项”包含全部n个变量，每个变量都以原变量或反变量形式出现一次，且仅出现一次，则该“与项”被称为最最小小项项。有时又将最小项称为标准标

32、准“与项与项”。1最小项最小项（3）简写：）简写：用mi表示最小项。下标下标i的取值规则是：的取值规则是：按照变量顺序将最小项中的原变量用1表示，反变量用0表示，由此得到一个二进制数，与该二进制数对应的十进制数即下标i的值。（2）最小项的数目：）最小项的数目：n个变量可以构成2n个最小项。例如，3个变量A、B、C可以构成、ABC共8个最小项。42第42页，本讲稿共94页在由n个变量构成的任意“与项”中，最小项是使其值为1的变量取值组合数最少的一种“与项”，这也就是最小项名字的由来。（4）性质性质 最小项具有如下四条性质。性质性质1：任意一个最小项，其相应变量有且仅有一种取任意一个最小项，其相应

33、变量有且仅有一种取值使这个最小项的值为值使这个最小项的值为1。并且，最小项不同，使其值为。并且，最小项不同，使其值为1的的变量取值不同。变量取值不同。例如，3变量A、B、C构成的最小项AC可用m5表示。因为m5(5)10101AC43第43页，本讲稿共94页性质性质3：n个变量的全部最小项相“或”为1。通常借用数学中的累加符号“”，将其记为性质性质2：相同变量构成的两个不同最小项相相同变量构成的两个不同最小项相“与与”为为0。因为任何一种变量取值都不可能使两个不同最小项同时为1，故相“与”为0。即mimj=0性质性质4：n个变量构成的最小项有个变量构成的最小项有n个相邻最小项。个相邻最小项。相

34、邻最小项：相邻最小项：是指除一个变量互为相反外，其余部分均相同的最小项。例如，三变量最小项ABC和相邻。44第44页，本讲稿共94页定定义义：如果一个具有n个变量函数的“或项”包含全部n个变量，每个变量都以原变量或反变量形式出现一次，且仅出现一次，则该“或项”被称为最大项。有时又将最大项称为标准“或项”。2 2最大项最大项数目：数目：n个变量可以构成个变量可以构成2n 个最大项。个最大项。例如，3个变量A、B、C可构成、共8个最大项。45第45页，本讲稿共94页性质：性质：最大项具有如下四条性质。性性质质1任意一个最大项，其相应变量有且仅有一种取值使这个最大项的值为0。并且，最大项不同，使其值

35、为0的变量取值不同。简写：用简写：用Mi表示最大项。表示最大项。下标下标i的取值规则是的取值规则是：将最大项中的原变量用0表示，反变量用1表示，由此得到一个二进制数，与该二进制数对应的十进制数即下标i的值。例如，3变量A、B、C构成的最大项可用M5表示。因为M5(5)10101在n个变量构成的任意“或项”中，最大项是使其值为1的变量取值组合数最多的一种“或项”，因而将其称为最大项。最大项。46第46页，本讲稿共94页性质性质2相同变量构成的两个不同最大项相相同变量构成的两个不同最大项相“或或”为为1。因为任何一种变量取值都不可能使两个不同最大项同时为0，故相“或”为1。即Mi+Mj=1性性质质

36、3n个个变变量量的的全全部部最最大大项项相相“与与”为为0。通常借用数学中的累乘符号“”将其记为性性质质4 n个个变变量量构构成成的的最最大大项项有有n个个相相邻邻最最大大项项。相邻最大项是指除一个变量互为相反外，其余变量均相同的最大项。47第47页，本讲稿共94页两变量最小项、最大项的真值表如下。m2 000101001000M3 M2 M 1 M 0 m 3 m1m 0 001011101101101101110 00 11 01 1A B最最 大大 项项 最最 小小 项项 变变 量量 2变量最小项、最大项真值表变量最小项、最大项真值表真值表反映了最小项、最大项的有关性质。48第48页，本

37、讲稿共94页3最小项和最大项的关系最小项和最大项的关系 在同一问题中，下标相同的最小项和最大项互为反函数。在同一问题中，下标相同的最小项和最大项互为反函数。或者说，相同变量构成的最小项mi和最大项Mi之间存在互补关系。即或者例如，由3变量A、B、C构成的最小项m3和最大项M3之间有49第49页，本讲稿共94页二、二、逻辑逻辑函数表达式的函数表达式的标标准形式准形式 逻辑函数表达式的标准形式有标标准准“与与-或或”表表达达式式和和标准标准“或或-与与”表达式表达式两种类型两种类型。1标准标准“与与-或或”表达式表达式由由若若干干最最小小项项相相“或或”构构成成的的逻逻辑辑表表达达式式称称为为标标

38、准准“与与-或或”表达式，也叫做最小项表达式。表达式，也叫做最小项表达式。该函数表达式又可简写为F(A，B，C)=m1+m2+m4+m7=例如，如下所示为一个3变量函数的标准“与-或”表达式50第50页，本讲稿共94页2标准标准“或或-与与”表达式表达式由由若若干干最最大大项项相相“与与”构构成成的的逻逻辑辑表表达达式式称称为为标标准准“或或-与与”表达式，也叫做最大项表达式表达式，也叫做最大项表达式。该表达式又可简写为例如，、为3变量构成的3个最大项，对这3个最大项进行“与”运算，即可得到一个3变量函数的标准“或-与”表达式51第51页，本讲稿共94页2.3.3 2.3.3 逻辑逻辑函数表达

39、式的函数表达式的转换转换 将一个任意逻辑函数表达式转换成标准表达式有两种常用方法。一、代数转换法一、代数转换法 1.求标准求标准“与与-或或”式式一般步骤如下：一般步骤如下：第一步第一步：将函数表达式变换成一般“与-或”表达式。所谓代数转换法，就是利用逻辑代数的公理、定理和规所谓代数转换法，就是利用逻辑代数的公理、定理和规则进行逻辑变换，将函数表达式从一种形式变换为另一种形则进行逻辑变换，将函数表达式从一种形式变换为另一种形式。式。第二步：第二步：反复使用将表达式中所有非最小项的“与项”扩展成最小项。52第52页，本讲稿共94页例例 将逻辑函数表达式将逻辑函数表达式 转换成标准转换成标准“与与

40、-或或”表达式。表达式。解解 第一步：第一步：将函数表达式变换成“与-或”表达式。即第第二二步步：把“与-或”式中非最小项的“与项”扩展成最小项。53第53页，本讲稿共94页所得标准“与-或”式的简写形式为当给出函数表达式已经是“与-或”表达式时，可直接进行第二步。2.求一个函数的标准求一个函数的标准“或或-与与”式式一般步骤：一般步骤：第一步：第一步：将函数表达式转换成一般“或-与”表达式。第二步：第二步：反复利用定理把表达式中所有非最大项的“或项”扩展成最大项。54第54页，本讲稿共94页解解 第一步：第一步：将函数表达式变换成“或-与”表达式。即例例 将逻辑函数表达式变换成标准“或-与”

41、表达式。=155第55页，本讲稿共94页第第二二步步：将所得“或-与”表达中的非最大项扩展成最大项。即当给出函数已经是“或-与”表达式时，可直接进行第二步。该标准“或-与”表达式的简写形式为56第56页，本讲稿共94页二、真值表转换法二、真值表转换法 具具体体：真真值值表表上上使使函函数数值值为为1的的变变量量取取值值组组合合对对应应的的最最小项相小项相“或或”,即可构成一个函数的标准即可构成一个函数的标准“与与-或或”式式。逻辑函数的最小项表达式与真值表具有一一对应的关系。逻辑函数的最小项表达式与真值表具有一一对应的关系。假定函数假定函数F的真值表中有的真值表中有k组变量取值使组变量取值使F

42、的值为的值为1，其他，其他变量取值下变量取值下F的值为的值为0，那么，函数，那么，函数F的最小项表达式由这的最小项表达式由这k组组变量取值对应的变量取值对应的k个最小项相或组成。个最小项相或组成。1.求标准求标准“与与-或或”式式57第57页，本讲稿共94页1 0 0 11 0 1 10 1 1 0A B C F1 1 0 11 1 1 00 0 0 00 1 0 10 0 1 0函数的真值表解解:首先，列出F的真值表如下表所示，然后，根据真值表可直接写出F的最小项表达式例例 将函数表达式变换成标准“与-或”表达式。58第58页，本讲稿共94页具具体体：真真值值表表上上使使函函数数值值为为0的

43、的变变量量取取值值组组合合对对应应的的最最大项相大项相“与与”即可构成一个函数的标准即可构成一个函数的标准“或或-与与”式式。2.求一个函数的标准求一个函数的标准“或或-与与”式式逻辑函数的最大项表达式与真值表之间同样具有一一逻辑函数的最大项表达式与真值表之间同样具有一一对应的关系。对应的关系。假定在函数F的真值表中有p组变量取值使F的值为0，其他变量取值下F的值为1，那么，函数F的最大项表达式由这p组变量取值对应的p个最大项“相与”组成。59第59页，本讲稿共94页解：解：首先，列出F的真值表如下表所示。然后，根据真值表直接写出F的最大项表达式函数的真值表101001110100100111

44、101100ABC F00000011例例 将函数表达式表示成最大项表达式的形式。60第60页，本讲稿共94页由于函数的真值表与函数的两种标准表达式之间存在一一对应的关系，而任何个逻辑函数的真值表是唯一的，可见，任何一个逻辑函数的两种标准形式也是唯一的任何一个逻辑函数的两种标准形式也是唯一的。逻辑函数表达式的唯一性给我们分析和研究逻辑问题带来了很大的方便。61第61页，本讲稿共94页2.4 2.4 逻辑逻辑函数化函数化简简实现某一逻辑功能的逻辑电路的复杂性与描述该功能的实现某一逻辑功能的逻辑电路的复杂性与描述该功能的逻辑表达式的复杂性直接相关。逻辑表达式的复杂性直接相关。为了降低系统成本、减小

45、复杂度、提高可靠性，必须对为了降低系统成本、减小复杂度、提高可靠性，必须对逻辑函数进行化简。逻辑函数进行化简。由于“与-或”表达式和“或-与”表达式可以很方便地转换成任何其他所要求的形式。因此，从这两种基本形式出发讨论函数化简问题，并将重点放在“与-或”表达式的化简上。逻逻辑辑函函数数化化简简有有3种种常常用用方方法法。即即：代代数数化化简简法法、卡卡诺诺图化简法图化简法和列表化简法列表化简法。62第62页，本讲稿共94页2.4.1 2.4.1 代数化简法代数化简法代数化简法就是运用逻辑代数的公理、定理和规则对逻代数化简法就是运用逻辑代数的公理、定理和规则对逻辑函数进行化简的方法。辑函数进行化

46、简的方法。一、一、“与与-或或”表达式的化简表达式的化简 最简最简“与与-或或”表达式应满足两个条件：表达式应满足两个条件：1表达式中的表达式中的“与与”项个数最少；项个数最少；2在在满满足足上上述述条条件件的的前前提提下下，每每个个“与与”项项中中的的变变量量个个 数最少。数最少。满足上述两个条件可以使相应逻辑电路中所需门的数量以及门的输入端个数均为最少，从而使电路最经济。63第63页，本讲稿共94页 几种常用方法如下：几种常用方法如下：1并项法并项法2吸收法吸收法 利用定理3中A+AB=A，吸收多余的项。例如，利用定理7中的，将两个“与”项合并成一个“与”项，合并后消去一个变量。例如，64

47、第64页，本讲稿共94页3消去法消去法利用定理4中，消去多余变量。例如，4配项法配项法 利用公理4和公理5中的A1=A及A+A=1，先从函数式中适当选择某些“与”项，并配上其所缺的一个合适的变量，然后再利用并项、吸收和消去等方法进行化简。例如，65第65页，本讲稿共94页例例 化简化简解解实际应用中遇到的逻辑函数往往比较复杂，化简时应实际应用中遇到的逻辑函数往往比较复杂，化简时应灵活使用所学的公理、定理及规则，综合运用各种方法灵活使用所学的公理、定理及规则，综合运用各种方法。66第66页，本讲稿共94页例例 化简化简解解67第67页，本讲稿共94页二、二、“或或-与与”表达式的化简表达式的化简

48、 最简最简“或或-与与”表达式应满足两个条件：表达式应满足两个条件：1表达式中的表达式中的“或或”项个数最少；项个数最少；2在在满满足足上上述述条条件件的的前前提提下下，每每个个“或或”项项中中的的变变量量个数最少。个数最少。用代数化简法化简“或-与”表达式可直接运用公理、定理中的“或-与”形式，并综合运用前面介绍“与-或”表达式化简时提出的各种方法进行化简。68第68页，本讲稿共94页例例 化简化简解解此外，可以采用两次对偶法两次对偶法。具体如下：具体如下：第一步：第一步：对对“或或-与与”表达式表示的函数表达式表示的函数F求对偶，得求对偶，得到到“与与-或或”表达式表达式F；第二步：第二步

49、：求出求出F的最简的最简“与与-或或”表达式；表达式；第三步：第三步：对对F再次求对偶再次求对偶,即可得到即可得到F的最简的最简“或或-与与”表达式。表达式。69第69页，本讲稿共94页例例 化简化简第二步：第二步：化简化简F；第三步：第三步：对F求对偶,得到F的最简“或-与”表达式。解解 第一步：第一步：求求F的对偶式的对偶式F；70第70页，本讲稿共94页归纳：归纳：代代数数化化简简法法的的优优点点是是：不不受受变变量量数数目目的的约约束束；当当对对公公理理、定理和规则十分熟练时，化简比较方便。定理和规则十分熟练时，化简比较方便。缺缺点点是是：没没有有一一定定的的规规律律和和步步骤骤，技技

50、巧巧性性很很强强，而而且且在在很多情况下难以判断化简结果是否最简。很多情况下难以判断化简结果是否最简。71第71页，本讲稿共94页2.4.2 2.4.2 卡诺图化简法卡诺图化简法 卡诺图化简法具有简简单单、直直观观、容容易易掌掌握握等等优优点点，在逻辑设计中得到广泛应用。一、卡诺图的构成一、卡诺图的构成卡诺图是一种平面方格图，每个小方格代表一个最小项，卡诺图是一种平面方格图，每个小方格代表一个最小项，故又称为最小项方格图。故又称为最小项方格图。结构特点：结构特点：(1)n n个变量的卡诺图由2n个小方格构成；(2)几何图形上处在相邻、相对相邻、相对、相重相重位置的小方格所代表的最小项为相邻最小