第一章 命题逻辑-4th.ppt

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,规则，,(2),和,I,1,4(4),P,Q,P,规则,4(5),P,T,规则，,(4),和,I,1,1,4(6),P,P,T,规则，,(3),(5),和,I,16,1,4(7),(,P,Q,),F,规则，,(1),(6),30,/38,反证法,例：证明,PQ,，,PR,，,QR R,解：,1,、,R P,规则（假设前提）,2,、,PR P,规则,3,、,P T,规则及,1,和,2,4,、,PQ P,规则,5,、,Q T,规则及,3,和,4,6,、,QR P,规则,7,、,R T,规则及,5,和,6,8,、,RR T,规则及,1,和,7,9,、,R F,规则及,1,和,8,31,/38,反证法,例：足坛,4,支甲级队进行比赛，已知情况如下：,前提：,1,、若大连万达获冠军，则北京国安和上海申花 获得亚军,2,、若上海申花获亚军，则大连万达不能获冠军,3,、若陕西国力获亚军，则北京国安不能获亚军,4,、最后大连万达获冠军,结论：,5,、陕西国力未获亚军,32,/38,反证法,用推理的方法证明由,1,、,2,、,3,、,4,能否推出,5,解：首先将命题符号化,令,P,：大连万达获冠军,Q,：北京国安获亚军,R,：上海申花获亚军,S,：陕西国力获亚军,33,/38,反证法,于是问题可符号化为：,P(Q R),RP,SQ,P S/*,注意这里自然语言中的和表示的是排斥或，所以用 来表示*,/,解：,1,、,S P,规则（假设前提）,2,、,S T,规则和,1,3,、,SQ P,规则,4,、,Q T,规则,2,和,3,5,、,P P,规则,6,、,P(QR)P,规则,7,、,QR T,规则,5,和,6,8,、,R T,规则,4,和,7,9,、,RP P,规则,34,/38,反证法,10,、,P T,规则,8,和,9,11,、,PP T,规则,5,和,10,12,、,S F,规则,1,和,11,/*,问题得证*,/,35,/38,证明有效结论使用方法规律,当要证明的结论是条件式时，可考虑使用,CP,规则,当要证明的结论比较简单，而仅仅使用前提推导不明显时，可考虑使用间接证明法即,F,规则，以使推导过程变得简捷。,36,/38,小结,本章我们学习了命题的概念以及在命题集合上的运算：,、。,但是这些逻辑联结词并不是必不可少的，于是引出了逻辑联结词最小全功能完备集的概念：,，,和,，,。,37,/38,小结,此外，我们完成了命题逻辑中的一个重要任务：合式公式的判定求解方法：,A,：真值表法；,B,：等价公式变换法；,C,：利用对偶原理,D,：通过求主范式的方法。,我们学习了一些常用的等价式和永真蕴涵式及推理规则；目的是用命题逻辑解决推理问题；我们介绍了,P,规则，,T,规则，,CP,规则，,F,规则的使用及使用我们介绍的等价式和蕴含式及四条规则正确进行推理的练习。,38,/38,作业,P25,习题,5(1),，,7,（,1,）：要求使用,F,规则,9,（,1,）：要求使用,F,规则,补充题：,1,，验证下列论述有效性,如果李明学习努力，那么他成绩好,如果李明不热衷于玩扑克，那么他就学习努力,李明成绩不好。,所以，李明热衷于玩扑克。,39,/38,作业（续）,2,，证明下列各式的有效性,上机作业：,必做：任意输入一个析取范式，计算并输出其主析取范式,选作：任意输入一个命题公式，计算并输出其真值表以及主析取和主合取范式。,