《第02讲逻辑代数基础优秀课件.ppt》由会员分享，可在线阅读，更多相关《第02讲逻辑代数基础优秀课件.ppt（65页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第02讲逻辑代数基础第1页，本讲稿共65页n逻辑代数是研究数字系统逻辑设计的数学工具。逻辑代数是研究数字系统逻辑设计的数学工具。无无论何种形式的数字系统，都是由一些基本逻辑电路所论何种形式的数字系统，都是由一些基本逻辑电路所组成的。为了组成的。为了解决数字系统分析和设计解决数字系统分析和设计中的各种具体问中的各种具体问题，必须掌握题，必须掌握逻辑代数逻辑代数这一重要数学工具。这一重要数学工具。n本章知识要点本章知识要点n掌握逻辑代数的基本概念（包括变量、运算、函数掌握逻辑代数的基本概念（包括变量、运算、函数等）；等）；n能灵活运用公理、定理和规则；能灵活运用公理、定理和规则；n掌握逻辑函数的各
2、种表示形式及相互转换；掌握逻辑函数的各种表示形式及相互转换；n掌握逻辑函数化简的常用方法（重点掌握代数法和卡掌握逻辑函数化简的常用方法（重点掌握代数法和卡诺图法）。诺图法）。第2页，本讲稿共65页2.1逻辑代数的基本概念逻辑代数的基本概念n2.1.1、逻辑变量、逻辑变量逻辑代数和普通代数一样，也是用逻辑代数和普通代数一样，也是用字母表示其值可以字母表示其值可以变化的量，即变量。需注意的是：变化的量，即变量。需注意的是：1在普通代数中，变量的取值可以是任意实数，而逻辑在普通代数中，变量的取值可以是任意实数，而逻辑代数是一种二值代数系统，即代数是一种二值代数系统，即任何逻辑变量的取值只有两任何逻辑
3、变量的取值只有两种可能性种可能性-取值取值0或取值或取值1。2逻辑值逻辑值0和和1不再像普通代数中那样具有数量的不再像普通代数中那样具有数量的概念，而是用来表征矛盾的双方和判断事件真伪的概念，而是用来表征矛盾的双方和判断事件真伪的形式符号，形式符号，无大小、正负之分。无大小、正负之分。在数字系统中，开关的在数字系统中，开关的接通与断开，电压的高和低，信号的有和无，晶体管的导接通与断开，电压的高和低，信号的有和无，晶体管的导通与截止等两种稳定的物理状态，均可用通与截止等两种稳定的物理状态，均可用1和和0这两种不同这两种不同的逻辑值来表征。的逻辑值来表征。第3页，本讲稿共65页2.1.2逻辑运算逻
4、辑运算n描述一个数字系统，仅用逻辑变量的取值来反映单个开关描述一个数字系统，仅用逻辑变量的取值来反映单个开关元件的两种状态是不够的，还必须反映一个复杂系统中各元件的两种状态是不够的，还必须反映一个复杂系统中各开关元件之间的联系，这种相互联系反映到数学上就是几开关元件之间的联系，这种相互联系反映到数学上就是几种运算关系。种运算关系。逻辑代数中定义了逻辑代数中定义了“或或”、“与与”、“非非”三种基本运算。三种基本运算。n1“或或”运算运算在逻辑问题的描述中，如果决定某一事件是否发生的在逻辑问题的描述中，如果决定某一事件是否发生的多个条件中，只要有一个或一个以上条件成立，事件便多个条件中，只要有一
5、个或一个以上条件成立，事件便可发生，则这种因果关系称之为可发生，则这种因果关系称之为“或或”逻辑。逻辑。第4页，本讲稿共65页n逻辑代数中，逻辑代数中，“或或”逻辑用逻辑用“或或”运算描运算描述述。“或或”运算又称逻辑加运算又称逻辑加(Logicadition)，其运算符号为，其运算符号为“+”，有时也用，有时也用“”表示。两变量表示。两变量“或或”运算的关系可运算的关系可表示为表示为F=A+B或者或者F=AB读作读作“F等于等于A或或B”。这里，。这里，A、B是两个逻是两个逻辑变量，辑变量，F表示运算结果表示运算结果.n意思是：意思是：A、B中只要有一个为中只要有一个为1，则，则F为为1；仅
6、当；仅当A、B均为均为0时，时，F才为才为0。第5页，本讲稿共65页ABF000110110111表表2.1“或或”运算表运算表由表2.1可得出“或或”运算的运算的运算法则为运算法则为0+0=01+0=10+1=11+1=1第6页，本讲稿共65页2“与与”运算运算n在逻辑问题中，如果决定某一事件发生的多个条件必在逻辑问题中，如果决定某一事件发生的多个条件必须同时具备，事件才能发生，则这种因果关系称之须同时具备，事件才能发生，则这种因果关系称之“与与”逻辑。逻辑。在逻辑代数中，在逻辑代数中，“与与”逻辑关系用逻辑关系用“与与”运算描述。运算描述。“与与”运算又称为逻辑乘运算又称为逻辑乘(Logi
7、cMultiplication)，其运算符号为，其运算符号为“”，有时也用，有时也用“”表示。两变量表示。两变量“与与”运算关系可表示为运算关系可表示为nF=AB或者或者F=ABn读作读作“F等于等于A与与B”。意思是：若意思是：若A、B均为均为1，则，则F为为1；否则，；否则，F为为0。该逻辑关系可用表该逻辑关系可用表2.2来描述。来描述。第7页，本讲稿共65页表表2.2“与与”运算表运算表ABF000110110001由表2.2可得出“与与”运算的运运算的运算法则为算法则为0+0=01+0=00+1=01+1=1第8页，本讲稿共65页3.“非非”运算运算n在逻辑问题中，如果某一事件的发生取
8、决在逻辑问题中，如果某一事件的发生取决于条件的否定，即事件与事件发生的条件之于条件的否定，即事件与事件发生的条件之间构成矛盾，则这种因果关系称为间构成矛盾，则这种因果关系称为“非非”逻逻辑。辑。在逻辑代数中，在逻辑代数中，“非非”逻辑用逻辑用“非非”运运算描述。算描述。“非非”运算也叫求反运算或者逻辑运算也叫求反运算或者逻辑否定否定(LogicNegation)。其运算符号为。其运算符号为“-”，有时也用有时也用“”表示。“非非”运算的逻辑运算的逻辑关系可表示为关系可表示为F=A或者或者F=An读作读作“F等于等于A非非”。意思是：若意思是：若A为为0，则，则F为为1；若；若A为为1，则，则F
9、为为0。该逻辑关系可用表。该逻辑关系可用表2.3描述。描述。第9页，本讲稿共65页表表2.3“非非”运算表运算表AF01100=11=0由表由表2.3可得出可得出“非非”运算的运运算的运算法则为算法则为第10页，本讲稿共65页n1、逻辑函数的定义、逻辑函数的定义逻辑代数中函数的定义与普通代数中函数的定义极逻辑代数中函数的定义与普通代数中函数的定义极为相似，即随自变量变化的因变量。为相似，即随自变量变化的因变量。但和普通代数中函但和普通代数中函数的概念相比，逻辑函数具有它自身的特点：数的概念相比，逻辑函数具有它自身的特点：(1)逻辑函数和逻辑变量一样，取值只有逻辑函数和逻辑变量一样，取值只有0和
10、和1两种可两种可能能；(2)函数和变量之间的关系是由函数和变量之间的关系是由“或或”、“与与”、“非非”3种基本运算决定的。种基本运算决定的。2.1.3逻辑函数逻辑函数第11页，本讲稿共65页n设某一逻辑电路的设某一逻辑电路的输入逻辑变量为输入逻辑变量为A1，A2，An，输出逻辑变量输出逻辑变量为为F，如果，如果A1，A2，An的值确定后，的值确定后，F的值就唯一地被确的值就唯一地被确定下来，则定下来，则F被称为被称为A1，A2，An的逻的逻辑函数，辑函数，n记为记为F=f(A1,A2,，An)第12页，本讲稿共65页n逻辑函数和普通代数中的函数一样存在相等逻辑函数和普通代数中的函数一样存在相
11、等的问题。的问题。什么叫做两个逻辑函数相等呢什么叫做两个逻辑函数相等呢?n设有两个相同变量的逻辑函数设有两个相同变量的逻辑函数nF1=f1(A1,A2,An)nF2=f2(A1,A2,An)n若对应于逻辑变量若对应于逻辑变量A1,A2,An的任何一的任何一组取值，组取值，F1和和F2的值都相同，则称的值都相同，则称函数函数F1和和F2相等相等。记作。记作F1=F2。2、逻辑函数的相等、逻辑函数的相等第13页，本讲稿共65页n如何判断两个逻辑函数是否相等？如何判断两个逻辑函数是否相等？通常有通常有两种方法两种方法。一种方法是列出输入变。一种方法是列出输入变量所有可能的取值组合，并按逻辑运算法则量
12、所有可能的取值组合，并按逻辑运算法则计算出各种输入取值下两个函数的相应值，计算出各种输入取值下两个函数的相应值，然后进行比较。另一种方法是用逻辑代数的然后进行比较。另一种方法是用逻辑代数的公理、定理和规则进行证明。公理、定理和规则进行证明。第14页，本讲稿共65页2.2逻辑代数的公理、定理及规则逻辑代数的公理、定理及规则公理公理1交换律交换律对于任意逻辑变量对于任意逻辑变量A、B，有，有A+B=B+A；AB=BA公理公理2结合律结合律对于任意的逻辑变量对于任意的逻辑变量A、B、C，有，有(A+B)+C=A+(B+C)；(AB)C=A(BC)公理公理3分配律分配律对于任意的逻辑变量对于任意的逻辑
13、变量A、B、C，有，有A+(BC)=(A+B)(A+C)；A(B+C)=AB+AC第15页，本讲稿共65页公理公理401律律对于任意逻辑变量对于任意逻辑变量A，有，有A+0=A；A1=A；A+1=1；A0=0公理公理5互补律互补律对于任意逻辑变量对于任意逻辑变量A，存在唯一的，存在唯一的，使得，使得A+A=1AA=0第16页，本讲稿共65页重叠律重叠律 Idempotency A+A=A A A =A 对合律对合律 involution A=A吸收律吸收律 AbsorptionA+A B=A+B A (A+B)=A BA B+A B=A (A+B)(A+B)=AA+AB=A A (A+B)=A
14、基本定理基本定理：见书上P30A+B=A B A B=A+B反演律反演律DeMorgans Theorem (摩根定理摩根定理)第17页，本讲稿共65页三个规则：三个规则：（1）代入规则：）代入规则：对于任一个含有变量对于任一个含有变量A的逻辑等式，可以将等式的逻辑等式，可以将等式两边的所有变量两边的所有变量A用同一个逻辑函数替代，替代后等用同一个逻辑函数替代，替代后等式仍然成立。式仍然成立。代入规则的正确性是由逻辑变量和逻辑函数值的二代入规则的正确性是由逻辑变量和逻辑函数值的二值性保证的。值性保证的。第18页，本讲稿共65页（2）反演规则）反演规则 用于求反函数。用于求反函数。若两函数相等，
15、则其反演式也相等。若两函数相等，则其反演式也相等。（3）对偶规则）对偶规则 用于求对偶函数。用于求对偶函数。若两函数相等，则其对偶式也相等。若两函数相等，则其对偶式也相等。第19页，本讲稿共65页2.3.1逻辑函数的表示法逻辑函数的表示法2.3逻辑函数表达式的形式与变换逻辑函数表达式的形式与变换描述逻辑函数的方法并不是唯一的，常用的方法有描述逻辑函数的方法并不是唯一的，常用的方法有逻辑表达式、真值表、卡诺图逻辑表达式、真值表、卡诺图3种。种。逻辑表达式是由逻辑变量和逻辑表达式是由逻辑变量和“或或”、“与与”、“非非”3种运算符所构成的式子。种运算符所构成的式子。例如，例如，该逻辑表达式描述了一
16、个两变量的逻辑函数该逻辑表达式描述了一个两变量的逻辑函数F。函数函数F和变量和变量A、B的关系是：当变量的关系是：当变量A和和B取值不同时，取值不同时，函数函数F的值为的值为“1”；取值相同时，函数取值相同时，函数F的值为的值为“0”。1、逻辑表达式、逻辑表达式第20页，本讲稿共65页逻辑表达式的简写逻辑表达式的简写:1.进行进行“非非”运算可不加括号，如运算可不加括号，如A,A+B等等。2.“与与”运算符一般可省略，如运算符一般可省略，如AB可写成可写成AB。3.在一个表达式中，如果既有在一个表达式中，如果既有“与与”运算又有运算又有“或或”运算，则按运算，则按先先“与与”后后“或或”的规则
17、进行运算，的规则进行运算，而可省去括号，如而可省去括号，如(AB)+(CD)可写为可写为AB+CD。注意注意：(A+B)(C+D)不能省略括号，不能省略括号，即不能写成即不能写成A+BC+D！运算优先法则：运算优先法则：.由于由于“与与”运算和运算和“或或”运算均满足结合律，运算均满足结合律，因此，因此，(A+B)+C或者或者A+(B+C)可用可用A+B+C代替；代替；(AB)C或者或者A(BC)可用可用ABC代替。代替。第21页，本讲稿共65页n依次列出一个逻辑函数的所有输入变量取值组依次列出一个逻辑函数的所有输入变量取值组合及其相应函数值的表格称为真值表。合及其相应函数值的表格称为真值表。
18、由于由于一个逻辑变量只有一个逻辑变量只有0和和1两种可能的取值，故两种可能的取值，故n个逻辑变量一共只有个逻辑变量一共只有2n种可能的取值组合。任种可能的取值组合。任何逻辑函数总是和若干个逻辑变量相关的，何逻辑函数总是和若干个逻辑变量相关的，有限的变量个数使得变量取值组合的总数必有限的变量个数使得变量取值组合的总数必然是有限的，从而，能够用穷举的方法来描然是有限的，从而，能够用穷举的方法来描述逻辑函数的功能。述逻辑函数的功能。真值表由两部分组成：真值表由两部分组成：左边一栏列出变量左边一栏列出变量的所有取值组合，为了不发生遗漏，通常各的所有取值组合，为了不发生遗漏，通常各变量取值组合按二进制数
19、码顺序给出；右边变量取值组合按二进制数码顺序给出；右边一栏为逻辑函数值。例如，逻辑函数一栏为逻辑函数值。例如，逻辑函数F=AB+AC的真值表如表的真值表如表2.4所示。所示。2、真值表、真值表第22页，本讲稿共65页第23页，本讲稿共65页n3、卡诺图、卡诺图卡诺图是由表示逻辑变量所有取值组合的卡诺图是由表示逻辑变量所有取值组合的小方格所构成的平面图。它是一种用图形描小方格所构成的平面图。它是一种用图形描述逻辑函数的方法，这种方法在逻辑函数化述逻辑函数的方法，这种方法在逻辑函数化简中十分有用，将在后面结合函数化简问题简中十分有用，将在后面结合函数化简问题进行详细介绍。进行详细介绍。描述逻辑逻辑
20、函数的描述逻辑逻辑函数的3种方法各有特点，种方法各有特点，可用于不同场合。但针对某个具体问题而言，可用于不同场合。但针对某个具体问题而言，它们仅仅是同一问题的不同描述形式，相互它们仅仅是同一问题的不同描述形式，相互之间可以很方便地进行变换。之间可以很方便地进行变换。第24页，本讲稿共65页2.3.2逻辑函数表达式的基本形式逻辑函数表达式的基本形式n1、“与与-或或”表达式表达式“与与-或或”表达式：是指由若干表达式：是指由若干“与项与项”进进行行“或或”运算构成的表达式。运算构成的表达式。每个每个“与项与项”可以是可以是单个单个变量的原变量或者反变量，也可变量的原变量或者反变量，也可以由以由多
21、个多个原变量或者反变量相原变量或者反变量相“与与”组成。组成。例如，例如，n“与项与项”有时又被称为有时又被称为“积项积项”，相应地，相应地“与与-或或”表达式又称为表达式又称为“积之和积之和”表达式。表达式。第25页，本讲稿共65页n2、“或或-与与”表达式表达式“或或-与与”表达式：是指由若干表达式：是指由若干“或项或项”进行进行“与与”运算构成的表达式。运算构成的表达式。每个每个“或项或项”可以是单个变量可以是单个变量的原变量或者反变量，也可以由多个原变量或者反变量的原变量或者反变量，也可以由多个原变量或者反变量相相“或或”组成。例如，组成。例如，nn“或项或项”有时又被称为有时又被称为
22、“和项和项”，相应地，相应地“或或-与与”表达式又称为表达式又称为“和之积和之积”表达式。表达式。通常通常,逻辑函数表达式可以被表示成任意的混合形式，逻辑函数表达式可以被表示成任意的混合形式，例如，例如，n该逻辑函数是该逻辑函数是“与与-或或”式？不是！是式？不是！是“或或-与与”式？也不是！式？也不是！但不论什么形式都可以变换成两种基本但不论什么形式都可以变换成两种基本形式。形式。第26页，本讲稿共65页2.3.3逻辑函数表达式的标准形式逻辑函数表达式的标准形式n1最小项表达式最小项表达式定义：如果一个具有定义：如果一个具有n个变量的函数的个变量的函数的“与项与项”包包含全部含全部n个变量，
23、每个变量都以原变量或反变量形式个变量，每个变量都以原变量或反变量形式出现一次，且仅出现一次出现一次，且仅出现一次，则该，则该“与项与项”被称为被称为最小最小项项。有时又将最小项称为标准。有时又将最小项称为标准“与项与项”。n最小项的数目：最小项的数目：n个变量可以构成个变量可以构成2n个最小项。个最小项。简写：简写：在变量个数和变量顺序确定之后，通常用在变量个数和变量顺序确定之后，通常用mi表示表示最小项。下标最小项。下标i的取值规则是：的取值规则是：按照变量顺序将最小项按照变量顺序将最小项中的原变量用中的原变量用1表示，反变量用表示，反变量用0表示，由此得到一表示，由此得到一个二进制数，与该
24、二进制数对应的十进制数即下标个二进制数，与该二进制数对应的十进制数即下标i的值。的值。第27页，本讲稿共65页n由若干最小项相由若干最小项相“或或”构成的逻辑表达式构成的逻辑表达式称为标准称为标准“与与-或或”表达式，也叫做最小项表达式，也叫做最小项表达式。表达式。例如，如下所示为一个例如，如下所示为一个3变量函数的标准变量函数的标准“与与-或或”表达式表达式通常借用数学中的累加符号通常借用数学中的累加符号“”，该函数表达式又可简写为该函数表达式又可简写为F(A,B,C)=m1+m2+m4+m7=m(1,2,4,7)第28页，本讲稿共65页n2最大项表达式最大项表达式定义：如果一个具有定义：如
25、果一个具有n个变量的函数的个变量的函数的“或项或项”包含全部包含全部n个变量，每个变量都以原变量或反变量形个变量，每个变量都以原变量或反变量形式式出现一次，且仅出现一次，出现一次，且仅出现一次，则该则该“或项或项”被称为被称为最大最大项项。有时又将最大项称为标准。有时又将最大项称为标准“或项或项”。n数目：数目：n个变量可以构成个变量可以构成2n个最大项。个最大项。n简写：简写：在变量个数和变量顺序确定之后，通常用在变量个数和变量顺序确定之后，通常用Mi表表示最大项。下标示最大项。下标i的取值规则是：的取值规则是：将最大项中的原变量用将最大项中的原变量用0表示，反变量用表示，反变量用1表示，由
26、此得到一个二进制数，表示，由此得到一个二进制数，与该二进制数对应的十进制数即下标与该二进制数对应的十进制数即下标i的值。的值。第29页，本讲稿共65页n由若干最大项相由若干最大项相“与与”构成的逻辑表达式构成的逻辑表达式称为标准称为标准“或或-与与”表达式，也叫做最大项表达式，也叫做最大项表达式。表达式。例如，一个例如，一个3变量函数的标准变量函数的标准“或或-与与”表达式表达式通常借用数学中的累乘符号通常借用数学中的累乘符号“”，该函数表达式又可简写为该函数表达式又可简写为第30页，本讲稿共65页3最小项和最大项的关系最小项和最大项的关系n在同一问题中下标相同的最小项和最大项在同一问题中下标
27、相同的最小项和最大项互为反函数。互为反函数。或者说，相同变量构成的最或者说，相同变量构成的最小项小项mi和最大项和最大项Mi之间存在互补关系。即之间存在互补关系。即第31页，本讲稿共65页2.3.4逻辑函数表达式的转换逻辑函数表达式的转换n将一个任意逻辑函数表达式转换成标准表达式有两将一个任意逻辑函数表达式转换成标准表达式有两种常用方法，一种是种常用方法，一种是代数转换法代数转换法，另一种是另一种是真值表转真值表转换法换法。n1、代数转换法、代数转换法n所谓代数转换法，就是利用逻辑代数的公理、定理和规所谓代数转换法，就是利用逻辑代数的公理、定理和规则进行逻辑变换，将函数表达式从一种形式变换为另
28、一种则进行逻辑变换，将函数表达式从一种形式变换为另一种形式。形式。（1）.求一个函数的标准求一个函数的标准“与与-或或”表达式表达式第一步第一步：将函数表达式变换成一般将函数表达式变换成一般“与与-或或”表达式。表达式。第二步：反复使用第二步：反复使用X=X(Y+Y)将表达式中所有非最将表达式中所有非最小项的小项的“与项与项”扩展成最小项。扩展成最小项。第32页，本讲稿共65页第33页，本讲稿共65页n（2）.求一个函数标准求一个函数标准“或或-与与”表达式表达式第一步：将函数表达式转换成一般第一步：将函数表达式转换成一般“或或-与与”表达式。表达式。第二步：反复利用定理第二步：反复利用定理A
29、=(A+B)(A+B)把把表达式中所有非最大项的表达式中所有非最大项的“或项或项”扩展成扩展成最大项。最大项。第34页，本讲稿共65页第35页，本讲稿共65页n2.真值表转换法真值表转换法一个逻辑函数的真值表与它的最小项表达式具有一个逻辑函数的真值表与它的最小项表达式具有一一对应的关系。假定在函数一一对应的关系。假定在函数F的真值表中有的真值表中有k组变组变量取值使量取值使F的值为的值为1，其他变量取值下，其他变量取值下F的值为的值为0，那，那么，函数么，函数F的最小项表达式由这的最小项表达式由这k组变量取值对应的组变量取值对应的k个最小项相或组成。因此，可以通过函数的真值表个最小项相或组成。
30、因此，可以通过函数的真值表写出最小项表达式。写出最小项表达式。（1）.求函数的标准求函数的标准“与与-或或”式式具体：真值表上使函数值为具体：真值表上使函数值为1的变量取值组合对的变量取值组合对应的最小项相应的最小项相“或或”即可构成一个函数的标准即可构成一个函数的标准“与与-或或”式。式。第36页，本讲稿共65页第37页，本讲稿共65页n（2）.求函数的标准求函数的标准“或或-与与”式式一个逻辑函数的真值表与它的最大项表达式之间一个逻辑函数的真值表与它的最大项表达式之间同样具有一一对应的关系同样具有一一对应的关系。假定在函数假定在函数F的真值表中的真值表中有有k组变量取值使组变量取值使F的值
31、为的值为0，其他变量取值下，其他变量取值下F的值为的值为1，那么，函数，那么，函数F的最大项表达式由这的最大项表达式由这k组变量取值对应的组变量取值对应的k个最大项个最大项“相与相与”组成。因此，可以根据真值表直接组成。因此，可以根据真值表直接写出函数最大项表达式写出函数最大项表达式。具体：真值表上使函数值为具体：真值表上使函数值为0的变量取值组合对应的的变量取值组合对应的最大项相最大项相“与与”即可构成一个函数的标准即可构成一个函数的标准“或或-与与”式。式。第38页，本讲稿共65页n由于函数的真值表与函数的两种标准表达式之间存在一一对由于函数的真值表与函数的两种标准表达式之间存在一一对应的
32、关系，而任何个逻辑函数的真值表是唯一的，所以，应的关系，而任何个逻辑函数的真值表是唯一的，所以，任何任何一个逻辑函数的两种标准形式是唯一的。一个逻辑函数的两种标准形式是唯一的。这给我们分析和研究逻这给我们分析和研究逻辑函数带来了很大的方便。辑函数带来了很大的方便。第39页，本讲稿共65页2.4逻辑函数化简逻辑函数化简n实现某一逻辑功能的逻辑电路的复杂性与描实现某一逻辑功能的逻辑电路的复杂性与描述该功能的逻辑表达式的复杂性直接相关。述该功能的逻辑表达式的复杂性直接相关。一般说，逻辑函数表达式越简单，设计出来一般说，逻辑函数表达式越简单，设计出来的相应逻辑电路也就越简单的相应逻辑电路也就越简单。然
33、而，从逻辑然而，从逻辑问题概括出来的逻辑函数通常都不是最简的。问题概括出来的逻辑函数通常都不是最简的。为了降低系统成本、减小复杂度、提高可为了降低系统成本、减小复杂度、提高可靠性，必须对逻辑函数进行化简。靠性，必须对逻辑函数进行化简。第40页，本讲稿共65页2.4.1代数化简法代数化简法n代数化简法就是运用逻辑代数的公理、定代数化简法就是运用逻辑代数的公理、定理和规则对逻辑函数进行化简的方法。这理和规则对逻辑函数进行化简的方法。这种方法没有固定的步骤可以遵循，主要取种方法没有固定的步骤可以遵循，主要取决于决于对逻辑代数中公理、定理和规则的熟对逻辑代数中公理、定理和规则的熟练掌握及灵活运用的程度
34、练掌握及灵活运用的程度。1、“与与-或或”表达式的化简表达式的化简最简最简“与与-或或”表达式应满足两个条件：表达式应满足两个条件：n1表达式中的表达式中的“与与”项个数最少；项个数最少；2满足上述条件的前提下，每个满足上述条件的前提下，每个“与与”项中的变量个数最少项中的变量个数最少。第41页，本讲稿共65页第42页，本讲稿共65页第43页，本讲稿共65页2、“或或-与与”表达式的化简表达式的化简n最简最简“或或-与与”表达式应满足两个条件：表达式应满足两个条件：n1表达式中的表达式中的“或或”项个数最少；项个数最少；2在满足上述条件的前提下，每个在满足上述条件的前提下，每个“或或”项中项中
35、的变量个数最少。的变量个数最少。用代数化简法化简用代数化简法化简“或或-与与”表达式可直接运用公理、表达式可直接运用公理、定理中的定理中的“或或-与与”形式，并综合运用前面介绍形式，并综合运用前面介绍“与与-或或”表达式化简时提出的各种方法进行化简。表达式化简时提出的各种方法进行化简。第44页，本讲稿共65页n当对于公理、定理中的当对于公理、定理中的“或或-与与”形式不太形式不太熟悉时，可以采用熟悉时，可以采用两次对偶法两次对偶法,具体如下：具体如下：n第一步第一步:对用对用“或或-与与”表达式表示的函数表达式表示的函数F求对偶，得到求对偶，得到“与与-或或”表达式表达式F；第二步第二步:求出
36、求出F的最简的最简“与与-或或”表达式；表达式；第三步第三步:对对F再次求对偶，得到再次求对偶，得到F的最简的最简“或或-与与”表达式。表达式。第45页，本讲稿共65页n归纳：归纳：优点优点：不受变量数目的约束，当对公理、定理和不受变量数目的约束，当对公理、定理和规则十分熟练时化简比较方便。规则十分熟练时化简比较方便。缺点：缺点：没有一定的规律和步骤，技巧性很强，而且在没有一定的规律和步骤，技巧性很强，而且在很多情况下难以判断化简结果是否最简。很多情况下难以判断化简结果是否最简。第46页，本讲稿共65页2.4.2卡诺图化简法卡诺图化简法n卡诺图化简法又称为卡诺图化简法又称为图形化简法图形化简法
37、。该方法简单、直观、容。该方法简单、直观、容易掌握，因而在逻辑设计中得到广泛应用。易掌握，因而在逻辑设计中得到广泛应用。1.卡诺图的构成卡诺图的构成卡诺图是一种平面方格图，每个小方格代表一个最卡诺图是一种平面方格图，每个小方格代表一个最小项，故又称为小项，故又称为最小项方格图最小项方格图。n（1）结构特点）结构特点卡诺图中最小项的排列方案不是唯一的，图卡诺图中最小项的排列方案不是唯一的，图25(a)、(b)、(c)、(d)分别为分别为2变量、变量、3变量、变量、4变量、变量、5变量卡诺图的一种变量卡诺图的一种排列方案。图中，排列方案。图中，变量的坐标值变量的坐标值0表示相应变量的反变量，表示相
38、应变量的反变量，1表示相应变量的原变量。各小方格依变量顺序取坐标值，表示相应变量的原变量。各小方格依变量顺序取坐标值，所得二进制数对应的十进制数即相应最小项的下标所得二进制数对应的十进制数即相应最小项的下标i。在在五变量五变量卡诺图中，为了方便省略了符号卡诺图中，为了方便省略了符号“m”，直接标出直接标出m的下标的下标i。第47页，本讲稿共65页第48页，本讲稿共65页n从图从图2.5所示的各卡诺图可以看出，卡诺图上变量的排列规律使最小项所示的各卡诺图可以看出，卡诺图上变量的排列规律使最小项的相邻关系能在图形上清晰地反映出来。具体地说，的相邻关系能在图形上清晰地反映出来。具体地说，在在n个变量
39、的卡个变量的卡诺图中，能从图形上直观、方便地找到每个最小项的诺图中，能从图形上直观、方便地找到每个最小项的n个相邻最个相邻最小项。小项。以四变量卡诺图为例，图中每个最小项应有以四变量卡诺图为例，图中每个最小项应有4个相邻最小项，如个相邻最小项，如m5的的4个相邻最小项分别是个相邻最小项分别是m1，m4，m7，m13，这，这4个最小项对应的个最小项对应的小方格与小方格与m5对应的小方格分别相连，也就是说在几何位置上是相邻的，对应的小方格分别相连，也就是说在几何位置上是相邻的，这种相邻称为这种相邻称为几何相邻几何相邻。而。而m2则不完全相同，它的则不完全相同，它的4个相邻最小个相邻最小项除了与之几
40、何相邻的项除了与之几何相邻的m3和和m6之外，另外两个是处在之外，另外两个是处在“相对相对”位置的位置的m0(同一列的两端同一列的两端)和和m10(同一行的两端同一行的两端)。这种相。这种相邻似乎不太直观，但只要把这个图的上、下边缘连接，卷成圆邻似乎不太直观，但只要把这个图的上、下边缘连接，卷成圆筒状，便可看出筒状，便可看出m0和和m2在几何位置上是相邻的。同样，把图在几何位置上是相邻的。同样，把图的左、右边缘连接，便可使的左、右边缘连接，便可使m2和和m10相邻。通常把这种相邻相邻。通常把这种相邻称为称为相对相邻相对相邻。除此之外，还有。除此之外，还有“相重相重”位置的最小项相邻，如位置的最
41、小项相邻，如五变量卡诺图中的五变量卡诺图中的m3，除了几何相邻的，除了几何相邻的m1，m2，m7和相对相和相对相邻的邻的m11外，还与外，还与m19相邻。对于这种情形，可以把卡诺图左边相邻。对于这种情形，可以把卡诺图左边的矩形重叠到右边矩形之上来看，凡上下重叠的最小项相邻，这的矩形重叠到右边矩形之上来看，凡上下重叠的最小项相邻，这种相邻称为种相邻称为重叠相邻。重叠相邻。第49页，本讲稿共65页n归纳起来，卡诺图在构造上具有以下两个特点归纳起来，卡诺图在构造上具有以下两个特点：n个变量的卡诺图由个变量的卡诺图由2n个小方格组成，每个小方格代表个小方格组成，每个小方格代表一个最小项；一个最小项；卡
42、诺图上处在相邻、相对、相重位置的小方格所代表的卡诺图上处在相邻、相对、相重位置的小方格所代表的最小项为相邻最小项。最小项为相邻最小项。由于两个相邻最小项只有一个变量不同且互为反变量，因而由于两个相邻最小项只有一个变量不同且互为反变量，因而两个相邻最小项合并后可以消去一个变量。也就是说卡诺图两个相邻最小项合并后可以消去一个变量。也就是说卡诺图上两个相邻的小方格合并可以消去一个变量；四个相邻的小上两个相邻的小方格合并可以消去一个变量；四个相邻的小方格合并可以消去二个变量；八个相邻的小方格合并可以消方格合并可以消去二个变量；八个相邻的小方格合并可以消去三个变量；十六个相邻的小方格合并可以消去四个变量
43、；去三个变量；十六个相邻的小方格合并可以消去四个变量；。这就是用卡诺图化简逻辑函数的原理。这就是用卡诺图化简逻辑函数的原理。第50页，本讲稿共65页2逻辑函数在卡诺图上的表示逻辑函数在卡诺图上的表示n（1）给定逻辑函数为标准）给定逻辑函数为标准“与与-或或”表达式表达式当逻辑函数为标准当逻辑函数为标准“与与-或或”表达式时，只需在卡诺图上表达式时，只需在卡诺图上找出和表达式中最小项对应的小方格填上找出和表达式中最小项对应的小方格填上1，其余小方格填，其余小方格填上上0，即可得到该函数的卡诺图。，即可得到该函数的卡诺图。例如，例如，3变量函数变量函数F(A,B,C)=m(1,2,3,7)的卡诺图
44、如图的卡诺图如图26所示。所示。第51页，本讲稿共65页n（2）逻辑函数为一般）逻辑函数为一般“与与-或或”表达式表达式当逻辑函数为一般当逻辑函数为一般“与与-或或”表达式时，可根据表达式时，可根据“与与”的的公共性和公共性和“或或”的叠加性作出相应卡诺图。的叠加性作出相应卡诺图。n例如，例如，4变量函数变量函数F(A,B,C,D)=AB+CD+ABC的卡的卡诺图如图诺图如图27所示。所示。填写该函数卡诺图时，只需在填写该函数卡诺图时，只需在4变量卡诺变量卡诺图上依次找出和图上依次找出和“与项与项”AB、CD、ABC对应的小方格填上对应的小方格填上1，便可得到该函数的，便可得到该函数的卡诺图。
45、卡诺图。当逻辑函数表达式为其他形式时，可将当逻辑函数表达式为其他形式时，可将其变换成上述形式后再作卡诺图。其变换成上述形式后再作卡诺图。为了叙述的方便，通常将卡诺图上填为了叙述的方便，通常将卡诺图上填1的小方格称为的小方格称为1方格方格，填，填0的小方格称为的小方格称为0方格方格。0方格有时用空格表示。方格有时用空格表示。第52页，本讲稿共65页3卡诺图上最小项的合并规律卡诺图上最小项的合并规律n卡诺图的一个重要特征是，它从图形上直观、清晰地反映了最小项的相卡诺图的一个重要特征是，它从图形上直观、清晰地反映了最小项的相邻关系。当一个函数用卡诺图表示后，究竟哪些最小项可以合并呢？下邻关系。当一个
46、函数用卡诺图表示后，究竟哪些最小项可以合并呢？下面以面以2、3、4变量卡诺图为例予以说明。变量卡诺图为例予以说明。n（1）两个小方格相邻）两个小方格相邻,或处于某行或处于某行(列列)两端时，所代表的最小两端时，所代表的最小项可以合并，合并后可消去一个变量。项可以合并，合并后可消去一个变量。n例如，图例如，图2.8给出了给出了2变量卡诺图上两个相邻最小项合并的典型变量卡诺图上两个相邻最小项合并的典型情况的。情况的。第53页，本讲稿共65页n（2）四个小方格组成一个大方格、或组成一行（列）、四个小方格组成一个大方格、或组成一行（列）、或处于相邻两行（列）的两端、或处于四角时，所的表的最或处于相邻两
47、行（列）的两端、或处于四角时，所的表的最小项可以合并，合并后可消去两个变量。小项可以合并，合并后可消去两个变量。例如，图例如，图2.9给出了给出了3、4变量卡诺图上四个相邻最小项合变量卡诺图上四个相邻最小项合并的典型情况的。并的典型情况的。第54页，本讲稿共65页n（3）八个小方格组成一个大方格、或组成相邻的两行（列）、或处于）八个小方格组成一个大方格、或组成相邻的两行（列）、或处于两个边行（列）时，所代表的最小项可以合并，合并后可消去三个变量。两个边行（列）时，所代表的最小项可以合并，合并后可消去三个变量。例如，图例如，图210给出了给出了3、4变量卡诺图上八个相邻最小项合并的典变量卡诺图上
48、八个相邻最小项合并的典型情况的。型情况的。至此，以至此，以3、4变量卡诺图为例，讨论了变量卡诺图为例，讨论了2，4，8个最小项的合并个最小项的合并方法。依此类推，不难得出方法。依此类推，不难得出n个变量卡诺图中最小项的合并规律。个变量卡诺图中最小项的合并规律。第55页，本讲稿共65页n归纳起来，归纳起来，n个变量卡诺图中最小项的合并规律如个变量卡诺图中最小项的合并规律如下：下：（1）卡诺圈中小方格的个数必须为）卡诺圈中小方格的个数必须为2m个，个，m为小为小于或等于于或等于n的整数。的整数。（2）卡诺圈中的）卡诺圈中的2m个小方格有一定的排列规律，具体个小方格有一定的排列规律，具体地说，它们含
49、有地说，它们含有m个不同变量，个不同变量，(n-m)个相同变量。个相同变量。（3）卡诺圈中的）卡诺圈中的2m个小方格对应的最小项可用个小方格对应的最小项可用(n-m)个变量的个变量的“与与”项表示，该项表示，该“与与”项由这些最小项中的相项由这些最小项中的相同变量构成。同变量构成。（4）当）当m=n时，卡诺圈包围了整个卡诺图，可用时，卡诺圈包围了整个卡诺图，可用1表表示，即示，即n个变量的全部最小项之和为个变量的全部最小项之和为1。第56页，本讲稿共65页n4.卡诺图化简逻辑函数的步骤卡诺图化简逻辑函数的步骤n（1）求函数最简）求函数最简“与与-或或”表达式表达式用卡诺图化简逻辑函数可按下列步
50、骤进行：用卡诺图化简逻辑函数可按下列步骤进行：n将逻辑函数用卡诺图表示出来。将逻辑函数用卡诺图表示出来。n首先圈出没有相邻最小项的孤立的值为首先圈出没有相邻最小项的孤立的值为1的最小项方的最小项方格，这是一个主要项。格，这是一个主要项。n找出只有一种合并可能的值为找出只有一种合并可能的值为1的最小项方格，从它出发的最小项方格，从它出发将所有为将所有为1的相邻最小项按的相邻最小项按2的整数次幂为一组构成卡诺圈，的整数次幂为一组构成卡诺圈，所有圈中必须至少有一个为所有圈中必须至少有一个为1的最小项方格没有被圈过，并的最小项方格没有被圈过，并使所有的圈尽可能大。使所有的圈尽可能大。n写出最简的函数表