离散数学一阶逻辑

《离散数学一阶逻辑》由会员分享，可在线阅读，更多相关《离散数学一阶逻辑（38页珍藏版）》请在金锄头文库上搜索。

1、1,第3章 一阶逻辑,2,第3章 一阶逻辑,3.1 一阶逻辑基本概念 3.2 一阶逻辑等值演算,3,3.1 一阶逻辑基本概念,3.1.1 命题逻辑的局限性 3.1.2 个体词、谓词与量词 个体常项、个体变项、个体域、全总个体域 谓词常项、谓词变项 全称量词、存在量词 3.1.3 一阶逻辑命题符号化,4,3.1 一阶逻辑基本概念(续),3.1.4 一阶逻辑公式与分类 一阶语言L （字母表、项、原子公式、合式公式） 辖域和指导变元、约束出现和自由出现 闭式 一阶语言L 的解释 永真式、矛盾式、可满足式 代换实例,5,命题逻辑的局限性,考虑下述推理: 凡偶数都能被2整除, 6是偶数, 所以6能被2整

2、除. 在命题逻辑中 令 p: 凡偶数都能被2整除, q: 6是偶数, r: 6能被2整除 符号化为 (p q) r 不能证明其正确性,6,个体词与个体域,个体词: 所研究对象中可以独立存在的具体或抽象的客体 个体常项: 表示具体事物的个体词, 用a, b, c等表示 个体变项: 表示抽象事物的个体词, 用x, y, z等表示 个体域: 个体变项的取值范围 全总个体域: 宇宙间一切事物 例如 “若x是偶数, 则x能被2整除.” x、 偶数和2是个体词, 偶数和2是个体常项, x是个体变项 个体域可以是自然数集N, 整数集Z, 也可以是全总个 体域,7,谓词,谓词: 表示个体词性质或相互之间关系的

3、词 谓词常项: 表示具体性质或相互之间关系的谓词 谓词变项: 表示抽象性质或相互之间关系的谓词 谓词用F,G,H,P等表示 n元谓词P(x1, x2, xn): 含n个命题变项的谓词, 是定义在 个体域上, 值域为0,1的n元函数 一元谓词: 表示事物的性质 多元谓词(n2): 表示事物之间的关系 0元谓词: 不含个体变项的谓词,即命题常项或命题变项,8,实例,例1 (1) 4是偶数 4是个体常项, “是偶数”是谓词常项, 符号化为: F(4) (2) 小王和小李同岁 小王, 小李是个体常项, 同岁是谓词常项. 记a:小王, b: 小李, G(x,y): x与y同岁, 符号化为: G(a,b)

4、 (3) x y x,y是命题变项, 是谓词常项, 符号化为: L(x,y) (4) x具有某种性质P x是命题变项, P是谓词变项, 符号化为: P(x),9,实例,例2 将下述命题用0元谓词符号化, 并讨论它们的真值: (1) 是无理数, 而 是有理数 (2) 如果23，则3y, G(x,y): xy, 符号化为 F(2,3)G(3,4) 真值为1,10,量词,量词: 表示数量的词 全称量词: 表示任意的, 所有的, 一切的等 如 x 表示对个体域中所有的x x F(x) 表示所有的x具有性质F 存在量词: 表示存在, 有的, 至少有一个等 如 x 表示在个体域中存在x x F(x) 表示

5、存在x具有性质F,11,一阶逻辑命题符号化,例3 在一阶逻辑中将下面命题符号化: (1) 人都爱美; (2) 有人用左手写字 个体域分别取(a) 人类集合, (b) 全总个体域 . 解: (a) (1) 设F(x): x爱美, 符号化为 x F(x) (2) 设G(x): x用左手写字, 符号化为 x G(x) (b) 设M(x): x为人， F(x), G(x)同(a)中 (1) x (M(x)F(x) (2) x (M(x)G(x) M(x)称作特性谓词,12,实例,例4 将下列命题符号化, 并讨论其真值: (1) 对任意的x, 均有x2-3x+2=(x-1)(x-2) (2) 存在x,

6、使得x+5=3 分别取(a) 个体域D1=N, (b) 个体域D2=R 解 记F(x): x2-3x+2=(x-1)(x-2), G(x): x+5=3 (a) (1) x F(x) 真值为1 (2) x G(x) 真值为0 (b) (1) x F(x) 真值为1 (2) x G(x) 真值为1,13,实例,例5 将下面命题符号化: (1) 兔子比乌龟跑得快 (2) 有的兔子比所有的乌龟跑得快 (3) 并不是所有的兔子都比乌龟跑得快 (4) 不存在跑得一样快的兔子和乌龟 解 用全总个体域, 令F(x): x是兔子, G(y): y是乌龟, H(x,y): x比y跑得快, L(x,y): x和y

7、跑得一样快 (1) xy(F(x)G(y)H(x,y) (2) x(F(x)(y (G(y)H(x,y) (3) xy(F(x)G(y)H(x,y) (4) xy(F(x)G(y)L(x,y),14,注意,(1) 一元谓词和多元谓词的使用 (2) 全称量词和存在量词的区别 (3) 多个量词出现时, 不能随意交换顺序 如 在个体域R中, 记H(x,y): x+y=10 xy H(x,y) 真值为1 yx H(x,y) 真值为0 (4) 命题的符号化不惟一 如例5 (1) x (F(x)y(G(y)H(x,y) (3) xy(F(x)G(y)H(x,y) (4) xy(F(x)G(y)L(x,y)

8、,15,一阶语言L,定义3.1 一阶语言L 的字母表定义如下： (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) 括号与逗号：( ), ，,16,一阶语言L (续),定义3.2 L 的项的定义如下： (1) 个体常项和个体变项是项. (2) 若(x1, x2, , xn)是任意的

9、n元函数，t1,t2,tn是任意 的n个项，则(t1, t2, , tn) 是项. (3) 所有的项都是有限次使用 (1), (2) 得到的. 定义3.3 设R(x1, x2, , xn)是L 的任意n元谓词，t1,t2, tn 是L 的任意n个项，则称R(t1, t2, , tn)是原子公式,17,一阶语言L (续),定义3.4 L 的合式公式定义如下： (1) 原子公式是合式公式 (2) 若A是合式公式, 则 (A)也是合式公式 (3) 若A, B是合式公式, 则(AB), (AB), (AB), (AB)也 是合式公式 (4) 若A是合式公式, 则xA, xA也是合式公式 (5) 只有有

10、限次地应用(1)(4)形成的符号串才是合式公式. 合式公式又称谓词公式, 简称公式,18,量词的辖域,定义3.5 在公式xA和xA中, 称x为指导变元, A为相应量 词的辖域. 在x和x的辖域中, x的所有出现称为约束出现， A中不是约束出现的其他变项称为自由出现 例6 公式 x(F(x,y)yG(x,y,z) x的辖域:(F(x,y)yG(x,y,z)， 指导变元为x y的辖域:G(x,y,z)， 指导变元为y x的两次出现均为约束出现 y的第一次出现为自由出现, 第二次出现为约束出现 z为自由出现.,19,实例,例7 公式 x(F(x)xG(x) x的辖域:(F(x)xG(x)， 指导变元

11、为x x的辖域:G(x)， 指导变元为x x的两次出现均为约束出现. 但是, 第一次出现的x是x中 的x, 第二次出现的x是x中的x. 闭式: 不含自由出现的个体变项的公式.,20,解释的直观涵义,例 公式x(F(x)G(x) 指定1 个体域:全总个体域, F(x): x是人, G(x): x是黄种人 假命题 指定2 个体域:实数集, F(x): x10, G(x): x0 真命题,21,解释,定义3.7 设一阶语言L 的个体常项集ai| i1, 函数符号集 fi| i1, 谓词符号集Fi| i1, L 的解释I由下面4部分组成: (1) 非空个体域DI (2) 对每一个个体常项ai, DI,

12、 称作ai在I中的解释 (3) 对每一个函数符号fi, 设其为m元的, 是DI上的m元函 数, 称作fi在I中的解释 (4) 对每一个谓词符号Fi, 设其为n元的, 是一个n元谓词, 称作Fi在I中的解释,22,实例,例8 给定解释I 如下: (a) 个体域 D=N (b) (c) (d) 谓词 说明下列公式在 I 下的含义, 并讨论其真值 (1) xF(g(x,a),x),x(2x=x) 假命题,(2) xy(F(f(x,a),y)F(f(y,a),x),xy(x+2=yy+2=x) 假命题,23,实例(续),(3) xyzF(f(x,y),z),(5) F(f(x,a), g(x,a),(

13、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 不是命题,24,闭式的性质,定理3.1 闭式在任何解释下都变成命题. 例8 (1)(4)都是闭式, 在I下全是命题. (5)和(6)不是闭式, 在I下(5)不是命题, (6)是命题,25,一阶逻辑公式的分类,永真式(逻辑有效式): 无成假解释 矛盾式(永假式): 无成真解释 可满足式: 至少有一个成真解释 在一阶逻辑中, 公式的可满足性(永真性,永假性)是不可 判定的,即不存在算法能在有

14、限步内判断任给的公式是否 是可满足式(永真式,矛盾式),26,代换实例,定义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 重言式的代换实例都是永真式，矛盾式的代换实 例都是矛盾式.,27,实例,例9 判断下列公式的类型: (1) x(F(x)G(x),非永真式的可满足式,(2) (xF(x)(xF(x),这是 pp 的代换实例, pp是重言式,取解释I1, D1=R, :x是整数, :x是

15、有理数, 真命题,永真式,(3) (xF(x)yG(y) yG(y),这是(pq)q的代换实例, (pq)q是矛盾式,矛盾式,取解释I2, D2=R, :x是整数, :x是自然数, 假命题,28,3.2 一阶逻辑等值演算,3.2.1 一阶逻辑等值式与置换规则 基本等值式 置换规则、换名规则、代替规则 3.2.2 一阶逻辑前束范式,29,等值式,定义3.10 若AB是永真式, 则称A与B是等值的, 记作 AB, 并称AB为等值式,基本等值式 命题逻辑中基本等值式的代换实例 如，xF(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),30,基本等值式(续),量词辖域收缩与扩张等值式 设A(x)是含x自由出现的公式，B中不含x的出现 关于全称量词的： x(A(x)B)xA(x)B x(A(x)B)xA(x)B x(A