《离散数学 (15)》由会员分享，可在线阅读，更多相关《离散数学 (15)（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) (3) x y x,y是命题变
4、项, 3，则3y, G(x,y): x10, G(x): x0真命题,21,解释,定义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中的解释,22,实例,例8 给定解释I 如下: (a) 个体域 D=N(b) (c) (d) 谓词 说明下列公式在 I
5、下的含义, 并讨论其真值 (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),(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下全是
6、命题. (5)和(6)不是闭式, 在I下(5)不是命题, (6)是命题,25,一阶逻辑公式的分类,永真式(逻辑有效式): 无成假解释 矛盾式(永假式): 无成真解释 可满足式: 至少有一个成真解释在一阶逻辑中, 公式的可满足性(永真性,永假性)是不可 判定的,即不存在算法能在有限步内判断任给的公式是否 是可满足式(永真式,矛盾式),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
7、.2 重言式的代换实例都是永真式，矛盾式的代换实 例都是矛盾式.,27,实例,例9 判断下列公式的类型: (1) x(F(x)G(x),非永真式的可满足式,(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是自然数, 假命题,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,基本等值式(续),
