离散数学04ppt课件

1、离散数学,1,第一部分,数理逻辑,第四章 一阶逻辑基本概念,2,复习命题演算,命题演算形式系统: 语法: 语义: 可靠性: 凡是推出来的都是正确的. 完全性: 凡是正确的都可以推出来.,3,问题的提出,命题演算不能表达所有正确的推理. 例: 所有实数的平方都是非负的. 是一个实数. 的平方是非负的. 如用命题演算推理形式来表示: 由p, q推出r. 非有效推理形式,4,1 一阶逻辑命题符号化,需要进一步分析推理结构. 上述推理中, 各命题之间的关系在于简单命题的成分之间. 需要进一步分解简单命题. 简单命题的符号化.,5,简单命题的结构,个体词, 谓词,6,例1,分析下列各命题中的个体和谓词

2、(1) 是无理数. (2) 张三与李四同在计算机系. (3) x与y的和等于z (x, y, z是确定的数). (4) 的平方是非负的. (5) 所有实数的平方都是非负的. (6) 有一个比21000大的素数.,7,例1(1),(1) 是无理数. 解: 个体: (代表圆周率) 谓词: 是无理数, 表示” ”的性质.,8,例1(2),(2) 张三与李四同在计算机系. 解: 个体: 张三, 李四 谓词: 与 同在计算机系, 表示”张三”与”李四”之间的关系. 个体: 张三 谓词: 与李四同在计算机系, 表示”张三”的性质. 个体: 李四 谓词: 张三与 同在计算机系, 表示”李四”的性质.,9,例

3、1(3),(3) x与y的和等于z (x, y, z 是确定的数). 解: 个体: x, y, z 谓词: 与 的和等于 个体: x, z 谓词: 与y的和等于 个体: y 谓词: x与 的和等于z 谓词可以表示单个个体的性质, 也可以表示两个个体 词之间的关系或性质, 分别称为一元谓词和二元谓词. 表示n个个体间的关系或性质的谓词称为n元谓词.,10,例1(4),(4) 的平方是非负的. 解: 个体: 谓词: 的平方是非负的 个体: 的平方 谓词: 是非负的 “的平方”是一个”复合”个体, 需要再分解. 个体: 函词: 的平方一元函词 谓词: 是非负的,11,例1(5),(5) 所有实数的平

4、方都是非负的. 解: 个体: 每一个实数 函词: 的平方 谓词: 是非负的 “所有”是什么? 量词: 所有,12,例1(6),(6) 有一个比21000大的素数. 解: 个体: 一个素数 谓词: 比21000大 “有一个”是什么? 量词: 有一个,13,表示简单命题的新符号,个体: x, y, z, a, b, c, 谓词: Fn, Gn, Hn, n表示元数 函词: fn, gn, hn, n表示元数 量词: -所有: 全称量词 -有一个: 存在量词,14,例1(1)的符号化,(1) 是无理数. 解: 个体: (代表圆周率) 谓词: 是无理数, 以F表示 则此命题可表示为F().,15,例1

5、(2)的符号化,(2) 张三与李四同在计算机系. 解: 个体: 张三, 李四: 分别以a, b表示 谓词: 与 同在计算机系: 以G表示 则此命题可表示为: G(a, b) 个体: 张三: 以a表示 谓词: 与李四同在计算机系: 以G表示 此命题可表示为: G(a) 个体: 李四: 以b表示 谓词: 张三与 同在计算机系: 以G表示 此命题可表示为: G(b),16,例1(3)的符号化,(3) x与y的和等于z (x, y, z 是确定的数). 解: 个体: x, y, z 谓词: 与 的和等于 : 以R表示 符号化: R(x, y, z) 个体: x, z 谓词: 与y的和等于 : 以R表示

6、 符号化: R(x, z) 个体: x, y, z 函词: 与 的和: 以f2表示 谓词: 等于 : 以R表示 符号化: R(f2(x, y), z),17,例1(4)的符号化,(4) 的平方是非负的. 解: 个体: 的平方: 以a表示 谓词: 是非负的: 以R表示 符号化: R(a) 个体: 函词: 的平方: 以f表示 谓词: 是非负的: 以R表示 符号化: R(f(),18,例1(5)的符号化,(5) 所有实数的平方都是非负的. 解: 个体: 每一个实数: 以x表示 函词: 的平方: 以f表示 谓词: 是非负的: 以R表示 量词: 所有: 以 表示 符号化: xR(f(x) x可以代表不同

7、的个体, 称为个体变元 相对地等称为个体常元,19,例1(5)的符号化(续),(5) 所有实数的平方都是非负的. 解: 个体: 每一个实数: 以z表示 谓词: 是一个实数, 以R表示 函词: 的平方: 以f表示 谓词: 是非负的: 以R表示 量词: 所有: 以 表示 符号化: (z)(R(z) R(f(z)最清晰 个体变元x和z的取值范围不同. 个体变元的取值范围称为它的论域.,20,例1(6)的符号化,(6) 有一个比21000大的素数. 解: 个体: 一个素数: 以y表示 谓词: 比21000大: 以P1表示 量词: 有一个: 以表示 符号化: (y)P1(y) 还可以表示为: (x)(P

8、2(x) P1(x), 其中: x表示某个数, P2表示” 是一个素数”, P1同上.,21,表示命题的符号,个体变元: x, y, z, 个体常元: a, b, c, 谓词: Fn, Gn, Hn, 函数: fn, gn, hn, 量词: 全称量词 , 存在量词 联结词: , , , , ,22,例2,将下列命题符号化. (1) 凡是有理数皆可写成分数. (2) 教室里有同学在说话. (3) 对于任意x, y, 都存在唯一的z, 使x+y=z. (4) 在我们班中, 并非所有同学都能取得优秀成绩. (5) 有一个整数大于其它每个整数. (6) 任意 0, 存在 0, 如果|x-a| , 则

9、|F(x) b| . (7) 恰有三个互不相同的素数小于7.,23,例2(1)的符号化,(1) 凡是有理数皆可写成分数. 解: (x) (Q1(x) F1(x) x: 数 Q1: 是有理数 F1: 可写成分数 注: 不能写成(x)(Q1(x) F1(x) 也不能写成(x Q)F1(x),24,例2(2)的符号化,(2) 教室里有同学在说话. 解: (x)(C1(x) T1(x) x: 同学 C1: 在教室里 T1: 在说话 注: 不能写成(x)(C1(x) T1(x) 也不能写成(x C)T1(x).,25,例2(3)的符号化,(3) 对于任意x, y, 都存在唯一的z, 使x+y=z. 解:

10、 (x)(y)(z)(x+y=z) (u)(u=x+y u=z). 注: 量词的嵌套 “存在唯一”的表示,26,例2(4)的符号化,(4) 在我们班中, 并非所有同学都能取得优秀成绩. 解: (x)(C(x) E(x) x: 同学 C: 在班级里 E: 能取得优秀成绩 注: C(x) E(x) C(x) E(x) (C(x) E(x), 从而命题可表示为: (x) (C(x) E(x). 另一方面, 此命题也可表为(x)(C(x) E(x), 即: “(x)”与”x”有相同的意义.,27,例2(5)的符号化,(5) 有一个整数大于其它每个整数。 解： (x)(Z(x)(y)(Z(y)(y=x)

11、xy) x, y: 数 Z: 是整数 注: 此符号串中, “=“和”是什么类型的符号?,28,例2(6)的符号化,(6) 任意 0, 存在 0, 如果|x-a| 0 ( )( 0 (|x-a| |f(x)-b| ) 注: 此符号串中有哪些谓词符号?,29,例2(7)的符号化,(7) 恰有三个互不相同的素数小于7. 解: (x1)(x2)(x3)( (x17 x27 x37) (P(x1) P(x2) P(x3) (x1=x2) (x1=x3) (x2=x3) (y)(y7 P(y) (y=x1 y=x2 y=x3) 注: 两个量词可以表示任意确定个数的个体.,30,应注意的问题,谓词(函数)的

12、元数是固定的. 谓词(函数)中的变元是有顺序性的. 例如: F(x, y) 与 F(y, x) 不具有相同的含义. 量词也有顺序性. 例如: (x)(y)(xy) 与 (y)(x)(xy) 并不表示同一含义. 谓词公式真假值判别的困难性.,31,本章开头推理的正确表示,因为(x)(G12(x)G11(f(x) G12( ) 所以G11(f( ) 其中: x代表”数”. f代表”的平方”. G11代表”是非负实数”. G12代表”是实数”.,32,2 一阶逻辑公式及其解释,一阶语言是谓词演算系统形式语言. 符号库 谓词公式,33,非逻辑符号,可能包括下列符号: 个体常元符号: c, c1, c2

13、, , cn, 谓词符号: Fn, Gn, Pn, Qn, Rn等 n (n , n0)表示此谓词符号的元数 函数符号: fm, gm, hm 等 m (m , m0)表示此函数符号的元数 由一些非逻辑符号作为元素组成的集合常记为 .,34,逻辑符号,包括下列符号: 个体变元符号: x0, x1, x2, 联结词符号: , , , , 量词符号: , 辅助符号: ), , , (,35,逻辑符号与非逻辑符号,非逻辑符号更象是所描述的特定对象中的符号. 而逻辑符号是逻辑系统中的符号. 故此得名. 在描述特定对象时, 并不需要所有非逻辑符号. 但可能用到所有逻辑符号. 一阶语言与符号库指定的非逻辑

14、符号集 有关, 称为 生成的一阶语言.,36,项, 生成的一阶语言的”项”归纳定义如下: 1.个体变元符号和 中的个体常元符号都是项; 2.若fm是 中一个m元函数符号, t1, t2, , tm是 中项, 则fm(t1, t2, , tm)是 中项; 3.每个项都是有限次应用(1)和(2)得到的. “项”相当于”复合个体”.,37,公式, 生成的一阶语言的”公式”归纳定义如下: (1)如果Fn是 中的一个n元谓词符号, t1, t2, , tn 是 中项, 则Fn(t1, t2, , tn)是 中公式, 称为原子公式 (2) 若A是公式, 则(A)是公式; (3)若A, B是公式, 则(AB

15、), (AB), (AB), (AB)是 中公式; (4)若A是公式, x是个体变元符号, 则 (x)A, (x)A也是公式; (5)每个公式都是有限次使用(1)-(4)得到的.,38,一些注记,注1: 与命题演算的形式语言相比, 一阶语言中没有 符号, 代之的是原子公式. 注2:所有一阶语言中都含有相同的逻辑符号, 但所 含的非逻辑符号不一定相同. 注3:在定义中没有要求个体变元x一定要在A中出现: (x1)F2(x1, x2)和(x3)F2(x1, x2)都是公式. 注4:总假设: 中至少有一个谓词符号. 否则 生成的一阶语言中没有公式.,39,括号省略规则,(1)省略公式最外层的括号;

16、(2)联结词符号”的优先级高于其它的四个联结 词, 可以去掉(A)中的外层括号; (3)A1A2An-1An表示 (A1(A2(An-1An); 对, , 也类似规定. (4)x, x的优先级高于所有联结词. 将(x)A, (x)A分别记为xA, xA. (5)(x1)(xn)A简记为x1xnA; (x1)(xn)A简记为x1xnA.,40,项和公式,项的作用是描述”复合”个体 公式的作用是描述命题. “项”相当于”词组”, 它们不表达完整的判断; “公式”代表完整的句子, 表达判断. f(x1, x2, , xn)表示f作用到个体x1, , xn得到的个体 Fn(x1, x2, , xn)表

17、示x1, x2, , xn是否具有关系 Fn(或性质Fn).,41,例3,用一阶语言描述群的定义 解: 令 = f2, E2, c, 其中: f2代表群的乘法运算, 是一个二元函数符号; E2描述元素的相等关系, 是一个二元谓词符号; c代表群的单位元, 是一个常元符号. 则群公理可表示为由 中的如下三个公式: (1)x1x2x3 E( f( f(x1, x2), x3), f(x1, f(x2, x3) ) ) (2)x0(E( f(x0, c), x0) E( f(c, x0), x0) ) (3)x1x2(E( f(x1, x2), c) E( f(x2, x1), c) ),42,用一

18、阶语言描述等价关系的定义,解: 令 = E2, 其中: E2描述元素的等价关系, 是一个二元谓词符号; 则等价关系的定义可表示为由 中的如下三个公式: (1) (x) E(x, x); (2) (xy) (E(x, y) E(y, x); (3) (xyz) (E(x, y) E(y, x) E(x, z).,43,辖域,定义3: 称公式(x)A中的A为量词(x)的辖域; 称公式(x)A中的A为量词(x)的辖域. 例: 在x1x2(x3F(x1, x2)F(x2, x3)中, (x1)的辖域为x2(x3F(x1, x2)F(x2, x3), (x2)的辖域为(x3F(x1, x2)F(x2,

19、x3), (x3)的辖域为F(x1, x2).,44,约束出现与自由出现,定义4: 变元符号x在公式A中的某处出现称为是约束出现, 如果 此处出现是在(x)或(x)的辖域内, 或者 是(x)中的x, 或者 是(x)中的x. 若x在A中的某处出现不是约束出现, 则称x的 此处出现为自由出现.,45,例4,下列公式中, 指出变元的各处出现是自由出现还是 约束出现. (1)x1x2(F(x1, x2)F(x1, x3) (2)x1F(x1)F(x1) (3)x1F(x1, x2)x1F(x2),46,例4的解,解: (1)x1 x2 (F(x1, x2) F(x1, x3) 约束约束 约束 约束 约

20、束 自由 (2)x1F(x1) F(x1) 约束 自由 (3)x1 (F(x1, x2) x1 F(x2) 约束 约束 自由 约束 自由,注: 同一个变元在同一个公式中可能既有自由出现,又有约束出现.,47,约束变元与自由变元,定义5: 设个体变元符号x在公式A中出现. 如果x在A中的所有出现都是约束出现, 称x为A的约束变元; 如果x不是A的约束变元, 则称x为A的自由变元. 易知: x是A的自由变元 x在A中有某处出现是自由出现.,48,约束变元与自由变元的例,例4中: (1)中的x1, x2为约束变元, x3是自由变元; (2)中的x1是自由变元; (3)中的x1是约束变元, x2是自由

21、变元. 约定: 以A(x1, , xn)表示公式A的自由变元都在x1, , xn中.,49,约束变元与自由变元的差别,约束变元与自由变元的差别很大. 令 = E2, c, 其中: E代表二元谓词”=”, c代表一个常量. 考虑 的公式: x1E(x1, c)与x2E(x1, c). x1E(x1, c)为真 个体域中只能有一个元素c. 故x1E(x1, c)的真假与x1取值无关. 但x2E(x1, c)的真假与x1取值有关. 约束变元的出现反映论域的某种性质 并非决定其取值,50,t对x在A中可代入,考察将公式y(yx)中的x换为项y前后的真假值. 公式y(yx)是可为真的. 但将y(yx)中

22、的x换为y后就不能为真了. 即y(yy)不能为真. 问: 将x换成什么样的项t, A的真假值不会改变? y(yx) y(yt),51,t对x在A中可代入的定义,定义6: 设A是 的公式, t是 的项, x是 的变元符号, 如果 对t中出现的每个变元符号yi, A中每处自由出现 的x不在(yi)或(yi)的辖域内, 则称t对x在A中 可代入, 或称t对x在A中自由. y对x在y(yx)中不可代入. z对x在y(yx)中可代入.,52,检查t对x在A中是否自由的步骤,1. 找出t中包含的所有变元y1, y2, , yn; 2. 找出A中所有自由出现的x; 3. 对x在A中的每处自由出现, for

23、i=1 to n step 1 do 检查x是否出现在(yi)或(yi)的辖域中, 若是, 则t对x在A中不自由. endfor 4. t对x在A中自由.,53,例5,设一阶公式A为x1F12(x1, x2)x2F22(x3, x1), 问: (1) x2及f12(x4, x5)对x1在A中是否自由? (2) f22(x1, x4)及f32(x2, x3)对x2在A中是否自由?,54,例5的解,A为x1F12(x1, x2)x2F22(x3, x1) 答: (1) x2对x1在A中不自由, 在A中, 有自由出现的x2出现在x1的辖域内. f12(x4, x5)对x1在A中自由. (2) f22

24、(x1, x4)对x2在A中不自由, f32(x2, x3)对x2在A中自由.,55,A(x/t),A(x/t)是将A中每个自由出现的x都换为项t后得到 的公式(不论t对x在A是否自由). A(x/t)称为A的一个例式. 例5中: A(x2/x1) = x1F12(x1, x2) x2F22(x3, x1). A(x1/f12(x4, x5) =x1F12(x1, x2) x2F22(x3, f12(x4, x5).,56,用A(x/t)判断t对x在A中是否自由,要看t对x在公式A中是否自由, 只要在A(x/t)中看: 在新代入t的地方, t中的每个变元的各个出现是否有 约束出现. 若有, 则

25、t的对x在A中不自由, 否则自由. 这也是”t对x在A中可代入”这个名称的由来.,57,简单性质,(1) x对x在A中自由. (2) 若x不在A中自由出现, 则t对x在A中自由.,58,闭公式,定义7 (1) 若 的项t中不含任何个体变元符号, 则称t为 的 一个闭项; (2) 若 的公式A中不含任何自由变元符号, 则称A为 的一个闭公式, 简称闭式. 例如 xy(F(x)G(y)H(x,y) 为闭式， x(F(x)G(x,y) 不是闭式,59,定义4.7 设L 是生成的一阶语言, L 的解释I由4部分组成： (a) 非空个体域 DI . (b) 对每一个个体常项符号aL, 有一个 DI, 称

26、 为a在I 中的解释. (c) 对每一个n元函数符号fL, 有一个DI上的n元函数 , 称 为f在I中的解释. (d) 对每一个n元谓词符号FL, 有一个DI上的n元谓词常项 , 称 为F在I中的解释.,公式的解释,设公式A, 取个体域DI , 把A中的个体常项符号a、函数符 号f、谓词符号F分别替换成它们在I中的解释 、 、 , 称 所得到的公式A为A在I下的解释, 或A在I下被解释成A.,60,实例,例6 给定解释 I 如下： (a) 个体域 D=R (b) (c) (d) 写出下列公式在I下的解释, 并指出它的真值. (1) xF(f(x,a),g(x,a),x(x+0=x0) 真,(2

27、) xy(F(f(x,y),g(x,y)F(x,y),xy(x+y=xyx=y) 假,(3) xF(g(x,y),a),x(xy=0) 真值不定, 不是命题,61,公式的类型,定理4.1 闭式在任何解释下都是命题 注意: 不是闭式的公式在解释下可能是命题, 也可能不是命题. 定义4.8 若公式A在任何解释下均为真, 则称A为永真式(逻辑有效式). 若A在任何解释下均为假, 则称A为矛盾式(永假式). 若至少有一个解释使A为真, 则称A为可满足式. 几点说明： 永真式为可满足式，但反之不真 判断公式是否是可满足的(永真式, 矛盾式)是不可判定的(不存在一个算法能在有限步内判断任意给定的公式是否是

28、可满足的),62,代换实例,定义4.9 设A0是含命题变项 p1, p2, , pn的命题公式，A1, A2, , An是n个谓词公式，用Ai (1in) 处处代替A0中的pi，所得公式A称为A0的代换实例. 例如， F(x)G(x), xF(x)yG(y)等都是pq的代换实例. 定理4.2 重言式的代换实例都是永真式，矛盾式的代换实例都是矛盾式.,63,实例,例7 判断下列公式中，哪些是永真式，哪些是矛盾式？ (1) xF(x)(xyG(x,y)xF(x),重言式 p(qp) 的代换实例，故为永真式.,(2) (xF(x)yG(y)yG(y),矛盾式 (pq)q 的代换实例，故为永假式.,(

29、3) x(F(x)G(x),解释I1: 个体域N, F(x):x5, G(x): x4, 公式为真 解释I2: 个体域N, F(x):x5, G(x):x4, 公式为假 结论: 非永真式的可满足式,64,练习1,1. 在分别取个体域为 (a) D1=N (b) D2=R (c) D3为全总个体域 的条件下, 将下面命题符号化，并讨论真值 (1) 对于任意的数x，均有,解 设G(x): (a) xG(x),(b) xG(x),(c) 又设F(x):x是实数 x(F(x)G(x),真,真,假,65,练习1(续),解 设H (x)：x+7=5 (a) xH (x),(2) 存在数x，使得 x+7=5

30、,(b) xH (x),(c) 又设F (x)：x为实数 x (F (x)H (x),本例说明：不同个体域内，命题符号化形式可能不同（也可能相同），真值可能不同（也可能相同）.,真,真,假,66,练习2,2. 在一阶逻辑中将下列命题符号化 (1) 大熊猫都可爱,(2) 有人爱发脾气,(3) 说所有人都爱吃面包是不对的,设F(x): x为大熊猫，G(x): x可爱 x(F(x)G(x),设F(x): x是人，G(x): x爱发脾气 x(F(x)G(x),设F(x): x是人，G(x): x爱吃面包 x(F(x)G(x) 或 x(F(x)G(x),67,练习2,(4) 没有不爱吃糖的人,(5) 任

31、何两个不同的人都不一样高,(6) 不是所有的汽车都比所有的火车快,设F(x): x是人，G(x): x爱吃糖 x(F(x)G(x) 或 x(F(x)G(x),设F(x):x是人, H(x,y), x与y相同, L(x,y): x与y一样高 x(F(x)y(F(y)H(x,y)L(x,y) 或 xy(F(x)F(y)H(x,y)L(x,y),设F(x):x是汽车, G(y):y是火车, H(x,y):x比y快 xy(F(x)G(y)H(x,y) 或 xy(F(x)G(y)H(x,y),68,练习3,x(2x=x) 假,3. 给定解释 I 如下: (a) 个体域D=N (b) =2 (c) (d) 说明下列公式在 I 下的涵义,并讨论真值 (1) xF(g(x,a),x),(2) xy(F(f(x,a),y)F(f(y,a),x),xy(x+2=yy+2=x) 假,69,练习3,(3) xyzF(f(x,y),z),(5) xF(f(x,x),g(x,x),(4) xyzF(f(y,z),x),xyz(y+z=x) 假