山东科技大学离散数学离散数学15

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,离 散 数 学,Discrete Mathematics,Email:,二零一零年三月,1,上次课内容回顾,析取范式,主析取范式,合取范式,主合取范式,小项,大项,2,第一章 第,5,讲,18,推理理论,在数学和其它自然科学中，经常要考虑从某些前提,A,1,，,A,2,，,，,A,n,能够推导出什么结论。,例如：,从分子学说，原子学说，能够得到什么结论；,从光的波动学说，能得到什么结论。,我们一般地要对“假设”的内容作深入分析，并推究其间的关系，从而得到结论。,但也有一些推理，只需分析假设中的真值和联结词，便可获得结论。,3,在数理逻辑中，集中注意的是研究和提供用来从前提导出结论的推理规则和论证原理，这些规则有关的理论称为推理理论。,在实际应用的推理中，我们常常把本门学科的一些定律、定理和条件，作为假设前提，尽管这些前提在数理逻辑中实非永真，但在推理过程中，却总是假设这些命题为,T,，并使用一些公认的规则，得到另外的命题，形成结论，这种过程就是论证。,注意，必须把推理的有效性和结论的真实性区别开。,4,一、有效结论,1.,定义,定义,1-8.1,设,A,和,C,是两个命题公式，当且仅当,AC,为一重言式，即,A,C,，称,C,是,A,的有效结论。或,C,可由,A,逻辑地推出。,3 .,论证过程,判别有效结论的过程就是论证过程。,2.,推广,有效结论定义可以推广到有,n,个前提的情况。,设,H,1,，,H,2,，,，,H,n,，,C,是命题公式，当且仅当,H,1,H,2,H,n,C (A),称,C,是一组前提,H,1,，,H,2,，,，,H,n,的有效结论。,5,二、证明方法,1.,真值表法,2.,直接证法,3.,间接证法,6,二、证明方法,1.,真值表法,2.,直接证法,3.,间接证法,7,1.,真值表法,设,P,1,，,P,2,，,，,P,n,是出现于前提,H,1,，,H,2,，,，,H,n,和结论,C,中的全部命题变元，假定对,P,1,，,P,2,，,，,P,n,作了全部的真值指派，这样就能对应地确定,H,1,，,H,2,，,，,H,n,和,C,的所有真值，列出这个真值表，即可看出,(A),式是否成立。,H,1,，,H,2,，,，,H,n,真值均为,T,的行，对于每一个这样的行，若,C,也有真值,T,，则,(A),式成立；,或者看,C,的真值为,F,的行，在每一个这样的行中，,H,1,，,H,2,，,，,H,n,的真值至少有一个为,F,，则,(A),式也成立。,8,例题,1,一份统计表格的错误或者是由于材料不可靠，或者是由于计算有错误；这份统计表格的错误不是由于材料不可靠，所以这份统计表格是由于计算有错误。,解 设各命题变元为,P,：统计表格的错误是由于材料不可靠。,Q,：统计表格的错误是由于计算有错误。,本例可译为：,Q,是前提,PQ,，,P,的有效结论，即,P(PQ),Q,9,我们列出真值表,1-8.1,如下,P,Q,PQ,P,T,T,T,F,T,F,T,F,F,T,T,T,F,F,F,T,从表上看到只有在第三行,PQ,和,P,的真值都为,T,，这时,Q,的真值亦为,T,。故,(PQ)(P),Q,成立。,或者考察,Q,的真值为,F,的情况，在第二行和第四行，其相应的,PQ,或,P,中至少有一真值为,F,，故亦说明,(PQ)(P),Q,成立。,10,例题2 如果张老师来了，这个问题可以得到解答，如果李老师来了，这个问题也可以得到解答，总之张老师或李老师来了，这个问题就可得到解答。,解 若设,P,：张老师来了。,Q,：李老师来了。,R,：这个问题可以得到解答。,上述语句可翻译成下述命题关系式,(PR)(QR)(PQ),R,11,列出真值表,P,Q,R,PR,QR,PQ,T,T,T,T,T,T,T,T,F,F,F,T,T,F,T,T,T,T,T,F,F,F,T,T,F,T,T,T,T,T,F,T,F,T,F,T,F,F,T,T,T,F,F,F,F,T,T,F,从真值表看到，,PR,，,QR,，,PQ,的真值都为,T,的情况为第一行、第三行和第五行，而在这三行中,R,的真值均为,T,。故,(PR)(QR)(PQ),R,12,真值表法证明,前真：看后真；,后假：前至少有一个假。,13,二、证明方法,1.,真值表法,2.,直接证法,3.,间接证法,14,2.,直接证法,直接证法就是,由一组前提，利用一些公认的推理规则，根据已知的等价或蕴含公式，,推演得到有效的结论。,真值表法是把所给前提一起使用，而直接证法则是不断使用前提和前面推出的结论，构成推导序列，是把前提一步一步拿来使用。,P,规则,前提,在推导过程中的任何时候都可以使用。,T,规则,在推导中，如果有一个或多个公式重言蕴含着公式,S,，则公式,S,可作为条件引入推导之中。,15,常用的蕴含式（,43,页表,1-8.3,）,I,1,PQ,P,I,9,P,Q,PQ,I,2,PQ,Q,I,10,P,PQ,Q,I,3,P,PQ,I,11,P,PQ,Q,I,4,Q,PQ,I,12,Q,PQ,P,I,5,P,PQ,I,13,PQ, QR,PR,I,6,Q,PQ,I,14,PQ,PR,QR,R,I,7,(PQ),P,I,15,AB,(AC)(BC),I,8,(PQ),Q,I,16,AB,(AC)(BC),16,常用的等价式,(43,页表,1-8.4),E,1,P,P,E,12,R (PP),R,E,2,PQ,QP,E,13,R (P P),R,E,3,P Q,Q P,E,14,R (P P),T,E,4,(PQ) R,P (QR),E,15,R (PP),T,E,5,(P Q) R,P (Q R),E,16,PQ,P Q,E,6,P (Q R),(PQ) (PR),E,17,(P Q),PQ,E,7,P (QR),(P Q) (P R),E,18,PQ,Q P,E,8,(PQ),P Q,E,19,P (QR),(PQ) R,E,9,(P Q),P Q,E,20,P,Q,(PQ) (QP),E,10,P P,P,E,21,P,Q,(PQ) (P Q),E,11,PP,P,E,22,(P,Q),P,Q,17,例题,1,证明,(PQ),(PR)(QS),SR,(8) SR T(7) E,(7) SR T(5),(6) I,(6) PR P,(5) SP T(4) E,(4) PS T(2) ,(3) I,(3) QS P,(2),PQ T(1) E,证法,1,(1),PQ P,18,例题,1,证明,(PQ),(PR)(QS),SR,证法,2 (1),PR P,(2),PQ,RQ T(1) I,(3) QS P,(4) QR,SR T(3) I,(5) PQ,SR T(2),(4) I,(6) PQ P,(7) SR T(5),(6) I,19,例题,2,证明,(WR) V,VCS,SU, C U,W,(13) W T(12) I,(12) W R T(11) E,(11) (WR) T(7),(10) I,(10) (WR) CS T(8),(9) I,(9) VCS P,(8) (WR) V P,(7) (CS) T(6) E,(6) C S T(4),(5) I,(5) C T(1) I,(4) S T(2) ,(3) I,(3) SU P,(2),U T(1) I,证明,(1),C U P,20,二、证明方法,1.,真值表法,2.,直接证法,3.,间接证法,21,3.,间接证法,(1),定义,定义,1-8.2,假设公式,H,1,，,H,2,，,，,H,n,中的命题变元为,P,1,，,P,2,，,，,P,n,，,对于,P,1,，,P,2,，,，,P,n,的,一些,真值指派，如果能使,H,1,H,2, ,H,n,的真值为,T,，则称公式,H,1,，,H,2,，,，,H,n,是相容的。,如果对于,P,1,，,P,2,，,，,P,n,的,每一组,真值指派使得,H,1,H,2, ,H,n,的真值均为,F,，则称公式,H,1,，,H,2,，,，,H,n,是不相容的。,22,(2),证法,可以把不相容的概念应用于命题公式的证明。,设有一组前提,H,1,，,H,2,，,，,H,n,，要推出结论,C,，即证,H,1,H,2, ,H,n,C,，记作,S,C,，即,C S,为永真，或,CS,为永真，故,C S,为永假,。因此要证明,H,1,H,2, ,H,n,C,，只要证明,H,1,，,H,2,，,，,H,n,与是,C,是不相容的。即假定,C,为真，推出矛盾。,23,例题,3,证明,AB,，,(BC),可逻辑推出,A,(7) B B(,矛盾,) T(3),(6) I,(6) B T(5) I,(3) B T(1),(2) I,(5) B C T(4) E,(4) (BC) P,(2),A P(,附加前提,),(1),AB P,证明,24,例题,4,证明,(PQ),(PR)(QS),SR,(13) (P R) (P R)(,矛盾,) T(9),(12) I,(12) (P R) T(11) E,(11) PR T(10) E,(10) P R P,(9) P R T(2),(8) I,(8) (S R ) (P R ) T(7) I,(7) S P T(6) E,(6) P S T(4),(5) I,(5) Q,S P,(4) P,Q T(3) E,(3) PQ P,(2),S R T(1) E,(1),(SR) P(,附加前提,),证明,25,(3) CP,规则（ 结论为,R C,时使用）,间接证法的另一种情况是：若要证,H,1,H,2, ,H,n,(R C),。 设,H,1,H,2, ,H,n,为,S,，即证,S,(R C),或,S,(, RC),，故,S ( RC),为永真式。因为,S ( RC),S( RC),(S R)C,(S R)C,(S R) C,，所以若将,R,作附加前提，如有,(S R),C,，即证得,S,(RC),。,由,(S R),C,，证得,S,(RC),称为,CP,规则。,26,例题,5,证明,A(BC),，,DA,，,B,重言蕴含,DC,(8) DC,CP,(7) C T(5),(6) I,(6) B P,(5) BC T(3),(4) I,(4) A(BC) P,(3) A T(1),(2) I,(2),DA P,(1),D P(,附加前提,),证明,27,例题,6,设有下列情况，结论是否有效？,(a),或者是天晴，或者是下雨。,(b),如果是天晴，我去看电影。,.,(c),如果我去看电影，我就不看书。,结论：如果我在看书则天在下雨。,(1) R P(,附加前提,),(2) S R P,(3) R S T(2) E,(4) S T(1),(3) I,(5) M S P,(6)M T(4),(5) I,(10) (M Q) (Q M) T(9) E,(11) Q M T(10) I,(12) M Q T(11) E,(13) Q T(6),(12) I,(14) RQ CP,(8) ( M,Q) T(7) E,(9) M, Q T(8) E,(7),MQ P,解 若设,M：,天晴。,Q：,下雨。,S：,我看电影。,R：,我看书。,故本题即证：,M Q，MS，S R，,推出,RQ,28,真值表法：,前真：看后真；,后假：前至少有一个假。,直接证法：由一组前提，利用一些公认的推理规则，根据已知的等价或蕴含公式，推演得到有效的结论。,间接证法,要证明,H1 ,H2 , ,Hn,C,，只要证明,H1,，,H2,，,，,Hn,与是,C,是不相容的。,要证明,H1 ,H2 , ,Hn,(R C),。 如能证明,H1 ,H2 , ,Hn,R,C,，即证得,H1 ,H2 , ,Hn,(RC),。这个证明称为,CP,规则。,命题推理方法,29,作业,P46-P47,(1)a,、,b,(2)a,、,c,、,e,(3)a,、,c,(4)b,、,c,30,第一章 内容回顾,一、知识点,1命题的概念、表示方法；联结词的逻辑意义。,2命题公式的递归定义，自然语言翻译成命题公式,3真值表的构造、命题公式等价的概念。,4重言式与蕴涵式的定义、逻辑意义，逻辑等价与逻辑蕴涵的意义和证明方法。常用的逻辑等价公式和逻辑蕴涵公式。,31,5命题公式的对偶式、合取范式、析取范式、主合取范式、主析取范式。逻辑小项、逻辑大项。任给公式化为析取范式、任给公式化为主析取范式、任给公式化为合取范式、任给公式化为主合取范式。,6命题逻辑的推理理论，主要的推理方法：真值表法、直接证明法、间接证明法。常用推理规则：,P,规则、,T,规则、,CP,规则。,32,