第4章谓词逻辑-1

2020/5/1,数学科学学院,35-1,第4章谓词逻辑,又如，数学中常涉及一些判断，如x2-2x+1=0？,例考察著名的苏格拉底三段论推理：因为所有的人都要死；苏格拉底是人。所以，苏格拉底是要死的。,解：假设,P：所有的人都是要死的；Q：苏格拉底是人。R：苏格拉底是要死的。,应有：PQR，即（PQ）R永真,可见，R不是P，Q的逻辑结果。,但在上述公式中，取P：1，Q：1，R：0，此时，该公式取0。,2020/5/1,数学科学学院,35-2,4.1-2谓词与量词一、谓词,1.个体词(定义4.2.1)：在句子中，可以独立存在的客体称为个体词.,例：上海，教师，*班级，电子计算机，聪明等等都是个体词。,个体词分：（1）个体常量：表示具体或特定的个体词，一般用带或不带下标的小写英文字母a,b,c,a1,a2,a3,表示。,可为一具体事物或为抽象的概念。,2020/5/1,数学科学学院,35-3,3.谓词(定义4.2.1):用以刻划客体的性质或关系的词。一般用大写字母表示。,（2）个体变量：表示抽象的或泛指的个体词，一般用带或不带下标的小写英文字x,y,z,.,x1,x2,x3,表示。,2.个体域(定义4.2.2)个体词的取值范围称为个体域或论域，常用D表示。,全总个体域:宇宙间的所有个体域聚集在一起的个体域。,例：5是一个实数。3大于2。点A位于点B和点C之间。小王高于小李。,2020/5/1,数学科学学院,35-4,例：（1）苹果是红的。可表示为:R(苹果)或R(a),其中a:苹果,（2）3大于2。可表示为:C(3,2),4.n元命题函数(n元谓词)设D为非空的个体域，定义在Dn(表示n个个体都在个体域D上取值)上取值于0,1上的n元函数，称为n元命题函数或n元谓词,记为P(x1,x2,xn)。此时，个体变量x1,x2,xn的定义域都为D，P(x1,x2,xn)的值域为0,1。,例：A(x)：x是一个实数。-1元谓词,B(x,y)：x高于y。-2元谓词,R(x,y,z)：点x位于点y和点z之间。-3元谓词,2020/5/1,数学科学学院,35-5,几个结论：,（1）谓词中个体词的顺序是十分重要的，不能随意变更。,（2）一元谓词描述的是某个体的特性或性质，而n（n2）元谓词描述的是n个个体之间的关系。,（3）n（n2）元谓词不是命题，0元谓词(不含个体变量的谓词)实际上就是一般的命题。,例：设R(x)：x是一个实数。G(x,y)：x大于y。H(x,y)：x个子高于y。,则R(5)：5是一个实数。G(2,3)：2大于3。H(鲁迅,毛泽东)：鲁迅个子高于毛泽东。,-真命题,-假命题,-假命题,2020/5/1,数学科学学院,35-6,二、量词,而(M(x)D(x)M(x)(x)M(x)(x),考查：设：M(x):x是人D(x)：x要死的。则M(x)D(x)可翻译为：若x是人，则x要死。即“所有人都要死”。,？,上式表明：“所有人都要死”的否定是：“所有的人都不死”。,2020/5/1,数学科学学院,35-7,1.量词及其符号(定义4.2.4)(1)(x)-称为全称量词表示:所有的x；任意的x；一切x；每一个x；等等。,(2)(x)-称为存在量词表示：存在x；有些x；(至少)有一个x；等等。,相关概念,作用变量:(x)和(x)中的x。,辖域：量词使用时一般其后紧跟一个谓词，如(x)F(x),(x)F(x)，其中F(x)称为全称量词和存在量词的辖域。,例：(x)(I(x)(y)P(x,y)N(x)中,(x)的辖域为:(I(x)(y)P(x,y),(y)的辖域为:P(x,y),2020/5/1,数学科学学院,35-8,例：对个体域D,符号化下述命题：(1)每一个苹果都是红的。D=苹果(2)有一些实数是有理数。D=实数(3)任意一个整数都是正整数或负整数。D=整数(4)对每一个实数，都有x2+2x+1=(x+1)2。D=实数(5)有一些实数，使得x+6=5。D=实数,2.符号化举例,解：设R(x)：x是红的；Q(x)：x是有理数；P(x)：x是正的；N(x)：x是负的；L(x)：x2+2x+1=(x+1)2；M(x)：x+6=5。,2020/5/1,数学科学学院,35-9,(1)每一个苹果都是红的。D=苹果(2)有一些实数是有理数。D=实数(3)任意一个整数都是正整数或负整数。D=整数(4)对每一个实数，都有x2+2x+1=(x+1)2。D=实数(5)有一些实数，使得x+6=5。D=实数,R(x)：x是红的；Q(x)：x是有理数；P(x)：x是正的；N(x)：x是负的L(x)：x2+2x+1=(x+1)2；M(x)：x+6=5。,(1)可表为:(x)R(x);(2)可表为:(x)Q(x),(3)可表为:(x)(P(x)N(x),(4)可表为:(x)L(x)或(x)(x2+2x+1=(x+1)2),(5)可表为:(x)M(x)或(x)(x+6=5),2020/5/1,数学科学学院,35-10,例：对全总个体域,符号化下述命题：(1)每一个苹果都是红的。(2)有一些实数是有理数。(3)任意一个整数都是正整数或负整数。,解：设H(x)：x是红的；Q(x)：x是有理数；P(x)：x是正的；N(x)：x是负的。,则(1)可表为:(x)(A(x)H(x),(2)可表为:(x)(R(x)Q(x),(3)可表为:(x)(Z(x)(P(x)N(x),再设A(x)：x是苹果；R(x)：x是实数；Z(x)：x是整数。,说明:(1)例中红体标出的谓词称为特性谓词,其作用是对个体变量的变化范围给出限制.,(2)未给出个体域的题目总假定为全总个体域.,2020/5/1,数学科学学院,35-11,(3)每一个苹果都是红的:(x)(A(x)H(x)其中A(x)：x是苹果；H(x)：x是红的不能表为:(x)(A(x)H(x),(4)有一些实数是有理数:(x)(R(x)Q(x)其中Q(x)：x是有理数；R(x)：x是实数不能表为:(x)(R(x)Q(x),例：设M(x):x是人，D(x)：x要死的,a:苏格拉底则三段论“因为所有的人都要死；苏格拉底是人。所以，苏格拉底是要死的。”可表示为：,(x)(M(x)D(x),M(a),D(a),2020/5/1,数学科学学院,35-12,例：符号化下述语句：(1)每个实数都存在比它大的另外的实数。(2)每个人都有某些专长。(3)有会说话的机器人。(4)尽管有人很聪明，但未必一切人都聪明。,解：(1)设R(x)：x是实数.L(x,y)：x小于y.则有：(x)(R(x)(y)(R(y)L(x，y)(2)设M(x)：x是人.N(x)：x是专长.P(x,y)：x都有y.则有:(x)(M(x)(y)(N(y)P(x，y)(3)设M(x)：x是机器人.F(x)：x会说话.则有：(x)(M(x)F(x)(4)设M(x)：x是人。C(x)：x很聪明。则有:(x)(M(x)C(x)(x)(M(x)C(x),2020/5/1,数学科学学院,35-13,4.谓词与命题的关系,设G(x)是一元谓词,D为个体域.,(1)G(x)不是命题,但对aD,G(a)是命题(0元命题).,(2)(x)G(x),(x)G(x)均为命题,其真值定义为:,(x)G(x),(x)G(x),2020/5/1,数学科学学院,35-14,(4)当个体域D是有限集合时，如D=a1,a2,，an，则有：(x)G(x)G(a1)G(a2).G(an)(x)G(x)G(a1)G(a2).G(an),(5)(x)G(x)1(x)G(x)1,(6)(x)(y)G(x,y)(y)(x)G(x,y)(x)(y)G(x,y)(y)(x)G(x,y),但(x)(y)G(x,y)(y)(x)G(x,y),例如，设G(x,y)：x+y=0，个体域为整数集合。则有(x)(y)G(x,y)=，(y)(x)G(x,y)=,1,0,2020/5/1,数学科学学院,35-15,例：设P(x):x是素数I(x):x是整数Q(x,y):x+y=0用语句描述下述句子，并判断其真假值。(x)(I(x)P(x)(x)(I(x)P(x)(x)(y)(I(x)I(y)Q(x，y)(x)(I(x)(y)(I(y)Q(x，y)(x)(y)(I(x)(I(y)Q(x，y),解：1)可描述为：“任意的整数都是素数”。（假）可描述为：“存在一些整数是素数”。（真）可描述为：“任意两个整数x和y，都有x+y=0”。（假）可描述为：“对任意的整数x，都存在着整数y，使得x+y=0”。（真）,（5）可描述为：“存在着整数x，使得对任意的整数y，都有x+y=0”。（假）,2020/5/1,数学科学学院,35-16,4.3谓词公式与解释,1.四类符号(1)常量符号：一般用a,b,c,a1,b1,c1,来表示，它是D中的某个元素;,(2)变量符号：一般用x,y,z,x1,y1,z1,来表示.它表示D中任意元素；,(3)函数符号：一般用f,g,h,f1,g1,h1,来表示。n元函数符号f(x1,x2,.xn)可以是DnD的任意一个函数；,(4)谓词符号：一般用P,Q,R,.,P1,Q1,R1,.来表示。N元谓词符号P(x1,x2,.xn)可以是Dn0,1的任意一个谓词。,2020/5/1,数学科学学院,35-17,2.项定义：谓词逻辑中的项,被递归地定义为：任意的常量符号或任意的变量符号是项；若f(x1,x2,x3,xn)是n元函数符号，t1,t2,tn是项，则f(t1,t2,t3,tn)是项；仅仅由有限次使用1),2)所产生的表达式才是项。,例：a,x,f(a),g(a,x),g(f(a),g(a,x),f(g(f(a),g(a,x)均为项.其中,2020/5/1,数学科学学院,35-18,4.合式公式定义：满足下列条件的表达式，称为合式公式,简称公式。,3.原子公式定义：设P(x1,x2,x3,.xn)是n元谓词，t1,t2,t3,.tn是项,则P(t1,t2,t3,.tn)是原子谓词公式，简称原子公式。,(1)原子公式是合式公式；,(2)若G，H是合式公式，则(G)、(H)、(GH)、(GH)、(GH)、(GH)也是合式公式；,(3)若G是合式公式，x是个体变量，则(x)G、(x)G也是合式公式；,(4)仅仅有1)-3)产生的表达式才是合式公式。,2020/5/1,数学科学学院,35-19,(P(x)(Q(x,y)R(x,a,f(z)(p(x)R(y)(x)(P(x)等都是公式。,例如,而(P(x)R(x)(x)，(x)P(x)等则不是公式。,2020/5/1,数学科学学院,35-20,5.自由变元和约束变元,定义：合式公式中的变元x若出现在以x为作用变元的量词的辖域之内，则称变元x的出现为约束出现，此时的变元x称为约束变元(量)。若x的出现不是约束出现，则称它为自由出现，此时的变元x称为自由变元(量)。,例：(1)(x)(P(x)Q(x)(2)(x)(P(x)(y)(R(x,y)(3)(y)(P(y,z)(x)Q(x,y)R(y),解：在(1)中,P(x)和Q(x)中的x都为约束变元。(2)中，P(x)中的x和R(x,y)中的y都为约束变元，R(x,y)中的x为自由变元。(3)中，P(y,z)与Q(x,y)中的y为约束变元,Q(x,y)中的x也为约束变元,z为自由变元，R(y)中的y为自由变元。,2020/5/1,数学科学学院,35-21,两个规则,规则1(约束变元的改名规则)：1)、将量词中出现的变元以及该量词辖域中此变量之所有约束出现都用新的个体变元替换。2)、新的变元一定要有别于改名辖域中的所有其它变量。规则2(自由变元的代入规则)：1)、将公式中出现该自由变元的每一处都用