1、本章说明本章的主要内容一阶逻辑基本概念、命题符号化一阶逻辑公式、解释及分类本章与后续各章的关系克服命题逻辑的局限性是第五章的先行准备引言命题逻辑的局限性在命题逻辑中，研究的基本单位是简单命题，对简单命题不再进行分解，并且不考虑命题之间的内在联系和数量关系。例如：所有的人都是要死的，苏格拉底是人，所以苏格拉底是要死的。这个简单而有名的苏格拉底三段论，却无法用命题逻辑予以证明。一阶逻辑所研究的内容为了克服命题逻辑的局限性，将简单命题再细分，分析出个体词、谓词和量词，以期达到表达出个体与总体的内在联系和数量关系。本章内容4.1一阶逻辑命题符号化4.2一阶逻辑公式及解释本章小结习题作业一阶
5、一元谓词F(x):x是素数，a:2，b:4。命题符号化为0元谓词的蕴涵式F(b)F(a)由于此蕴涵前件为假，所以命题为真。(2)设二元谓词G(x,y):x大于y，a:4，b:5，c:6。命题符号化为0元谓词的蕴涵式G(b,a)G(a,c)由于G(b,a)为真，而G(a,c)为假，所以命题为假。例题将命题“这只大红书柜摆满了那些古书。”符号化.(1)设F(x,y)：x摆满了y，R(x)：x是大红书柜Q(y)：y是古书，a：这只，b：那些符号化为：R(a)Q(b)F(a,b)(2)设A(x)：x是书柜，B(x)：x是大的C(x)：x是红的，D(y)：y是古老的E(y)：y是
7、域分别限制为(a)和(b)条件时，将下面两个命题符号化:(1)凡人都呼吸。(2)有的人用左手写字。其中:(a)个体域D1为人类集合；(b)个体域D2为全总个体域。一阶逻辑命题符号化解:(a)个体域为人类集合。令F(x):x呼吸。G(x):x用左手写字。(1)在个体域中除了人外，再无别的东西，因而“凡人都呼吸”应符号化为xF(x)(2)在个体域中除了人外，再无别的东西，因而“有的人用左手写字”符号化为xG(x)(b)个体域为全总个体域。即除人外，还有万物，所以必须考虑将人先分离出来。令F(x):x呼吸。G(x):x用左手写字。M(x):x是人。(1)“凡
8、人都呼吸”应符号化为x(M(x)F(x)(2)“有的人用左手写字”符号化为x(M(x)G(x)在使用全总个体域时，要将人从其他事物中区别出来，为此引进了谓词M(x)，称为特性谓词。同一命题在不同的个体域中符号化的形式可能不同。思考：在全总个体域中，能否将(1)符号化为x(M(x)F(x)？能否将(2)符号化为x(M(x)G(x)？结论例题在个体域限制为(a)和(b)条件时，将下列命题符号化:(1)对于任意的x，均有x2-3x+2=(x-1)(x-2)。(2)存在x，使得x+5=3。其中:(a)个体域D1=N(N为自然数集合)(b)个体域D2=R(R为实数集合)(a)令F(
9、x):x2-3x+2=(x-1)(x-2)，G(x):x+5=3。命题(1)的符号化形式为xF(x)（真命题）命题(2)的符号化形式为xG(x)（假命题）(b)在D2内，(1)和(2)的符号化形式同(a)，皆为真命题。在不同个体域内，同一个命题的符号化形式可能不同，也可能相同。同一个命题，在不同个体域中的真值也可能不同。说明例4.4将下列命题符号化，并讨论真值。（1）所有的人长着黑头发。（2）有的人登上过月球。（3）没有人登上过木星。（4）在美国留学的学生未必都是亚洲人。分析：谓词逻辑中命题的符号化，主要考虑：(1)非空个体域的选取。若是为了确定命题的真值，一般约定在某个个体域上进行，否
10、则，在由一切事物构成的全总个体域上考虑问题时，需要增加一个指出个体变量变化范围的特性谓词。(2)量词的使用及作用范围。(3)正确地语义。例题例题解：没有提出个体域，所以认为是全总个体域。（1）所有的人长着黑头发。令F(x):x长着黑头发，M(x):x是人。命题符号化为x(M(x)F(x)。命题真值为假。（2）有的人登上过月球。令G(x):x登上过月球，M(x):x是人。命题符号化为x(M(x)G(x)。命题真值为真。例题（3）没有人登上过木星。令H(x):x登上过木星，M(x):x是人。命题符号化为x(M(x)H(x)。命题真值为真。（4）在美国留学的学生未必都是亚
11、洲人。令F(x):x是在美国留学的学生，G(x):x是亚洲人。符号化x(F(x)G(x)命题真值为真。例题n元谓词的符号化例4.5将下列命题符号化（1）兔子比乌龟跑得快。（2）有的兔子比所有的乌龟跑得快。（3）并不是所有的兔子都比乌龟跑得快。（4）不存在跑得同样快的两只兔子。解：令F(x):x是兔子，G(y):y是乌龟，H(x,y):x比y跑得快，L(x,y):x与y跑得同样快。（1）xy(F(x)G(y)H(x,y)（2）x(F(x)y(G(y)H(x,y)（3）xy(F(x)G(y)H(x,y)（4）xy(F(x)F(y)L(x,y)一阶逻辑命题符号化时需要注意的事项分
12、析命题中表示性质和关系的谓词，分别符号为一元和n（n2）元谓词。根据命题的实际意义选用全称量词或存在量词。一般说来，多个量词出现时，它们的顺序不能随意调换。例如，考虑个体域为实数集，H(x，y)表示x+y=10，则命题“对于任意的x，都存在y，使得x+y=10”的符号化形式为xyH(x,y)，为真命题。如果改变两个量词的顺序，得yxH(x,y)，为假命题。有些命题的符号化形式可不止一种。（例4.5之(3)）xy(F(x)G(y)H(x,y)xy(F(x)G(y)H(x,y)同在命题逻辑中一样，为在一阶逻辑中进行演算和推理，必须给出一阶逻辑中公式的抽象定义，以及它们的分类及解释。一阶语言是用于
13、一阶逻辑的形式语言，而一阶逻辑就是建立在一阶语言基础上的逻辑体系，一阶语言本身不具备任何意义，但可以根据需要被解释成具有某种含义。一阶语言的形式是多种多样的，本书给出的一阶语言是便于将自然语言中的命题符号化的一阶语言，记为F。一阶语言中的字母表定义4.1一阶语言F的字母表定义如下:(1)个体常项：a,b,c,,ai,bi,ci,,i1(2)个体变项：x,y,z,,xi,yi,zi,,i1(3)函数符号：f,g,h,,fi,gi,hi,,i1(4)谓词符号：F,G,H,,Fi,Gi,
14、Hi,,i1(5)量词符号:，(6)联结词符号:,(7)括号与逗号:(,),，一阶语言中的项定义4.2一阶语言F的项的定义如下:(1)个体常项和个体变项是项。(2)若(x1,x2,xn)是任意的n元函数，t1,t2,tn是任意的n个项，则(t1,t2,tn)是项。(3)所有的项都是有限次使用(1)，(2)得到的。一阶语言中的原子公式定义4.3设R(x1,x2,,xn)是一阶语言F的任意n元谓词，t1,t2,,tn是一阶语言F的任意的n个项，则称R(t1,t2,,tn)是一阶语言F的原子公式。例如：1元谓词F(x)，G(x)，2元谓词H(x,y
15、)，L(x,y)等都是原子公式。一阶语言F的合式公式定义4.4一阶语言F的合式公式定义如下:(1)原子公式是合式公式。(2)若A是合式公式，则(A)也是合式公式。(3)若A，B是合式公式，则(AB)，(AB)，(AB)，(AB)也是合式公式。(4)若A是合式公式，则xA，xA也是合式公式。(5)只有有限次的应用(1)(4)构成的符号串才是合式公式。一阶语言F的合式公式也称为谓词公式，简称公式。A，B代表任意公式，是元语言符号。下文的讨论都是在一阶语言F中，因而不再提及。说明自由出现与约束出现定义4.5指导变元、辖域、约束出现、自由出现在公式xA和xA中，称x为
16、指导变元。在公式xA和xA中，A为相应量词的辖域。在x和x的辖域中，x的所有出现都称为约束出现。A中不是约束出现的其他变项均称为是自由出现的。例4.6指出下列各公式中的指导变元，各量词的辖域，自由出现以及约束出现的个体变项。(1)x(F(x,y)G(x,z)(2)x(F(x)G(y)y(H(x)L(x,y,z)例题解答(1)x是指导变元。量词的辖域A=(F(x,y)G(x,z)。在A中，x的两次出现均是约束出现。y和z均为自由出现。(2)前件上量词的指导变元为x，量词的辖域A=(F(x)G(y)，x在A中是约束出现的，y在A中是自由出现的。后件中量词的指导变元为y，量词的辖域为
17、B=(H(x)L(x,y,z)，y在B中是约束出现的，x、z在B中均为自由出现的。本书中的记法用A(x1,x2,xn)表示含x1,x2,xn自由出现的公式。用表示任意的量词或，则x1A(x1,x2,xn)是含有x2,x3,xn自由出现的公式，可记为A1(x2,x3,xn)。类似的，x2x1A(x1,x2,xn)可记为A2(x3,x4,xn)xn-1xn-2x1A(x1,x2,xn)中只含有xn是自由出现的个体变项，可以记为An-1(xn)。xnx1A(x1,x2,xn)没有自由出现的个体变项。举例将例4.6(1)中的公式简记为A(y,z)，表明公式含有自由出现的个体变项y，z。而yA(y,z
18、)中只含有z为自由出现的公式，zyA(y,z)中已经没有自由出现的个体变项了，闭式定义4.6设A是任意的公式，若A中不含有自由出现的个体变项，则称A为封闭的公式，简称闭式。例如：xy(F(x)G(y)H(x,y)为闭式，x(F(x)G(x,y)不是闭式。一阶公式的解释一阶公式没有确定的意义，一旦将其中的变项（项的变项、谓词变项）用指定的常项代替后，所得公式就具备一定的意义，有时就变成命题了。例题例4.7将下列两个公式中的变项指定成常项使其成为命题:(1)x(F(x)G(x)(2)xy(F(x)F(y)G(x,y)H(f(x,y),g(x,y)(1)指定个体变项的变化范围
19、，并且指定谓词F，G的含义，下面给出两种指定法:(a)令个体域D1为全总个体域，F(x)为x是人，G(x)为x是黄种人，则命题为“所有人都是黄种人”，这是假命题。(b)令个体域D2为实数集合R，F(x)为x是自然数，G(x)为x是整数，则命题为“自然数都是整数”，这是真命题。例题(2)xy(F(x)F(y)G(x,y)H(f(x,y),g(x,y)含有两个2元函数变项，两个1元谓词变项，两个2元谓词变项。指定个体域为全总个体域，F(x)为x是实数，G(x,y)为xy，H(x,y)为xy，f(x,y)=x2+y2，g(x,y)=2xy，则表达的命题为“对于任意的x，y，若x与y都是实数，且x
20、y，则x2+y22xy”，这是真命题。如果H(x,y)改为xy，则所得命题为假命题。一阶公式的解释定义4.7一阶公式的解释I由下面4部分组成:(a)非空个体域DI。(b)DI中一些特定元素的集合。(c)DI上特定函数集合|i,n1。(d)DI上特定谓词的集合|i,n1。为第i个n元谓词，如i=2，n=3时，表示第2个3元谓词，它可能以(x,y,z)的形式出现在解释中，公式A若出现F2(x,y,z)就解释成(x,y,z)。为第i个n元函数。例如，i=1，n=2时，表示第一个二元函数，它出现在解释中，可能是(x,y)=x2+y2，(x,y)=2xy等，一旦公式中出现f1
21、(x,y)就解释成(x,y)，出现g1(x,y)就解释成(x,y)=2xy。对解释I的几点说明被解释的公式不一定全部包含解释中的四部分。在解释的公式A中的个体变项均取值于DI。若A中含有个体常项，就解释成。在解释的定义中引进了几个元语言符号，如例4.8给定解释I如下:(a)个体域D=N(N为自然数集合，即N=0,1,2,)(b)=0(c)(x,y)=x+y,(x,y)=xy。(d)(x,y)为x=y。在I下，下列哪些公式为真哪些为假哪些的真值还不能确定例题(1)F(f(x,y),g(x,y)(2)F(f(x,a),y)F(g(x,y),z)(3)F(g(x,
22、y),g(y,z)(4)xF(g(x,y),z)(5)xF(g(x,a),x)F(x,y)(6)xF(g(x,a),x)(7)xy(F(f(x,a),y)F(f(y,a),x)(8)xyzF(f(x,y),z)(9)xF(f(x,x),g(x,x)例题(1)F(f(x,y),g(x,y)公式被解释成“x+y=xy”，这不是命题。(2)F(f(x,a),y)F(g(x,y),z)公式被解释成“(x+0=y)(xy=z)”，这也不是命题。(3)F(g(x,y),g(y,z)公式被解释成“xyyz”，同样不是命题。(4)xF(g(x,y),z)公式被
23、解释成“x(xy=z)”，不是命题。例题(5)xF(g(x,a),x)F(x,y)公式被解释成“x(x0=x)(x=y)”，由于前件为假，所以被解释的公式为真。(6)xF(g(x,a),x)公式被解释成“x(x0=x)”，为假命题。(7)xy(F(f(x,a),y)F(f(y,a),x)公式被解释成“xy(x+0=y)(y+0=x)”，为真命题。(8)xyzF(f(x,y),z)公式被解释成“xyz(x+y=z)”，这也为真命题。(9)xF(f(x,x),g(x,x)公式被解释成“x(x+x=xx)”，为真命题。闭式在给定的解释中都变成了命题。如(6)(8)。
24、不是闭式的公式在某些解释下也可能变为命题。如(5)。结论例题定理4.1封闭的公式在任何解释下都变成命题。一阶公式的分类定义4.8永真式、永假式、可满足式设A为一个公式，若A在任何解释下均为真，则称A为永真式(或称逻辑有效式)。设A为一个公式，若A在任何解释下均为假，则称A为矛盾式(或永假式)。设A为一个公式，若至少存在一个解释使A为真，则称A为可满足式。永真式一定是可满足式，但可满足式不一定是永真式。在一阶逻辑中，到目前为止，还没有找到一种可行的算法，用来判断任意一个公式是否是可满足的，这与命题逻辑的情况是完全不同的。但对某些特殊的公式还是可以判断的。说明代换实例定义4.9设A0是含
25、有命题变项p1,p2,pn的命题公式，A1,A2,An是n个谓词公式，用Ai(1in)处处代替A0中的pi，所得公式A称为A0的代换实例。例如，F(x)G(x),xF(x)yG(y)等都是pq的代换实例，而x(F(x)G(x)等不是pq的代换实例。定理4.2重言式的代换实例都是永真式，矛盾式的代换实例都是矛盾式。例4.9判断下列公式中，哪些是永真式，哪些是矛盾式？（1）x(F(x)G(x)（2）x(F(x)G(x)（3）xF(x)(xyG(x,y)xF(x)（4）(xF(x)yG(y)yG(y)解:(1)x(F(x)G(x)解释1：个体域为实数集合R，F(x)：x是整数，G(x)：
26、x是有理数，因此公式真值为真。解释2：个体域为实数集合R，F(x)：x是无理数，G(x)：x能表示成分数，因此公式真值为假。所以公式为非永真式的可满足式。例题例题（2）x(F(x)G(x)公式为非永真式的可满足式。（3）xF(x)(xyG(x,y)xF(x)为p(qp)（重言式）的代换实例，故为永真式。（4）(xF(x)yG(y)yG(y)为(pq)q（矛盾式）的代换实例，故为永假式。例题例4.10判断下列公式的类型。(1)xF(x)xF(x)(2)xyF(x,y)xyF(x,y)(3)x(F(x)G(x)yG(y)解记(1)，(2)，(3)中的公式分别为A,B,C
27、。(1)设I为任意一个解释，个体域为D。若存在x0D，使得F(x0)为假，则xF(x)为假，所以A的前件为假，故A为真。若对于任意xD，F(x)均为真，则xF(x)，xF(x)都为真，从而A为真。所以在I下A为真。由I的任意性可知，A是永真式。例题(2)xyF(x,y)xyF(x,y)取解释I：个体域为自然数集合N，F(x,y)为xy。在I下B的前件与后件均为真，所以B为真。这说明B不是矛盾式。（在xyF(x,y)中，x0）再取I：个体域仍然为N，F(x,y)为x=y。在I下，B的前件真而后件假，所以B为假。这说明B不是永真式。故B是非永真式的可满足式。(3)x(F(x)G(x)
28、yG(y)C也是非永真式的可满足式。小节结束本章主要内容个体词个体常项个体变项个体域全总个体域谓词谓词常项谓词变项n(n1)元谓词特性谓词量词全称量词存在量词本章主要内容一阶逻辑中命题符号化一阶逻辑公式原子公式合式公式（或公式）闭式解释一阶逻辑公式的分类逻辑有效式（或永真式）矛盾式（或永假式）可满足式本章学习要求要求准确地将给出的命题符号化：当给定个体域时，在给定个体域内将命题符号化。当没给定个体域时，应在全总个体域内符号化。在符号化时，当引入特性时，注意全称量词与蕴含联结词的搭配，存在量词与合取联结词的搭配。深刻理解逻辑有效式、矛盾式、可满足式的概念。记住闭式的性质：在任何解释下均为命
29、题。对给定的解释，会判别公式的真值或不能确定真值。小节结束习题选讲命题符号化1.在一阶逻辑中将下列命题符号化。（1）每个人都有心脏。（2）有的狗会飞。（3）没有不犯错误的人。（4）发光的不都是金子。（5）一切人都不一样高。（6）并不是所有的汽车都比火车快。（7）没有一个自然数大于等于任何自然数。（8）有唯一的偶素数。（9）不管黑猫白猫，抓住老鼠就是好猫。（10）对平面上任意两点，有且仅有一条直线通过这两点。习题选讲命题符号化解：由于没指出个体域，故用全总个体域（1）每个人都有心脏。本命题的含义：对于每一个x，如果x是人，则x有心脏。因而应首先从宇宙间的一切事物中，将人分离出
30、来，这就必须引入特性谓词。令M(x):x是人，H(x):x有心脏。命题符号化为：x(M(x)H(x)如果将其中的改为，即x(M(x)H(x)，它表示的意思是：“对于每个x，x是人且x有心脏”。这是一个假命题，而“每个人都有心脏”是真命题。这说明将命题“每个人都有心脏”符号化为x(M(x)H(x)是错误的。习题选讲命题符号化（2）有的狗会飞。命题的意思是：存在一个x，使得x是狗，并且x会飞。设D(x)：x是狗，F(x)：x会飞。命题符号化为：x(D(x)F(x)如果将其中的改为，即x(D(x)F(x)，如果用a表示某只猫，则D(a)为假，因而，D(a)F(a)为真，所以x(D(x)F
31、(x)为真，而“有的狗会飞”为假，这说明将“有的狗会飞”符号化为(x)(D(x)F(x)是错误的。习题选讲命题符号化（3）没有不犯错误的人。命题的意思是：存在不犯错误的人是不可能的。只要是人，必然犯错误。设M(x):x是人，F(x):x犯错误命题符号化为x(M(x)F(x)x(M(x)F(x)习题选讲命题符号化（4）发光的不都是金子。命题的意思是：不是发光的东西都是金子。存在着发光的东西不是金子。设L(x)：x是发光的东西，G(x)：x是金子。命题符号化为x(L(x)G(x)x(L(x)G(x)（5）一切人都不一样高。设F(x):x是人,H(x,y),
32、x与y相同,L(x,y):x与y一样高，命题符号化为x(F(x)y(F(y)H(x,y)L(x,y)或xy(F(x)F(y)H(x,y)L(x,y)（6）并不是所有的汽车都比火车快。设F(x):x是汽车,G(y):y是火车,H(x,y):x比y快，命题符号化为xy(F(x)G(y)H(x,y)或xy(F(x)G(y)H(x,y)习题选讲命题符号化习题选讲命题符号化（7）没有一个自然数大于等于任何自然数。设N(x):x是自然数，G(x,y):xy命题符号化为：x(N(x)y(N(y)G(x,y)（8）有唯一的偶素数。设：Q(x):x是偶数，P(x):x是素数，E(x,y):xy命题符号化为：x(Q(x)P(x)y(Q(y)P(y)E(x,y)习题选讲命题符号化（9）不管黑猫白猫，抓住老鼠就是好猫。需要考虑问题：只是限制黑猫白猫，还是包含其它颜色的猫？是指至少抓住一只就可以，还是抓住所有的？因此在描述命题时，总是将这些模糊概念做某种确切理解。设C(x)：x是猫，W(x)：x是白的，B(x)：x是黑的G(x)：x是好的，M(x)：x是老鼠，K(x)：x抓住y命题符号化为xy(C(x)M(y)(B(x)W(x)K(x,y)G(x)习题