第2章 逻辑代数：谓词演算.docx

第2 章逻辑代数(下)：谓词演算2.1 谓词演算基本概念2.1.1 个体谓词演算中把一切讨论对象都称为个体(individuals),它们可以是客观世界中的具体 客体，也可以是抽象的客体，诸如数字、符号等确定的个体常用a, b，c等小写字母或字 母串表示a，b，c等小写字母或字母串称为个体常元(constants)不确定的个体常用字 母x, y， z, u，v，w等来表示它们被称为个体变元，或变元(variables)谓词演算中把讨论对象 个体的全体称为个体域(domain of individuals)，常用字 母D表示，并约定个体域都是非空的集合当讨论对象未作具体指定，而是泛指一切客体时， 个体域特称为全总域(universe)，用字母U表示当给定个体域时，常元表示该域中的一个确定的成员，而变元则可以取该域中的任何一 个成员为其值表示D上运算的运算符与常元、变元可组成所谓个体项(terms)例如，数 学中的代数式 a2+b， x2c 等由于在我们讨论的谓词演算中，其变元只能取值个体对象，不能取值函数、命题或谓词， 因此，它又常被叫做一阶谓词演算2.1.2 谓词2.1.3 量词谓词演算中的量词(quantifiers)指数学中常用的数量词“所有的”(或“每一个”)和 “有”(或“存在”)，用符号V和3来表示，分别称为全称量词和存在量词。

为了用全称 量词V表示个体域中所有(每一个)个体满足一元谓词P，用存在量词3表示有(存在)个体 满足一元谓词P,还需使用变元：VxP(x)读作“所有(任意，每一个)x满足P(x)”，表示个体域中所有的个体满足谓 词 P(x) 3x P(x)读作“有(存在，至少有一个)x满足P(x)”，表示个体域中至少有一个体满 足谓词 P(x)当量词用于一谓词填式或复合的谓词表达式时，该谓词或复合的谓词表达式称为量词 的辖域(domains of quantifiers)因此，量词的辖域或者是紧邻其右侧的那个谓词；或者 是其右侧第一对括号内的表达式量词的指导变元和量词辖域内的同名变元与通常谓词填式中的个体变元不同，因为它可以改名却不能取值作代入因此，我们把VxP(x)和mxP(x)中变元x称为约束变元(bound variables)，而那些可以取值作代入的变元则称为自由变元(free variables)对于一元谓词P(x)，VxP(x)，3xP(x)均为命题,它们所断言的“所有个体满足性质P(x) ” 与“存在个体满足性质P(x)”，其真值已经被给定的个体域所确定特别是,当个体域中个 体有穷时，例如D= {a,…,a },VxP(x)的意义与命题P(a) A„AP(a)相一致，而3xP(x)1 n 1 n的意义与命题P(a) V„VP(a)相一致。

1n2.1.4 谓词公式及语句形式化定义2.1归纳定义谓词公式(predicate formula)集合，谓词公式又称合式公式，简称 公式：(1) 谓词填式是公式，命题常元是公式(看作零元谓词)，常称原子公式2) 如果A，B是公式，x为任一个体变元，那么(「A), (A-B), (VxA)，(3x A)(当 使用五个联结词时还有(AAB), (AVB)，(AeB))都是公式3) (终极条款，略)括号省略原则同命题公式，并约定，(VxA), Gx A)中最外层括号也可省略 语句形式化过程的四个关键步骤是：• 准确地从语句中提取谓词一般说来，表示性质的谓语用一元谓词表示，表示关系 的谓语用二元或更多元数的谓词来表示• 准确使用量词和确定量词的辖域，当辖域中多于一个谓词时必须注意括号的使用• 准确地使用谓词之间的真值联结词，正确地反映谓词之间的逻辑关系• 准确地使用多个重叠的量词以及与它们配套的指导变元，量词的排列次序应与原语 句的表述相一致自然语言语句中，常常涉及全总个体域的某个局部的所有个体或某些个体，这时需要 使用所谓“限定谓词”把量词限于那个局部一般地说，当限定谓词用于限定全称量词时 它必须作为蕴涵词的前件加入；当限定谓词用于限定存在量词时，它必须作为合取词的合取 项加入，即用Vx(限定谓词A(x)-„) 和 3x(限定谓词A(x) A…)表示“所有满足A(x)的东西都…”和“在满足A(x)的东西中有满足…的个体”。

这里A(x) 是限定谓词，将个体域暂时限定在满足A(x)的那些个体上练习 2.11. 选择题(1) 下面哪个公式不是谓词公式( )A. P B. P(x) VQ(y)fR(x)C. Vx(P(x) AR(x,y) D. Vx(R(x) f P(x,y))【答案】：C(2) 谓词公式Vx(P(x)V3yR(y))fQ(x)中量词Vx的辖域是()A. Vx(P(x) V3yR(y)) B. P(x)C. P(x) V3yR(y) D. P(x), Q(x)【答案】： C(3) 谓词公式Vx(P(x) V3yR(y)) f Q(x)中变元 x 是()A.自由变元 B.约束变元C.既不是自由变元也不是约束变元 D.既是自由变元也是约束变元【答案】： D(4) 设C(x):x是国家足球队选手，G(x):x是健壮的命题“没有一个国家足球队选手不 是健壮的”可符号化为( )A. Vx(C(x) A—iG(x)) B. Vx(C(x)f G(x))C. 3x(C(x) A—G(x)) D. 3x(C(x) f—G(x))【答案】： B(5) 设L(x) : x是学员，J(x) : x是老师，A(x,y)： x钦佩y。

命题”所有学员都钦佩某 些老师”符号化为( )A. VxL(x) f A(x,y) B. Vx(L(x) f 3y(j(y) AA(x,y)))C. Vx 3y(L(x) A J(y) AA(x,y)) D. Vx 3y(L(x) A J(y) f A(x,y))【答案】: B(6) 命题”没有不犯错误的人”形式化为(设A(x) : x是人，B(x) : x犯错误()A. Vx(A(x) AB(x)) B. —3x(A(x) f—B(x))C. —3x(A(x) AB(x)) D. —3x(A(x) A—B(x))【答案】：D(7) 设I(x):x是整数，N(x):x是负数，S(x,y):y是x的平方，则“任何整数的平方非负” 可表示为下述谓词公式：( )A. VxVy(I(x) AS(x,y)f「N(y)) B. Vx^y(I(x) AS(x,y) f「N(y))C. VxVy(l(x)f S(x,y)「N(y)) D. Vx(l(x) AS(x,y) f ^N(y))【答案】：A(8) 令F(x):x是火车，G(y):y是汽车，H(x):x比y快贝I」语句“某些汽车比所有的火车 慢”可表示为： ( )A. 3y(G(y) f Vx(F(x) AH(x,y))) B. 3y(G(y) A Vx(F(x) f H(x,y)))C. Vx3y(G(y) f (F(x) AH(x,y))) D. 3y(G(y) f Vx(F(x) f H(x,y)))【答案】： B2. 填空题(1) 通常一元谓词表示事物的 ,多元谓词表示事物之间的 。

答案】：性质；关系(2) VxVy(P(x,y) AQ(y,z)) A3x P(x,y)中，Vx 的辖域为 , Vy 的辖域为 ,3x的辖域为 答案】： Vy(P(x,y)AQ(y,z))；P(x,y)AQ(y,z)；P(x,y)(3 )公式Vx(P(x) f Q(x,y) V 3zR(y,z)) f S(u)中自由变元为 ,约束变元为 答案】： y， u； x ， z(4) 设个体域为自然数集，则命题“不存在最大自然数”形式化为 答案】：「mxVy(x2y)(5) 个体域为自然数集，P(x):x为奇数，Q(x):x为偶数，则命题“不存在既是奇数又是偶数的自然数”形式化为 答案】：^3x(P(x) AQ(x))(6) 设个体域为实数集，则命题“任意实数总能比较大小”形式化为 答案】： VxVy(x>yVx0f x+y

则命题“所有的有理数是实数”,“有些有理数是整数”，“有些有理数是实数但不是整数”可分别 形式化为 ， ， 答案】：Vx(Q(x)f R(x)) ； 3x(Q(x) Al(x)) ； 3x(Q(x) AR(x) A「I(x))(9) 令 R(x):x 是实数， Q(x):x 是有理数命题“并非每个实数都是有理数”，可符号化为 答案】：「Vx(R(x)fQ(x))(10) 设:C(x):x是计算机，P(x,y):x能做y，I(x):x是智能工作，则命题“并非所有智能工作都能由计算机来做”形式化为 答案】：「Vx(I(x)f my(C(y) AP(y,x))3. 指出下列谓词公式中的量词及其辖域，指出各自由变元和约束变元，并回答它们是否是命题：(1) Vx(P(x) VQ(x)) AR(y)【答案】:全称量词V,辖域P(x) VQ(x)，其中x为约束变元o R(y)中y为自由变元Vx(P(x)V Q(x)) A R(y) 不是命题2) Vx(P(x) AQ(x)) A3xS(x) ^T(x)【答案】：全称量词V,辖域P(x)VQ(x)，其中x为约束变元存在量词玉辖域S(x)，其中x为约束变元。

T(x)中 x 为自由变元Vx(P(x) AQ(x)) A3xS(x) f T(x)不是命题3) Vx(P(x) f 3y(B(x,y) AQ(y)) VT(y))【答案】：全称量词V，辖域P(x) f 3y(B(x,y) AQ(y)) VT(y)，其中x为约束变元，T(y) 中y为自由变元存在量词玉 辖域B(x,y) AQ(y)，其中y为约束变元Vx(P(x) f 3y(B(x,y) AQ(y))VT(y)) 不是命题4) P(x) f (Vy3x(P(x) AB(x,y)) f P(x))【答案】：全称量词V,辖域3x(P(x) AB(x,y))，其中y为约束变元存在量词玉辖域P(x)AB(x,y)，其中x为约束变元不在量词辖域中的P(x)中的x为自由变元P(x) f (Vy3x(P(x) AB(x,y)) f P(x))不是命题4. 对个体域｛0,1｝判定下列公式的真值，E(x)表示“x是偶数”：(1) Vx(E(x) f —ix=1) (2) Vx(E(x) A—ix=1)(3) 3x(E(x) Ax=1) (4) mx(E(x)—x=1)再将它们的量词消去， 表示成合取或析取命题公式,鉴别你所确定的真值是否正确【答案】：(1) Vx(E(x)f—x=1) 真Vx(E(x) f—x=1)可表示成命题公式(E(0) f—0=1) A (E(1) f—1=1)其中 E(0)f—0=1 真，E(1)f—1=1 也真，故(E(0)f—0=1) A(E(1)f—1=1)真。

2) Vx(E(x)A—x=1) 假Vx(E(x)。