数理逻辑2014

1、数理逻辑,数理逻辑：用数学的方法研究逻辑问题。逻辑演算：命题逻辑演算、谓词逻辑演算。公理集合论证明论模型论递归论,命题,命题：可以区分真假的陈述句。今天是星期一。南京是江苏的省会。今天天气真好啊！禁止抽烟！你有笔吗？,联结词与真值表,原子命题：不能再分解的命题。今天是星期一。南京是江苏的省会。他在跑步或打球。,联结词与真值表,否定(非）：含义：不如果p表示“今天是星期一”，则p表示“今天不是星期一”。,联结词与真值表,合取词：含义：并且如果p表示“今天是星期一”，q表示“今天是晴天”，则pq表示“今天是星期一并且今天是晴天”。,联结词与真值表,析取词：含义：或者如果p表示“小王在跑步”，q表示

2、“小李在打球”，则pq表示“小王在跑步或者小李在打球”。,联结词与真值表,不可兼或:小王现在在操场或者教室，用r表示。p表示“小王在操场”，q表示“小王在教室”,pq并没有完全刻划上述命题,r应该为：(pq)(pq),联结词与真值表,蕴含词：含义：如果.那么.如果p表示“我有空”，q表示“我去图书馆”，则pq表示“如果我有空,那么我就去图书馆”。,联结词与真值表,蕴含怪论：如果今天是星期一，那么南航位于北京。,联结词与真值表,等值(价)词：含义：当且仅当，同真假，同或如果p表示“今天天气好”，q表示“小李上街去”，则pq表示“当且仅当今天天气好，小李上街去”。,联结词与真值表,联结词的优先顺序

3、：、用命题符号及联结词来表示下列命题：p：今天下雨。q:我进城去。r：我有空。如果今天下雨，我就不进城去。如果今天不下雨，并且我有空，我就进城去。如果今天我没进城去，那么今天下雨或者我没有空。,联结词与真值表,指派：对命题逻辑公式中的每个命题符号指定真假值，称之为该公式的一个指派(解释、模型)。成真指派：使公式取值为真的指派。成假指派：使公式取值为假的指派。,联结词与真值表,永真式（重言式）：如果一个公式在所有指派下取值都为真，称之为永真式。永假式（矛盾式）：如果一个公式在所有指派下取值都为假，称之为永假式。,联结词与真值表,同真假式：如果两个公式在所有指派下的真假值都相同，称这两个公式是同真

4、假式。,联结词与真值表,一些同真假式交换律：pq与qp结合律：p(qr)与(pq)r德摩根律：(qr)与qr吸收律：p(pq)与p逆否律：pq与qppq与pqpq与(pq)(qp)(pq)与pq,命题逻辑自然推理系统N,N中的符号：命题符号：p,q,r,pi,qi,ri联结词：、辅助符号：(，),命题逻辑自然推理系统N,N中的合式公式：命题符号是合式公式如果A,B是合式公式，则A,(AB),(AB),(AB),(AB)也是合式公式。只有通过在有限步内得到的符号串才是合式公式。可以按优先级、省略括号判断下列符号串是否为合式公式pq,pq,pq,pq,pq,命题逻辑自然推理系统N,一些约定：A，B

5、，Ai，Bi表示合式公式。，i，i表示合式公式的集合。A表示可以变形为A。(或者说可以推出A。)A，B表示A并且B。A表示AA表示并且A注：以上各符号不在N中，是元语言，而不是对象语言。,命题逻辑自然推理系统N,系统N的推理规则：1.A1，A2.AnAi(i=1,2,.,n)()2.如果()且A，则A(传递律)3.如果A，则,A(增加前提律或单调律)4.如果,AB,B，则A()(反证律)5.AB，AB(-)6.如果,AB，则AB(+),命题逻辑自然推理系统N,7.ABA，B（-）8.A，BAB（+）9.如果AC且BC，则ABC（-）10.AAB，BA（+）11.AB，AB以及AB,BA（-）1

6、2.如果,AB且,BA，则AB（+）,命题逻辑自然推理系统N,系统N的证明：A的一个证明指下述的序列1A1，2A2，.nAn，其中nAn就是AiAi是由前面的推理形式及推理规则得到。,N系统的展开,pf:1.AA(),Th2:ABA（肯定后件律）,pf:1.A,BA()2.ABA(1,+),Th1:AA,N系统的展开,AB,ABAB，BC,ABAB，BC,ABCBC,BCAB，BC,ACAB，BCAC,pf:,(-)(1单调律)()(-)(2,3,4传递律)(7,+),Th3:AB，BCAC（传递律）,N系统的展开,A,A,BAA,A,BAA,A,BA,AA,AB,pf:,()()(合并)(3

7、,),Th4:作业,Th6:作业Th7:作业,Th5:A，AB（矛盾推出一切）,N系统的展开,A,AA,AAA,:,()(1,),()(1,Th8)(1,2,单调律)()(3,4,),Th8:AA（传递律）,N系统的展开,AAAA,AA,A,AB,B,AB,BA,pf:,()(-)(1,2,单调律)()(已知)(3,4,5,传递律)(6,),Th9:如果,AB,B,则A(+,归缪律),N系统的展开,A1.A2.A3.B1.B2.B3.B4B5,(已知或假设)(已知或假设)(已知或假设)A1,A2,A3B1A1,A2,A3B2A1,A2B3A1,A2B4A1B5,斜形证明：,N系统的展开,Th2

8、:ABA（肯定后件律）,斜形证明：,A(已知)A(),A(已知)B(H)假设A()BA(2,3,+),Th1:AA,N系统的展开,AB(已知)BC(已知).A(H).AB().B(3,4,-).BC().C(5,6,-)AC(3,7,+),AB,BC,AABAB,BC,ABAB,BC,ABCAB,BC,ACAB,BCAC,Th3:AB，BCAC（传递律）,N系统的展开,(已知).A(H).BAB(2,6,+),ABAB(+),斜形证明：+,N系统的展开,A（BC）(已知)AB(已知).A(H).BC(1,3,-).B(2,3,-).C(4,5,-)AC(3,6,+),A(BC),ABCA,AB

9、BB,BCCA(BC),AB,ABCA(BC),AB,ABA(BC),AB,ACA(BC),ABAC,Th4:A（BC），ABAC,N系统的展开,A(已知)A(已知).B(H)假设.A().A()B(3,4,5,),A,A,BAA,A,BAA,AB,Th5:A，AB（矛盾推出一切）,N系统的展开,A(已知).A(已知).B(Th5)AB(3,6,+),A,AB(Th5)AAB(1,+),Th6:AAB,N系统的展开,A(已知).A(已知).B(Th5)AB(3,6,+),A,AB(Th5)AAB(1,+),Th7:AAB,N系统的展开,(已知).A(H).B.BA(2,4,6,),AB,ABA

10、(),斜形证明：,N系统的展开,Th8:AA（传递律）,:,:,A(已知)A(H)A()A(1,2,3,),A(已知)A(H)A(2,Th8,)A()A(2,3,4,),N系统的展开,Th10:AB，BA,AB(已知).B(已知).A(H).B(1,3,-).A(2,3,4,+),N系统的展开,Th11:ABBA,AB(已知).B(H).A(1,2,TH10)BA(2,3,+),AB(已知).B(H).A(H).B(1,3,-).A(2,3,4,+)BA(2,5,+),N系统的展开,Th12:AB，BA,AB(已知).B(已知).A(H).B(1,3,-).A(2,3,4,),N系统的展开,T

11、h13:ABBA,AB(已知).B(H).A(1,2,TH12)AB，BABA(2,3,+),N系统的展开,Th14:AB，BA,AB(已知).B(已知).A(H).B(1,3,-).A(2,3,4,+),N系统的展开,Th15:ABBA,AB(已知).B(H).A(1,2,TH14)BA(2,3,+),N系统的展开,Th16:AB，BA,AB(已知).B(已知).A(H).B(1,3,-).A(2,3,4,),N系统的展开,Th17:ABBA,AB(已知).B(H).A(1,2,TH16)BA(2,3,+),N系统的展开,Th18:AAA,AA(已知).A(H).A(1,2,-)A(2,3,

12、),N系统的展开,Th19:AAA,AA(已知).A(H).A(1,2,-)A(2,3,+),N系统的展开,Th20:AB，ABA,AB(已知).AB(已知).A(H).B(1,3,-).B(2,3,-)A(3,4,5,+),N系统的展开,Th21:AB，ABB,AB(已知).AB(已知).B(H).A(1,3,Th10).A(2,3,Th16)B(3,4,5,),N系统的展开,Th22:(AB)A,B,(AB)(已知).A(H).AB(否定前件律)A(1,2,3,),(AB)(已知).B(H).AB(肯定后件律)B(1,2,3,),N系统的展开,Th23:如果，AC且，BC，则，ABC(-)

13、,如果AC且BC，则ABC（-）,N系统的展开,Th24:ABBA,AB(已知)A(1,-)B(1,-)BA(2,3,+),BA(已知)A(1,-)B(1,-)AB(2,3,+),N系统的展开,Th24:(AB)CA(BC),(AB)C(已知)AB(1,-)C(1,-)B(2,-)A(2,-)BC(4,3,+)A(BC)(5,6,+),N系统的展开,Th24:AB(AB),AB(已知)A,B(1,-).AB(H).B(1,3,-)(AB)(4,2,3,+),(AB)(已知)A(1,TH22)B(1,TH22)B(-)AB(2,4,+),N的可靠性：如果A，则A是永真式。N的完备性：如果A是永真

14、式，则A。,命题逻辑的可靠性与完备性,命题逻辑的可靠性与完备性,证明N中的公式A是永真式：1证明A。（可用斜形证明）2用真值表验证。证明N中的公式A不是永真式：用真值表验证。,谓词与量词,命题逻辑的局限性：所有的整数都是有理数。p2是整数。q2是有理数。r在命题逻辑中，分别用p,q,r来表示上述命题。一方面，我们希望有p,qr另一方面，在N中p,qr不成立。,谓词与量词,命题的分解：所有的整数都是有理数。x(P(x)Q(x),谓词与量词,命题的分解：所有的整数都是有理数。x(P(x)Q(x)2是整数。P(2)2是有理数。Q(2)在谓词逻辑推理系统中有x(P(x)Q(x)，P(2)Q(2),谓词

15、与量词,谓词：表示个体的性质或个体之间的关系。一元谓词：P(x):可以表示x是整数。二元谓词：P(x,y):可以表示xy。三元谓词：P(x,y,z):可以表示xyz。,谓词与量词,量词：所有，每一。(All,Any)：存在。(Exist)量词的辖域：量词所管辖的公式。x(P(x,y)yQ(x,y)xyQ(x,y)x(P(x,y)yQ(x,y)xyQ(x,y)x(P(x,y)yQ(x,y)xyQ(x,y)x(P(x,y)yQ(x,y)xyQ(x,y)x(P(x,y)yQ(x,y)xyQ(x,y),谓词与量词,约束变元与自由变元：如果x出现在x或x的辖域中，则称该x是约束出现，否则称该x为自由出现

16、。xP(x,y)yQ(x,y)xyR(x,y),谓词与量词,个体常元：表示固定的个体。a：表示小王。P(x):x是教师。P(a):小王是教师。函数符号：表示个体域上的n元函数。P(x):x是教师。f(x):x的父亲。P(f(x):x的父亲是教师。,谓词与量词,用符号来表示下述命题：P(x):x是素数。Q(x):x是偶数。R(x,y):xy。E(x,y):x=y。1.有的数既是素数又是偶数。2.任何大于2的素数都不是偶数。3.无论x是多大的素数，还有比x更大的素数。4.没有比2大的偶数是素数。5.没有最大的素数。6.有且只有一个偶数是素数。,谓词与量词,命题分解后引进的符号：个体常元个体变元（包

17、含约束出现的和自由出现的）函数符号谓词符号量词,谓词与量词,谓词逻辑公式的解释（模型）：指定一个集合作为论域。将每个常元指定为论域中的一个元素。将n元函数符号指定为论域上的n元函数。将n元谓词符号指定为论域上的n元关系。将自由出现的变元指定为论域中的一个元素。,谓词与量词,谓词逻辑公式的解释：xP(x)论域：1,2,3,4,P(x):x0x(P(x)Q(x)论域：1,2,3,4,P(x):x是整数，Q(x)：x是有理数,谓词与量词,谓词逻辑公式的真假值对于有限论域U=a1.anxB(x)为真iffB(a1)为真且B(a2)为真.B(an)为真iffB(a1)B(a2).B(an)为真xB(x)

18、为真iffB(a1)为真或B(a2)为真.B(an)为真iffB(a1)B(a2).B(an)为真,谓词与量词,谓词逻辑公式的真假值：xP(x)论域：1,2,3,4,P(x):x0x(P(x)Q(x)论域：1,2,3,4,P(x):x是整数，Q(x)：x是有理数,谓词与量词,永真式：如果一个公式在所有解释下取值都为真，称之为永真式。x(R(x)R(x)永假式：如果一个公式在所有解释下取值都为假，称之为永假式。x(R(x)R(x),谓词与量词,同真假式：如果两个公式在所有解释下的真假值都相同，称这两个公式是同真假式。一些同真假式xA(x)与xA(x)xA(x)与xA(x)xA(x)xB(x)与x

19、(A(x)B(x)xA(x)xB(x)与x(A(x)B(x),谓词逻辑自然推理系统NL,NL中的符号：个体词：a,b,c,ai,bi,ci谓词：F,G,H,Fi,Gi,Hi约束变元：x,y,z,xi,yi,zi量词：，联结词：、辅助符号：(，),谓词逻辑自然推理系统,中的合式公式：如果A是n元谓词符号，a1,a2.an是个体词，则A(a1,a2.an)是合式公式如果A,B是合式公式，则(A),(AB),(AB),(AB),(AB)也是合式公式。A(a)是合式公式，a在其中出现，x不在其中出现，则xA(x)与xA(x)是合式公式只有通过在有限步内得到的才是合式公式。判断下列符号串是否为合式公式P

20、(x),xQ(x),xF(x,a),谓词逻辑自然推理系统,系统的推理规则：1.A1，A2.AnAi(i=1,2,.,n)()2.如果()且A，则A()(传递律)3.如果A，则,A(0)(单调律)4.如果,AB,B，则A()(反证律)5.AB，AB(-)6.如果,AB，则AB(+),谓词逻辑自然推理系统,系统的推理规则：7.ABA，B（-）8.A，BAB（+）9.如果AC且BC，则ABC（-）10.AAB，BA（+）11.AB，AB以及AB,BA（-）12.如果,AB且,BA，则AB（+）,谓词逻辑自然推理系统,系统的推理规则：13xA(x)A(a)（-）（消去律）14如果A(a)且a不在中出现

21、，则xA(x)（+）（引入律）15,A(a)B且a不在和B中出现，则,xA(x)B（-）（消去律）16A(a)xA(x),A(x)是由A(a)中的a的部分出现替换为x而得(+)（引入律）,谓词逻辑自然推理系统,系统的推理规则：14如果A(a)且a不在中出现，则xA(x)（+）（引入律）=p,p:今天学校放假。a:小王A(a):小王没到学校上课。如果pA(a)，则pxA(x)=p(a),p(a):小王今天生病。A(a):小王没到学校上课。如果p(a)A(a)，则不一定有p(a)xA(x),谓词逻辑自然推理系统,系统的推理规则：15,A(a)B且a不在和B中出现，则,xA(x)B（-）（消去律）=

22、,A(a):小王没到学校上课。B:今天没有全部出勤。如果A(a)B，则xA(x)B=,A(a):小王没到学校上课。B(a):今天小王生病。如果A(a)B(a)，则不一定有xA(x)B(a),谓词逻辑自然推理系统,.A(a)取a1xA(x)(4,+),.A(a)(H)取a1.xA(x)(4,+),系统的推理规则：14如果A(a)且a不在中出现，则xA(x)（+）（引入律）,谓词逻辑自然推理系统,xA(x)(已知）A(a)(1,-),系统的推理规则：15,A(a)B且a不在和B中出现，则,xA(x)B（-）（消去律）,谓词逻辑自然推理系统,A(a)(H)取a1,4.B.xA(x)(已知).B(2,

23、4,-),xA(x)(已知).A(a)(H)取a1,4.BB(2,4,-),系统的推理规则：15,A(a)B且a不在和B中出现，则,xA(x)B（-）（消去律）,系统的展开,Th2:xA(x)yA(y),xA(x)(已知)A(a)(1,-)取a1yA(y)(2,+),yA(y)(已知)A(a)(1,-)取a1xA(x)(2,+),系统的展开,Th3:xA(x)yA(y),xA(x)(已知)A(a)(H)取ayA(y)yA(y)(2,+)yA(y)(2,3,-),或,A(a)(H)取ayA(y)yA(y)(1,+)xA(x)(已知)yA(y)(1,2,-),系统的展开,Th14:x(A(x)B(

24、x),x(B(x)C(x)x(A(x)C(x),x(A(x)B(x)(已知)x(B(x)C(x)(已知)A(a)B(a)(1,-)B(a)C(a)(2,-)A(a)C(a)(3,4传递律)x(A(x)C(x)(5,+),取a1,2,系统的展开,Th15:AxB(x)x(AB(x)xA,AxB(x)(已知)AB(a)(1,-)取a1x(AB(x)(2,+),AxB(x)(已知)A(H)xB(x)(1,2,-)B(a)(3,-)取a1AB(a)(4,+)x(AB(x)(5,+),系统的展开,Th15:AxB(x)x(AB(x)xA,AxB(x)(已知)A(H)xB(x)(1,2,-)B(a)(3,

25、-)取a1AB(a)(4,+)x(AB(x)(5,+),系统的展开,Th15:AxB(x)x(AB(x)xA,AxB(x)(已知)(AB(a)(H)取a1A,B(a)(2,(AB)A,B)xB(x)(3,+)xB(x)(4,xB(x)xB(x)xB(x)(1,3,-)xB(x)(6,xB(x)xB(x)AB(a)(2,5,)x(AB(x)(5,+),系统的展开,Th15:AxB(x)x(AB(x)xA,AxB(x)(已知)(AB(a)(H)取a1A,B(a)(2,(AB)A,B)xB(x)(1,3,-)B(a)(3,-)AB(a)(2,5,)x(AB(x)(5,+),系统的展开,Th15:AxB(x)x(AB(x)x