《清华离散数学(第2版)：3.1-2》由会员分享，可在线阅读，更多相关《清华离散数学(第2版)：3.1-2（38页珍藏版）》请在金锄头文库上搜索。
1、第3章 一阶逻辑1第3章 一阶逻辑 3.1 一阶逻辑基本概念 3.2 一阶逻辑等值演算23.1 一阶逻辑基本概念 3.1.1 命题逻辑的局限性 3.1.2 个体词、谓词与量词 个体常项、个体变项、个体域、全总个体域 谓词常项、谓词变项 全称量词、存在量词 3.1.3 一阶逻辑命题符号化33.1 一阶逻辑基本概念(续) 3.1.4 一阶逻辑公式与分类 一阶语言L （字母表、项、原子公式、合式 公式） 辖域和指导变元、约束出现和自由出现 闭式 一阶语言L 的解释 永真式、矛盾式、可满足式 代换实例4命题逻辑的局限性考虑下述推理: 凡偶数都能被2整除, 6是偶数, 所以6能被2整除.在命题逻辑中 令
2、 p: 凡偶数都能被2整除, q: 6是偶数, r: 6能被2整除 符号化为 (p q) r不能证明其正确性5个体词与个体域个体词: 所研究对象中可以独立存在的具体或抽象的客体个体常项: 表示具体事物的个体词, 用a, b, c等表示个体变项: 表示抽象事物的个体词, 用x, y, z等表示个体域: 个体变项的取值范围全总个体域: 宇宙间一切事物例如 “若x是偶数, 则x能被2整除.” x、 偶数和2是个体词, 偶数和2是个体常项, x是个体变 项个体域可以是自然数集N, 整数集Z, 也可以是全总个体域 6谓词谓词: 表示个体词性质或相互之间关系的词谓词常项: 表示具体性质或相互之间关系的谓词
3、谓词变项: 表示抽象性质或相互之间关系的谓词谓词用F,G,H,P等表示 n元谓词P(x1, x2, xn): 含n个命题变项的谓词, 是定义在 个体域上, 值域为0,1的n元函数一元谓词: 表示事物的性质多元谓词(n2): 表示事物之间的关系0元谓词: 不含个体变项的谓词,即命题常项或命题变 项7实例例1 (1) 4是偶数4是个体常项, “是偶数”是谓词常项, 符号化为: F(4) (2) 小王和小李同岁小王, 小李是个体常项, 同岁是谓词常项. 记a:小王, b: 小李, G(x,y): x与y同岁, 符号化为: G(a,b)(3) x3，则3y, G(x,y): x10, G(x): x0
4、真命题20解释定义3.7 设一阶语言L 的个体常项集ai| i1, 函数符号集 fi| i1, 谓词符号集Fi| i1, L 的解释I由下面4部分组成:(1) 非空个体域DI(2) 对每一个个体常项ai, DI, 称作ai在I中的解释(3) 对每一个函数符号fi, 设其为m元的, 是DI上的m元函数, 称作fi在I中的解释(4) 对每一个谓词符号Fi, 设其为n元的, 是一个n元谓词, 称作Fi在I中的解释21实例例8 给定解释I 如下: (a) 个体域 D=N(b) (c) (d) 谓词 说明下列公式在 I 下的含义, 并讨论其真值 (1) xF(g(x,a),x)x(2x=x) 假命题(2
5、) xy(F(f(x,a),y)F(f(y,a),x)xy(x+2=yy+2=x) 假命题 22实例(续)(3) xyzF(f(x,y),z)(5) F(f(x,a), g(x,a)(4) xF(f(x,x),g(x,x) x(2x=x2) 真命题xyz (x+y=z) 真命题(6) x (F(x,y)F(f(x,a), f(y,a) x (x=yx+2=y+2) 真命题x+2=2x 不是命题23闭式的性质定理3.1 闭式在任何解释下都变成命题.例8 (1)(4)都是闭式, 在I下全是命题. (5)和(6)不是闭式, 在I下(5)不是命题, (6)是命题24一阶逻辑公式的分类永真式(逻辑有效式
6、): 无成假解释矛盾式(永假式): 无成真解释可满足式: 至少有一个成真解释在一阶逻辑中, 公式的可满足性(永真性,永假性)是不 可判定的,即不存在算法能在有限步内判断任给的公式是 否是可满足式(永真式,矛盾式) 25代换实例定义3.9 设A0是含命题变项p1, p2, ,pn的命题公式, A1,A2, An是n个谓词公式, 用Ai处处代替A0中的pi(1in), 所得公式A称为A0的代换实例.例如 F(x)G(x), xF(x)yG(y) 等都是pq的代换实例定理3.2 重言式的代换实例都是永真式，矛盾式的代换实例都是矛盾式. 26实例例9 判断下列公式的类型: (1) x(F(x)G(x)
7、非永真式的可满足式(2) (xF(x)(xF(x) 这是 pp 的代换实例, pp是重言式, 取解释I1, D1=R, :x是整数, :x是有理数, 真命题永真式(3) (xF(x)yG(y) yG(y)这是(pq)q的代换实例, (pq)q是矛盾式矛盾式取解释I2, D2=R, :x是整数, :x是自然数, 假命题273.2 一阶逻辑等值演算 3.2.1 一阶逻辑等值式与置换规则 基本等值式 置换规则、换名规则、代替规则 3.2.2 一阶逻辑前束范式28等值式定义3.10 若AB是永真式, 则称A与B是等值的, 记作 AB, 并称AB为等值式基本等值式 命题逻辑中基本等值式的代换实例 如，x
8、F(x)yG(y) xF(x)yG(y)(xF(x)yG(y) xF(x)yG(y) 等 消去量词等值式 设D=a1,a2,an xA(x)A(a1)A(a2)A(an) xA(x)A(a1)A(a2)A(an)29基本等值式(续)量词辖域收缩与扩张等值式 设A(x)是含x自由出现的公式，B中不含x的出现关于全称量词的：x(A(x)B)xA(x)Bx(A(x)B)xA(x)Bx(A(x)B)xA(x)Bx(BA(x)BxA(x) 关于存在量词的:x(A(x)B)xA(x)Bx(A(x)B)xA(x)Bx(A(x)B)xA(x)Bx(BA(x)BxA(x)30基本等值式(续)量词否定等值式设A(
9、x)是含x自由出现的公式xA(x) x A(x) xA(x)x A(x)量词分配等值式 x(A(x)B(x)xA(x)xB(x)x(A(x)B(x)xA(x)xB(x)注意：对无分配律，对无分配律 31置换规则、换名规则、代替规则置换规则 设(A)是含公式A的公式, (B)是用公式B取 代(A)中的所有A得到的公式, 则(A)(B)换名规则 将公式A中某量词的指导变元及其在辖域内 的 所有约束出现改成该量词辖域内未曾出现的某个个体变 项, 其余部分不变, 记所得公式为A, 则AA 代替规则 将公式A中某个自由出现的个体变项的所有 自 由出现改成A中未曾出现的某个个体变项, 其余部分不变 , 记
10、所得公式为A, 则AA32实例例1 消去公式中既约束出现、又自由出现的个体变项 (1) xF(x,y,z) yG(x,y,z) uF(u,y,z) yG(x,y,z) 换名规则 uF(u,y,z) vG(x,v,z) 换名规则或者 xF(x,u,z) yG(x,y,z) 代替规则 xF(x,u,z) yG(v,y,z) 代替规则(2) x(F(x,y) yG(x,y,z) x(F(x,y) tG(x,t,z) 换名规则或者 x(F(x,t) yG(x,y,z) 代替规则33实例例2 设个体域D=a,b,c, 消去下面公式中的量词: (1) x(F(x)G(x) (F(a)G(a)(F(b)G(
11、b)(F(c)G(c)(2) x(F(x)yG(y) xF(x)yG(y) 量词辖域收缩 (F(a)F(b)F(c)(G(a)G(b)G(c) x(F(x,a)F(x,b)F(x,c)(3) xyF(x,y) (F(a,a)F(a,b)F(a,c)(F(b,a)F(b,b)F(b,c)(F(c,a)F(c,b)F(c,c) 34实例解 (F(f(2)G(2, f(2)(F(f(3)G(3, f(3)例3 给定解释I: (a) D=2,3, (b) (c) :x是奇数, : x=2 y=2, : x=y. 在I下求下列各式的真值: (1) x(F(f(x)G(x, f(x) (2) xyL(x,
12、y) (11)(01) 1解 yL(2,y)yL(3,y) (L(2,2)L(2,3)(L(3,2)L(3,3) (10)(01) 0 35实例例4 证明下列等值式: x(M(x)F(x) x(M(x) F(x)证 左边 x (M(x)F(x) 量词否定等值式 x(M(x)F(x) x(M(x) F(x)36前束范式定义3.11 设A为一个一阶逻辑公式, 若A具有如下形式Q1x1Q2x2Qkxk B 则称A为前束范式, 其中Qi 为或, 1ik, B为不含量词 的 公式.例如 xy(F(x)(G(y)H(x,y) x(F(x)G(x)是前束范式 x(F(x)y(G(y)H(x,y)x(F(x)G(x)不是前束范式37公式的前束范式定理3.3(前束范式存在定理) 一阶逻辑中的任何公式都 存 在与之等值的前束范式 例5 求公式的前束范式 (1) xF(x)xG(x)解 xF(x)xG(x) 量词否定等值式 x(F(x)G(x) 量词分配等值式 解2 xF(x)yG(y) 换名规则 xF(x)yG(y) 量词否定等值式 x(F(x)yG(y) 量词辖域扩张 xy(F(x)G(y) 量词辖域扩张38
