离散数学-1-8 推理理论

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,第一章 命题逻辑,1-8 推理理论,授课人：李朔,Email:,chn,.,nj,.,lS,gmail,.com,1,在数学和其它自然科学中，经常要考虑从某些前提,A,1,、A,2,、,A,n,出发，能推导出什么结论。,数理逻辑的主要任务是用,逻辑,的方法研究数学中的推理。所谓,推理,是指从前提出发，应用推理规则推出结论的思维过程。任何一个推理都由前提和结论两部分组成。前提就是推理所根据的,已知命题,，结论则是从前提出发,通过推理而得到的新命题。,要研究推理，首先应该明确,什么样的推理是有效的或正确的,2,一、有效推理,假设一些命题为，并使用一些公认的规则，得到另外的命题，形成结论，这种过程就是,论证,。,定义,1-8.1,设,A,和,C,是,2,个命题公式，当且仅当,A,C,为一重言式，即,A,C,，,则称,C,为,A,的有效结论,。,或,C,可由,A,逻辑的推出。,A,叫做,C,的前提,。,上述定义可以推广到,n,个前提的情况：,设,H,1,，,H,2,，,，,H,n,C,是,n,+1,个命题公式,当且仅当,H,1,H,2,H,n,C，,称,C,是一组前提,H,1,，,H,2,，,，,H,n,的有效结论,。,*,判断有效结论的过程就是论证过程,，基本方法是,真值表法,、,直接证法,、,间接证法,。,3,二、真值表法,由定义,1-8.1,可以看出，要证明,C,是一组前提,H,1,，,H,2,，,，,H,n,的有效结论，只需证明,H,1,H,2,H,n,C,为重言式。而,证明一个公式为重言式，可以用真值表、等值演算、主析,(,合,),取范式或已知的蕴含式,等方法进行。用等价演算和主析,(,合,),取范式证明重言式的方法前面已经讨论过了，我们已经非常熟悉了。这里仅对真值表法作简单说明。,（1）,真值表法,设,P,1,，,P,2,，,，,P,n,出现于前提,H,1,，,H,2,，,，,H,m,和结论,C,的全部命题变元，假定对,P,1,，,P,2,，,，,P,n,作了全部的真值指派，这样就能对应地确定,H,1,，,H,2,，,，,H,n,和,C,的所有真值，列出这个真值表，即可看出,H,1,H,2,H,m,C,是否成立,即找出,H,1,，,H,2,，,，,H,m,均为的行，对于每一个这样的行，若,C,也为,则上式成立。或,C,为，,H,1,，,H,2,，,，,H,m,中起码有一个为,4,二、真值表法,例：,分析事实：,“,如果我有时间，那么我就去上街；如果我上街，那么我就去书店买书；但我没有去书店买书，所以我没有时间。,”,。试指出这个推理前提和结论，并证明结论是前提的有效结论。,解：,令,：,我有时间。,：,我去上街。,：,我去书店买书。,根据题意，前提为：,，,，,结论为：,以下证明,是一组前提,的有效结论。,即证明：(,P,Q,)(,Q,R,),R,P,5,二、真值表法,作公式,P,Q,，,Q,R,，,R,，,P,的真值表,从表中可以看出:,P,Q,，,Q,R,，,R,都为,1,的行,(,赋值,000,的行,),，,P,也为,1,。,(或,P,为,0,的行,(,赋值,100,，,101,，,110,，,111,的行,),P,Q,，,Q,R,，,R,至少有一个为,0）,所以,(,P,Q,),(,Q,R,),R,P,P,Q,R,P,Q,Q,R,R,P,0,0,0,1,1,1,1,0,0,1,1,1,0,1,0,1,0,1,0,1,1,0,1,1,1,1,0,1,1,0,0,0,1,1,0,1,0,1,0,1,0,0,1,1,0,1,0,1,0,1,1,1,1,1,0,0,1,2,3,C,6,三、命题逻辑的推理理论,当推理中包含的命题变元较多时，真值表法或等值演算法，主析取范式法等方法的演算量太大。给推理带来了困难。为此,引入命题逻辑的推理理论,。命题逻辑的推理是一个描述推理过程的命题公式序列，其中的每个命题公式或者是已知前提，或者是由某些前提应用推理规则得到的结论(中间结论或推理中的结论)。它有两种方法：,直接证法（直接推理）,和,间接证法（间接推理）,。,7,直接证法（直接推理）,直接证法（直接推理）,基本思想,是：由一组前提出发，利用一些公认的规则，,根据已知的等价式或蕴含式，推演得到有效结论,。,公认的推理规则有4条,：,P,规则,：前提在推导过程中的任何时候都可以引入使用。,T,规则,：推导中，如果一个或多个公式蕴含着公式,S,，,则公式,S,可以引入到以后的推,理,之中。,置换规则,：在推导过程的任何步骤上，命题公式中的子,公式都可以用与之等价的公式置换。(等价式表）,合取引入规则,：任意两个命题公式,A,B,可以推出,A,B,常用的蕴含式和等价式见,P43,表1-8.3表1-8.4,8,直接证法（直接推理）,例题：,用直接推理法证明,(,)(,)(,),证法1:(1),P,-,(P,规则，引入前提),(2),Q,T(1),E,-,(对(1)式,T,规则,根据,E,16,蕴含等值式),(3),P,-,(P,规则，引入前提),(4),T(2),(3)I,-,(,对,(2),(3),式规则，根据,I,13,假言三,段论),(5),S,P,T(4)E,-,(对()式,T,规则,根据,E,16,蕴含等值式),(6),P,-,(P,规则，引入前提),(7),S,R,T(5),(6),I,(,对,(5),(6),式规则，根据,I,13,假言三段,论),(8),T(7)E-,(对(7)式,T,规则,根据,E,16,蕴含等值式),9,直接证法（直接推理）,证法2:(1),P,(2),R,T(1)I,(3),P,(4),R,SR,T(3)I,(5),SR,T(2)(4)I,(6),P,(7),T(5),(6),I,10,直接证法（直接推理）,用直接推理法证明,(,P,Q,)(,Q,R,),P,R,证明：,P,Q,P,P,P,Q,T I,假言推理(,I,11,),Q,R,P,R,T I,假言推理,(,I,11,),11,间接证法（间接推理）,定义1-8.2,假设公式,H,1,，,H,2,，,，,H,m,中的命题变元,P,1,，,P,2,，,，,P,n,，,对于,P,1,，,P,2,，,，,P,n,的一些真值指派，如果能使,H,1,H,2,H,m,的真值为,，则称,公式,H,1,，,H,2,，,，,H,m,是相容的。,如果对于,P,1,，,P,2,，,，,P,n,的每一组真值指派，使,H,1,H,2,H,m,的真值均为,，则称,公式,H,1,，,H,2,，,，,H,m,是不相容的。,12,间接证法（间接推理）,将不相容的概念应用于命题公式的证明(,归谬法,),设有一组前提,H,1,，,H,2，,，,H,n,，,要推出结论,C，,即要证,H,1,H,2,H,n,C,，,令,S,H,1,H,2,H,n,则上式可以简记为,S,C,由永真蕴含的定义有,1,S,C,S,C,两边否定0,S,C,H,1,H,2,H,n,C,即要证明,C,是前提,H,1,，,H,2,，,H,n,的有效结论，只须证明,H,1,H,2,H,n,C,0,(即,H,1,，,H,2，,，,H,n,与,C,不相容）,这种间接推理方法称为归谬法,13,间接证法（间接推理）,例题,证明,，,(,C),可逻辑推出,。,证明：(1),P,(2),P(,附加前提）,(3),(,C),P,(4),C,T(3)E,(E,9,德摩根律),(5),B,T(1),(2),I,(I,11,假言推理),(6),T(4)I,(I,1,简化式,),(7),(矛盾）,T(5),(6)I,(I,1,合取引入,规则),14,间接证法（间接推理）,CP,规则,间接证法的另一种情况：要证,H,1,H,2,H,n,(,)。,设,S,H,1,H,2,H,n,，,则上式可以简记为,S,(,A,B,),由永真蕴含的定义有,1,S,(,),S,(,),(,S,R,),C,(,S,R,),C,(,S,R,),C,H,1,H,2,H,n,R,C,即,H,1,H,2,H,n,R,C,所以，,要证明,H,1,H,2,H,n,(,R,C,),，,只需证明,H,1,H,2,H,n,R,C,，,其中,R,叫做附加前提,。,*,这种间接推理方法称为,CP,规则,。,15,间接证法（间接推理）,例题,证明,(,)，,B,重言蕴含,证明：(1),D,P,(,附加前提）,(2),P,(3),T(1)(2)I,析取三断论,(4),(,),P,(5),T(3),(4)I,(I,11,假言推理),(6),P,(7),T(5),(6)I,(I,11,假言推理),(8),D,CP,16,间接证法（间接推理）,例,用,CP,规则证明：,P,(,Q,R,),，,T,P,，,Q,T,R,证明：,T,P(,附加前提,),T,P,P,P,T,析取三段论,P,(,Q,R,)P,Q,R,T,假言推理,Q,P,R,T,假言推理,T,R,CP,规则,17,间接证法（间接推理）,例试构造下面推理的证明。,如果小张和小王去看电影，则小李也去看电影；,小赵不去看电影或小张去看电影；,小王去看电影。,所以，当小赵去看电影时，小李也去看电影。,解：,（,.,将简单命题符号化,),设,P:,小张去看电影。,Q:,小王去看电影。,R:,小李去看电影。,S:,小赵去看电影。,(,2.,找出前题与结论。,),前提：,(,P,Q),R,S,P,Q，,结论：,S,R,）,18,间接证法（间接推理）,故本题即要,证明：,(P,Q),R,S,P,Q,推出,S,R,证明：,(,.用,CP,规则证明,),(1),S P(,附加前提引入),(2)SP P,(3),P T(1)(2)I,(,析取三段论),(4)(,PQ)R P,(5),Q P,(6),PQ T(3)(5)I,(,合取引入规则）,(7)R T(4)(6)I,(,假言推理),(8),SR,CP,19,间接证法（间接推理）,例 构造下面推理的证明,。,如果小张守第一垒并且小李向,B,队投球，则,A,队将取胜；,或者,A,队未取胜，或者,A,队获得联赛第一名；,A,队没有获得联赛的第一名；,小张守第一垒。,因此，小李没有向,B,队投球。,解,:,设,P:,小张守第一垒。,Q:,小李向,B,队投球。,R:A,队取胜。,S:A,队获得联赛第一名。,20,间接证法（间接推理）,前提：(,PQ)R,RS,S,P,结论：,Q,证明：(,用归谬法,),(1),Q,P(,附加前提）,(2),RS,(3),S,(4),R,T(2)(3)I,(,析取三段论),(5)(,PQ)R P,(6)(,PQ),T(4)(5)I,(,拒取式),(7),PQ,T(6)E,(,德摩根律，置换）,(8),P,P,(9),Q,T(7)(8)I(,析取三段论,(10),QQ（,矛盾）,(1)(9),I,(,合取引入规则）,21,本课小结,有效推理,真值表法论证,命题逻辑的推理理论直接证法，间接证法（归缪法、规则）,22,课后作业,通读书本本节例题,P47(2)a,c,e (3)a,b,补充:构造下面推理的证明,以下前提已经成立:,(1)甲或乙作的案,(2)如果甲作的案,作案时间应在午夜后,(3)若乙证词正确,则午夜灯光未灭,(4)若乙证词不正确,则作案时间不在午夜之后,(5)午夜灯光灭了,结论:乙作的案,令,A:,甲做的,案,B:,乙做的案,C:,作案时间在午夜前,D:,乙证词正确,E:,午夜灯光未灭,23,