离散数学谓词逻辑.ppt

第二章 谓词逻辑 1 在命题逻辑中,原子命题是进行演算的基本单 位,不研究命题的内部结构以及命题之间的内在联系,因 而,命题逻辑中的推理有很大的局限性。例如,著名的苏 格拉底三段论： 所有的人都是要死的, 苏格拉底是人, 所以苏格拉底是要死的。 符号化： 分别用P、Q、R表示以上三个命题,则 PQR表示这一推理过程。 蕴含式PQR不是重言式,虽然凭我们的直 觉这个论断正确,在内部逻辑中却无法证明。 谓词逻辑的任务就是对原子命题作进一步的 分析,研究其内部的逻辑结构,并在此基础上更深入地刻 画推理。 2 谓词逻辑：原子命题客体词谓词 命题所陈述的对象称为客体词。它可以是一个具体的事 物,也可以是一个抽象的概念。例如,李明、自然数、思想等都 可以作为客体词。 定义用来刻画客体词的性质或客体词之间的关系的词称 为谓词。 例如： 是无理数。 小李是计算机系的学生。 李明比王宏高2厘米。 “”、“小李”、“李明”、“王宏”都是客体词 ； “是无理数”“是计算机系的学生”“高2 厘米”都是谓词。前两个谓词表示客体词的性质,而后一个谓 词描述客体词之间的关系。 2.1谓词的概念与表示 3 谓词的表示 客体词有两种：客体常元和客体变元。客 体常元表示具体的或特定的客体,一般用小写字 母a、b、c等表示；表示抽象的或泛指的客体的 词称为客体变元,常用小写字母x、y、z等表示 。 谓词,通常用大写的字母A、B、C等表示。 谓词填式：单独一个谓词不是完整的 命题,把谓词字母后填以客体所得的式子。 4 例子 例2-1.1 张明是位大学生。 解：设S(x)：x是大学生,c：张明, 则原句的谓词形式为S(c)。 例2-1.2我坐在张三和李四中间。 解：设S(x,y,z)：x坐在y和z之间,i：我,z ：张三,l：李四, 则原句的谓词形式为S(i,z,l)。 一元谓词：表 示客体性质 多元谓词：表 示客体间关系 5 一般来说,谓词P(x1 ,xn)不是命题,真值无 法确定,只有当n 个客体常元代替 x1,x2 , xn 这 n个客体变元之后 ,才有了确定的真值,因而也就 成了命题。 例如,L(x,y) 是表示x小于y的二元谓词,它 的真值不能确定,当以2(用a 表示)、3(用b表示 )替换x和y之后,L(a,b)成为真命题。 6 2.2命题函数与量词 例子： 假设 谓词H表示“能够到达山顶”,客体p 表示李四,q表示老虎,r表示汽车。 那么 H(p), H(q), H(r)表示三个不同的命 题 相同点：H(x) 定义 由一个谓词,一些客体变元组成的表达 式称为简单命题函数。由一个或者n个简单命题 函数以及逻辑联结词组合而成的表达式称为复 合命题函数。 7 客体变元的取值范围称为个体域(或 论述域)。个体域可以是有限客体的集合 ,如：a、b、c、计算机系的学生；也可以是无 限客体的集合,如实数几何、自然数集合等。 特别是,当没有特别声明时,可以将宇 宙间的一切事物和概念构成的集合作为 个体域,称为全总个体域。 8 量 词 1.所有的人都是要死的。 2.有些人是要死的。 这两个命题中的客体词和谓语均相同,区别在于“ 所有的”和“有些”这两个表示数量的词。表示数量 的词在谓词逻辑中称为量词,量词包括全称量词和存在 量词两种。 全称量词对应日常语言中的“一切”、“所有的 ”、“任意的”等词,表示对个体域的所有客体,用符 号“”表示。 存在量词对应对应日常语言中的“存在着”、“ 至少有一个”、“有些”等词,表示存在着个体域的客 体,用符号“ ”表示. 9 例如： xF(x)表示个体域中的所有客体都有性质F； xF(x)表示存在着个体域中的客体具有性质F 。 当个体域有限时,设个体域为a1,a2,an ,则 x F(x)F(a1)F(a2) F(an ) x F(x)F(a1) F(a2) F(an) 10 符号化:谓词F(x)表示是要死的。 当个体域为人类集合时,上述两命题可分别符号 化为 x F(x) x F(x)。 (所有的人都是要死的。 有些人是要死的。 ) 引入新的谓词M(x),将人类分离出来。在全总个 体域下,以上两命题可分别叙述为： x(M(x)F(x) x (M(x)F(x) 从以上两命题的符号化可以看出,同一命题在不同个体 域下符号化的形式可能不同。 11 这里,M(x)称为特性谓词。应该注 意的是,全称量词和存在量词符号化时,引 入特性谓词时的形式是不同的。 用全称量词 符号化时,特性谓词作为 条件式的前件； 用存在量词符号化时则作为合取式的 一项。 12 对于任一给定的实数x,都存在着一个实数y,使 得x+y=0。 如果取个体域为实数集合 x y H(x, y ) 然而 y x H(x, y )： 存在着一个少数y,对于任一实数x,使得x+y=0 由此可见,量词出现的不同顺序表达了不同的含 义,量词的顺序不能随意颠倒。我们约定,量词按从左 到右的顺序读出。 13 练习 Page59 (1)c. g. Page60 (2)a. i. 14 2.3谓词公式与翻译 1.谓词公式 为了使命题的符号化更准确和规范,以及正 确进行谓词演算和推理,我们介绍谓词演算合式 公式的概念。 定义 2.3.1 设R( x1,x2,xn)是n元谓词, 其中x1,x2,xn 是客体变元,则R(x1,x2,xn) 称为谓词演算的原子公式。 15 定义2.3.2 谓词演算的合式公式定义如下： (1)原子公式是合式公式； (2)若A是合式公式,则(A)是合式公式； (3)若A、B是合式公式,则(AB)、(AB)、 (AB)、(AB)是合式公式； (4)若A是合式公式,则(x) A、(x)A是合 式公式； (5)只要有限次地应用(1)(4)构成的符号串 才是合式公式。 谓语演算的合适公式简称为谓词公式。与命题公 式类似,谓词公式最外层的括号也可以省略。 16 例 1 在谓词逻辑中将下列命题符号化。 (1)没有不死的人。 (2)不存在最小数。 (3)教育技术系的学生都学离散数学。 解 题目中没有指定个体域,取个体域为全总个体域。 (1)假设,M(x)：x是人,F(x)：x是要死的，那么 x(M(x) F(x) (2)假设,N(x)：x是数,L(x,y)：x小于y，那么 x(N(x) y(N(y) L(x,y) (3)假设,S(x)：x是教育技术系的学生,F(x)：x要学离 散数学，那么 (x)(S(x) F(x) 本题也可以引入二元谓词G(x,y)：x是学习y,以及客体常元 a：离散数学,进行如下符号化： (x)(S(x)G(x,a) 17 练习 Page62 (1)a. c. e. Page62 (2) A:5是质数。 C:对所有的x,若x 被2除尽,则x是偶 数. E:对所有的x,若x 不是偶数,则x不能 被2除尽. 18 2.4变元的约束 定义 2.4.1 在谓词公式(x)A(x)和 (x)A(x),x 称为量词的指导变元或作用变元, A(x) 称为量词的辖域或作用域。辖域中x的所有出现称为约 束出现,也称x受相应量词指导变元的约束,A(x)中不是 约束出现的其他变元的出现成为自由出现(也称自由变 元、参数)。 19 例1 指出下列谓词公式中各量词的指导变元 、辖域以及客体变元的出现情况。 (1)(x)P(x)P(y) (2)(x)(P(x)Q(x)(x)R(x) (3)(x)(P(x,y)(x)Q(x)(y)R (y,s) 解 (1)在(x)P(x)中,(x)的辖域是P(x),指导 变元是x。整个公式中,x是约束出现,受(x)的约束,y 是自由出现。 (2)在(x)(P(x)Q(x)中 (x)的指导变 元是x ,辖域是P(x)Q(x),x是约束出现,受(x)的约 束。(x)R(x)中(x)的指导变元是x ,辖域是R(x),x 是约束出现,受(x)的约束。整个公式中,x是约束出 现。 20 (3)(x)(P(x,y)(x)Q(x)(y)R(y, s) (x)Q(x)中的指导变元是x,辖域是Q(x),x的出 现是约束出现； (x)(P(x,y)(x)Q(x)中的辖域是 P(x,y)(x)Q(x),指导变元是x,x的第2个是约束出现 ,但受x的约束,y自由出现； yR(y,s)中的指导变元是y,辖域是R(y,s),y的 出现是约束出现,s自由出现； 整个公式中,x约束出现,y既有自由出现又有约束出 现,s自由出现。 21 从前面的讨论可以看出,一个谓词公式中, 有的客体变元既有自由出现又有约束出现(从例 2中的(3)、(4)式的y),这样就容易引起概念上 的混乱。为了避免这种混乱可以采用如下的两 条规则： 约束变元的改名规则 将量词辖域中出现 的某个约束变元及相应的指导变元换成一个辖 域中未曾出现过的客体变元名,公式的其余部分 不变。 22 自由变元的代入规则 对某个自由出现的客体 变元,用与原公式中所有变元名不同的变元名每一处代 入。 这两条规则之所以正确,是由于在构造一个公式时, 变元的名称是无关紧要的。例如,我们想将如下如下命题符号 化： 所有的人都是要死的。 设当前的个体域是人类集合,如果用P(x)表示x是要 死的,则命题可符号化为(x)P(x);如果用P(y)表示y是要死的 ,则(y)P(y)同样表达该命题。P(x)和P(y)在表达“是要 死的”这个意义上是相同的,变量的名称无关紧要。 23 例3 对例2中的公式实施改名或代入规则。 (1) xP(x) P(y)显然没有必要进行改名或 代入。 (2) 对 xR(x)实施改名规则,得 xR(y),这样原 公式就化为 x(P(x) Q(x) yR(y) (3) 对( x)Q(x)中x的约束出现实施改名规则, 得( )Q(),同时对( y)R(y,s)实施改名规则,得 ( t)R(t,s),这时原公式化为 ( x)P(x,y) ( )Q() ( t)R(t,s) 24 2.5 谓词演算的等价式与蕴含式 一个谓词公式中一般有客体常元、客体变元以及命题变 元等,对各种变元指定特定的常元代替,就构成了对公式的解释 (赋值)，即可以判断其逻辑真值T或F。 定义2.5.1 一个解释(赋值)I由下面几部分构成： (1)非空个体域D； (2)D中一部分特定元素； (3)D上一些特定谓词。 用一个解释I解释一个谓词公式A包括：将I的个体域D作 为A的个体域,A中的客体常元用I中的特定元素代替,谓词用I上 的特定谓词代替。 25 例1 给定解释I1如下： (1)个体域为自然数集合N； (2)N中的特定元素a=0； （3）F(x,y):x大于或等于y. 在解释I1下,求下列各式的真值： (1)(x)F(x,a)；(2)(xy)F(x,y) 解 在解释I1下,公式分别解释为： (1)任何自然数都大于或等于零, 为真命题. (2)对任一自然数x,都存在一自然数y使得xy, 为真命题. 26 例2 考虑以下解释 I2： (1)个体域D=0,1 ； (2)D中的特定元素 a=0； (3)D上的特定谓词 P： P(0,0)P(0,1)P(1,0)P(1,1) 0110 在解释I2下,下列那些公式为真？那些为假？ (1) (x)( y)P(x,y) (2) (x )( y)(P(x,y)P(y,x) (3) (x) P(x,a) 解 在解释I2下,原公式分别化为： (1)(x )( y)P(x,y)(y)P(0,y)(y)P(1,y) (P(0,0)P(0,1) (P(1,0)P(1,1) (FT)(T F) (TT) T 27 (2) (xy)(P(x,y)P(y,x) (P(0,0)P(0,0) (P(0,1) P(1,0) (P(1,0) P(0,1) (P(1,1) P(1,1) (F F) (T T) (T T) (F F) T T T T T (3)(x) P(x,a) P(0,0) P(1,0) FT F 28 从上述两个例子可以看出，有的公式在具 体解释下真值确定，是命题。 但是，如果公式不含自由变元，由于每个 客体变元都受量词的约束,因而在具体解释下总表达一 个意义确定的语句，即一个真命题或假命题。例2中的 (1)(3)都是，它们在各种解释下均是命题。 29 定义2.5.2 设A为一谓词公式,如果A在任何解释下都是 真的,则称A是重言式(永真式)；如果A在任何解释下都是假的, 则称A是矛盾式(永假式)；若至少存在一种解为真,则称A是可 满足式。 由定义可知,重言式也称可满足式。 定义2.5.3 设A、B是两个谓词公式,若AB是永真式, 则称A和B等价或A等价于B,记作AB,这个式子称为等价式。 定义2.5.4 设A、B为两个谓词公式,若AB是永真式, 则称A蕴含B,记作AB。 30 等价式和永真蕴含式 首先,命题演算的永真式也是谓词演算的永真式。 例如 : x(P(x)Q(x)x(P(x)Q(x) (蕴含表达式 ) (xP(x)yQ(y) xP(x)yQ(y) (德.摩根定律) xP(x)(xP(x)yQ(y)yQ(y) (假言推理 ) 31 特有的等价式和永真蕴含式 (1) 对的永真蕴含关系 xP(x) xP(x) (对的永真蕴含式) 这个式子显然成立。因为“对个体域中的任何客 体P(x) 成立”当然能推出“存在个体域中的某个使P(x)成立 ”。 (2)量词的否定(量词的转化律) xP(x) x P(x) x P(x) x P(x) 这里约定,出现在量词前面的否定,不是否定该量 词本身,而是否定被量化了的整个公式。 ？ 32 有限个体域上证明 设个体域为a1,a2,an,则 xP(x) (P(a1) P(a2) P(an) P(a1) P(a2) P(an) xP(x) xP(x) (P(a1) P(a2) P(an) P(a1) P(a2) P(an) (x)P(x) 33 (3)量词辖域的扩张与收缩 xA(x)Bx(A(x) B) xA(x)Bx(A(x) B) xA(x)Bx(A(x) B) xA(x)Bx(A(x) B) xA(x)Bx(A(x)B ) xA(x)Bx(A(x)B ) BxA(x)x(BA(x) ) BxA(x)x(BA(x) ) 34 例3 证明xA(x)B x(A(x)B) 证明： xA(x)B xA(x)B (蕴含表达式) xA(x)B (量词转化率) x(A(x)B) (量词辖域扩张) x(A(x)B) (蕴含表达式) (4) 量词的分配形式 x(A(x)B(x) xA(x)xB(x) (对的分配 率) “对于任意的x, A(x)和B(x)都成立”,当然等价于 “对于任意的x, A(x)成立,并且对于任意的x, B(x)成立”。 x(A(x)B(x) xA(x)xB(x)(对的分配率 ) ？ 35 但是,下面的式子却不成立： x(A(x)B(x) xA(x)xB(x) x(A(x)B(x)xA(x)xB(x) 要证明这两个等价式不成立,只要给出一种解 释,使得等价式在该解释下不成立既可。 虽然如此,却有如下的永真蕴含式： x(A(x)B(x) xA(x)xB(x) (对的永真蕴含式) 分别以A(x)、B(x)代入上式的A(x)、B(x)得 xA(x)xB(x) x(A(x)B(x) (对的永真蕴含式) 36 (5)关于多个量词的永真式 从前面的叙述我们知道,多个量词同时出现 时,其顺序不能随意颠倒。但是,按特定顺序出现的多 量词公式之间却存在着等价式和永真蕴含式。 在此,我们只举2个量词的情况,更多量词的 情况与之类似。 xyA(x,y); yxA(x,y); xyA(x,y); yxA(x,y); xyA(x,y); yxA(x,y); 37 xyA(x,y) yxA(x,y) xyA(x,y)yxA(x,y) xyA(x,y)yxA(x,y) 38 现将常用的谓词演算等价式和永真蕴含式 归纳如下： (1) 对的永真蕴含式 xP(x)xP(x) (2)量词的转化律 xP(x)xP(x) xP(x)xP(x) 39 (3)量词辖域的扩张与收缩 xA(x)Bx(A(x)B) xA(x)Bx(A(x)B) xA(x)Bx(A(x)B) xA(x)Bx(A(x)B) (4)对A的分配律 x(A(x)B(x) xA(x)xB(x) 40 (5) 对的分配律 x(A(x)B(x)xA(x)xB (x) (6) 对的永真蕴含式 xA(x)xB(x)x(A(x)B( x) (7) 对的永真蕴含式 x(A(x)B(x)xA(x)xB (x) 41 例5 判断下面的证明是否正确。 x(A(x)B(x) x(A(x)B(x) x(A(x)B(x) x(A(x)B(x) (xA(x)xB(x) xA(x)xB(x) xA(x)xB(x) xA(x)xB(x) 42 解 这个推证错误。错误在于下面的一步： x(A(x)B(x) (xA(x)x B(x) 由对的永真蕴含式(7)可得 x(A(x)B(x)xA(x)xB(x) 又由逆反律得 (xA(x)xB(x)x(A(x) B(x) 而反向的永真蕴含式却不一定成立,而且通常不成立。 43 2.6 前束范式 在命题演算中,常将公式化为规范形式。对于 谓词演算也有类似情况。 定义2.6.1 一个谓词公式,如果量词均在全式 的开头,且其辖域延伸到公式的末尾,则该公式称为前束 范式。 也就是说,前束范式有如下形式： v1v2vnA 其中,可以是或,vi(I=1,n)是客体变元,A是 不含量词的谓词公式。例如, xyz(P(x,y)Q(z)R(x,z), xz(P(x,y)Q(z)等 都是前束式。 44 定理 2.6.1 任意一个谓词公式均可化为与 之等价的前束范式。 证明 首先利用量词的转化律将量词前面的 否定深入到谓词前面,再利用改名和代入规则以及量词 辖域扩张的公式将量词移到全式的最前面,便得到前束 范式。 这个定理的证明实际上提供了求一个谓词公 式的前束范式的方法和步骤。下面我们举例说明。 45 例1 求下面谓词公式的前束范式。 (1)xy(zP(x,z)P(y,z)uQ(x,y,u) (2)x(yA(x,y) xy(B(x,y)y(A(x,y)B(x,y) 解 (1)xy(zP(x,z)P(y,z)uQ(x,y,u) xy(zP(x,z)P(y,z)uQ(x,y,u) (蕴含表达式) xy(zP(x,z)P(y,z)uQ(x,y,u) (量词转化律) xy(wP(x,w)P(y,z)uQ(s,t,u) (改名及代入规则) xywu(P(x,w)P(y,z)Q(s,t,u) (量词辖域扩张) 46 (2) x(yA(x,y)xy(B(x,y)y(A(x,y)B(x,y) x(yA(x,y)xy(B(x,y)y( A(x,y)B(x,y) (蕴含表达式) x(yA(x,y)xy(B(x,y)y(A(y,x) B(x,y) (量词转化律、德.摩根定律) x(yA(x,y)xy(B(x,y)z(A(z,x) B(x,z) (改名规则) x(yA(x,y)xyz(B(x,y)(A(z,x) B(x,z) (量词辖域扩张) x(yA(x,y)stz(B(s,t)(A(z,s) B(s,z) (改名规则) xyzstz(A(x,y)(B(s,t)(A(z,s) B(s,z) (量词辖域扩张)47 注意 由于进行演算时所用的方法不同,对于同 一公式可能得到不同的前束范式,因此,给定公式 的前束范式并不是惟一的。 但是,所有前束范式的各指导变元应各不 相同,原公式中自由出现的客体变元在前束范式 中也应自由出现；否则就应该检查纠正演算中的 错误。 48 前束范式中量词的个数必须等于原公式中量词的个数吗? 答案是否定的。原因是由于下面的等价式： xA(x)xB(x)x(A(x)B(x) xA(x)xB(x)x(A(x)B(x) 当然,如果你愿意,也可以保持原公式中量词的数目： xA(x)xB(x) xA(x)yB(y) (改名规则) xy(A(x)B(y) (量词辖域扩 张) 49 定义2.6.2 若一个谓词公式A有如下形式,则 称之为前束析取范式。 v1 v2 vn (A11A12A1k1)(A21A22A2k2) (Am1Am2Amkm) 其中 是量词,vi(I=1,2,n)是客体变元 ,Aikj(I,j=1,m)是原子公式或其否定。 定理2.6.3 任一谓词公式均可化为与之等价 的前束析取范式(证明从略)。 50 定义 2.6.3一谓词公式A如果有如下形式, 则称之为前束合取范式。 v1 v2 vn(A11A12 A1k1 ) (A21 A22 A2k2) (Am1 Am2 Amkm) 其中,、vi、Aiki的概念与定义2.4.2中相 同。 定理2.6.4 任一谓词公式均可化为与之等 价的前束合取范式(证明从略)。 51 作业 P72 (2)c P75 (1)b 52 2.7 谓词逻辑的推理理论 谓词逻辑的推理可以看作是对命题逻辑推理 的扩充。谓词逻辑中,前提、结论、推理等概念与命题 逻辑中相同,只不过参加推理的是谓词公式而非命题公 式。 命题逻辑的推理规则均可在谓词逻辑推理中 应用。但是,谓词逻辑的推理有着自己的特点。看两个 谓词逻辑推理的例子,第一个是苏氏三段论： 所有的人都是要死的, 苏格拉底是人, 所以苏格拉底是要死的。 53 第二个是实数域上的推理： 所有的有理数是实数, 某些有理数是整数, 因此某些实数是整数。 我们看到,前提和结论中均有量词出现。只有 消去前提中的量词,才能应用命题逻辑 中的推理规则 ；而推导出的结论又必须适当加上量词,才能得到含有 量词的最后结论。因此有如下消去和添加量词的规则 。在下面的叙述中,AB中的A、B可分别看作前提和结 论。 54 消去量词的规则有两类：全称规则和存在指定规 则。 1.全称指定规则(简称US规则) 这条规则有如下两中形式： (1) xP(x)P(y) (2)xP(x)P(c) 其中,(1)中y为任意不在P(x)中约束出现的客 体变元(因而可以是x本身)；(2)中c为个体域中的任一 客体常元。 这两个式子表达的含义分别是：如果对个 体域中的任意客体x,A(x)成立,则当然对可以取任何值 的客体变元y、A(y)成立；对任意的客体常元c、A(c) 成立。 55 2.存在指定规则(简称ES规则) xP(x)P(c) 其中,c是使P成立的特定客体常元。 看下面的推理过程： (1) xF(x) P (2) F(c) ES1 (3) xG(x) P (4) G(c) ES3 (5) F(c)G(c) T(2),(4) 有问题 吗？ 56 推理的第(4)步是错误的。使F成立的特定客 体不一定能使G成立,因此,一般地,对xG(x)运用ES规 则,只能得到G(d)。 添加量词的规则也有两条：全称推广规则和 存在推广规则。 3.全称推广规则(简称UG规则) P(y)xP(x) 如果能够证明,y取任何值时P均为真,则可得 结论xP(x)。 57 4.存在推广规则(简称EG规则