离散数学(第3讲)命题逻辑3.ppt

栾新成四川大学软件学院luanxch8599782213808024081,第1章命题逻辑(3),主要内容,联结词的完备集析取范式、合取范式、主析取（主合取）范式、极小项、极大项的定义求主析取范式和主合取范式的方法真值表法等价变换法,2020年6月14日,2,1.4联结词的完备集,根据对含两个命题变元的公式的解释方式看，共有2*2=4种不同的选择性，因而公式的真值表相应有2*2*2*2=16种可能结果。,2020年6月14日,3,联结词的完备集,定义设P和Q是命题公式，分别称PQ和PQ为“与非”和“或非”命题公式。其相应的真值表如下,2020年6月14日,4,联结词的完备集,由真值表可以看出PQ（PQ）,PQ（PQ）根据联结词和的定义，有下面的等价式。PP（PP）P(PQ)(PQ)(PQ)PQ(PP)(QQ)PQ（PQ）PQPP（PP）P(PQ)(PQ)(PQ)PQ(PP)(QQ)PQ（PQ）PQ可由和表示出来，可由和表示出来，反过来，和都可以单独表示出所有已知联结词,2020年6月14日,5,联结词的完备集,定义联结词“”,称为条件否定，其真值表如下：,2020年6月14日,6,条件联结词“”的否定形式，即有PQ(PQ),联结词的完备集,至此我们定义了9个联结词，其中1个一元联结词，8个二元联结词。那么，还能不能定义出新的联结词呢？9个联结词就是全部可以定义的联结词。这9个联结词之间还有着内在的联系。例如,可用和表达，可用,和表示,可用、和表达,可用和表达,可用和表达,可用和表达。,2020年6月14日,7,联结词的完备集,定义设S是由某些联结词构成的集合，如果每个逻辑联结词的功能都能够由S中的联结词实现，则称S是联结词的一个功能完备集；进一步，如果去掉S中的任何一个联结词后，至少有一个联结词的功能不能由S中剩余的联结词实现时，则称S是逻辑联结词的一个最小功能完备集。根据定义,，构成了逻辑联结词的一个功能完备集，此外，根据和满足的恒等式来看,或都能单独表达,和,从而和也是功能完备集，而且、是最小的功能完备集。，是不是最小功能完备集？,2020年6月14日,8,1.5命题公式的范式表示,一个命题公式可有无穷多个和它等价的命题公式，用真值表或等价变换证明它们是否等价，往往比较困难，甚至连计算机也不能解决，要解决判定问题，可用范式(公式的标准型)。范式全名叫规范型式normalform,又叫标准型式,正规型式。把公式进行标准化，正规化，就叫对公式求范式。,2020年6月14日,9,定义,定义命题变元或命题变元的否定称为句节。有限个句节的析取式称为子句；有限个子句的合取式称为合取范式有限个句节的合取式称为短语。有限个短语的析取式称为析取范式；,2020年6月14日,10,定义,例、是句节、子句、短语、析取范式、合取范式。是子句、析取范式、合取范式；(why?)是短语、析取范式、合取范式；(why?)（）（）是析取范式。（）（）是合取范式。,2020年6月14日,11,定义,句子（）仅是子句、合取范式，句子（）仅是短语、析取范式；句子（）、（）即不是析取范式也不是合取范式。但转换后：（）（）上述两式的右端即是析取范式和合取范式。,2020年6月14日,12,结论,从上述定义和例子可以得出如下关系：单个的句节是一个子句、短语、析取范式、合取范式。单个的子句是合取范式、单个的短语是析取范式。若省略外层括号，单个的子句也是析取范式，单个的短语也是合取范式。析取范式、合取范式仅含联结词、，且仅出现在命题变元前。,2020年6月14日,13,结论,求一个命题公式的与之等价的析取范式和合取范式，其步骤如下：(1)利用等价公式中的等价式和蕴涵式将公式中的、用联结词、来取代；1:(GH)(GH)(HG)(等价)(GH)(HG)(GH)(HG)2：(GH)(GH)(蕴涵),2020年6月14日,14,结论,(2)利用德摩根定律将否定号移到各个命题变元的前端；23：(GH)GH(DeMorgan定律)24：(GH)GH。E19:PP(3)利用结合律、分配律、吸收律、幂等律、交换律等将公式化成其等价的析取范式和合取范式,2020年6月14日,15,范式的求取(化归)过程,例:求（P（QR）S的合取范式解：（P（QR）S（P（QR）S(1)（P（QR）S(1)P（QR）S（PS）（QR）(2)求合取范式（）()（PQS）（PSR）,2020年6月14日,16,主析取范式,一个公式的范式不是唯一的。如P（QR）(析取）（PQ）（PR）(合取）（PQ）P（PQ）R(合取）（PP）（PQ)(PR）（QR）(析取）由于范式不唯一，所以直接用范式判断命题间等价还不方便。需要求公式的主范式。,2020年6月14日,17,主析取范式,定义在n个变元的短语中，若每一个变元与其否定并不同时存在，且二者之一必出现且仅出现一次，则称这种短语为极小项。由有限个极小项组成的析取式称为主析取范式。析取式与主析取范式之间的区别（？）,2020年6月14日,18,主析取范式,以下是由两个原子构成的极小项的真值表,2020年6月14日,19,主析取范式,由真值表可知：任何两个命题公式（极小项）都不是相互等价的，并且只有一组真值指派，使得该公式的值为T。2个命题变元有22=4种不同的组合（极小项）对于n个命题变元，共有2n个不同的极小项，记为m0，m1，m2n-1,2020年6月14日,20,主析取范式,没有两个不同的极小项是等价的，且每个极小项只有一组真值指派，使该极小项的真值为真，因此可给极小项编码，使极小项为“T”的那组真值指派为对应的极小项的编码；如极小项只有在P、Q、R分别取真值0、0、0时才为真，所以有时又可用m000（m0）来表示，同理，如也可用m010（m2）来表示；,2020年6月14日,21,主合取范式,定义在n个变元的子句中，若每一个变元与其否定并不同时存在，且二者之一必出现且仅出现一次，则这种子句称为极大项。由有限个极大项组成的合取式称为主合取范式。合取式与主合取范式之间的区别（？）,2020年6月14日,22,主合取范式,以下是由两个原子构成的极大项的真值表,2020年6月14日,23,主合取范式,由真值表可知：极大项取值0“当且仅当”：如果极大项中出现的是原子本身，则原子赋值为0；如果出现的是原子的否定，则原子赋值为1。任何两个极大项都不是相互等价的且只有一组真值指派使其值为F。2个命题变元有22=4种不同的组合（极大项）对于n个命题变元，共有2n个不同的极大项，记为M0，M1，M2n-1。,2020年6月14日,24,主合取范式,没有两个不同的极大项是等价的，且每个极大项只有一组真值指派，使该极大项的真值为假，因此可给极大项编码，使极大项为“F”的那组真值指派为对应的极大项的编码；如极大项只有在P、Q、R分别取真值1、1、1时才为假，所以有时又可用M111（M7）来表示，同理，如也可用M101（M5）来表示；,2020年6月14日,25,主合取范式,极小项和极大项具备如下性质：（1）没有两个不同的极小项是等价的，且每个极小项只有一组真值指派，使该极小项的真值为真。（2）没有两个不同的极大项是等价的，且每个极大项只有一组真值指派，使该极大项的真值为假。,2020年6月14日,26,主合取范式,2020年6月14日,27,极小项与极大项的性质,(1)mi=Mi；Mi=mi；i=0,1,2,2n-1(2)MiMj=T；mimj=F；ij；i,j0,1,2,2n-1(3),2020年6月14日,28,极小项与极大项的性质,(4)极大项取值0“当且仅当”：如果极大项中出现的是原子本身，则原子赋值为0；如果出现的是原子的否定，则原子赋值为1。(5)极小项取值1“当且仅当”：如果极小项中出现的是原子本身，则原子赋值为1；如果出现的是原子的否定，则原子赋值为0。(6)当一个极大项在一种解释下取值0时，其余极大项在同一解释下取值1。(7)当一个极小项在一种解释下取值1时，其余极小项在同一解释下取值0。,2020年6月14日,29,范数存在定理,定理（范数存在定理）任何一个公式都有与之等价的析取范式和合取范式。定理任何一个公式都有与之等价的主析取范式和主合取范式。求主析（合）取范式的方法有：1、真值表技术法2、公式转换法,2020年6月14日,30,利用真值表求主析（合）取范式,定理在命题公式的真值表中，使公式取值0时的解释所对应的全部极大项的合取式，是该公式的主合取范式。定理1-4.4在命题公式的真值表中，使公式取值1时的解释所对应的全部极小项的析取式，是该公式的主析取范式。,2020年6月14日,31,利用真值表求主析（合）取范式,例设G:(PQ)R，求出它的主析取范式和主合取范式。解：首先列出其真值表如下：,2020年6月14日,32,利用真值表求主析（合）取范式,1)、求公式的主析取范式,2020年6月14日,33,利用真值表求主析（合）取范式,将极小项全部进行析取后，可得到相应的主析取范式：G:（）（P）（P）（）（）,2020年6月14日,34,利用真值表求主析（合）取范式,2)、求公式的主合取范式,2020年6月14日,35,利用真值表求主析（合）取范式,将极大项全部进行合取后，可得到相应的主合取范式：G:（）（P）（P）（）（）,2020年6月14日,36,公式转换法,（1）利用等价公式中的等价式和蕴涵式将公式中的、用联结词、来取代；（2）利用德摩根定律将否定号移到各个命题变元的前端；（3）利用结合律、分配律、吸收律、幂等律、交换律等将公式化成其等价的析取范式和合取范式。（4）在析取范式的短语和合取范式的子句中，如同一命题变元出现多次，则将其化成只出现一次。（5）去掉析取范式中所有永假式的短语和合取范式中所有永真式的子句，即去掉短语中含有形如PP的子公式和子句中含有形如PP的子公式。,2020年6月14日,37,公式转换法,（6）若析取范式的某一个短语中缺少该命题公式中所规定的命题变元，则可用公式：Q（）Q将命题变元P补进去，并利用分配律展开，然后合并相同的短语，此时得到的短语将是标准的极小项；（7）若合取范式的某一个子句中缺少该命题公式中所规定的命题变元，则可用公式：Q（）Q将命题变元P补进去，并利用分配律展开，然后合并相同的子句，此时得到的子句将是标准的极大项。（8）利用幂等律将相同的极小项和极大项合并，同时利用交换律进行顺序调整，由此可转换成标准的主析取范式和主合取范式。,2020年6月14日,38,公式转换法,例利用公式的等价求G：(PQ)R的主析取范式和主合取范式。解：G：(PQ)R(PQ)R（蕴涵）(PQ(RR)(PP)(QQ)R)（添加R、P、Q）(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)（分配律）(PQR)(PQR)(PQR)(PQR)(PQR)（结合律）这是主合取范式,2020年6月14日,39,公式转换法,G：(PQ)R(PQ)R（蕴