《离散数学屈婉玲_耿素云_张立昂第5章_高教剖析》由会员分享，可在线阅读，更多相关《离散数学屈婉玲_耿素云_张立昂第5章_高教剖析（40页珍藏版）》请在金锄头文库上搜索。
1、1,主要内容 一阶逻辑等值式与基本的等值式 置换规则、换名规则、代替规则 前束范式 自然推理系统NL 及其推理规则,第五章 一阶逻辑等值演算与推理,2,5.1 一阶逻辑等值式与置换规则,定义5.1 设A, B是两个谓词公式, 如果AB是永真式, 则称A 与B等值, 记作AB, 并称AB是等值式 基本等值式 第一组 命题逻辑中16组基本等值式的代换实例 例如，xF(x)xF(x), xF(x)yG(y) xF(x)yG(y) 等 第二组 (1) 消去量词等值式 设D =a1, a2, , an xA(x) A(a1)A(a2)A(an) xA(x) A(a1)A(a2)A(an),3,命题逻辑的
2、基本等值式（1）,双重否定律 AA 幂等律 AAA, AAA 交换律 ABBA, ABBA 结合律 (AB)CA(BC), (AB)CA(BC) 分配律 A(BC)(AB)(AC), A(BC)(AB)(AC) 德摩根律 (AB)AB (AB)AB 吸收律 A(AB)A, A(AB)A,4,命题逻辑的基本等值式（2）,零律 A11, A00 同一律 A0A. A1A 排中律 AA1 矛盾律 AA0 蕴涵等值式 ABAB 等价等值式 AB(AB)(BA) 假言易位 ABBA 等价否定等值式 ABAB 归谬论 (AB)(AB) A 特别提示：必须牢记这16组等值式，这是继续学习的基础,5,基本等值
3、式,(2) 量词否定等值式 xA(x) xA(x) xA(x) xA(x) (3) 量词辖域收缩与扩张等值式. A(x) 是含 x 自由出现的公式，B 中不含 x 的自由出现 关于全称量词的： x(A(x)B) xA(x)B x(A(x)B) xA(x)B x(A(x)B) xA(x)B x(BA(x) BxA(x),6,基本等值式,关于存在量词的： x(A(x)B) xA(x)B x(A(x)B) xA(x)B x(A(x)B) xA(x)B x(BA(x) BxA(x) (4) 量词分配等值式 x(A(x)B(x) xA(x)xB(x) x(A(x)B(x) xA(x)xB(x) 注意：对
4、，对无分配律,7,置换规则、换名规则、代替规则,1. 置换规则 设(A)是含A的公式, 那么, 若AB, 则(A)(B). 2. 换名规则 设A为一公式，将A中某量词辖域中个体变项的所有约束 出现及相应的指导变元换成该量词辖域中未曾出现过的个 体变项符号，其余部分不变，设所得公式为A，则AA. 3. 代替规则 设A为一公式，将A中某个个体变项的所有自由出现用A中 未曾出现过的个体变项符号代替，其余部分不变，设所得 公式为A，则AA.,8,实例,例1 将下面命题用两种形式符号化, 并证明两者等值: (1) 没有不犯错误的人,解 令F(x)：x是人，G(x)：x犯错误. x(F(x)G(x) 或
5、x(F(x)G(x),x(F(x)G(x) x(F(x)G(x) 量词否定等值式 x(F(x)G(x) 置换 x(F(x)G(x) 置换,9,实例,(2) 不是所有的人都爱看电影,解 令F(x)：x是人，G(x)：爱看电影. x(F(x)G(x) 或 x(F(x)G(x),x(F(x)G(x) x(F(x)G(x) 量词否定等值式 x(F(x)G(x) 置换 x(F(x)G(x) 置换,10,实例,例2 将公式化成等值的不含既有约束出现、又有自由出现 的个体变项: x(F(x,y,z)yG(x,y,z),解 x(F(x,y,z)yG(x,y,z) x(F(x,y,z)tG(x,t,z) 换名规
6、则 xt(F(x,y,z)G(x,t,z) 辖域扩张等值式,或者 x(F(x,y,z)yG(x,y,z) x(F(x,u,z)yG(x,y,z) 代替规则 xy(F(x,u,z)G(x,y,z) 辖域扩张等值式,11,实例,例3 设个体域D=a,b,c, 消去下述公式中的量词: (1) xy(F(x)G(y),解 xy(F(x)G(y) (y(F(a)G(y)(y(F(b)G(y)(y(F(c)G(y) (F(a)G(a)(F(a)G(b)(F(a)G(c) (F(b)G(a)(F(b)G(b)(F(b)G(c) (F(c)G(a)(F(c)G(b)(F(c)G(c),12,实例,解法二 xy
7、(F(x)G(y) x(F(x)yG(y) 辖域缩小等值式 x(F(x)G(a)G(b)G(c) (F(a)G(a)G(b)G(c) (F(b)G(a)G(b)G(c) (F(c)G(a)G(b)G(c),13,实例,(2) xyF(x,y),xyF(x,y) x(F(x,a)F(x,b)F(x,c) (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),例3 设个体域D=a,b,c, 消去下述公式中的量词:,14,5.2 一阶逻辑前束范式,定义5.2 设A为一个一阶逻辑公式，若A具有如下形式 Q1x1Q2x2QkxkB 则称A
8、为前束范式，其中Qi (1 i k)为或，B为不含量词 的公式. 例如， x(F(x)G(x) xy(F(x)(G(y)H(x,y) 是前束范式 而 x(F(x)G(x) x(F(x)y(G(y)H(x,y) 不是前束范式,15,前束范式存在定理,定理5.1（前束范式存在定理） 一阶逻辑中的任何公式都存在与之等值的前束范式,例4 求下列公式的前束范式 (1) x(M(x)F(x),解 x(M(x)F(x) x(M(x)F(x) （量词否定等值式） x(M(x)F(x) 后两步结果都是前束范式，说明公式的前束范式不惟一.,16,求前束范式的实例,(2) xF(x)xG(x),解 xF(x)xG(
9、x) xF(x)xG(x) （量词否定等值式） x(F(x)G(x) （量词分配等值式）,或 xF(x)xG(x) xF(x)xG(x) 量词否定等值式 xF(x)yG(y) 换名规则 xy(F(x)G(y) 辖域收缩扩张规则,17,求前束范式的实例,(3) xF(x)y(G(x,y)H(y),或 xF(x)y(G(z,y)H(y) 代替规则 xy(F(x)(G(z,y)H(y),解 xF(x)y(G(x,y)H(y) zF(z)y(G(x,y)H(y) 换名规则 zy(F(z)(G(x,y)H(y) 辖域收缩扩张规则, x(A(x)B) xA(x)B x(BA(x) BxA(x), x(A(
10、x)B) xA(x)B x(BA(x) BxA(x),18,5.3 一阶逻辑的推论理论,推理的形式结构 1. A1A2Ak B 若上式是永真式, 则称推理正确, 记作A1A2Ak B 2. 前提: A1, A2, Ak 结论: B 推理定理: 永真式的蕴涵式,19,推理定理,第一组 命题逻辑推理定理的代换实例 如, xF(x)yG(y) xF(x) 第二组 基本等值式生成的推理定理 如, xF(x) xF(x), xF(x) xF(x) xF(x)xF(x), xF(x) xF(x) 第三组 其他常用推理定律 (1) xA(x)xB(x) x(A(x)B(x) (2) x(A(x)B(x)xA
11、(x)xB(x) (3) x(A(x)B(x) xA(x)xB(x) (4) 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) 注意：对，对无分配律,反向不行,反向不行,20,量词消去引入规则,1. 全称量词消去规则(-) 或 其中x,y是个体变项符号, c是个体常项符号, 且在A中x不在y 和y的辖域内自由出现. 2. 全称量词引入规则(+) 其中x是个体变项符号, 且不在前提的任何公式中自由出现,21,量词消去引入规则,3. 存在量词消去规则(-) 其中x是个体变项符号, 且不在前提的任何公式和B中自由 出
12、现,22,量词消去引入规则,4. 存在量词引入消去规则(+) 或 或 其中x,y是个体变项符号, c是个体常项符号, 且在A中y和c不在 x和x的辖域内自由出现.,3. 存在量词消去规则(-),23,自然推理系统NL,定义5.3 自然推理系统NL 定义如下: 1. 字母表. 同一阶语言L 的字母表 2. 合式公式. 同L 的合式公式 3. 推理规则: (1) 前提引入规则 (2) 结论引入规则 (3) 置换规则 (4) 假言推理规则 (5) 附加规则 (6) 化简规则 (7) 拒取式规则,1. A (AB) 附加律 2. (AB) A 化简律 3. (AB)A B 假言推理 4. (AB)B A 拒取式 5. (AB)B A 析取三段论 6. (AB)(BC) (AC) 假言三段论 7. (AB)(BC) (AC) 等价三段论 8. (AB)(CD)(AC) (BD) 构造性二难 (AB)(AB) B 构造性二难(特殊形式) 9. (AB)(CD)( BD) (AC) 破坏性二难 每个等值式可产生两个推理定律 如, 由AA可产生 AA 和 AA,24,自然推理系统NL,(8) 假言三段论规则 (9) 析取三段论规则 (10) 构造性二难推理规则 (11) 合取引入规则 (12) -规则 (13) +规则 (14) -规则 (1
