数理逻辑逻辑公理系统幻灯片.ppt

《数理逻辑逻辑公理系统幻灯片.ppt》由会员分享，可在线阅读，更多相关《数理逻辑逻辑公理系统幻灯片.ppt（157页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、数理逻辑逻辑公理系数理逻辑逻辑公理系统统第1页，共157页，编辑于2022年，星期六主要内容主要内容逻辑公理系统逻辑公理系统命题逻辑公理系统命题逻辑公理系统谓词逻辑公理系统谓词逻辑公理系统定理证明定理证明公理系统性质公理系统性质理论与模型理论与模型判定问题判定问题第2页，共157页，编辑于2022年，星期六形式系统形式系统一个形式系统应当包括以下几部分。一个形式系统应当包括以下几部分。(1)(1)各种初始符号各种初始符号。初始符号是一个形式系统的。初始符号是一个形式系统的“字母字母”，经解释后其中一部分，经解释后其中一部分是初始概念。是初始概念。(2)(2)形成规则形成规则。规定初始符号组成各

2、种合适符号序列的规则。经解释后合式符号序。规定初始符号组成各种合适符号序列的规则。经解释后合式符号序列是一子句，称为系统里的合式公式或命题。列是一子句，称为系统里的合式公式或命题。(3)(3)公理公理。把某些所要肯定的公式选出，作为推导其它所要肯定的公式的出发点，这。把某些所要肯定的公式选出，作为推导其它所要肯定的公式的出发点，这些作为出发点的公式称为公理。些作为出发点的公式称为公理。(4)(4)变形规则变形规则。变形规则规定如何从公理和已经推导出的一个或几个公式经过符。变形规则规定如何从公理和已经推导出的一个或几个公式经过符号变换而推导出另一公式。经过解释，变形规则就是推理规则。号变换而推导

3、出另一公式。经过解释，变形规则就是推理规则。应用变形规则进行推导可以得到一系列公式，这些公式经过解释是系统的定应用变形规则进行推导可以得到一系列公式，这些公式经过解释是系统的定理。理。形式系统完全由一套表意符号建立，它能克服日常语言的歧义形式系统完全由一套表意符号建立，它能克服日常语言的歧义性，使概念、判断、推理精确化。性，使概念、判断、推理精确化。第3页，共157页，编辑于2022年，星期六逻辑公理系统逻辑公理系统公理系统公理系统从一些从一些公理公理出发，根据出发，根据演绎法演绎法，推导出一系列，推导出一系列定理定理，形成的演绎体系叫，形成的演绎体系叫作作公理系统公理系统。公理系统的组成：公

4、理系统的组成：符号集；符号集；公式集公式集公式是用于表达命题的符号串；公式是用于表达命题的符号串；公理集公理集公理是用于表达推理由之出发的初始肯定命题；公理是用于表达推理由之出发的初始肯定命题；推理规则集推理规则集推理规则是由公理及已证定理得出新定理的规则；推理规则是由公理及已证定理得出新定理的规则；定理集定理集表达了肯定的所有命题。表达了肯定的所有命题。第4页，共157页，编辑于2022年，星期六主要内容主要内容逻辑公理系统逻辑公理系统命题逻辑公理系统命题逻辑公理系统谓词逻辑公理系统谓词逻辑公理系统定理证明定理证明公理系统性质公理系统性质理论与模型理论与模型判定问题判定问题总结总结第5页，共

5、157页，编辑于2022年，星期六命题逻辑公理系统命题逻辑公理系统定义：命题逻辑的公理系统定义定义：命题逻辑的公理系统定义:(1).(1).符号集合：符号集合：1).1).命题变元命题变元Q Q1 1,Q,Q2 2,Q Qn n2).2).联结词符号：联结词符号：，;3).3).括号：括号：(,)(,)(2).(2).形成规则形成规则(公式定义公式定义)：1).1).若若Q Q是命题变元，则是命题变元，则Q Q是公式；是公式；2).2).若若Q Q是公式，则是公式，则(Q)Q)是公式；是公式；3).3).若若Q,RQ,R是公式，则是公式，则(Q(QR)R)是公式。是公式。第6页，共157页，编

6、辑于2022年，星期六命题逻辑公理系统命题逻辑公理系统(续续)(3).(3).公理：公理模式中公理：公理模式中P,Q,RP,Q,R为任意公式为任意公式1).1).公理模式公理模式A A1 1：R R(Q(QR)R)2).2).公理模式公理模式A A2 2：(P(P(Q(QR)R)(P(PQ)Q)(P(PR)R)3).3).公理模式公理模式A A3 3：(Q QR)R)(R(RQ)Q)(4).(4).变形规则：推理规则变形规则：推理规则(分离规则分离规则MPMP规则规则)若若Q Q和和Q QR R成立，则成立，则R R成立。其中，成立。其中，Q Q和和Q QR R称为前提，称为前提，R R称称为

7、结论。为结论。第7页，共157页，编辑于2022年，星期六缩写定义缩写定义谓词公理系统中仅使用了谓词公理系统中仅使用了 和和联结词符号，而其他联结词符联结词符号，而其他联结词符号号,可以认为是缩写公式，用可以认为是缩写公式，用表示缩写定义。表示缩写定义。(1).Q(1).Q R R(Q QR)R)(2).Q(2).Q R R (Q(QR)R)(3).Q(3).QR R(Q(QR)R)(R(RQ)Q)(4).Q(4).Q R R (Q(QR)R)第8页，共157页，编辑于2022年，星期六推理序列推理序列已知已知Q成立成立，证明证明RQ成立成立A1=Q(RQ)A A1A2=Q Q A3=RQ推理

8、序列推理序列=Q，公式集，公式集前提前提A A1 1、A A2 2、A A3 3 推理序列推理序列A A3 3 结论结论第9页，共157页，编辑于2022年，星期六演绎与推理序列演绎与推理序列定义定义3.2 3.2 设设是合式公式集是合式公式集,Q Q是合式是合式公式，有推理步骤公式，有推理步骤A A1 1,A,A2 2,A An n，公式序列，公式序列 1 1,2 2,n n，其中，其中A A1 1=1 1A A2 2=2 2.A An n=n n (n n =Q=Q)每个每个 k k满足以下条件之一，满足以下条件之一，(1)(1)是公理；是公理；(2)(2)k k ；(3)(3)有有i,j

9、k i,jk k k=i i j j由由 i i,j j用用MPMP规则推出。规则推出。则称它为则称它为Q Q的从的从的一个的一个推演推演(演绎演绎),记记为为 Q Q。称为推演的称为推演的前提集前提集，称称为为结论结论推理序列推理序列如果推理步骤序列是如果推理步骤序列是A A1 1,A,A2 2,A An n，则推理则推理序列长度序列长度n n。推论：推论：如果如果Q Q是公理或是公理或 Q，则则Q第10页，共157页，编辑于2022年，星期六证明与定理证明与定理如果存在从如果存在从推演出推演出Q，则记为，则记为Q。Q1,Q2,QnQ简记为简记为Q1,Q2,QnQ如果如果为空集为空集，则记为

10、，则记为Q。如果如果Q，并且有推理步骤，并且有推理步骤A1,A2,An，则，则A1,A2,An称为的一个称为的一个证明证明。如果如果Q，则，则Q称为称为定理定理。第11页，共157页，编辑于2022年，星期六P,Q(PR)QRA1=P A1A2=P(QP)A1 A1 A3=QP A2=A1 A3 A4=Q(PR)A4 A5=(Q(PR)(QP)(QR)A2 A2 A6=(QP)(QR)A5=A4A6 A7=(QR)A6=A3A7 第12页，共157页，编辑于2022年，星期六例：例：(QR)(QQ)A1=Q(RQ)A A1 1A2=(Q(RQ)(QR)(QQ)A A2 2A3=(QR)(QQ)

11、A2=A1A3第13页，共157页，编辑于2022年，星期六 Q(QR)(涵义涵义)A1=Q(RQ)A1A1A2=(RQ)(QR)A3A3A3=Q(QR)A1，A2A3第14页，共157页，编辑于2022年，星期六演绎定理演绎定理QR 当且当且 仅当仅当QR归纳基础：归纳基础：用关于用关于Q到到R的推演长度的推演长度n作归纳证明。作归纳证明。当当n=1时，时，R或为公理，或属于或为公理，或属于，或，或R是是Q。若若R是公理，则是公理，则A1=RA2=R(QR)A3=(QR)所以所以QR，从而从而QR若若R，则，则A1=RA2=R(QR)A3=(QR)有有QR若若R=Q，则，则QQ所以所以 QQ

12、第15页，共157页，编辑于2022年，星期六演绎定理演绎定理(2)(2)归纳假设：归纳假设：假设假设Q到到R的推演长度小于的推演长度小于n定理成立。定理成立。归纳证明：当归纳证明：当Q到到R的推演长度等于的推演长度等于n时，有时，有QRA1=Q1A2=Q2Ai=PRAj=PAn=R从从的推演的推演A1=D1Am=QPAk=Q(PR)Ak+1=Q(PR)(QP)(QR)Ak+2=(QP)(QR)Ak+3=(QR)因为因为i,jn,有所以有所以QPQPQPRQ(PR)第16页，共157页，编辑于2022年，星期六演绎定理演绎定理(3)(3)到到QR的推演的推演由由QR可知，有推理序列可知，有推理

13、序列A1,A2,Am，使使得得Am=QR。证明有证明有QR。因为。因为有推理序列有推理序列A1,A2,Am，其中，其中Am=QRAm+1=QAm+2=R第17页，共157页，编辑于2022年，星期六P,QP QP,Q,(P Q)Q，P,Q,(P Q)QA1 1=P A1 1 A2 2=Q A2 2 A3 3=(P Q)A3 3 A4 4=(P Q)(P Q)QQA5 5=P Q A A4 4=A=A3 3 A A5 5A6 6=Q A A5 5=A=A1 1 A A6 6所以有所以有P,Q(P Q)，即，即P,QP Q第18页，共157页，编辑于2022年，星期六(PQ)(PR)(PQ R)演

14、绎定理：演绎定理：(PQ)(PR)，PQ RA1 1=(PQ)(PR)A1 1 A2 2=P A2 2 A3 3=(PQ)(PR)(PQ)Q RQA4 4=PQ A A3 3=A=A1 1 A A4 4A5 5=Q A A4 4=A=A2 2 A A5 5A6 6=(PQ)(PR)(PR)Q RRA7 7=PR A A6 6=A=A1 1 A A7 7A9 9=R A A7 7=A=A2 2 A A8 8A1010=Q RQ,RQ R第19页，共157页，编辑于2022年，星期六反证律反证律如果如果,QR,QR,则 QA1 1=QR QR QRA2 2=QR QR QRA3 3=(=(QR)(

15、R Q)A A 3 3A4 4=RQA A3 3=A=A2 2 A A4 4A5 5=QQ A A1 1,A,A4 4A A5 5A6 6=(Q Q)Q (Q Q)Q A7 7=QA A6 6=A=A5 5 A A7 7第20页，共157页，编辑于2022年，星期六归谬律归谬律如果如果,QR,Q R，则，则 QA1 1=Q R QR QRA2 2=Q R QR QRA3 3=(QR)(RQ)(QR)(RQ)A4 4=RQ A A3 3=A=A1 1 A A4 4A5 5=Q QA A2 2,A,A4 4A A5 5A6 6=QQ QQA7 7=Q Q A A6 6,A,A5 5A A7 7A8

16、 8=(Q Q)Q (Q Q)Q A9 9=QA A8 8=A=A7 7 A A9 9第21页，共157页，编辑于2022年，星期六定理：若定理：若R，则则QR。A1=C1Ak-1=Ck-1Ak=R RAk+1=R(QR)A1Ak+2=QR Ak+1=Ak Ak+2 QR第22页，共157页，编辑于2022年，星期六定理：若定理：若 PQ，P(QR)，则则 PR。A1=D1Am-1=Dm-1Am=PQ PQAm+1=Dm+1Am+n-1=Dm+n-1Am+n=P(QR)P(QR)Am+n+1=(P(QR)(PQ)(PR)A A2 2Am+n+2=(PQ)(PR)Am+n+1=Am+nAm+n+

17、2Am+n+3=PR Am+n+2=AmAm+n+3第23页，共157页，编辑于2022年，星期六主要内容主要内容逻辑公理系统逻辑公理系统命题逻辑公理系统命题逻辑公理系统谓词逻辑公理系统谓词逻辑公理系统定理证明定理证明公理系统性质公理系统性质理论与模型理论与模型判定问题判定问题总结总结第24页，共157页，编辑于2022年，星期六谓词逻辑公理系统谓词逻辑公理系统谓词逻辑的公理系统定义：谓词逻辑的公理系统定义：(1).(1).符号集合：符号集合：1).1).个体变元：个体变元：x x1 1,x,x2 2,2).2).个体常元：个体常元：c c1 1,c,c2 2,3).3).函词符号：函词符号：

18、f f1 11 1,f,f2 21 1,.,.；f f1 12 2,f,f2 22 2,.,.；4).4).谓词符号：谓词符号：Q Q1 11 1,Q,Q2 21 1,.,.；Q Q1 12 2,Q,Q2 22 2,.;,.;5).5).运算符号：运算符号：,；6).6).逗逗 号：号：,;,;7).7).括括 号：号：(,)(,)第25页，共157页，编辑于2022年，星期六谓词逻辑公理系统（续）谓词逻辑公理系统（续）(2).(2).项定义：项定义：1).1).个体常元是项；个体常元是项；2).2).个体变元是项；个体变元是项；3).3).若是若是t t1 1,t,tn n项，则是项，则是f

19、 fk kn n (t(t1 1,t,tn n)项。项。(3).(3).公式集合：公式集合：1).1).若是若是t t1 1,t,tn n项，则项，则Q Q k kn n (t(t1 1,t,tn n)是公式。是公式。2).2).若若Q Q是公式，则是公式，则(Q)Q)是公式；是公式；3).3).若若Q Q和和R R是公式，则是公式，则(Q(QR)R)是公式；是公式；4).4).若若Q Q是公式，则是公式，则(xQ)xQ)是公式。是公式。第26页，共157页，编辑于2022年，星期六谓词逻辑公理系统（续）谓词逻辑公理系统（续）(4).(4).公理集合：公理集合：1).1).公理模式公理模式A

20、A 1 1：Q Q(R(RQ)Q)2).2).公理模式公理模式A A 2 2：(P(P(Q(QR)R)(P(PQ)Q)(P(PR)R)3).3).公理模式公理模式A A 3 3：(Q QR)R)(R(RQ)Q)4).4).公理模式公理模式A A 4 4：xQ(x)xQ(x)Q(x)Q(x)x/t x/t 其中，项其中，项t t对于对于Q Q中的中的x x是可代入的。是可代入的。5).5).公理模式公理模式A A 5 5：x x(Q QR(x)R(x)(Q QxR(x)xR(x)其中其中x x不是不是Q Q中自由变元。中自由变元。(5).(5).推理规则推理规则1).1).分离规则（简称分离规则

21、（简称MPMP规则）：从规则）：从Q Q和和Q QR R推出推出R R。2).2).概括规则（简称概括规则（简称UGUG规则）：从规则）：从Q(x)Q(x)推出推出(xQ)xQ)。第27页，共157页，编辑于2022年，星期六缩写定义缩写定义谓词公理系统中仅使用了谓词公理系统中仅使用了 和和联结词符号，而其他联结词符号联结词符号，而其他联结词符号,可以认为是缩写公式，用可以认为是缩写公式，用表示缩写定义。表示缩写定义。(1).Q(1).Q R R(Q QR)R)(2).Q(2).Q R R (Q(QR)R)(3).Q(3).QR R(Q(QR)R)(R(RQ)Q)(4).Q(4).Q R R

22、(Q(QR)R)谓词公理系统中仅使用了量词谓词公理系统中仅使用了量词，而量词，而量词 可以认为是缩写公式，可以认为是缩写公式，用用表示缩写定义。表示缩写定义。xQ(x)xQ(x)Q(x)Q(x)第28页，共157页，编辑于2022年，星期六公理系统公理系统弗雷格公理系统弗雷格公理系统Q(RQ)(P(QR)(PQ)(PR)(P(QR)(Q(PR)(QR)(RQ)QQQQa=b(F(a)F(b)a=a xF(x)xF(x)f(a)卢卡西维茨公理系统卢卡西维茨公理系统Q(RQ)(P(QR)(PQ)(PR)(QR)(R Q)罗素公理系统罗素公理系统AA AAABABBA(AB)(ACBC)第29页，共

23、157页，编辑于2022年，星期六演绎与证明演绎与证明定义定义 设设是合式公式集是合式公式集,Q Q是合式公式，是合式公式，有推理步骤有推理步骤A A1 1,A,A2 2,A An n，公式序列，公式序列 1 1,2 2,n n，其中，其中A A1 1=1 1A A2 2=2 2.A An n=n n (n n =Q=Q)每个每个 k k满足以下条件之一，满足以下条件之一，(1)(1)是公理；是公理；(2)(2)k k ；(3)(3)有有i,jk i,jk k k=i i j j由由 i i,j j用用MPMP规则推出。规则推出。(4)(4)有有ijij使使A Aj j=x xA Ai i由用

24、由用UGUG规则推出规则推出则称它为则称它为Q Q的从的从的一个的一个推演推演(演绎演绎),记为记为 Q Q。称为推演的称为推演的前提集前提集，称称为为结论结论序列序列A A1 1,A,A2 2,A An n，称为称为从从演绎出演绎出n n的一个的一个证明证明。n n也称由也称由可可证明证明n n。推理序列推理序列如果推理步骤序列如果推理步骤序列是是A A1 1,A,A2 2,A An n，则推则推理序列长度理序列长度n n。推论：推论：如果如果Q Q是公理或是公理或 Q，则则Q第30页，共157页，编辑于2022年，星期六定理定理从系统的公理出发，根据系统允许的变形规则推得的合式公式称从系统

25、的公理出发，根据系统允许的变形规则推得的合式公式称为可证公式，或称系统里的定理。为可证公式，或称系统里的定理。定义：如果定义：如果QQ，则，则Q Q称为定理。称为定理。第31页，共157页，编辑于2022年，星期六设设 是前提，是前提，=Q=Q1 1,.,Q,.,Qn n，Q Q是结论，并且是结论，并且Q Q。一般讲，一般讲，是事实知识或归纳知识。是事实知识或归纳知识。由于证明是逻辑的，公理是逻辑真，推导规则是逻辑真，由于证明是逻辑的，公理是逻辑真，推导规则是逻辑真，但是，前提但是，前提 不是逻辑真。不是逻辑真。如果实践检验如果实践检验Q Q不为真，则不为真，则 一定有不为真语句。一定有不为真

26、语句。第32页，共157页，编辑于2022年，星期六x(P(x)P(x)A1 1=P(x)P(x)QQA2 2=P(x)P(x)Q Q R R(Q QR)R)A3 3=x(P(x)P(x)UGUG第33页，共157页，编辑于2022年，星期六 xP(x)xP(x)A1 1=xP(x)P(y)A A 4 4A2 2=(xP(x)P(y)(P(y)xP(x)(Q R)(R Q)A3 3=P(y)xP(x)A1 1,A2 2 A3 3A4 4=P(y)P(y)QQ A5 5=P(y)xP(x)A4 4,A3 3 A5 5A6 6=xP(x)P(y)A A 4 4A7 7=xP(x)xP(x)A6 6

27、,A5 5 A7 7A8 8=xP(x)xP(x)xQ(x)xQ(x)Q(x)Q(x)第34页，共157页，编辑于2022年，星期六演绎定理演绎定理 A A B B 当且仅当当且仅当 A AB B因为因为A(x)A(x)xA(x)不是有效公式，不是有效公式，A A 可证，可证，xA可证？变元变元约束变元约束变元自由变元自由变元出现出现约束出现约束出现自由出现自由出现第35页，共157页，编辑于2022年，星期六演绎定理演绎定理 A A B B，且且A A为闭公式为闭公式，当且仅当当且仅当 A AB B归纳基础：用关于归纳基础：用关于 A A 到到B B的推演长度的推演长度n n作归纳证明。作归

28、纳证明。当当n=1n=1时，时，B B或为公理，或属于或为公理，或属于 ，或，或B B是是A A。若若B B是公理，则是公理，则A A1 1=B=BA A2 2=B=B(AB)A A3 3=(AB)所以所以 AB，从而从而 A AB B若若 B B ，则，则 若若B=AB=A，则，则 A A A AA A1 1=B =B 所以所以 A AA AA A2 2=B=B(AB)A A3 3=(AB)有有 A AB B第36页，共157页，编辑于2022年，星期六演绎定理演绎定理(2)(2)归纳假设：假设归纳假设：假设 A A 到到B B的推演长度小于的推演长度小于n n定理成立。定理成立。归纳证明：

29、当归纳证明：当 A A 到到B B的推演长度等于的推演长度等于n n时，并且时，并且B B由分离规则推由分离规则推出有出有 A A B BA A1 1=B=B1 1A A2 2=B=B2 2A An n=B=BA Ai i=R R A Aj j=R R B B从从 的推演的推演A A1 1=D=D1 1A Am m=A=AR RA Ak k=A=A(R(RB B)A Ak+1k+1=(=(A A (R (R B B)(A A R R)(A (A B B)A Ak+2k+2=(A A R R)(A (A B B)A Ak+3k+3=A=A B B因为因为i,jn,i,jn,所以所以 A A R

30、R A AR R A A R RB B A A(R(RB B)第37页，共157页，编辑于2022年，星期六演绎定理演绎定理(3)(3)归纳证明：当归纳证明：当 A A 到到B B的推演长度等于的推演长度等于n n时，并且时，并且B B由综由综合规则推出，所以合规则推出，所以从从 的推演的推演A A1 1=B B1 1.A Am m=A A R R A Am+1m+1=x(A A R R)A Am+2m+2=A A xRA A为闭公式为闭公式ABA1=B1A2=B2An-1=RAn=xRAn=B因为因为 A RA R推演长推演长度等于度等于n-1n-1，所以，所以 A AR R第38页，共15

31、7页，编辑于2022年，星期六演绎定理演绎定理(4)(4)到到A AB B 的推演的推演由由 A AB B可知，有推理序列可知，有推理序列A A1 1,A,A2 2,A,Am m，使得，使得A Am m=A AB B 。证明有证明有 A A B B 。因为。因为有推理序列有推理序列A A1 1,A,A2 2,A,Am m，其中，其中A Am m=A AB BA Am+1m+1=A AA Am+2m+2=B B第39页，共157页，编辑于2022年，星期六x(P(x)Q(x)(xP(x)xQ(x)x(P(x)Q(x)xP(x)xQ(x)A1 1=x(P(x)Q(x)A2 2=x(P(x)Q(x)

32、P(x)Q(x)A3 3=P(x)Q(x)A4 4=P(x)Q(x)P(x)A5 5=P(x)A6 6=xP(x)A A7 7=P(x)P(x)Q(x)Q(x)Q(x)Q(x)A A8 8=Q(x)Q(x)A A9 9=xQ(x)xQ(x)A A1010=xP(x)xP(x)xQ(x)xQ(x)第40页，共157页，编辑于2022年，星期六自由出现变元问题自由出现变元问题 x(P(x,y)Q(x,y)(xP(x,y)xQ(x,y)？x(P(x,b)Q(x,b)(xP(x,b)xQ(x,b)第41页，共157页，编辑于2022年，星期六定理定理 设设c1,cm是在是在语句集中不出现的不同常元，语

33、句集中不出现的不同常元，y1,ym是在公式是在公式Q(c1,cm)中不出现的不同变元，用中不出现的不同变元，用y1,ym分分别同时代替别同时代替Q(c1,cm)中的中的c1,cm得到得到Q(y1,ym)。若。若Q(c1,cm)，则，则Q(y1,ym)。第42页，共157页，编辑于2022年，星期六证明步骤证明步骤A1 1 An n：(1)(1)使用公理模式对应使用公理模式对应;(2)(2)使用使用Ak k对应对应;(3)(3)使用使用MPMP规则对应；规则对应；(4)(4)使用使用UGUG规则对应。规则对应。证明：证明：Q(c1,cm)A1 1=Q1(c1,cm)An n=Qn(c1,cm)A

34、n n=Q(c1,cm)z1,zn是在是在中不出现的不同变元，中不出现的不同变元，并且并且z1,zn y1,yn=。A1 1=Q1(z1,zm)An n=Qn(z1,zm)An n=Q(z1,zm)An+1=z1 znQ(z1,zm)An+2=z1 znQ(z1,zm)Q(y1,ym)An+3=Q(y1,ym)第43页，共157页，编辑于2022年，星期六x(P(x,y)Q(x,y)(xP(x,y)xQ(x,y)x(P(x,c)Q(x,c)(xP(x,c)xQ(x,c)x(P(x,c)Q(x,c),xP(x,c)xQ(x,c)A1 1=x(P(x,c)Q(x,c)A2 2=P(x,c)Q(x,

35、c)A3 3=xP(x,c)A4 4=P(x,c)A5 5=Q(x,c)A6 6=xQ(x,c)第44页，共157页，编辑于2022年，星期六若若A(x)B(x)，则则xA(x)x B(x)A1 1=C1Am m=A(x)B(x)Am+1m+1=x A(x)A(x)Am+2m+2=xA(x)B(x)Am+3m+3=x(xA(x)B(x)Am+4m+4=x(xA(x)B(x)(xA(x)xB(x)Am+5m+5=xA(x)x B(x)问题是什么问题是什么?X X是自由出现是自由出现第45页，共157页，编辑于2022年，星期六主要内容主要内容逻辑公理系统逻辑公理系统命题逻辑公理系统命题逻辑公理系

36、统谓词逻辑公理系统谓词逻辑公理系统定理证明定理证明公理系统性质公理系统性质理论与模型理论与模型判定问题判定问题总结总结第46页，共157页，编辑于2022年，星期六重要定律重要定律三段论：三段论：Q,QRR传递律：传递律：PQ,QRPR反证律：反证律：如果如果,QR,Q R,则则Q归谬律：归谬律：如果如果,QR,Q R，则，则 Q第47页，共157页，编辑于2022年，星期六重要定理重要定理(P(QR)(Q(PR)(QR)(PQ)(PR)(PQ)(QR)(PR)(PQ)(PR)(P(QR)QQQQQQQ QQ(QQ)(QQ)(QR)(QR)(QR)(QR)(QR)(RQ)(QR)(RQ)(QR

37、)(RQ)Q(QR)(QQ)(RQ)(QQ)Q(QR)(RQ)(QR)(QR)第48页，共157页，编辑于2022年，星期六重要定理重要定理Q(QR)R)Q(QR)R(PQ)(QR)(PR)(QR)(QR)Q)(QR)(QR)Q)(QRR)Q(P QR)(P(QR)Q(R(Q R)(PQ)(PR)(PQ R)(PR)(QR)(P Q)R)第49页，共157页，编辑于2022年，星期六三段论三段论Q,QRRA1=QRA1 A2=QA2 A3=RA1=A2A3第50页，共157页，编辑于2022年，星期六传递律传递律PQ,QRPRA1=(QR)(P(QR)A1 A1A2=QRA2 A3=P(QR)

38、A1=A2A3A4=(P(QR)(PQ)(PR)A2A2A5=(PQ)(PR)A4=A3A5A6=(PQ)A6 A7=(PR)A5=A6A7第51页，共157页，编辑于2022年，星期六(P(QR)(Q(PR)A A1 1=(P=(P(Q(Q R)R)(P(P Q)Q)(P(P R)R)A A 2 2A A2 2=(P(P Q)Q)(P(P R)R)(Q(Q(P(P Q)Q)(P(P R)R)A A 1 1A A3 3=(=(Q Q(P(P Q)Q)(P(P R)R)(Q(Q(P(P Q)Q)(Q(Q(P(P R)R)A A 2 2A A4 4=(P=(P(Q(Q R)R)(Q(Q(P(P Q

39、)Q)(Q(Q(P(P R)AR)A1 1,A A2 2,A A3 3A A4 4A A5 5=(P(P(Q(Q R)R)(Q(Q(P(P Q)Q)(Q(Q(P(P R)R)(P(P(Q(Q R)R)(Q(Q(P(P Q)Q)(P (P(Q(Q R)R)(Q(Q(P(P R)R)A A 2 2A A6 6=(P(P(Q(Q R)R)(Q(Q(P(PQ)Q)(P(P(Q(Q R)R)(Q(Q(P(PR)AR)A5 5=A=A4 4 A A6 6A A7 7=Q=Q(P(PQ)Q)A A 1 1A A8 8=(Q=(Q(P(P Q)Q)(P(P(Q(Q R)R)(Q(Q(P(P Q)Q)A A 1

40、 1A A9 9=(P=(P(Q(Q R)R)(Q(Q(P(P Q)AQ)A8 8=A=A7 7 A A9 9A A1010=(P=(P(Q(Q R)R)(Q(Q(P(P R)AR)A6 6=A=A9 9 A A1010第52页，共157页，编辑于2022年，星期六(QR)(PQ)(PR)A1=(QR)(P(QR)A1 A1A2=(P(QR)(PQ)(PR)A2 A2A3=(QR)(PQ)(PR)A1,A2A3第53页，共157页，编辑于2022年，星期六(PQ)(QR)(PR)A1=(QR)(PQ)(PR)(QR)(PQ)(PR)A2=(QR)(PQ)(PR)(PQ)(QR)(PR)(P(Q

41、R)(Q(PR)A3=(PQ)(QR)(PR)A A2 2=A A1 1 A A3 3第54页，共157页，编辑于2022年，星期六P(QR),QPRA1=P(QR)A1 A2=(P(QR)(PQ)(PR)A2 A2A3=(PQ)(PR)A A2 2=A A1 1 A A3 3A4=Q(PQ)A1 A1A5=Q A5 A6=PQ A A4 4=A A5 5 A A6 6A7=PR A A3 3=A A6 6 A A7 7第55页，共157页，编辑于2022年，星期六(PQ)(PR)(P(QR)A1=(PQ)(PR)(Q(PQ)(PR)A1A1A2=(Q(PQ)(PR)(Q(PQ)(Q(PR)A

42、2 A2A3=Q(PQ)A1 A1A4=(Q(PQ)(PR)(Q(PR)P(QR),QPRA5=(PQ)(PR)(Q(PR)A1,A4A5A6=(Q(PR)(P(QR)(P(QR)(Q(PR)A7=(PQ)(PR)(P(QR)A5,A6A7第56页，共157页，编辑于2022年，星期六QQA1=(Q(QQ)Q)(Q(QQ)(QQ)A A2 2A2=Q(QQ)Q)A1A1A3=(Q(QQ)(QQ)A1=A2A3A4=Q(QQ)A1A1A5=QQ A3=A4A5第57页，共157页，编辑于2022年，星期六QQA1=Q(QQ)A1A1A2=(QQ)(QQ)A3A3A3=(QQ)(QQ)A3A3A4

43、=Q(QQ)A1,A2,A3A4A5=(Q(QQ)(QQ)(QQ)A2A2A6=(QQ)(QQ)A5=A4A6A7=(QQ)QQA8=QQA6=A7A8第58页，共157页，编辑于2022年，星期六QQA1=(QQ)(QQ)A3 A3A2=(QQ)QQA3=(QQ)(QQ)A3 A3A4=QQA3=A2A4第59页，共157页，编辑于2022年，星期六 (Q QR)R)(Q(QR)R)A1=(Q QR)R)(R RQ)Q)A3 A3 A2=(R RQ)Q)(Q(QR)R)A3 A3第60页，共157页，编辑于2022年，星期六 (Q(QR)R)(Q QR)R)A A1 1=R=RR R Q Q

44、Q QA A2 2=(R=(RR)R)(Q Q(R(RR)R)A A 1 1A A3 3=Q Q(R(RR)AR)A2 2=A=A1 1 A A3 3A A4 4=(=(Q Q(R(RR)R)(Q QR)R)(Q QR)R)A A 2 2A A5 5=(=(Q QR)R)(Q QR)AR)A4 4=A=A3 3 A A5 5A A6 6=Q Q Q Q Q QQ QA A7 7=(=(Q Q Q)Q)(Q(QR)R)(Q Q R)R)(P(P Q)Q)(Q(Q R)R)(P(P R)R)A A8 8=(Q=(QR)R)(Q Q R)AR)A7 7=A=A6 6 A A8 8A A9 9=(Q=

45、(QR)R)(Q QR)AR)A8 8,A,A5 5A A9 9第61页，共157页，编辑于2022年，星期六(QR)(RQ)A1 1=(QR)(QR)(Q(QR)R)(Q QR)R)A2 2=(QR)(RQ)A3A3A3 3=(QR)(R Q)A A2 2=A A1 1 A A3 3 第62页，共157页，编辑于2022年，星期六(QR)(RQ)A1 1=(QR)(RQ)(QR)(RQ)A2 2=QQQQA3 3=(QQ)(RQ)(RQ)(QR)(PQ)(PR)A4 4=(RQ)(RQ)A A3 3=A A2 2 A A4 4A5 5=(QR)(RQ)A1,A4A5第63页，共157页，编辑

46、于2022年，星期六(QR)(RQ)A1 1=(QR)(RQ)A3A3A2 2=(QQ)(QR)(QR)(P Q)(QR)(PR)A3 3=(QQ)(QQ)A4 4=(QR)(QR)A A2 2=A A3 3 A A4 4A5 5=(QR)(RQ)A4,A1A5第64页，共157页，编辑于2022年，星期六(Q QQ)Q)(R(RQ)Q)A A1 1=Q Q(R RQ)Q)A1A1A A2 2=(=(R RQ)Q)(Q(QR R)A3A3A A3 3=Q Q(Q(QR R)A A1 1,A,A2 2A A3 3A A4 4=(=(Q Q(Q(QR)R)(Q QQ)Q)(Q QR)R)A2A2A

47、 A5 5=(=(Q Q Q)Q)(Q Q R)AR)A4 4=A=A3 3 A A5 5A A6 6=(=(Q Q R)R)(R(RQ)Q)A 3A 3A A7 7=(=(Q QQ)Q)(R(RQ)AQ)A5 5,A,A6 6A A7 7第65页，共157页，编辑于2022年，星期六(Q QQ)Q)Q Q A A1 1=(=(Q QQ)Q)(Q QQ)Q)Q)Q)(Q QQ)Q)(R(RQ)Q)A A2 2=(=(Q QQ)Q)(Q QQ)Q)Q)Q)(Q QQ)Q)(Q QQ)Q)(Q QQ)Q)Q)Q)A2A2A A3 3=(=(Q QQ)Q)(Q QQ)Q)(Q QQ)Q)Q)AQ)A

48、2 2=A=A1 1 A A3 3A A4 4=(=(Q QQ)Q)(Q QQ)Q)A 1A 1A A5 5=(=(Q QQ)Q)Q AQ A3 3=A=A4 4 A A5 5第66页，共157页，编辑于2022年，星期六Q QQA1=Q Q(Q QQ Q)Q Q (Q QR)R)A2=(Q QQ Q)Q(Q QQ)Q)Q Q A3=Q QQ A A1 1,A,A2 2A A3 3第67页，共157页，编辑于2022年，星期六(QQ)A1=QQ QQA2=(QQ)(QQ)QQA3=(QQ)A A2 2=A A1 1 A A3 3A4=(QQ)Q R(QR)第68页，共157页，编辑于2022年

49、，星期六(QQ)A1=QQ QQA2=(QQ)Q Q R QR第69页，共157页，编辑于2022年，星期六 Q Q(Q Q R)R)A1 1=Q Q(R R Q)Q)A1 A1A2 2=(R R Q)Q)(Q(Q R)R)A3 A3A3 3=Q Q(Q(Q R)R)A1,A2A3第70页，共157页，编辑于2022年，星期六(Q(QR)R)(R(RQ)Q)A1 1=Q Q(R R Q Q)A1 A1A2 2=(R R Q Q)(Q(QR)R)A3 A3A3 3=Q Q(Q(QR)R)Q Q(Q(QR)R)A4 4=(Q Q(Q(QR)(R)(R R(Q Q(Q(QR)R)A1 A1A5 5=

50、R R(Q Q(Q(QR)R)A4=A3 A5A6 6=(Q Q(Q(QR)R)(Q(QR)R)Q)Q)(Q QR R)()(R RQ Q)A7 7=R R(Q(QR)R)Q)Q)A5,A6A7A8 8=(Q(QR)R)(R(R Q)Q)(P(P(Q(Q R)R)(Q(Q(P(P R)R)A9 9=(Q(QR)R)(R(RQ)Q)Q Q R R Q Q R R第71页，共157页，编辑于2022年，星期六(Q(Q R)R)(Q(Q R)R)A1 1=R R(Q(Q R)R)A1 A1A2 2=(R(R(Q(Q R)R)(Q Q (R(R(Q(Q R)R)A1 A1A3 3=Q Q(R(R(Q(