离散数学课程组国家级课程课件.ppt
《离散数学课程组国家级课程课件.ppt》由会员分享,可在线阅读,更多相关《离散数学课程组国家级课程课件.ppt(100页珍藏版)》请在三一办公上搜索。
1、离 散 数 学,电子科技大学,计算机科学与工程学院示范性软件学院,2022年11月24日星期四,离 散 数 学电子科技大学计算机科学与工程学院24 九月 2,第5章 推理与证明技术,第5章 推理与证明技术 数学归纳法的使用 3CP规则相关证,5.1 本章学习要求,5.1 本章学习要求1掌握各种不同类型的规则和公理,特别是命,5.2 命题逻辑的推理理论,5.2 命题逻辑的推理理论 概念描述问题的句子;Add Y,推理的有效性和结论的真实性,有效的推理不一定产生真实的结论;而产生真实结论的推理过程未必是有效的。有效的推理中可能包含为“假”的前提,而无效的推理却可能得到为“真”的结论 。,推理的有效
2、性和结论的真实性有效的推理不一定产生真实的结论;,推理的有效性和结论的真实性,所谓推理有效, 指的是它的结论是它前提的合乎逻辑的结果。 即,如果它的前提都为真,那么所得的结论也必然为真,而并不是要求前提或结论一定为真或为假; 如果推理是有效的话,那么不可能它的前提都为真时,而它的结论为假。,推理的有效性和结论的真实性所谓推理有效,,5.2.1 推理的基本概念和推理形式,定义5.2.1 设G1, G2, ,Gn,是公式,称H是G1, G2, ,Gn的逻辑结果(G1, G2, ,Gn共同蕴涵H),当且仅当H 是G1G2Gn的逻辑结果(logic conclusion)。记为G1, G2, ,Gn
3、,此时称G1, G2, ,Gn 为有效的(efficacious),否则称为无效的(inefficacious)。G1, G2, ,Gn称为一组前提(Premise),有时用集合来表示,记 = G1, G2, ,Gn。H称为结论(conclusion)。又称H是前提集合的逻辑结果。记为 H。,5.2.1 推理的基本概念和推理形式 定义5.2.1 设G,判定定理,定理5.2.1 公式H是前提集合=G1, G2, , Gn的逻辑结果当且仅当G1G2Gn为永真公式。,证明:“”若G1, G2, ,Gn ,但G1G2GnH不是永真式。于是,必存在G1, G2, ,Gn,H的一个解释I,使得G1G2Gn
4、为真,而H为假,因此对于该解释I,有G1, G2, ,Gn都为真,而H为假,这就与推理形式G1, G2, ,Gn 是有效的相矛盾,故:G1G2GnH是永真公式。,判定定理定理5.2.1 公式H是前提集合=G1, G2,判定定理(续),“”若G1G2GnH是永真式,但G1, G2, ,Gn 不是有效的推理形式,故存在G1, G2, ,Gn, H的一个解释I,使得G1, G2, ,Gn都为真,而H为假,故G1G2Gn为真,而H为假,即是说G1G2GnH为假,这就与G1G2GnH是永真式相矛盾,所以G1, G2, ,Gn 是有效的推理形式。,判定定理(续) “”若G1G2GnH是永真,“”与“”的不
5、同,1.“”仅是一般的蕴涵联结词,GH的结果仍是一个公式,而“”却描述了两个公式G,H之间的一种逻辑蕴涵关系,G H的“结果”,是非命题公式;,2. 用计算机来判断G H是办不到的。然而计算机却可“计算”公式GH是否为永真公式。,“”与“”的不同1.“”仅是一般的蕴涵联结词,GH的,1、真值表技术,设P1,P2,Pn是出现在前提G1,G2,Gn和结论H中的一切命题变元,如果将P1,P2,Pn中所有可能的解释及G1,G2,Gn,H的对应真值结果都列在一个表中,根据“”的定义,则有判断方法如下:,对所有G1,G2,Gn都具有真值T的行(表示前提为真的行),如果在每一个这样的行中,H也具有真值T,则
6、H是G1,G2,Gn的逻辑结果。对所有H具有真值为F的行(表示结论为假的行),如果在每一个这样的行中,G1,G2,Gn中至少有一个公式的真值为F(前提也为假),则H是G1,G2,Gn的逻辑结果.,1、真值表技术 设P1,P2,Pn是出现在前提G1,例5.2.1,判断下列H是否是前提G1,G2的逻辑结果(1)H:Q;G1:P;G2:PQ;(2)H:P; G1:PQ;G2:Q;(3)H:Q;G1:P;G2:PQ。,解,例5.2.1 判断下列H是否是前提G1,G2的逻辑结果解PQ,5.2.2 判断有效结论的常用方法,5.2.2 判断有效结论的常用方法 要求=G1, G2,离散数学课程组国家级课程课件
7、,设G,H,S是任何的公式,则:,基本等价公式,1:G(HS)(GH)S(结合律)2: G(HS)(GH)S3:GHHG (交换律)4:GHHG5:GGG (幂等律)6:GGG7:G(GH) G (吸收律)8:G(GH) G,设G,H,S是任何的公式,则:基本等价公式1:G(HS,9:G(HS)(GH)(GS)(分配律) 10:G(HS)(GH)(GS)11:GG(同一律) 12:GG 13:G(零律) 14:G15:GG (排中律)16:GG (矛盾律),基本等价公式(续),9:G(HS)(GH)(GS)(分配律)基本,基本等价公式(续),17:(G)G(双重否定律)18:(GH)GH(De
8、 MoRGan定律) 19:(GH)GH20: (GH)(GH)(HG)(等价式)21:(GH)(GH)(蕴涵式)E22: GG(假言易位)E23: GG(等价否定等式)E24: (G)(G)G(归谬论),基本等价公式(续)17:(G)G(双重否定律),5.2.2 判断有效结论的常用方法,5.2.2 判断有效结论的常用方法 要求=G1, G2,真值表技术,真值表技术G1G2G3GnH0101001011101001,2 推理定律,设G,H,I,J是任意的命题公式,则有:,I1:GHG(简化规则)I2:GHHI3:GGH(添加规则)I4:HGHI5:GGHI6:HGHI7:(GH)GI8:(GH
9、)HI9:G,HGH,2 推理定律设G,H,I,J是任意的命题公式,则有:I1:,2 推理定律(续),6)I10:G,GHH (选言三段论) I11:G,G HH7)I12:G,GHH(分离规则)8)I13:H,GHG(否定后件式)9)I14:GH,HIGI(假言三段论)10)I15:GH,GI,HII (二难推论),2 推理定律(续)6)I10:G,GHH,例子,1)、前提:1. 如果明天天晴,我们准备外出旅游。PQ2明天的确天晴。P结论:我们外出旅游。Q可描述为:PQ,PQ(分离规则)2)、前提:1.如果一个人是单身汉,则他不幸福。PQ2.如果一个人不幸福,则他死得早。QR结论:单身汉死得
10、早。 PR可描述为:PQ,QRPR(假言三段论),例子1)、前提:,例子(续1),3)、某女子在某日晚归家途中被杀害,据多方调查确证,凶手必为王某或陈某,但后又查证,作案之晚王某在工厂值夜班,没有外出,根据上述案情可得前提:1.凶手为王某或陈某。PQ 2.如果王某是凶手,则他在作案当晚必外出PR 3.王某案发之晚并未外出。 R结论:陈某是凶手。Q则可描述为:PR,RP(否定后件式) PQ,PQ(选言三段论),例子(续1)3)、某女子在某日晚归家途中被杀害,据多方调查确,例子(续2),4)、前提:1.如果某同学为省二级以上运动员,则他将被大学录取。PR2.如果某同学高考总分在560分以上,则将被
11、大学录取。QR3.某同学高考总分在560分以上或者是省二级运动员。PQ 结论:该同学被大学录取。R 则上述例子可描述为: PQ,PR,QRR(二难推论),例子(续2)4)、前提:,3 演绎法,演绎法是从前提(假设)出发,依据公认的推理规则和推理定律,推导出一个结论来。,3 演绎法 演绎法是从前提(假设)出发,依据公,引入推理规则,在数理逻辑中,主要的推理规则有: P规则(称为前提引用规则):在推导的过程中,可随时引入前提集合中的任意一个前提; 规则(逻辑结果引用规则):在推导的过程中,可以随时引入公式S,该公式S是由其前的一个或多个公式推导出来的逻辑结果。 规则(附加前提规则):如果能从给定的
12、前提集合与公式P推导出S,则能从此前提集合推导出PS。,引入推理规则在数理逻辑中,主要的推理规则有:,演绎的定义,定义5.2.2 从前提集合推出结论H的一个演绎是构造命题公式的一个有限序列: H1,H2,Hn 其中,Hi或者是中的某个前提,或者是前面的某些Hj(ji)的有效结论,并且Hn就是H,则称公式H为该演绎的有效结论,或者称从前提能够演绎出结论H来。,演绎的定义定义5.2.2,例5.2.2 设前提=PQ,PR,QS,G=SR。证明G。,例5.2.2,证明G的方法 ?,(1)建立公式PQ, PR, QS, SR的真值表,利用真值表技术,判断前提与结论之间是否有逻辑关系;(2)利用公式的等价
13、转换,判断公式(PQ)(PR)(QS)(SR)是否是永真公式;(3)任取解释I,若I满足(PQ)(PR)(QS),证明I满足(SR);(4)利用演绎法中的直接证明方法,证明如何从前提演绎出结论;(5)由于结论为(SR),而SRSR,为此可以采取引入附加前提S,采用CP规则,利用演绎法证明如何从前提演绎出结论。,证明G的方法 ?(1)建立公式PQ, PR, Q,例5.2.2,证明1 PQP PQT,(1),E QSP PST,I SPT,E PRP (PR)(RP) ,E PR ,I SR T,I SRT,(9),E,设前提=PQ,PR,QS,G=SR。证明G。,例5.2.2 证明1 PQP设前
14、提=P,证明2 SP(附加前提) QSP QT,I PQP PT,I PR P (PR)(RP) ,E PR,I R T,I SR CP, SR T, ,E,设前提=PQ,PR,QS,G=SR。证明G。,证明2 SP(附加前提)设前提=PQ,P,例5.2.3,证 RP(附加前提)RPPPT,IP(QS)PQST,IQPST,IRSCP,设=P(QS),RP,Q,G=RS。证明:G。,例5.2.3证 RP(附加前提)设=P(Q,4 间接证明法(反证法),前面使用过的一些证明方法都是正向推理。但在数学领域中,经常会遇到一些问题,当采用正向推理时很难从前提为真推出结论为真。,PQ等价于QP,因此,为
15、了间接地证明PQ,可以假设Q为假(Q),然后证明P为假(P)。,4 间接证明法(反证法) 前面使用过的一些证明方法,例5.2.4,设n是一个整数,证明:如果n2是奇数,那么n是奇数。,证明 设n是偶数,则n2k,这里k是一个整数。于是有: n2(2k)2=4k2=2(2k2)所以n2是偶数。 因而证明了若n是偶数,则n2是偶数,它是已知命题的逆否式。因此,证明了所给的命题。,例5.2.4 设n是一个整数,证明:如果n2是奇数,那么,定义5.2.3, 假设G1,G2,Gn是一组命题公式,P1,P2,Pn是出现在中的一切命题变元,I是它的任意解释,若有解释I使G1G2Gn取值为“真”,则称公式G1
16、,G2,Gn是一致的,或者说是相容的。 如对任意的解释I,都有G1G2Gn取值为“假”,则称公式G1,G2,Gn是不一致的。或者说G1G2Gn是一个矛盾式。,G1G2Gn是矛盾式当且仅当G1G2Gn,其中,R可为任意公式,RR为一矛盾式。,定义5.2.3 假设G1,G2,Gn是一组命题公式,,间接证明方法,将结论的否定加入到前提集合中构成一组新的前提,然后证明这组新的前提集合是不相容的,即蕴涵一个矛盾式。G1,G2,Gn,H RR,定理5.2.2 设命题公式集合G1,G2,Gn是一致的,于是从前提集合出发可以逻辑地推出公式H的充要条件是从前提集合G1,G2,Gn ,H出发,可以逻辑地推出一个矛
17、盾(永假)式来。,间接证明方法将结论的否定加入到前提集合中构成一组新的前提,然,例5.2.5,证明不存在有理数p/q其平方为2,即,证明 是无理数。,证明 对某两个整数p和q,假设(p/q)2=2成立,并且p和q没有公因子。如果原来选择的p/q不是最小项,则可以用它等价的最小项形式来取代它。 于是p2=2q2,所以p2是偶数,这就推出p是偶数,因为一个奇数的平方是奇数。,例5.2.5证明不存在有理数p/q其平方为2,即,证明,例5.2.5 证明(续),因此存在某个整数n使得p2n成立。因此2q2p2(2n)2=4n2, 即有q2=2n2,所以q2是偶数,从而q是偶数,于是得到p和q都是偶数,故
18、它们有一个公因子2,这与假设相矛盾。 因此假设一定为假。,例5.2.5 证明(续) 因此存在某个整数n使得p2n成,例5.2.6,用反证法证明二难推论 PQ,PR,QRR,证明 PR P R (附加前提) P T,I QR P Q T,I PQ P ,I PP ,I,例5.2.6用反证法证明二难推论 PQ,PR,QR,三种证明方法之间的关系,G1,G2,Gn, G1,G2,Gn () G1,G2,Gn() G1,G2,Gn,反证法CP规则证明法直接证明法,三种证明方法之间的关系 G1,G2,Gn,5.2.3 命题逻辑推理的难点,1、弄清楚蕴涵式PQ的逻辑关系及其真值,这里Q是P的必要条件。无论
19、蕴涵关系如何表述,都要仔细地区分出蕴涵式的前件和后件。2、推理过程中推理规则、基本等值式和逻辑蕴涵式的引用要适当,逻辑思维要清晰。,5.2.3 命题逻辑推理的难点 1、弄清楚蕴涵式PQ的逻,5.2.3 命题逻辑推理的难点,3、弄清楚几种推理方法的区别与联系,对于命题逻辑推理而言,任何一个问题的推理,都可以采取三种推理方法中的任何一种来证明,针对不同的问题选用不同的推理方法。一般而言,对于结论是蕴涵式或析取式的,大多可以采取带CP规则的直接证明方法。,5.2.3 命题逻辑推理的难点 3、弄清楚几种推理方法的区,5.2.4 命题逻辑推理的应用,例5.2.7 符号化下面的语句,并用演绎法证明结论是否
20、有效。 或者明天下午是天晴,或者是下雨;如果明天下午是天晴,则我将去看电影;如果我去看电影,我就不看书。如果我看书,则天在下雨。,设P:明天下午天晴; Q:明天下午下雨; R:明天下午去看电影;S:明天下午看书。 则上述命题可符号化为: P Q,PR,RS SQ。,5.2.4 命题逻辑推理的应用 例5.2.7 符号化下面,例5.2.7 证明,(1)S P (附加前提) (2)RS P (3)R ,(1),(2),I (4)PR P (5)P ,(3),(4),I (6)P Q (7)Q ,(4),(7),I,例5.2.7 证明 (1)S,例5.2.8,一个公安人员审查一件盗窃案,已知的事实如下
21、: A或B盗窃了x; 若A盗窃了x,则作案时间不能发生在午夜前; 若B证词正确,则在午夜时屋里灯光未灭; 若B证词不正确,则作案时间发生在午夜前; 午夜时屋里灯光灭了。B盗窃了x。,例5.2.8一个公安人员审查一件盗窃案,已知的事实如下:,例5.2.8 证明,设 P:A盗窃了x;Q:B盗窃了x; R:作案时间发生在午夜前; S:B证词正确; T:在午夜时屋里灯光未灭。 则上述命题可符号化为:PQ,PR,ST,SR,T Q,例5.2.8 证明 设 P:A盗窃了x;Q:B盗窃了x;,例5.2.8 证明(续),证明1 采用直接证明方法(反证法请学生完成) (1)T (2)ST (3)S ,(1),(
22、2),I (4)SR (5)R ,(3),(4),I (6)PR P (7)P ,(5),(6),I (8)PQ (9)Q ,(7),(8),I,例5.2.8 证明(续)证明1 采用直接证明方法(反证法请,回顾,1、推理规则:P: 前提T: 中间结论CP: PQ E24:I15:,回顾1、推理规则:,2、三种证明方法,G1,G2,Gn G1,G2,Gn,直接证明法反证法CP规则证明法,G1,G2,Gn (),2、三种证明方法 G1,G2,Gn直接证明法G1,证明 令 P:马会飞;Q:羊吃草; R:母鸡是飞鸟; S:烤熟的鸭子会跑。符号化上述语句为:=PQR,RS,S,G=Q。证明G。,如果马会
23、飞或羊吃草,则母鸡就会是飞鸟;如果母鸡是飞鸟,那么烤熟的鸭子还会跑;烤熟的鸭子不会跑。所以羊不吃草。,例5.2.8,证明 令 P:马会飞;Q:羊吃草;如果马会飞或羊吃草,则母,例5.2.8 证明 (续),S PRS PR T,IPQR P(PQ) T,IPQ T,EQ T,I,例5.2.8 证明 (续)S,5.3 谓词逻辑的推理理论,5.3.1 谓词演算的演绎与推理,定义5.3.1 设G1, G2, ,Gn,是公式,称H是G1, G2, ,Gn的逻辑结果(G1, G2, ,Gn共同蕴涵H),当且仅当H 是G1G2Gn的逻辑结果(logic conclusion)。记为G1, G2, ,Gn ,
24、此时称G1, G2, ,Gn 为有效的(efficacious),否则称为无效的(inefficacious)。G1, G2, ,Gn称为一组前提(Premise),有时用集合来表示,记 = G1, G2, ,Gn。H称为结论(conclusion)。又称H是前提集合的逻辑结果。记为 H。,5.3 谓词逻辑的推理理论 5.3.1 谓词演算的演绎与,定理5.3.1,定理5.3.1 公式H是前提集合=G1, G2, ,Gn的逻辑结果当且仅当G1G2Gn为有效公式。,定理5.3.1 定理5.3.1 公式H是前提集合=G1,谓词演算中的有效公式,(1)E25:(x)G(x) = (y)G(y); E2
25、6:(x)G(x) = (y)G(y); -(改名规则) (2)E27: (x)G(x) = (x)G(x); E28:(x)G(x) = (x)G(x); - (量词转换律/量词否定等值式),谓词演算中的有效公式 (1)E25:(x)G(x) = (,谓词演算中的有效公式(续),(3)E29:(x)(G(x)S) = (x)G(x)S; E30:(x)(G(x)S) = (x)G(x)S; E31:(x)(G(x)S) = (x)G(x)S; E32:(x)(G(x)S) = (x)G(x)S; - (量词辖域的扩张与收律),谓词演算中的有效公式(续),谓词演算中的有效公式,(4)E33:(
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 离散数学 课程 国家级 课件
链接地址:https://www.31ppt.com/p-1440533.html