命题演算系统.pptx

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,命题演算系统,命题演算系统,Lp,命题演算系统通常记为:,P,分为公理演算系统和自然演绎推理系统,她们都就是用形式语言构造出来得。所谓公理演算系统,指得就是由一些基本命题(即公理)和推导规则以及由此推出得一些命题(即定理)而形成得演绎系统。所谓自然演绎系统,指得就是没有公理只依赖推导规则推出一些命题(即定理)而形成得演绎系统。,命题演算系统,Lp,形式化得公理系统又称为形式系统。一个形式系统主要由形式语言、初始公式、变形规则以及由她们得到得公式四部分组成。下面具体介绍命题演算系统。,命题演算系统,Lp,初始符号,1,、命题变元:,p,q,r,;,2,、命题联接词:,;,3,、辅助符号:(,)。,形成规则,1,、任何命题变元就是合式公式;,2,、如果,A,就是合式公式,则(,A,)就是合式公式;,3,、如果,A,、,B,就是合式公式,则(,A B,)、(,A B,)、(,A B,)、(,A,B,)就是合式公式;,4,、只有按照,1,、,2,、,3,得规定形成得符号串才就是合式公式。,命题演算系统,Lp,下面给出初始公式(即公理演算系统得公理)和初始规则:,初始公式,AP1 A(B A),AP2 (A (B C)(A B)(A C),AP3 (,A B)(,A B)A),初始规则(又叫变形规则),MP 分离规则 若 A B且A,则B。,SB 代入规则 若 A,则 A(p1/B1,p2/B2,pn/Bn),其中,A(p1/B1,p2/B2,pn/Bn)表示将A中得命题变元p1,p2,pn(如果有得话)处处分别换成B1,B2,Bn。这就就是代入规则,运用代入规则时请注意,一定就是处处代入。,命题演算系统,Lp,一个使用形式语言得形式系统,通过初始公式和初始规则得到得公式就就是这个系统得定理。一个形式系统得任务也就就是证明这些定理得成立。下面给出系统中得一些定义。,命题演算系统,Lp,定义,3,(证明得定义),LP,中得证明就是一个合式公式得有限序列:,A1,A2,An,且满足以下条件:对每一个,Ai,(,1in,)要么就是公理,要么就是由前面得公式根据变形规则得到得。,定义,4,(,A,证明得定义)如果一个证明,A1,A2,An,中得,An=A,我们就称这个证明叫做关于,A,得证明,也就就是,A,证明。,定义,5,(定理得定义)如果有一个,A,证明,则称,A,就是这个系统得定理。记作:,LP A,。,定理,1,AA,证明:,(,1,),A,(,B A,),AP1,(,2,),A,(,A A,),A,)(,1,),SB,(,3,)(,A,(,B C,)(,A B,)(,A C,),AP2,(,4,),A,(,A A,),A,)(,A,(,A A,)(,A A,)(,3,),SB,(,5,)(,A,(,A A,)(,A A,)(,2,)(,4,),MP,(,6,),A,(,A A,)(,1,),SB,(,7,),A A (5)(6)MP,命题演算系统,Lp,定义6,(推演得定义)如果A1,A2,An就是一个满足如下条件得公式序列,则称她就是以,为前提得推演。,条件:,任一Ai(1i n)就是,中得元素,或者,就是公理,或者,就是由前面得公式根据变形规则得到得。,定义7,从,到A得推演:如果A1,A2,An就是,以为前提得推演,并且An=A,我们就称她就是从,到A得推演,或者说A就是从,出发得到得推论,记作:,A。,如果,=B,可以记作:BA;如果,=B,C,可以记作:B,CA;如果,=,就记作:A。从出发推出A,A就就是一个定理。,演绎定理得证明见教材。,演绎定理:,如果,A B,则,AB。,演绎定理得证明需要数学归纳法,数学归纳法就是证明无穷个命题成立得方法,她由两部分组成,分别就是归纳基础和归纳步骤。归纳法可以分为两类:,第一类归纳法:有一批编了号码得命题,(1)我们能证明第1号命题就是正确得;,(2)如果我们还能证明,在第,n,号命题正确得时候,第,n,+1号命题也正确,那么这一批命题就都就是正确得。,第二类归纳法:有一批编了号码得命题,(,1,)我们能证明第,1,号命题就是正确得;,(,2,)如果我们还能证明,在,k,n,时命题正确得时候,k,=,n,时命题也正确,那么这一批命题都就是正确得。,大家有疑问的，可以询问和交流,可以互相讨论下，但要小声点,证明:,归纳基础:令该演绎序列有一个公式B构成,为LP中任意合式公式得集合,如果如果,A B,则,AB。,情况1:B就是公理,(1)B 公理,(2)B (A B)AP1 SB,(3)A B (1)(2)MP,即,A B得证。,情况2:B就是,中得公式,记作:B,(1)B 前提,(2)B (A B)AP1 SB,(3)A B (1)(2)MP,即 A B得证。,情况3:B就就是A。此时要证 A A,根据定理1得证。,归纳基础证毕。,归纳步骤:假设当由,和A得出B得演绎得公式数目小于,n,时,演绎定义成立,现在证明当由,和A得出B得演绎得公式数目等于,n,时,演绎定理也成立。分四种情况:,情况1:B就是公理,同归纳基础中情况1相同。,情况2:B就是中得公式,同上。,情况3:B就就是A,也同上。,情况4:B就是由出现在演绎序列中在前得两个公式,通过分离规则得到得,此时前面必定有两个这样得公式:一个就是C,一个就是C B。两者中得任一必然在LP中由,和A为前提推出,把这些公式序列数目分别设为:,k,和,m,k,和,m,都小于,n,。根据归纳假设可得:,(A C)和,(A (C B),以为,前提得出(A B)得演绎如下:,(1),(k)(A C),(,m,)A (C B),(,m,+1)(A (C B)(A C)(A B)AP2,(,m,+2)(A C)(A B)(m)(m+1)MP,(,m,+3)A B (m+2)(k)MP,因此,在以上四种情况下,都有,A B。演绎定义证毕。,命题演算系统得可靠性,命题演算系统,LP,得可靠性,古典得一致性,系统,S,就是一致得,当且仅当,不存在公式,和都就是,S-,可证得。,语法得一致性,系统,S,就是一致得,当且仅当,并非任一公式都就是,S-,可证得。,语义得一致性,系统,S,就是一致得,当且仅当,S,得内定理都就是有效得。,语义一致性就就是可靠性,因此,通常情况下把系统得一致性和可靠性看作就是相同得。,定义8,命题演算系统LP中得一个赋值就是一个函数,v,v,得定义域就是系统LP中得合式公式,值域就是1,0(1表示真,0表示假),对LP中得任意公式A,B,满足:,定义9,LP中得公式A就是重言式,当且仅当,对每一个赋值,v,都有,v,(A)=1。,引理1,(MP保真性定理)令A,B就是LP中得任意公式,如果A就是重言式且AB就是重言式,则B也就是重言式。,定理,4,(可靠性定理):系统,LP,中得每一个定理都就是重言式。,证明:,令,A,就是,LP,中得一个定理,必然存在,LP,中对,A,得一个证明,假设该证明就是由,n,个公式,A1,A2,A,n,组成得序列,现在对,n,进行数学归纳即可证得可靠性定理。,归纳基础:,当,n,=1,时,即,A,在,LP,中得证明序列只有一个公式,很显然,A,一定就是系统中得一个初始公式,即公理,公理都就是重言式。(可用真值表法证明),归纳步骤:,假设LP中得证明序列小于,n,得所有定理都就是重言式,证明LP中得证明序列为,n,得定理也就是重言式。现在令A得证明序列为,n,证明序列中得第,n,个公式就就是A,有两种情况:,情况1:A就是公理。,情况2:A就是由证明序列中在前得两个公式通过分离规则得到得,此时必有两个公式为:B和B A。又因为她们都就是在A前面得公式,因此证明序列必然小于,n,根据归纳假设,B和B A都就是重言式。再根据引理1,得到A也就是重言式。可靠性定理证毕。,定义,10,一个系统就是一致得,当且仅当,对系统中得任意合式公式,A,A,和,A,不能都就是该系统得定理。,定理,5,(一致性定理)命题演算系统,LP,就是一致得,即对,LP,中得任一公式,A,和,A,不能都就是命题演算系统,LP,得定理。,定理,6,LP,就是一致得,当且仅当,LP,中存在一个公式不就是她得定理。,