Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,/38,离散数学,第一章 命题逻辑,2,/38,回顾,对偶原理,定义，,三条原理：非运算与对偶，等价，永真蕴含,析取范式和合取范式,基本积，基本和,基本和的积，基本积的和,主析取范式和主合取范式,极小项（积），极大项（和），基,二进制数,十进制数,描述符,极小项的和，极大项的积，两者的关系。,3,/38,求范式步骤：,(2),否定消去或内移。,(3),利用分配律。,(1),消去联结词,回顾,4,/38,1.7,命题演算的推理理论,数理逻辑的一个主要任务就是提供一套推理规则，给定一些前提，利用所提供的推理规则，推导出一些结论来，这个过程称为演绎或证明。,生活中：,倘若认定前提是真的，从前提推导出结论的论证是遵守了逻辑推理规则，则认为此结论是真的，并且认为这个论证过程是,合法的,。,数理逻辑中：,不关心前提的真实真值，把注意力集中于推理规则的研究，依据这些推理规则推导出的任何结论，称为,有效结论,，而这种论证则被称为,有效论证,。,5,/38,有效结论,定义,:,设,A,和,B,是两个命题公式，当且仅当,AB,是个永真式，即,AB,，则说,B,是,A,的,有效结论,，或,B,由,A,可逻辑的推出。,可把该定义推广到有,n,个前提的情况。,6,/38,有效结论,定义：,例：,H,1,：今天周一或者今天下雨。,H,2,：今天不是周一。,C,：今天下雨。,7,/38,证明有效结论的方法,1,，真值表法,思路,:,“,证明使前提集合取值为真的那些组真值指派，也一定使结论取值为真,”,。,例,:,考察结论,C,是否是下列前提,H,1,，,H,2,H,3,的结论。,(1)H,1,：,PQ,，,H,2,：,P,，,C,：,Q,P,Q,H,1,H,2,C,H,1,H,2,C,0,0,1,0,0,1,0,1,1,0,1,1,1,0,0,1,0,1,1,1,1,1,1,1,8,/38,真值表法,(2),真值表构造如下：,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,1,0,1,1,1,0,1,1,0,1,0,1,0,1,0,1,1,1,1,0,0,0,0,9,/38,真值表法,(3),0 0,0 1,1 0,1 1,1,1,0,0,0,1,1,1,0,0,0,1,10,/38,真值表法,例：一份统计表格的错误或者是由于材料不可靠，或者是由于计算有错误；这份统计表格的错误不是由于材料不可靠，所以这份统计表格是由于计算有错误。,解：,设,P:,一份统计表格的错误是由于材料不可靠。,Q:,一份统计表格的错误是由于计算有错误。,于是问题可符号化为：,(PQ)PQ,11,/38,真值表法,P Q,(PQ)P,Q,0 0 0 0,0 1 1 1,1 0 0 0,1 1 0 1,12,/38,证明有效结论的方法,2,，直接证法,在命题变元较多的情况下，真值表法显得不方便，我们采用直接证明法，为此先给出如下的定义,定义：设,S,是一个命题公式的集合，从,S,推出命题公式,C,的推理过程是命题公式的一个有限序列：,C,1,，,C,2,，,，,C,n,。,其中，,C,i,或者属于,S,，或者是某些,C,j,(ji),的有效结论，并且,C,n,就是,C,。,如何构造这个推理序列以得出结论,C,呢？只要遵循下面的推理规则，使用列出的等价式或永真蕴涵式，就能构造出满足要求的公式序列。为了帮助大家记忆，我们把常用的等价式和永真蕴涵式再次列出来。,13,/38,常用永真蕴含式,I,1,：,PQP,I,2,:PPQ,I,3,:PPQ,I,4,:QPQ,I,5,:(PQ)P,I,6,:(PQ)Q,I,7,：,P,Q PQ,I,8,：,P,PQQ,I,9,：,P,PQ Q,I,10,：,Q,PQP,I,11,：,PQ,QRPR,I,12,：,PQ,PR,QRR,公式中,“,”,代表,“,”,公式不必死记硬背，其证明均可从,“,”,的定义出发。例如对,I,11,前件为真时保证,PQ,和,QR,都必为真，,PQ,为真，则保证,P,为真时,Q,一定为真，而,Q,为真和,QR,为真则保证了,R,必为真，,P,为真，,R,为真自然保证了,PR,为真，问题得证。,14,/38,常用等价式,E,1,:PP,E,2,:PQQP,E,3,:PQQP,E,4,:(PQ)RP(QR),E,5,:(PQ)RP(QR),E,6,:(PQ)R(P R)(Q R),E,7,:(PQ)R(P R)(Q R),E,8,:(PQ)PQ,E,9,:(PQ)PQ,E,10,:PPP E,11,:PPP,15,/38,常用等价式,E,12,:R(PP)R E,13,:R(PP)R,E,14,:R(PP)T E,15,:R(PP)F,E,16,:PQPQ E,17,:(PQ)PQ,E,18,:PQQP,E,19,:P(QR)(PQ)R,E,20,:(P,Q)P,Q,E,21,:P,Q(PQ)(QP),E,22,:P,Q(PQ)(PQ),16,/38,常用等价公式,17,/38,直接证法,直接证明法：使用推理规则和给定的等价式及永真蕴涵式进行推导证明。,推理规则：,规则,P,：在推导过程中，任何时候都可以引入前提。引入一个前提称为使用一次,P,规则。,规则,T,：在推导中，如果前面有一个或多个公式永真蕴含公式,S,，则可以把公式,S,引进推导过程中。换句话说，引进前面推导过程中的推理结果称为使用,T,规则。,18,/38,直接证法,解,:1(1)(,P,Q,)P,规则,1(2),P,Q,T,规则,(1),和,E,11,1(3),P,Q,T,规则,(2),和,E,27,4(4),Q,R,P,规则,4(5),Q,R,T,规则,(4),和,E,27,1,4(6),P,R,T,(3),(5),和,I,12,7(7),R,P,规则,1,4,7(8),P,T,(6),(7),和,I,12,19,/38,直接证法,例：证明公式,SR,可由公式,PQ,，,PR,，,QS,推出,解：问题即证,PQ,，,PR,，,QS SR,1,、,PQ P,规则,2,、,PQ T,规则和,1,3,、,QS P,规则,4,、,QS T,规则和,3,5,、,PS T,规则及,2,和,4,6,、,SP T,规则和,5,7,、,PR P,规则,8,、（,PR,）（,RP,）,T,规则和,7,9,、,PR T,规则和,8,10,、,SR T,规则及,6,和,9,；,11,、,SR T,规则和,9,得证。,20,/38,直接证法,例：,(P,Q),(RS),(Q,P),R,R,PQ,1,、,R P,规则,2,、,(Q,P),R P,规则,3,、,Q,P,T,规则及,1,和,2,4,、,RS T,规则及,1,5,、,(P,Q),(RS)P,规则,6,、,P,Q,T,规则及,4,和,5,7,、,(P,Q),(Q,P),T,规则及,3,和,6,8,、,PQ T,规则和,7,21,/38,直接证法,推理规则：,CP,规则：如果能从,R,和前提集合中推导出,S,来，则就能够从前提集合中推导出,R,S,。,换句话说，当结论是,R,S,的形式的时候，可以把结论的前件当作一个附加前提使用，并且它和前提一起若能推出结论的后件，则问题得证,实际上恒等式,E,28,就可以推出,CP,规则：,（,P,Q,）,R,（,P,Q,）,R,（,P,Q,）,R,P,（,Q,R,）,P,（,Q,R,）,22,/38,直接证法,解：,1(1),R,P,规则（附加前提）,2(2),R,P,P,规则,1,2(3),P,T,规则,(1),(2),和,I,9,4(4),P,(,Q,S,)P,规则,1,2,4(5),Q,S,T,规则,(3),(4),和,I,10,6(6),Q,P,规则,1,2,4,6(7),S,T,规则,(5),(6),和,I,10,1,2,4,6(8),R,S,CP,规则,(1),(7),23,/38,例：证明,RS,是前提,P(QS),R(PQ),的有效结论,解：原证明即证,:P(QS),R(PQ)RS,1,、,R P,规则（附加前提）,2,、,R(PQ)P,规则,3,、,PQ T,规则及,1,和,2,4,、,P T,规则和,3,5,、,P(QS)P,规则,6,、,QS T,规则及,4,和,5,7,、,Q T,规则和,3,8,、,S T,规则及,6,和,7,9,、,RS CP,规则及,1,和,8,直接证法,24,/38,例：证明,P(QR),Q,PS SR,解：,1,、,S P,规则（附加前提）,2,、,PS P,规则,3,、,P T,规则及,1,和,2,4,、,P(QR)P,规则,5,、,QR T,规则及,3,和,4,6,、,Q P,规则,7,、,R T,规则及,5,和,6,8,、,SR CP,规则及,1,和,7,直接证法,25,/38,证明有效结论的方法,3,，间接证明法（反证法）,定义：设公式,H,1,H,2,H,m,中的原子变元是,P,1,P,2,P,n,。如果给各原子变元,P,1,P,2,P,n,指派某一个真值集合，能使,H,1,H,2,H,m,具有真值,T,，则命题公式集合,H,1,H,2,H,m,称为,一致的,(,或相容的,),；,对于各原子变元的每一个真值指派，如果命题公式,H,1,H,2,H,m,中至少有一个是假，从而使得,H,1,H,2,H,m,是假，则称命题公式集合是,不一致的,(,或不相容的,),。,例如：令,H,1,=P,，,H,2,=P,，,则,H,1,H,2,=PP,是矛盾式，所以,P,，,P,是不相容的。,26,/38,反证法,定理：若存在一个公式,R,，使得,H,1,H,2,H,m,R R,则公式,H,1,，,H,2,，,H,m,是不相容的。,证明：,设,，,H,1,H,2,H,m,R R,则意味着（,H,1,H,2,H,m,）（,RR,）是重言式，,而,RR,是矛盾式，所以前件,H,1,H,2,H,m,必永假。,因此，,H,1,，,H,2,，,H,m,是不相容的。,27,/38,反证法,定理：,设命题公式集合,H,1,，,H,2,，,，,H,m,是一致的，于是从前提集合出发可以逻辑的推出公式,C,的充要条件是从前提集合,H,1,，,H,2,，,，,H,m,，,C,出发，可以逻辑地推出一个矛盾（永假）式。,证明：,必要性：由于,H,1,H,2,H,m,C,，即,H,1,H,2,H,m,C,为永真式，因而使,H,1,H,2,H,m,为真的真值指派一定使,C,为真，,C,为假，从而使,H,1,H,2,H,m,C,为假。必要性证完。,28,/38,反证法,证充分性：由于,H,1,H,2,H,m,C,可以逻辑地推出一个矛盾，即,H,1,H,2,H,m,C F,即,H,1,H,2,H,m,C F,为永真式，即,H,1,H,2,H,m,C,为假，由假设知,H,1,，,H,2,，,，,H,m,是一致的，所以任何使,H,1,H,2,H,m,为真的命题变元的真值指派必然使,C,为假，从而使,C,为真。故有,H,1,H,2,H,m,C,该定理说明用直接证明法可以证明的结论，用间接证明法都可以证明，反之亦然。,因此，为了证明,B,是,A,的结论，可以把,A,和,B,作为前提，然后推出一个矛盾，从而使问题得证。下面用例子说明。,29,/38,反证法,F,规则：如果前体集合和,S,不相容，那么可以从前提集合中推出,S,。,例：证明,(,P,Q,),是,P,Q,的有效结论。,解：把,(,P,Q,),作为假设前提，并证明该假设前提导致一个永假式。,1(1),(,P,Q,),P,规则（假设前提）,1(2),P,Q,T,规则，,(1),和,E,10,1(3),P,T,