《主析取范式的求法》PPT课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第一章 命题逻辑,第七讲,定义,对于给定的命题公式，如果有一个等价公式,仅由小项的析取所组成，则该等价式称为原式的,主析,取范式。,内容回顾,小项,定义,n,个命题变元的合取式，称为布尔合取或小项，其中每个变元与它的否定不能同时存在，但两者必须出现且仅出现一次。,每个小项可用,n,位二进制编码表示。以变元自身出现的用,1,表示，以其否定出现的用,0,表示：,小项的性质如下：,（,1,）每一个小项当其真值指派与编码相同时，其真值为,1,，其余的,2,n,1,种均为,0;,（,2,）任意两个不同小项的合取式永假：,（,3,）全体小项的析取式永为真，记为：,主析取范式的求法,真值表法,等值演算法,趣味推理题,A,、,B,、,C,三人去餐馆吃饭，他们每人要的不是火腿就是猪排。（,1,）如果,A,要的是火腿，那么,B,要的就是猪排。（,2,）,A,或,C,要的是火腿，但是不会两人都要火腿。（,3,）,B,和,C,不会两人都要猪排。谁昨天要的是火腿，今天要的是猪排？,只有,B,才能昨天要火腿，今天要猪排。,1,5,4,主合取范式,定义,1-,n,个命题变元的析取式，称为布尔析取或极大项，其中每个变元与它的否定不能同时存在，但两者必须出现且仅出现一次。,例如，,2,个命题变元,p,和,Q,的大项为：,3,个命题变元,p,、,Q,、,R,的大项为：,n,个命题变元共有,2,n,个大项，每个大项可表示为,n,位二进制编码，以变元自身出现的用,0,表示，以变元的否定出现的用,1,表示；且对应十进制编码。这一点与小项的表示刚好相反。,若,n,=2,，则有,若,n,=3,，则有,:,大项的性质如下：,(1),每一个大项当其真值指派与编码相同时，其真值为,0,，其余的,2,n,1,种赋值均为,1;,(2),任意两个不同大项的析取式永真：,(3),全体大项的合取式必为假，记为：,定义,1-,对于给定的命题公式，如果有一个等价公式仅由极大项的合取所组成，则该等价式称为原式的主合取范式。,定理,1-,（主合取范式存在惟一定理）任何命题公式的主合取范式一定存在，并且惟一。,由真值表方法可,知,：一个公式的真值为,0,的真值指派所对应的大项的合取，即为此公式的主合取范式。,例,1-,用真值表方法求,的主合取范式,解,:,公式的真值表如下,P Q R,P,Q,R,(,p,Q)R,0 0 0,0 0 1,0 1 0,0 1 1,1 0 0,1 0 1,1 1 0,1 1 1,1,1,1,1,0,0,1,1,1,0,1,0,1,0,1,0,1,0,1,0,1,1,1,0,所以公式 的主合取范式为,:,用等值演算方法构成主合取范式的主要步骤如下：,（,1,）将原命题公式化归为合取范式；,（,2,）除去合取范式中所有永真的合取项；,（,3,）合并相同的析取项和相同的变元；,（,4,）对合取项补入没有出现的命题变元，即添加如,(,p,p,),的式子，再按分配律进行演算；,（,5,）将大项按下标由小到大的顺序排列。,例,1-,用等值演算方法求 的主合取范式。,解：,【,说明,】,(1),主析取范式的析取项为小项，用小,m,加下标表示。如,m,010,，,其中,0,表示对应的命题变元的否定出现在析取项中,1,表示对应的命题变元出现在析取项中。,(2),主合取范式的合取项为大项,用大,M,加下标表示,如,M,010,其中,0,表示对应的命题变元出现在合取项中,1,表示对应命题变元的否定出现在合取项中。,(3),在真值表中,一个公式的主析取范式由其真值为,1,的真值指派所在对应的小项的析取组成。,(4),在,真值表,中,一个公式的,主合取范式由其,真值为,0,的真值指派所对应的大项的合取所组成。,极小项与极大项,由,p,q,两个命题变项形成的极小项与极大项,公式,成真赋值,名称,公式,成假赋值,名称,p,q,p,q,p,q,p,q,0 0,0 1,1 0,1 1,m,0,m,1,m,2,m,3,p,q,p,q,p,q,p,q,0 0,0 1,1 0,1 1,M,0,M,1,M,2,M,3,极小项,极大项,由,p,q,r,三个命题变项形成的极小项与极大项,极小项,极大项,公式,成真,赋值,名称,公式,成假,赋值,名称,p,q,r,p,q,r,p,q,r,p,q,r,p,q,r,p,q,r,p,q,r,p,q,r,0 0 0,0 0 1,0 1 0,0 1 1,1 0 0,1 0 1,1 1 0,1 1 1,m,0,m,1,m,2,m,3,m,4,m,5,m,6,m,7,p,q,r,p,q,r,p,q,r,p,q,r,p,q,r,p,q,r,p,q,r,p,q,r,0 0 0,0 0 1,0 1 0,0 1 1,1 0 0,1 0 1,1 1 0,1 1 1,M,0,M,1,M,2,M,3,M,4,M,5,M,6,M,7,1.6,蕴含公式,如果双条件命题,AB,为重言式，则,A B,。而条件命题,AB,是不对称的，如果,A,B,为真，,B,不一定能推出,A,。那么,A,和,B,究竟存在什么关系呢？,1,6,1,蕴含公式,定义,1-26,设,A,，,B,是命题公式,若,A,B,是重言式,则称,A,B,是蕴含重言式，记为,A,B,，,读作“,A,永真蕴含,B,”,。简称,A,蕴含,B,即,AB,iff,A,B,1,注意,:,与,是意义不同的符号。,证明：,所以,P(pQ)Q,下面介绍几种证明,A,永真蕴含,B,的方法。,方法一：用真值表法或等价变换,(,推导,),法证明,A,B,1,。,例,1-24,证明 。,P Q PQ P,(PQ)(P,(PQ)Q,0 0,0 1,1 0,1 1,1,1,0,1,0,0,0,1,1,1,1,1,方法二：通过分析的方法来证明一个条件命题是蕴含式。由于原命题等于其逆反命题，即,ABBA,，所以用分析法证明,AB,，有如下两种方法,:,(1),假设前件,A,为真时,推出后件,B,也为真,则,AB,;,(2),假设后件,B,为假时,推出前件,A,也为假,则,AB,。,例,1-25,证法,1,：,证法,2,：,例,1-26,如果我认真学习，我的“离散数学”不会不及格，,如果我不热衷于玩电子游戏，我将认真学习，,但我的“离散数学”不及格。,结论：我热衷于玩电子游戏。,证明：设,P,：我认真学习。,Q,：我的“离散数学”及格。,R,：我热衷于玩电子游戏。,常见的蕴含重言式,析取三段论,假言推论,拒取式,假言三段论,二难推论,化简式一,附加式,化简式二,例,1-27,分析证明 。,证明：假设后件 为,0,，则,P,为,1,，,R,为,0,。,(a),若,Q,为,1,，则 为,0,，所以 为,0,；,(b),若,Q,为,0,，则 为,0,，所以 为,0,。,故此：成立。,1,6,2,蕴含公式的性质,（,1,）设,A,、,B,是命题公式，若,A,B,且,A,为重言式，则,B,必是重言式。,证明,:,因为,A,B,，所以,A,B,为,1,，又因为,A,为,1,，所以,B,为,1,，即,B,为重言式。,（,2,）蕴含关系是传递的，即,A,B,且,B,C,，则,A,C,。,1.8,推理理论,逻辑学的主要任务是提出一套推理规则，按照公认的推理规则从前提集合中推导出一个结论来，这个推理过程称为演绎或形式证明。,在一般的论证中，主要是根据实践经验。如果确认前提为真，并遵守恰当的推理规则，则可期望所得的结论也是真的。倘若认定前提是真的，从前提推导出结论的论证是遵守逻辑推理规则，且公认此结论是真实的，则这个论证称为合法论证。一般论证中必须特别注意论证的合法性。,所谓合法是指前提和结论都符合客观实际情况，大家公认是真实的。即合情、合理、合法，令人信服。,在数理逻辑中情况稍有不同，它把注意力集中在推理规则的研究上，如果依据这些推理规则，从前提推导出来的任何结论都称为有效结论，这种论证称为有效论证。在确认论证有效性时，前提与结论的真实性不起任何作用，也就是说，在数理逻辑中，只关心论证的有效性，而不大关心论证的合法性。,前提,：,如果马会飞或羊吃草，则母鸡就会是飞鸟；如果母鸡是飞鸟，那么烤熟的鸭子还会跑；烤熟的鸭子不会跑。,结论,：,羊不吃草。,蕴含式的定义是：给定两个命题公式,A,和,B,，当且仅当,A,B,是一个重言式，则称,A,蕴含,B,，记为,A,B,，又称,B,是,A,的有效结论或,B,由,A,逻辑推出。这个定义可以推广到有,n,个前提的情况。,定义,1-27,设 是命题公式，当且仅当,则称,C,是前提集合 的有效结论。,判别有效结论的过程就是论证的过程，论证方法千变万化，但基本方法是真值表法、直接证法和间接证法。,（一）真值表法,设 是出现的前提集合 和,C,中的所有命题分量，假定对 作全部的真值指派就能确定 和,C,的真值，那么通过真值表就可以确定结论,C,是否是前提集合的有效论证，这个方法称为真值表法。,利用真值表判别一个有效论证的方法：,方法一：,在真值表上，若前提,H,1,H,2,H,3,H,n,均为真的所有行，结论,C,也为真，则论证有效。,方法二：,在真值表上，若结论,C,为假的每一行，其前提,H,1,H,2,H,3,H,n,中至少有一个为假，则论证有效。,例,1-28,如果我认真学习，我的“离散数学”不会不及格，,如果我不热衷于玩电子游戏，我将认真学习，,但我的“离散数学”不及格。,结论：我热衷于玩电子游戏。,P:,我认真学习，,Q:,我的“离散数学”及格，,R:,我热衷于玩电子游戏。,符号化为：,其真值表如下：,解：,判断法一：真值表中，只有第,2,行的前提都为,1,，其结论也为,1,，所以论证有效。,判断法二：真值表中，第,1,、,3,、,5,、,7,行为,0,，每行的前提至少有一个为,0,，所以论证有效。,P Q R,R,p,Q,Rp,Q,R,0 0 0,0 0 1,0 1 0,0 1 1,1 0 0,1 0 1,1 1 0,1 1 1,1,0,1,0,1,0,1,0,1,1,1,1,0,0,1,1,0,1,0,1,1,1,1,1,1,1,0,0,1,1,0,0,0,1,0,1,0,1,0,1,p,q,pq,p,q,0,0,1,1,1,0,1,1,1,0,1,0,0,0,1,1,1,1,0,0,（二）构造证明法,(1),推理规则,常用的推理规则有：,P,规则：,在推导的任意一步都可以引入一个前提。,T,规则：,如果公式,S,等价于或被重言蕴含在一个或多个前提或中间结果命题中，则推导中可以引入,S,。,CP,规则：,如果能从,R,及一组前提推导出,C,，则可从这组前提推导出,R,C,。,设前提,若,则,(2),推理定律,在推导过程除推理规则外,还需要推理定律,这些推理定律就是前面所讲的常用的蕴含式（用,I,表示）和命题定律（用,E,表示）。现在将蕴含式和命题定律再次显示如下。,化简,1,附加,化简,2,化简,2,假言推论,拒取式,假言三段论,二难推论,联结词归化,（,3,）推理方法,直接证明法,利用推理规则和已知的等价式和蕴含式，从前提集合中直接推导出有效结论。,例,1-29,证明,证明：,P,T(1)E,11,联结词归化,P,T(2)(3)I,13,假言三段论,T(4)E,14,P,T(5)(6)I,13,假言三段论,T(7)E,11,联结词归化,老歌经典大全 http:/