第四章一阶逻辑基本概念

第4章一阶逻辑基本概念2本章说明本章的主要内容–一阶逻辑基本概念、命题符号化–一阶逻辑公式、解释及分类本章与后续各章的关系–克服命题逻辑的局限性–是第五章的先行准备3引言命题逻辑的局限性在命题逻辑中，研究的基本单位是简单命题，对简单命题不再进行分解，并且不考虑命题之间的内在联系和数量关系。例如：所有的人都是要死的，苏格拉底是人，所以苏格拉底是要死的。这个简单而有名的苏格拉底三段论，却无法用命题逻辑予以证明。一阶逻辑所研究的内容为了克服命题逻辑的局限性，将简单命题再细分，分析出个体词、谓词和量词，以期达到表达出个体与总体的内在联系和数量关系。4本章内容4.1一阶逻辑命题符号化4.2一阶逻辑公式及解释本章小结习题作业54.1一阶逻辑命题符号化一阶逻辑命题符号化的三个基本要素–个体词–谓词–量词6个体词及相关概念个体词一般是充当主语的名词或代词。说明个体词：指所研究对象中可以独立存在的具体或抽象的客体。举例–命题：电子计算机是科学技术的工具。个体词：电子计算机。–命题：他是三好学生。个体词：他。7个体常项：表示具体或特定的客体的个体词，用小写字母a,b,c，…表示。个体变项：表示抽象或泛指的客体的个体词，用x,y,z,…表示。个体域（或称论域）：指个体变项的取值范围。–可以是有穷集合，如{a,b,c},{1,2}。–可以是无穷集合，如N,Z,R,…。全总个体域（universe）——宇宙间一切事物组成。个体词及相关概念本教材在论述或推理中，如果没有指明所采用的个体域，都是使用的全总个体域。说明8谓词及相关概念谓词（predicate）是用来刻画个体词性质及个体词之间相互关系的词。(1)是无理数。是个体常项，“是无理数”是谓词，记为F，命题符号化为F()。(2)x是有理数。x是个体变项，“是有理数”是谓词，记为G，命题符号化为G(x)。(3)小王与小李同岁。小王、小李都是个体常项，“与同岁”是谓词，记为H，命题符号化为H(a,b)，其中a：小王，b：小李。(4)x与y具有关系L。x，y都是个体变项，谓词为L，命题符号化为L(x,y)。9谓词常项：表示具体性质或关系的谓词。用大写字母表示。如(1)、(2)、(3)中谓词F、G、H。谓词变项：表示抽象的、泛指的性质或关系的谓词。用大写字母表示。如(4)中谓词L。n(n1)元谓词：P(x1,x2,…,xn)表示含n个命题变项的n元谓词。–n=1时，一元谓词——表示x1具有性质P。–n≥2时，多元谓词——表示x1,x2,…,xn具有关系P。0元谓词：不含个体变项的谓词。如F(a)、G(a,b)、P(a1,a2,…,an)。n元谓词是命题吗？不是，只有用谓词常项取代P，用个体常项取代x1,x2,…,xn时，才能使n元谓词变为命题。思考谓词及相关概念10例题例4.1将下列命题在一阶逻辑中用0元谓词符号化，并讨论真值。(1)只有2是素数，4才是素数。(2)如果5大于4，则4大于6.解：(1)设一元谓词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)为假，所以命题为假。11量词（quantifiers）是表示个体常项或个体变项之间数量关系的词。1.全称量词：符号化为“”日常生活和数学中所用的“一切的”、“所有的”、“每一个”、“任意的”、“凡”、“都”等词可统称为全称量词。x表示个体域里的所有个体，xF(x)表示个体域里所有个体都有性质F。2.存在量词：符号化为“”日常生活和数学中所用的“存在”、“有一个”、“有的”、“至少有一个”等词统称为存在量词。y表示个体域里有的个体，yG(y)表示个体域里存在个体具有性质G等。量词及相关概念12例4.2在个体域分别限制为(a)和(b)条件时，将下面两个命题符号化:(1)凡人都呼吸。(2)有的人用左手写字。其中:(a)个体域D1为人类集合；(b)个体域D2为全总个体域。一阶逻辑命题符号化13解:(a)个体域为人类集合。令F(x):x呼吸。G(x):x用左手写字。(1)在个体域中除了人外，再无别的东西，因而“凡人都呼吸”应符号化为xF(x)(2)在个体域中除了人外，再无别的东西，因而“有的人用左手写字”符号化为xG(x)14(b)个体域为全总个体域。即除人外，还有万物，所以必须考虑将人先分离出来。令F(x):x呼吸。G(x):x用左手写字。M(x):x是人。(1)“凡人都呼吸”应符号化为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))？结论15例题例4.3在个体域限制为(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(x):x2-3x+2=(x-1)(x-2)，G(x):x+5=3。命题(1)的符号化形式为xF(x)（真命题）命题(2)的符号化形式为xG(x)（假命题）(b)在D2内，(1)和(2)的符号化形式同(a)，皆为真命题。在不同个体域内，同一个命题的符号化形式可能不同，也可能相同。同一个命题，在不同个体域中的真值也可能不同。说明16例4.4将下列命题符号化，并讨论真值。（1）所有的人长着黑头发。（2）有的人登上过月球。（3）没有人登上过木星。（4）在美国留学的学生未必都是亚洲人。分析：谓词逻辑中命题的符号化，主要考虑：(1)非空个体域的选取。若是为了确定命题的真值，一般约定在某个个体域上进行，否则，在由一切事物构成的全总个体域上考虑问题时，需要增加一个指出个体变量变化范围的特性谓词。(2)量词的使用及作用范围。(3)正确地语义。例题17例题解：没有提出个体域，所以认为是全总个体域。（1）所有的人长着黑头发。令F(x):x长着黑头发，M(x):x是人。命题符号化为x(M(x)→F(x))。命题真值为假。（2）有的人登上过月球。令G(x):x登上过月球，M(x):x是人。命题符号化为x(M(x)∧G(x))。命题真值为真。18例题（3）没有人登上过木星。令H(x):x登上过木星，M(x):x是人。命题符号化为┐x(M(x)∧H(x))。命题真值为真。（4）在美国留学的学生未必都是亚洲人。令F(x):x是在美国留学的学生，G(x):x是亚洲人。符号化┐x(F(x)→G(x))命题真值为真。19例题n元谓词的符号化例4.5将下列命题符号化（1）兔子比乌龟跑得快。（2）有的兔子比所有的乌龟跑得快。（3）并不是所有的兔子都比乌龟跑得快。（4）不存在跑得同样快的两只兔子。解：令F(x):x是兔子，G(y):y是乌龟，H(x,y):x比y跑得快，L(x,y):x与y跑得同样快。（1）xy(F(x)∧G(y)H(x,y))（2）x(F(x)∧(y(G(y)H(x,y)))（3）┐xy(F(x)∧G(y)H(x,y))（4）┐xy(F(x)∧F(y)∧L(x,y))20一阶逻辑命题符号化时需要注意的事项分析命题中表示性质和关系的谓词，分别符号为一元和n（n2）元谓词。根据命题的实际意义选用全称量词或存在量词。一般说来，多个量词出现时，它们的顺序不能随意调换。–例如，考虑个体域为实数集，H(x，y)表示x+y=10，–则命题“对于任意的x，都存在y，使得x+y=10”的符号化形式为xyH(x,y)，为真命题。–如果改变两个量词的顺序，得yxH(x,y)，为假命题。有些命题的符号化形式可不止一种。（例4.5之(3)）–xy(F(x)∧G(y)H(x,y))–xy(F(x)∧G(y)∧┐H(x,y))214.2一阶逻辑公式及解释同在命题逻辑中一样，为在一阶逻辑中进行演算和推理，必须给出一阶逻辑中公式的抽象定义，以及它们的分类及解释。一阶语言是用于一阶逻辑的形式语言，而一阶逻辑就是建立在一阶语言基础上的逻辑体系，一阶语言本身不具备任何意义，但可以根据需要被解释成具有某种含义。一阶语言的形式是多种多样的，本书给出的一阶语言是便于将自然语言中的命题符号化的一阶语言，记为F。22一阶语言中的字母表定义4.1一阶语言F的字母表定义如下:(1)个体常项：a,b,c,…,ai,bi,ci,…,i1(2)个体变项：x,y,z,…,xi,yi,zi,…,i1(3)函数符号：f,g,h,…,fi,gi,hi,…,i1(4)谓词符号：F,G,H,…,Fi,Gi,Hi,…,i1(5)量词符号:，(6)联结词符号:┐,∧,∨,→,(7)括号与逗号:(,),，23一阶语言中的项定义4.2一阶语言F的项的定义如下:(1)个体常项和个体变项是项。(2)若(x1,x2,…,xn)是任意的n元函数，t1,t2,…,tn是任意的n个项，则(t1,t2,…,tn)是项。(3)所有的项都是有限次使用(1)，(2)得到的。24一阶语言中的原子公式定义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)，L(x,y)等都是原子公式。25一阶语言F的合式公式定义4.4一阶语言F的合式公式定义如下:(1)原子公式是合式公式。(2)若A是合式公式，则(┐A)也是合式公式。(3)若A，B是合式公式，则(A∧B)，(A∨B)，(A→B)，(AB)也是合式公式。(4)若A是合式公式，则xA，xA也是合式公式。(5)只有有限次的应用(1)～(4)构成的符号串才是合式公式。一阶语言F的合式公式也称为谓词公式，简称公式。A，B代表任意公式，是元语言符号。下文的讨论都是在一阶语言F中，因而不再提及。说明26自由出现与约束出现定义4.5指导变元、辖域、约束出现、自由出现在公式xA和xA中，称x为指导变元。在公式xA和xA中，A为相应量词的辖域。在x和x的辖域中，x的所有出现都称为约束出现。A中不是约束出现的其他变项均称为是自由出现的。27例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，量词的辖域为B=(H(x)∧L(x,y,z))，y在B中是约束出现的，x、z在B中均为自由出现的。28本书中的记法用A(x1,x2,…,xn)表示含x1,x2,…,xn自由出现的公式。用Δ表示任意的量词或，则Δx1A(x1,x2,…,xn)是含有x2,x3,…,xn自由出现的公式，可记为A1(x2,x3,…,xn)。类似的，Δx2Δx1A(x1,x2,…,xn)可记为A2(x3,x4,…,xn)Δxn-1Δxn-2…Δx1A(x1,x2,…,xn)中只含有xn是自由出现的个体变项，可以记为An-1(xn)。Δxn…Δx1A(x1,x2,…,xn)没有自由出现的个体变项。举例将例4.6(1)