《数字逻辑课件第7章状态化简ppt.ppt》由会员分享，可在线阅读，更多相关《数字逻辑课件第7章状态化简ppt.ppt（40页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用7.3 状态化简状态化简 通过原始状态图就可以得到一张原始状态表。通过原始状态图就可以得到一张原始状态表。通过原始状态图就可以得到一张原始状态表。通过原始状态图就可以得到一张原始状态表。本节提出的问题是：这张状态表中的状态数是不是本节提出的问题是：这张状态表中的状态数是不是本节提出的问题是：这张状态表中的状态数是不是本节提出的问题是：这张状态表中的状态数是不是最少？这直接关系到电路的繁简和优化。最少？这直接关系到电路的繁简和优化。最少？这直接关系到电路的繁简和优化。
2、最少？这直接关系到电路的繁简和优化。当采用硬件描述语言建模时，关系到当采用硬件描述语言建模时，关系到当采用硬件描述语言建模时，关系到当采用硬件描述语言建模时，关系到PLDPLD器件器件器件器件中逻辑资源的有效占用。中逻辑资源的有效占用。中逻辑资源的有效占用。中逻辑资源的有效占用。为求得最简状态表，需要我们将等价的状态从为求得最简状态表，需要我们将等价的状态从为求得最简状态表，需要我们将等价的状态从为求得最简状态表，需要我们将等价的状态从原始状态表中解析出来，进行化简后形成一张最简原始状态表中解析出来，进行化简后形成一张最简原始状态表中解析出来，进行化简后形成一张最简原始状态表中解析出来，进行化
3、简后形成一张最简状态表（最小状态表）。状态表（最小状态表）。状态表（最小状态表）。状态表（最小状态表）。经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用 所所谓谓状状态态化化简简，就就是是采采用用某某种种化化简简技技术术从从原原始始状状态态表表中中消消去去多多余余状状态态，得得到到一一个个既既能能正正确确描描述述给给定定的的逻逻辑辑功功能能，又又能能使使所所包包含含的的状状态态数目达到最少的状态表数目达到最少的状态表最小状态表。最小状态表。最小状态表。最小状态表。最常用的化简方法最常用的化简方法隐含表法隐含表法经
4、营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用7.3.1 7.3.1 完全给定同步时序电路状态表的化简完全给定同步时序电路状态表的化简完全给定同步时序电路状态表的化简完全给定同步时序电路状态表的化简 完完完完全全全全给给给给定定定定同同同同步步步步时时时时序序序序电电电电路路路路状状状状态态态态表表表表的的的的化化化化简简简简，是是是是利利利利用状态之间的用状态之间的用状态之间的用状态之间的等效关系等效关系等效关系等效关系进行的。进行的。进行的。进行的。完全给定同步时序电路是指其状态表中的所有完全给定同步时序电路
5、是指其状态表中的所有完全给定同步时序电路是指其状态表中的所有完全给定同步时序电路是指其状态表中的所有次态及输出都是确定的。次态及输出都是确定的。次态及输出都是确定的。次态及输出都是确定的。经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用 假设状态假设状态假设状态假设状态S SA A和和和和S SB B是完全给定同步时序电路状态是完全给定同步时序电路状态是完全给定同步时序电路状态是完全给定同步时序电路状态表中的两个状态，如果对于所有可能的输入序列，表中的两个状态，如果对于所有可能的输入序列，表中的两个状态，如果对于
6、所有可能的输入序列，表中的两个状态，如果对于所有可能的输入序列，分别从分别从分别从分别从S SA A和和和和S SB B出发，所得到的输出响应序列完全相出发，所得到的输出响应序列完全相出发，所得到的输出响应序列完全相出发，所得到的输出响应序列完全相同，则两个状态是等效（等价）的，称同，则两个状态是等效（等价）的，称同，则两个状态是等效（等价）的，称同，则两个状态是等效（等价）的，称S SA A和和和和S SB B为等为等为等为等效对，记作：（效对，记作：（效对，记作：（效对，记作：（S SA A，S SB B）。）。）。）。所有可能的输入序列，指输入序列的长度和结所有可能的输入序列，指输入序列
7、的长度和结所有可能的输入序列，指输入序列的长度和结所有可能的输入序列，指输入序列的长度和结构是任意的。构是任意的。构是任意的。构是任意的。状态等效状态等效有有 关关 概概 念念经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用 从从整整体体上上讲讲，原原始始状状态态表表已已经经反反映映了了各各状状态态在在任意输入序列下的输出。任意输入序列下的输出。等效状态可以合并为一个状态，这种合并不会等效状态可以合并为一个状态，这种合并不会改变电路的外部特性。改变电路的外部特性。等效状态的三个特点：等效状态的三个特点：对称性：若
8、（对称性：若（SA，SB），则（），则（SB，SA)。自反性：对任何状态，（自反性：对任何状态，（SA，SA）。）。传递性：若（传递性：若（SA，SB）且（）且（SB，SC），则（），则（SA，SC）。）。经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用若干彼此等价的状态构成的集合。若干彼此等价的状态构成的集合。由（由（SA，SB）和（）和（SB，SC），可以推出（），可以推出（SA，SC），），进而可知进而可知SA、SB、SC属于同一等价类，记作：属于同一等价类，记作：（SA，SB），），（SB，SC）SA，S
9、B，SC 在等效关系中，等效对是狭义的概念，针对两个状态在等效关系中，等效对是狭义的概念，针对两个状态而言。等效类是广义的概念，针对若干个状态而言，甚至而言。等效类是广义的概念，针对若干个状态而言，甚至一个状态可称为等效类。一个状态可称为等效类。等等 效效 类类经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用不是任何其它等效类子集的等效类称为最大等效类。不是任何其它等效类子集的等效类称为最大等效类。完完完完全全全全给给给给定定定定同同同同步步步步时时时时序序序序电电电电路路路路原原始始状状态态表表的的化化简简过过
10、程程，就就是是寻寻找找最最大大等等效效类类，将将每每个个最最大大等等价价类类中中的的所所有有状状态态合合并为一个新状态，从而得到并为一个新状态，从而得到最小状态表最小状态表最小状态表最小状态表的过程。的过程。化简后的状态数等于最大等效类的个数。化简后的状态数等于最大等效类的个数。最大等效类最大等效类经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用 判断原始状态表中两个状态是否判断原始状态表中两个状态是否 等效（等价）等效（等价）的标准：的标准：如果两个状态，对每一位可能的输入都满足下如果两个状态，对每一位可能的输
11、入都满足下列两个条件，则这两个状态等效。列两个条件，则这两个状态等效。第一，它们的输出完全相同。第一，它们的输出完全相同。第二，它们的次态属于下列情况之一：第二，它们的次态属于下列情况之一：1）次态相同）次态相同 2）次态交错或者次态维持）次态交错或者次态维持 3）后继状态等效）后继状态等效 4）次态循环次态循环经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用S1S2S4S3输入输入/输出输出0/00/01/01/0次态相同次态相同S4S3S1,S21/00/0在原始状态图上判别状态的等效在原始状态图上判别状态的
12、等效经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用S1S2S3输入输入/输出输出0/00/01/01/0次态交错次态交错S3S1,S21/00/0经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用S1S2S3输入输入/输出输出0/00/01/01/0次态维持次态维持S3S1,S21/00/0经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用S1S2S3,
13、S4S50/00/01/11/11/00/1S1,S2S3,S4S50/01/11/00/1S1S2S4S3S50/00/01/11/11/01/00/10/1后继状态等效后继状态等效经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用S1S2S3S4S6S5次态循环次态循环0/00/01/11/11/01/00/10/11/11/10/00/0S1,S2S3,S4S5,S60/00/01/11/10/11/0经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品
14、的价款或接受服务的费用在原始状态表中判断状态的等效在原始状态表中判断状态的等效输出不相等，则不等效。例如：输出不相等，则不等效。例如：C和和D输出相等时：输出相等时：1）次态相等，等效。如状态）次态相等，等效。如状态D 和和E等效；等效；2）次态交错，等效。如状态）次态交错，等效。如状态A 和和B等效；等效；3）后继状态等效，等效。此例）后继状态等效，等效。此例 中中B和和C是否等效，要看是否等效，要看E和和 D是不是等效，因为是不是等效，因为E和和D等等 效，所以效，所以B和和C等效。等效。根据等效的传递性可知，根据等效的传递性可知，A和和B等效，等效，B和和C等效，则等效，则A和和C等效等
15、效等效对等效对：(A,B)(B,C)(A,C)(D,E)最大等效类最大等效类:A,B,CD,E等效类：等效类：A,B,CD,E经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用 将所有最大等效类重新命名，令：将所有最大等效类重新命名，令：S1=A，B，C S2=D，E 则可得到化简后的状态表则可得到化简后的状态表（最小化状态表）：（最小化状态表）：S1S2化简后的状态图：化简后的状态图：经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用
16、利用隐含表进行利用隐含表进行利用隐含表进行利用隐含表进行完全完全给定同步时序电路状态表的化简给定同步时序电路状态表的化简给定同步时序电路状态表的化简给定同步时序电路状态表的化简1）作隐含表）作隐含表2）寻找等效对）寻找等效对3）求出最大等效类）求出最大等效类 注意：注意：a)各最大等效类之间不应出现相同状态各最大等效类之间不应出现相同状态 b)原始状态表中的每一个状态必须属于某一个最原始状态表中的每一个状态必须属于某一个最 大等效类大等效类4）作出最小化状态表）作出最小化状态表一般步骤：一般步骤：一般步骤：一般步骤：经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，
17、增加赔偿的金额为消费者购买商品的价款或接受服务的费用隐含表隐含表 隐含表是用来标注原始状态表中所有的状态对之间，按照隐含表是用来标注原始状态表中所有的状态对之间，按照等效的判定条件进行等效的判定条件进行“状态对状态对”比较的一种表格。比较的一种表格。隐含表是一个直角三角形阶梯表，两直角边的网格数相同，隐含表是一个直角三角形阶梯表，两直角边的网格数相同，它等于原始状态表中的状态数减它等于原始状态表中的状态数减 1，用状态名进行顺序标注。，用状态名进行顺序标注。纵坐标从上到下标注且纵坐标从上到下标注且“缺头缺头”（缺少第一个状态）；横坐标从（缺少第一个状态）；横坐标从左到右标注且左到右标注且“少尾
18、少尾”（缺少最后一个状态）。横纵坐标交汇的（缺少最后一个状态）。横纵坐标交汇的每个方格代表一个状态对。每个方格代表一个状态对。经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用 例例1：化简图示状态表。化简图示状态表。1）作隐含表）作隐含表2）求等效对）求等效对 顺序比较顺序比较 所有所有“状态对状态对”逐一检查、比较。逐一检查、比较。等效：方格内画等效：方格内画 ；不等效：方格内画不等效：方格内画 x;与其它状态对有关：方格内填写相关状态对。与其它状态对有关：方格内填写相关状态对。BEBCBEXXXXXX经营者提
19、供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用等效对为：等效对为：（B，C），（），（D，E）关联比较关联比较 若相关状态对都等效，则方格对应的状态对等效。不增若相关状态对都等效，则方格对应的状态对等效。不增加标志。加标志。若相关状态对有一个不等效，则方格对应的状态对不等若相关状态对有一个不等效，则方格对应的状态对不等效。画效。画/。BEBCBEXXXXXX经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用3）求出最大等效类）求出最大等效类
20、利用等效状态的对称性、自反性、传递性，求出等效类。利用等效状态的对称性、自反性、传递性，求出等效类。B,C，D,E，A。等效类等效类 B，C，D，E，A 均不包含在任何其他等效类中，均不包含在任何其他等效类中，所以所以 A，B，C，D，E 是最大等价类。是最大等价类。4）作最小化状态表）作最小化状态表令令S1=A，S2=B，C，S3=D，E经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用例例2：化简图示原始状态表：化简图示原始状态表现态现态次态次态/输出输出输入输入X=0输入输入X=1AC/0B/1BF/0A/1
21、CF/0G/0DD/1E/0EC/0E/1FC/0G/0GC/1D/0BCDEFGABCDEFCFXXXXXXXXXXXXXXXXBEAECFCDDE请同学自己求出最大等效类、作出最小状态表请同学自己求出最大等效类、作出最小状态表因为因为CF等效，所以等效，所以AB等效等效CF等效且等效且AE,BE次态次态循环，所以循环，所以AE等效，等效，BE也等效。也等效。经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用作业：作业：P263265 5.4 5.7（用（用Verilog HDL建模）建模）补充题：补充题：1）画
22、出满足下列要求的序列检测器原始状态）画出满足下列要求的序列检测器原始状态 图和最简状态表。图和最简状态表。输入输入X:0 0 1 0 1 0 1 1 0 1输出输出Z:0 0 0 0 1 0 1 0 0 12）画出）画出3位二进制码的串行奇偶检测器的原始状位二进制码的串行奇偶检测器的原始状 态图态图和最简状态表和最简状态表。输入为。输入为X，每三位一组，每三位一组，其中其中“1”的个数为偶数时，输出的个数为偶数时，输出Z=1，否则，否则 Z=0。经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用7.3.2 7.3.
23、2 不完全给定同步时序电路状态表的化简不完全给定同步时序电路状态表的化简不完全给定同步时序电路状态表的化简不完全给定同步时序电路状态表的化简特点：原始状态图（表）中含有无关状态特点：原始状态图（表）中含有无关状态化简：如何利用无关态化简：如何利用无关态 硬件描述语言中的硬件描述语言中的if_else语句和语句和case语句的语句的default分支可以有效的处理无关状态。分支可以有效的处理无关状态。所以，传统的所以，传统的不完全给定同步时序电路状态表的不完全给定同步时序电路状态表的不完全给定同步时序电路状态表的不完全给定同步时序电路状态表的化简化简化简化简方法不作为教学要求，但课件保留，供学生
24、自学方法不作为教学要求，但课件保留，供学生自学时参考。时参考。经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用 当原始状态表中含有不确定的次态或输出，即含有无关当原始状态表中含有不确定的次态或输出，即含有无关项（项（d）,它所对应的电路称为它所对应的电路称为不完全给定同步时序电路。不完全给定同步时序电路。不完全给定同步时序电路。不完全给定同步时序电路。例如，用四位触发器构成十进制计数器时，只需要例如，用四位触发器构成十进制计数器时，只需要16个状态中的个状态中的10个，在原始状态表中有个，在原始状态表中有6个状态
25、的次态被标注个状态的次态被标注为无关项（无关态）。为无关项（无关态）。若若将将非非完完全全描描述述状状态态表表变变为为完完全全描描述述状状态态表表，当当有有n个个无无关关项项，就就会会有有2n张张状状态态表表，化化简简后后会会有有2n个个繁繁简简不不同同的的结果。因此，需要有新的逻辑工具简化设计过程。结果。因此，需要有新的逻辑工具简化设计过程。非非完全描述状态表的化简是建立在完全描述状态表的化简是建立在完全描述状态表的化简是建立在完全描述状态表的化简是建立在状态相容状态相容状态相容状态相容基础上的。基础上的。基础上的。基础上的。7.3.2 7.3.2 不完全给定同步时序电路状态表的化简不完全给
26、定同步时序电路状态表的化简不完全给定同步时序电路状态表的化简不完全给定同步时序电路状态表的化简经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用 假设状态假设状态假设状态假设状态S SA A和和和和S SB B是非完全描述状态表中的两个状态，如果是非完全描述状态表中的两个状态，如果是非完全描述状态表中的两个状态，如果是非完全描述状态表中的两个状态，如果对于对于对于对于所有的有效输入序列所有的有效输入序列所有的有效输入序列所有的有效输入序列，分别从，分别从，分别从，分别从S SA A和和和和S SB B出发，所得到的
27、输出出发，所得到的输出出发，所得到的输出出发，所得到的输出响应序列（除不确定的那些位之外）完全相同，则两个状态是响应序列（除不确定的那些位之外）完全相同，则两个状态是响应序列（除不确定的那些位之外）完全相同，则两个状态是响应序列（除不确定的那些位之外）完全相同，则两个状态是相容的，记为（相容的，记为（相容的，记为（相容的，记为（S SA A，S SB B）。或者说，状态）。或者说，状态）。或者说，状态）。或者说，状态S SA A和和和和S SB B是相容对。是相容对。是相容对。是相容对。状态相容状态相容有效输入序列：有效输入序列：有效输入序列：有效输入序列：从状态表中的状态从状态表中的状态从状
28、态表中的状态从状态表中的状态S S出发，如果给定某输入序列所得到的出发，如果给定某输入序列所得到的出发，如果给定某输入序列所得到的出发，如果给定某输入序列所得到的状态响应除最后一个次态外，其他次态都是确定的，那么，这状态响应除最后一个次态外，其他次态都是确定的，那么，这状态响应除最后一个次态外，其他次态都是确定的，那么，这状态响应除最后一个次态外，其他次态都是确定的，那么，这个输入序列对状态个输入序列对状态个输入序列对状态个输入序列对状态S S是有效的。是有效的。是有效的。是有效的。所有的有效输入序列：所有的有效输入序列：所有的有效输入序列：所有的有效输入序列：指有效输入序列的长度和结构是任意
29、的。指有效输入序列的长度和结构是任意的。指有效输入序列的长度和结构是任意的。指有效输入序列的长度和结构是任意的。经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用现态现态次态次态/输出输出输入输入X=0输入输入X=1AA/dd/dBC/1B/0CD/0d/1Dd/dB/dEA/0C/1非完全描述原始状态表非完全描述原始状态表对于状态对于状态B输入序列输入序列0010是有效的，因为它是有效的，因为它产生的次态响应序列是产生的次态响应序列是CDBC，是，是确定的。确定的。而输入序列而输入序列0100是无效的，因为是无效
30、的，因为它产生的次态响应序列是它产生的次态响应序列是C?，是不确定的是不确定的。相容状态不具有传递性。相容状态不具有传递性。即即：若若（S1,S2）,（S1,S3）是是相相容容对对，不不一一定定有有S2和和S3相容。相容。因因为为在在判判断断两两个个状状态态是是否否相相容容时时，不不确确定定的的输输出出和不定的次态可以随意指定。和不定的次态可以随意指定。经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用若干彼此相容的状态构成的集合。若干彼此相容的状态构成的集合。相容类相容类例如：有相容对例如：有相容对(S1,S2)
31、,(S2,S3),(S1,S3)，可构成相容类可构成相容类 S1,S2,S3.不是任何其它相容类子集的相容类。不是任何其它相容类子集的相容类。由于相容状态无传递性，同一原始状态表的各最大相由于相容状态无传递性，同一原始状态表的各最大相容类之间可能存在相同状态。容类之间可能存在相同状态。最大相容类最大相容类经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用判别原始状态表中两个状态是否判别原始状态表中两个状态是否 相容的标准：相容的标准：如果两个状态，对每一位可能的输入都满足下列两个如果两个状态，对每一位可能的输入都满
32、足下列两个条件，则这两个状态相容。条件，则这两个状态相容。第一，它们的输出相同（一方输出给定，一方输出为第一，它们的输出相同（一方输出给定，一方输出为 无关项，均当作相同）。无关项，均当作相同）。第二，它们的次态属于下列情况之一：第二，它们的次态属于下列情况之一：1）次态相同）次态相同 2）次态交错或者次态维持）次态交错或者次态维持 3）后继状态相容）后继状态相容 4）次态循环次态循环 （注：一方给定，一方不给定的次态均当作相同）（注：一方给定，一方不给定的次态均当作相同）经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服
33、务的费用用用用用隐含表法隐含表法隐含表法隐含表法进行进行进行进行非完全描述状态表非完全描述状态表非完全描述状态表非完全描述状态表的化简的一般步骤：的化简的一般步骤：的化简的一般步骤：的化简的一般步骤：1）作隐含表，寻找相容状态对。）作隐含表，寻找相容状态对。2）利用完全图（状态合并图），求出最大相容类。）利用完全图（状态合并图），求出最大相容类。完全图是一种将完全图是一种将非完全描述状态表非完全描述状态表的状态，以的状态，以“点点”的形式均匀的形式均匀地绘在圆周上，然后把所有相容对用线段连接起来，得到的图。地绘在圆周上，然后把所有相容对用线段连接起来，得到的图。在在这这种种图图中中，所所有有点
34、点之之间间都都有有连连线线的的多多边边形形，构构成成一一个个最最大大相容类。相容类。S1S2S3S1,S2,S3S1S2S3S4S1,S2,S3,S4S1S2S3S4S5S1,S2,S3,S4,S5经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用3）利用闭覆盖表，求最小闭覆盖。）利用闭覆盖表，求最小闭覆盖。从从最最大大相相容容类类（或或相相容容类类）中中选选出出一一个个相相容容类类的的集集合合，它必须满足以下三个条件。它必须满足以下三个条件。a)覆盖性，包含原始状态表的全部状态。覆盖性，包含原始状态表的全部状态。
35、b)最小性，相容类个数最少。最小性，相容类个数最少。c)闭闭合合性性，所所选选相相容容类类集集合合中中的的任任一一相相容容类类，在在原原始始 状状态态表表中中任任一一输输入入条条件件下下产产生生的的次次态态应应该该属属于于该该集集合合中的某一个相容类。中的某一个相容类。非非完完全全描描述述状状态态表表的的化化简简，就就是是寻寻找找一一个个最最小小闭闭覆覆盖盖。将将其其中中的的每每个个相相容容类类用用一一个个新新的的状状态态符符号号表表示示，代代入入原始状态表中，得到最小化状态表。原始状态表中，得到最小化状态表。4）作出最小化状态表。）作出最小化状态表。经营者提供商品或者服务有欺诈行为的，应当按
36、照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用 例例1：试化简图示的原始状态表试化简图示的原始状态表解：解：1）画隐含表求相容对：）画隐含表求相容对：列出相容对：列出相容对：（A，B），（A，C），（A，D），（A，E），（B，D），（），（C，D），（），（C，E）。）。经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用2）做完全图求最大相容类：）做完全图求最大相容类：最大相容类有：最大相容类有：A，B，D，A，C，E，A，C，D。相相容容对对：（A，B），（A，C），（
37、A，D），（A，E），（B，D），（），（C，D），（），（C，E）。）。经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用3）做闭合覆盖表求最小闭合覆盖：）做闭合覆盖表求最小闭合覆盖：覆盖覆盖闭合闭合相容类相容类根据最小覆盖下的次态转移，进行闭合检查：根据最小覆盖下的次态转移，进行闭合检查：X=0时，（时，（A，B，D）次态转移为）次态转移为AC，属于（，属于（A,C,E）;（A，C，E）次态转移为）次态转移为AD，属于（，属于（A,B,D）；）；X=1时，均为单态转移，属于最小覆盖中的一个相容类。时，均为单态转
38、移，属于最小覆盖中的一个相容类。所以，最小闭合覆盖成立。所以，最小闭合覆盖成立。由于状态由于状态B仅属于（仅属于（A,B,D）状态状态E仅属于（仅属于（A,C,E）选择选择（A，B，D）和和（A，C，E）为最小覆盖。为最小覆盖。经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用4）画出最简状态表：）画出最简状态表：令：令：S1=（A，B，D），），S2=（A，C，E）最简状态表最简状态表原始状态表原始状态表经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的
39、价款或接受服务的费用 例例2：试化简图示的原始状态表：试化简图示的原始状态表解：解：1）画隐含表求相容对：）画隐含表求相容对：列出相容对：列出相容对：（A，B），（A，C），（A，D），（A，E），（B，C），（），（C，D），（），（D，E）。）。经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用2）做完全图求最大相容类：）做完全图求最大相容类：最大相容类有：最大相容类有：（A，B，C），），（A，C，D），），（A，D，E）。）。经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加
40、赔偿的金额为消费者购买商品的价款或接受服务的费用3）做闭合覆盖表求最小闭合覆盖：）做闭合覆盖表求最小闭合覆盖：覆盖覆盖闭合闭合相容类相容类选选择择（A，B，C）和和（A，D，E）为为最最小小覆覆盖盖，检检查查次次态态转转移移：X=0时时，（A，B，C）转转移移为为DE，属属于于（A，D，E）；但但（A，D，E）转转移移为为CD，而而CD不不属属最最小小覆覆盖盖中中的的某某一一个个相相容容类类。所以，最小闭合覆盖不成立。所以，最小闭合覆盖不成立。经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用覆盖覆盖闭合闭合相容类
41、相容类选选择择（A，B，C）和和（D，E）为为最最小小覆覆盖盖，检检查查次次态态转转移移：X=0时时，（A，B，C）转转移移为为DE，（D，E）转转移移为为C，为为单单态态转转移移；X=1时时的的次次态态转转移移为为AB，BC，同同属属最最小小覆覆盖中的某一个相容类。最小闭合覆盖成立。盖中的某一个相容类。最小闭合覆盖成立。修修正正：去去掉掉（A，D，E）中中的的重重复复状状态态A，用用相相容容对对代代替替最最大大相相容容类类，得下表：得下表：经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用4）画出最简状态表：）画
42、出最简状态表：令：令：S1=（A，B，C），），S2=（D，E）最简状态表最简状态表原始状态表原始状态表经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用注意：注意：选择全部最大相容类组成相容类集，不一定能满足最小化的选择全部最大相容类组成相容类集，不一定能满足最小化的要求；（例要求；（例1、例、例2）选择部分最大相容类组成相容类集，有可能不满足闭合性要选择部分最大相容类组成相容类集，有可能不满足闭合性要求；（例求；（例2）适当选择最大相容类、相容类组成相容类集，可以得到最小适当选择最大相容类、相容类组成相容类集，可以得到最小化状态表。（例化状态表。（例2）